COIN-OR::LEMON - Graph Library

Changeset 774:4297098d9677 in lemon-0.x for src/hugo/graph_wrapper.h


Ignore:
Timestamp:
08/30/04 14:01:47 (17 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1066
Message:

Merge back the whole branches/hugo++ to trunk.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/graph_wrapper.h

    r739 r774  
    1313#include <hugo/invalid.h>
    1414#include <hugo/maps.h>
    15 //#include <iter_map.h>
     15#include <iostream>
    1616
    1717namespace hugo {
     
    9797
    9898    GraphWrapper(Graph& _graph) : graph(&_graph) { }
     99    GraphWrapper(const GraphWrapper<Graph>& gw) : graph(gw.graph) { }
    99100//     Graph& getGraph() const { return *graph; }
    100101 
    101 //    typedef typename Graph::Node Node;
    102     class Node : public Graph::Node {
     102    typedef typename Graph::Node Node;
     103//     class Node : public Graph::Node {
     104//       friend class GraphWrapper<Graph>;
     105//     public:
     106//       Node() { }
     107//       Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
     108//       // /// \bug construction throughrthr multiple levels should be
     109//       // /// handled better
     110//       // Node(const typename ParentGraph::ParentGraph::Node& _n) :
     111//       // Graph::Node(_n) { }
     112//       Node(const Invalid& i) : Graph::Node(i) { }
     113//     };
     114    class NodeIt : public Node {
     115      const GraphWrapper<Graph>* gw;
    103116      friend class GraphWrapper<Graph>;
    104     public:
    105       Node() { }
    106       Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
    107       // /// \bug construction throughrthr multiple levels should be
    108       // /// handled better
    109       // Node(const typename ParentGraph::ParentGraph::Node& _n) :
    110       // Graph::Node(_n) { }
    111       Node(const Invalid& i) : Graph::Node(i) { }
    112     };
    113     class NodeIt {
    114       friend class GraphWrapper<Graph>;
    115       typename Graph::NodeIt n;
    116117     public:
    117118      NodeIt() { }
    118       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
    119       NodeIt(const Invalid& i) : n(i) { }
    120       NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
    121       operator Node() const { return Node(typename Graph::Node(n)); }
    122     };
    123 //    typedef typename Graph::Edge Edge;
    124     class Edge : public Graph::Edge {
     119      //      NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { }
     120      NodeIt(Invalid i) : Node(i) { }
     121      NodeIt(const GraphWrapper<Graph>& _gw) :
     122        Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }
     123      NodeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
     124        Node(n), gw(&_gw) { }
     125      NodeIt& operator++() {
     126        *(static_cast<Node*>(this))=
     127          ++(typename Graph::NodeIt(*(gw->graph), *this));
     128        return *this;
     129      }
     130    };
     131    typedef typename Graph::Edge Edge;
     132//     class Edge : public Graph::Edge {
     133//       friend class GraphWrapper<Graph>;
     134//     public:
     135//       Edge() { }
     136//       Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
     137//       Edge(const Invalid& i) : Graph::Edge(i) { }
     138//     };
     139    class OutEdgeIt : public Edge {
     140      const GraphWrapper<Graph>* gw;
    125141      friend class GraphWrapper<Graph>;
    126     public:
    127       Edge() { }
    128       Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
    129       Edge(const Invalid& i) : Graph::Edge(i) { }
    130     };
    131     class OutEdgeIt {
     142     public:
     143      OutEdgeIt() { }
     144      //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
     145      OutEdgeIt(Invalid i) : Edge(i) { }
     146      OutEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
     147        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
     148      OutEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
     149        Edge(e), gw(&_gw) { }
     150      OutEdgeIt& operator++() {
     151        *(static_cast<Edge*>(this))=
     152          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     153        return *this;
     154      }
     155    };
     156    class InEdgeIt : public Edge {
     157      const GraphWrapper<Graph>* gw;
    132158      friend class GraphWrapper<Graph>;
    133       typename Graph::OutEdgeIt e;
    134     public:
    135       OutEdgeIt() { }
    136       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
    137       OutEdgeIt(const Invalid& i) : e(i) { }
    138       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
    139         e(*(_G.graph), typename Graph::Node(_n)) { }
    140       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    141     };
    142     class InEdgeIt {
     159     public:
     160      InEdgeIt() { }
     161      //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
     162      InEdgeIt(Invalid i) : Edge(i) { }
     163      InEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
     164        Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
     165      InEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
     166        Edge(e), gw(&_gw) { }
     167      InEdgeIt& operator++() {
     168        *(static_cast<Edge*>(this))=
     169          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     170        return *this;
     171      }
     172    };
     173    //typedef typename Graph::SymEdgeIt SymEdgeIt;
     174    class EdgeIt : public Edge {
     175      const GraphWrapper<Graph>* gw;
    143176      friend class GraphWrapper<Graph>;
    144       typename Graph::InEdgeIt e;
    145     public:
    146       InEdgeIt() { }
    147       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
    148       InEdgeIt(const Invalid& i) : e(i) { }
    149       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
    150         e(*(_G.graph), typename Graph::Node(_n)) { }
    151       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    152     };
    153     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    154     class EdgeIt {
    155       friend class GraphWrapper<Graph>;
    156       typename Graph::EdgeIt e;
    157     public:
     177     public:
    158178      EdgeIt() { }
    159       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
    160       EdgeIt(const Invalid& i) : e(i) { }
    161       EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
    162       operator Edge() const { return Edge(typename Graph::Edge(e)); }
     179      //EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { }
     180      EdgeIt(Invalid i) : Edge(i) { }
     181      EdgeIt(const GraphWrapper<Graph>& _gw) :
     182        Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
     183      EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
     184        Edge(w), gw(&_gw) { }
     185      EdgeIt& operator++() {
     186        *(static_cast<Edge*>(this))=
     187          ++(typename Graph::EdgeIt(*(gw->graph), *this));
     188        return *this;
     189      }
    163190    };
    164191   
     
    176203    }
    177204
    178     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
    179     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
    180     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
    181     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
     205//     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
     206//     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
     207//     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
     208//     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
    182209
    183210    Node tail(const Edge& e) const {
     
    186213      return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
    187214
    188     bool valid(const Node& n) const {
    189       return graph->valid(static_cast<typename Graph::Node>(n)); }
    190     bool valid(const Edge& e) const {
    191       return graph->valid(static_cast<typename Graph::Edge>(e)); }
     215//     bool valid(const Node& n) const {
     216//       return graph->valid(static_cast<typename Graph::Node>(n)); }
     217//     bool valid(const Edge& e) const {
     218//       return graph->valid(static_cast<typename Graph::Edge>(e)); }
    192219
    193220    int nodeNum() const { return graph->nodeNum(); }
    194221    int edgeNum() const { return graph->edgeNum(); }
    195222 
    196     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    197     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    198     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
    199     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
     223//     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
     224//     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
     225//     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
     226//     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
    200227 
    201228    Node addNode() const { return Node(graph->addNode()); }
     
    219246      typedef typename Graph::template NodeMap<T> Parent;
    220247    public:
    221       NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }
    222       NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
     248      NodeMap(const GraphWrapper<Graph>& gw) :  Parent(*(gw.graph)) { }
     249      NodeMap(const GraphWrapper<Graph>& gw, T a) : Parent(*(gw.graph), a) { }
    223250    };
    224251
     
    226253      typedef typename Graph::template EdgeMap<T> Parent;
    227254    public:
    228       EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
    229       EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
     255      EdgeMap(const GraphWrapper<Graph>& gw) : Parent(*(gw.graph)) { }
     256      EdgeMap(const GraphWrapper<Graph>& gw, T a) : Parent(*(gw.graph), a) { }
    230257    };
    231258  };
     
    247274  public:
    248275    RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
     276    RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { }
    249277
    250278    typedef typename GraphWrapper<Graph>::Node Node;
     
    257285    //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
    258286
    259     class OutEdgeIt {
     287    class OutEdgeIt : public Edge {
     288      const RevGraphWrapper<Graph>* gw;
    260289      friend class GraphWrapper<Graph>;
    261       friend class RevGraphWrapper<Graph>;
    262       typename Graph::InEdgeIt e;
    263     public:
     290     public:
    264291      OutEdgeIt() { }
    265       OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
    266       OutEdgeIt(const Invalid& i) : e(i) { }
    267       OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
    268         e(*(_G.graph), typename Graph::Node(_n)) { }
    269       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    270     };
    271     class InEdgeIt {
     292      //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
     293      OutEdgeIt(Invalid i) : Edge(i) { }
     294      OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
     295        Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
     296      OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
     297        Edge(e), gw(&_gw) { }
     298      OutEdgeIt& operator++() {
     299        *(static_cast<Edge*>(this))=
     300          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     301        return *this;
     302      }
     303    };
     304    class InEdgeIt : public Edge {
     305      const RevGraphWrapper<Graph>* gw;
    272306      friend class GraphWrapper<Graph>;
    273       friend class RevGraphWrapper<Graph>;
    274       typename Graph::OutEdgeIt e;
    275     public:
     307     public:
    276308      InEdgeIt() { }
    277       InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
    278       InEdgeIt(const Invalid& i) : e(i) { }
    279       InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
    280         e(*(_G.graph), typename Graph::Node(_n)) { }
    281       operator Edge() const { return Edge(typename Graph::Edge(e)); }
     309      //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
     310      InEdgeIt(Invalid i) : Edge(i) { }
     311      InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
     312        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
     313      InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
     314        Edge(e), gw(&_gw) { }
     315      InEdgeIt& operator++() {
     316        *(static_cast<Edge*>(this))=
     317          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     318        return *this;
     319      }
    282320    };
    283321
     
    290328    }
    291329
    292     using GraphWrapper<Graph>::next;
    293     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
    294     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
    295 
    296     Node aNode(const OutEdgeIt& e) const {
    297       return Node(this->graph->aNode(e.e)); }
    298     Node aNode(const InEdgeIt& e) const {
    299       return Node(this->graph->aNode(e.e)); }
    300     Node bNode(const OutEdgeIt& e) const {
    301       return Node(this->graph->bNode(e.e)); }
    302     Node bNode(const InEdgeIt& e) const {
    303       return Node(this->graph->bNode(e.e)); }
     330//     using GraphWrapper<Graph>::next;
     331//     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
     332//     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
     333
     334//     Node aNode(const OutEdgeIt& e) const {
     335//       return Node(this->graph->aNode(e.e)); }
     336//     Node aNode(const InEdgeIt& e) const {
     337//       return Node(this->graph->aNode(e.e)); }
     338//     Node bNode(const OutEdgeIt& e) const {
     339//       return Node(this->graph->bNode(e.e)); }
     340//     Node bNode(const InEdgeIt& e) const {
     341//       return Node(this->graph->bNode(e.e)); }
    304342
    305343    Node tail(const Edge& e) const {
     
    309347
    310348  };
    311 
    312 
    313349
    314350  /// A graph wrapper for hiding nodes and edges from a graph.
     
    627663    typedef GraphWrapper<Graph> Parent;
    628664  protected:
    629     //const CapacityMap* capacity;
    630     //FlowMap* flow;
    631 
    632665    ForwardFilterMap* forward_filter;
    633666    BackwardFilterMap* backward_filter;
     
    648681      GraphWrapper<Graph>(_graph),
    649682      forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
     683    SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph,
     684                         ForwardFilterMap, BackwardFilterMap>& gw) :
     685      Parent(gw),
     686      forward_filter(gw.forward_filter),
     687      backward_filter(gw.backward_filter) { }
    650688
    651689    class Edge;
     
    658696
    659697    typedef typename GraphWrapper<Graph>::Node Node;
    660     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    661 
     698    //typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
     699
     700    typedef typename Graph::Edge GraphEdge;
    662701    class Edge : public Graph::Edge {
    663702      friend class SubBidirGraphWrapper<Graph,
     
    672711      Edge() { }
    673712      ///\bug =false kell-e? zsoltnak kell az addEdge miatt
    674       Edge(const typename Graph::Edge& _e, bool _backward=false) :
    675         Graph::Edge(_e), backward(_backward) { }
    676       Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
     713      Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
     714        Graph::Edge(e), backward(_backward) { }
     715      Edge(Invalid i) : Graph::Edge(i), backward(true) { }
    677716//the unique invalid iterator
    678       friend bool operator==(const Edge& u, const Edge& v) {
    679         return (v.backward==u.backward &&
    680                 static_cast<typename Graph::Edge>(u)==
     717//       friend bool operator==(const Edge& u, const Edge& v) {
     718//      return (u.backward==v.backward &&
     719//              static_cast<typename Graph::Edge>(u)==
     720//              static_cast<typename Graph::Edge>(v));
     721//       }
     722//       friend bool operator!=(const Edge& u, const Edge& v) {
     723//      return (u.backward!=v.backward ||
     724//              static_cast<typename Graph::Edge>(u)!=
     725//              static_cast<typename Graph::Edge>(v));
     726//       }
     727      bool operator==(const Edge& v) const {
     728        return (this->backward==v.backward &&
     729                static_cast<typename Graph::Edge>(*this)==
    681730                static_cast<typename Graph::Edge>(v));
    682731      }
    683       friend bool operator!=(const Edge& u, const Edge& v) {
    684         return (v.backward!=u.backward ||
    685                 static_cast<typename Graph::Edge>(u)!=
     732      bool operator!=(const Edge& v) const {
     733        return (this->backward!=v.backward ||
     734                static_cast<typename Graph::Edge>(*this)!=
    686735                static_cast<typename Graph::Edge>(v));
    687       } 
    688     };
    689 
    690     class OutEdgeIt {
     736      }
     737    };
     738
     739    class OutEdgeIt : public Edge {
    691740      friend class SubBidirGraphWrapper<Graph,
    692741                                        ForwardFilterMap, BackwardFilterMap>;
    693742    protected:
    694       typename Graph::OutEdgeIt out;
    695       typename Graph::InEdgeIt in;
    696       bool backward;
     743      const SubBidirGraphWrapper<Graph,
     744                                 ForwardFilterMap, BackwardFilterMap>* gw;
    697745    public:
    698746      OutEdgeIt() { }
    699       //FIXME
    700 //      OutEdgeIt(const Edge& e) : Edge(e) { }
    701       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
     747      OutEdgeIt(Invalid i) : Edge(i) { }
    702748//the unique invalid iterator
    703749      OutEdgeIt(const SubBidirGraphWrapper<Graph,
    704                 ForwardFilterMap, BackwardFilterMap>& _G, Node v) {
    705         backward=false;
    706         _G.graph->first(out, v);
    707         while(_G.graph->valid(out) && !(*_G.forward_filter)[*this]) { _G.graph->next(out); }
    708         if (!_G.graph->valid(out)) {
    709           backward=true;
    710           _G.graph->first(in, v);
    711           while(_G.graph->valid(in) && !(*_G.backward_filter)[*this]) { _G.graph->next(in); }
     750                ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
     751        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
     752        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     753               !(*(gw->forward_filter))[*this])
     754          *(static_cast<GraphEdge*>(this))=
     755            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     756        if (*static_cast<GraphEdge*>(this)==INVALID)
     757          *static_cast<Edge*>(this)=
     758            Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
     759        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     760               !(*(gw->backward_filter))[*this])
     761          *(static_cast<GraphEdge*>(this))=
     762            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     763      }
     764      OutEdgeIt(const SubBidirGraphWrapper<Graph,
     765                ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
     766        Edge(e), gw(&_gw) { }
     767      OutEdgeIt& operator++() {
     768        if (!this->backward) {
     769          Node n=gw->tail(*this);
     770          *(static_cast<GraphEdge*>(this))=
     771            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     772          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     773                 !(*(gw->forward_filter))[*this])
     774            *(static_cast<GraphEdge*>(this))=
     775              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     776          if (*static_cast<GraphEdge*>(this)==INVALID)
     777            *static_cast<Edge*>(this)=
     778              Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
     779          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     780                 !(*(gw->backward_filter))[*this])
     781            *(static_cast<GraphEdge*>(this))=
     782              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     783        } else {
     784          *(static_cast<GraphEdge*>(this))=
     785            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     786          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     787                 !(*(gw->backward_filter))[*this])
     788            *(static_cast<GraphEdge*>(this))=
     789              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
    712790        }
    713       }
    714       operator Edge() const {
    715 //      Edge e;
    716 //      e.forward=this->forward;
    717 //      if (this->forward) e=out; else e=in;
    718 //      return e;
    719         if (this->backward)
    720           return Edge(in, this->backward);
    721         else
    722           return Edge(out, this->backward);
    723       }
    724     };
    725 
    726     class InEdgeIt {
     791        return *this;
     792      }
     793    };
     794
     795    class InEdgeIt : public Edge {
    727796      friend class SubBidirGraphWrapper<Graph,
    728797                                        ForwardFilterMap, BackwardFilterMap>;
    729798    protected:
    730       typename Graph::OutEdgeIt out;
    731       typename Graph::InEdgeIt in;
    732       bool backward;
     799      const SubBidirGraphWrapper<Graph,
     800                                 ForwardFilterMap, BackwardFilterMap>* gw;
    733801    public:
    734802      InEdgeIt() { }
    735       //FIXME
    736 //      OutEdgeIt(const Edge& e) : Edge(e) { }
    737       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
     803      InEdgeIt(Invalid i) : Edge(i) { }
    738804//the unique invalid iterator
    739805      InEdgeIt(const SubBidirGraphWrapper<Graph,
    740                ForwardFilterMap, BackwardFilterMap>& _G, Node v) {
    741         backward=false;
    742         _G.graph->first(in, v);
    743         while(_G.graph->valid(in) && !(*_G.forward_filter)[*this]) { _G.graph->next(in); }
    744         if (!_G.graph->valid(in)) {
    745           backward=true;
    746           _G.graph->first(out, v);
    747           while(_G.graph->valid(out) && !(*_G.backward_filter)[*this]) { _G.graph->next(out); }
     806               ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
     807        Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
     808        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     809               !(*(gw->forward_filter))[*this])
     810          *(static_cast<GraphEdge*>(this))=
     811            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     812        if (*static_cast<GraphEdge*>(this)==INVALID)
     813          *static_cast<Edge*>(this)=
     814            Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
     815        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     816               !(*(gw->backward_filter))[*this])
     817          *(static_cast<GraphEdge*>(this))=
     818            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     819      }
     820      InEdgeIt(const SubBidirGraphWrapper<Graph,
     821               ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
     822        Edge(e), gw(&_gw) { }
     823      InEdgeIt& operator++() {
     824        if (!this->backward) {
     825          Node n=gw->head(*this);
     826          *(static_cast<GraphEdge*>(this))=
     827            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     828          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     829                 !(*(gw->forward_filter))[*this])
     830            *(static_cast<GraphEdge*>(this))=
     831              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     832          if (*static_cast<GraphEdge*>(this)==INVALID)
     833            *static_cast<Edge*>(this)=
     834              Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
     835          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     836                 !(*(gw->backward_filter))[*this])
     837            *(static_cast<GraphEdge*>(this))=
     838              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     839        } else {
     840          *(static_cast<GraphEdge*>(this))=
     841            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     842          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     843                 !(*(gw->backward_filter))[*this])
     844            *(static_cast<GraphEdge*>(this))=
     845              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
    748846        }
    749       }
    750       operator Edge() const {
    751 //      Edge e;
    752 //      e.forward=this->forward;
    753 //      if (this->forward) e=out; else e=in;
    754 //      return e;
    755         if (this->backward)
    756           return Edge(out, this->backward);
    757         else
    758           return Edge(in, this->backward);
    759       }
    760     };
    761 
    762     class EdgeIt {
     847        return *this;
     848      }
     849    };
     850
     851    class EdgeIt : public Edge {
    763852      friend class SubBidirGraphWrapper<Graph,
    764853                                        ForwardFilterMap, BackwardFilterMap>;
    765854    protected:
    766       typename Graph::EdgeIt e;
    767       bool backward;
     855      const SubBidirGraphWrapper<Graph,
     856                                 ForwardFilterMap, BackwardFilterMap>* gw;
    768857    public:
    769858      EdgeIt() { }
    770       EdgeIt(const Invalid& i) : e(i), backward(true) { }
     859      EdgeIt(Invalid i) : Edge(i) { }
     860//the unique invalid iterator
    771861      EdgeIt(const SubBidirGraphWrapper<Graph,
    772              ForwardFilterMap, BackwardFilterMap>& _G) {
    773         backward=false;
    774         _G.graph->first(e);
    775         while (_G.graph->valid(e) && !(*_G.forward_filter)[*this]) _G.graph->next(e);
    776         if (!_G.graph->valid(e)) {
    777           backward=true;
    778           _G.graph->first(e);
    779           while (_G.graph->valid(e) && !(*_G.backward_filter)[*this]) _G.graph->next(e);
     862                ForwardFilterMap, BackwardFilterMap>& _gw) :
     863        Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) {
     864        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     865               !(*(gw->forward_filter))[*this])
     866          *(static_cast<GraphEdge*>(this))=
     867            ++(typename Graph::EdgeIt(*(gw->graph), *this));
     868        if (*static_cast<GraphEdge*>(this)==INVALID)
     869          *static_cast<Edge*>(this)=
     870            Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
     871        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     872               !(*(gw->backward_filter))[*this])
     873          *(static_cast<GraphEdge*>(this))=
     874            ++(typename Graph::EdgeIt(*(gw->graph), *this));
     875      }
     876      EdgeIt(const SubBidirGraphWrapper<Graph,
     877             ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
     878        Edge(e), gw(&_gw) { }
     879      EdgeIt& operator++() {
     880        if (!this->backward) {
     881          *(static_cast<GraphEdge*>(this))=
     882            ++(typename Graph::EdgeIt(*(gw->graph), *this));
     883          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     884                 !(*(gw->forward_filter))[*this])
     885            *(static_cast<GraphEdge*>(this))=
     886              ++(typename Graph::EdgeIt(*(gw->graph), *this));
     887          if (*static_cast<GraphEdge*>(this)==INVALID)
     888            *static_cast<Edge*>(this)=
     889              Edge(typename Graph::EdgeIt(*(gw->graph)), true);
     890          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     891                 !(*(gw->backward_filter))[*this])
     892            *(static_cast<GraphEdge*>(this))=
     893              ++(typename Graph::EdgeIt(*(gw->graph), *this));
     894        } else {
     895          *(static_cast<GraphEdge*>(this))=
     896            ++(typename Graph::EdgeIt(*(gw->graph), *this));
     897          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     898                 !(*(gw->backward_filter))[*this])
     899            *(static_cast<GraphEdge*>(this))=
     900              ++(typename Graph::EdgeIt(*(gw->graph), *this));
    780901        }
    781       }
    782       operator Edge() const {
    783         return Edge(e, this->backward);
     902        return *this;
    784903      }
    785904    };
     
    800919    }
    801920 
    802     using GraphWrapper<Graph>::next;
    803 //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
    804     OutEdgeIt& next(OutEdgeIt& e) const {
    805       if (!e.backward) {
    806         Node v=this->graph->aNode(e.out);
    807         this->graph->next(e.out);
    808         while(this->graph->valid(e.out) && !(*forward_filter)[e]) {
    809           this->graph->next(e.out); }
    810         if (!this->graph->valid(e.out)) {
    811           e.backward=true;
    812           this->graph->first(e.in, v);
    813           while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
    814             this->graph->next(e.in); }
    815         }
    816       } else {
    817         this->graph->next(e.in);
    818         while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
    819           this->graph->next(e.in); }
    820       }
    821       return e;
    822     }
    823 //     FIXME Not tested
    824     InEdgeIt& next(InEdgeIt& e) const {
    825       if (!e.backward) {
    826         Node v=this->graph->aNode(e.in);
    827         this->graph->next(e.in);
    828         while(this->graph->valid(e.in) && !(*forward_filter)[e]) {
    829           this->graph->next(e.in); }
    830         if (!this->graph->valid(e.in)) {
    831           e.backward=true;
    832           this->graph->first(e.out, v);
    833           while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
    834             this->graph->next(e.out); }
    835         }
    836       } else {
    837         this->graph->next(e.out);
    838         while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
    839           this->graph->next(e.out); }
    840       }
    841       return e;
    842     }
    843     EdgeIt& next(EdgeIt& e) const {
    844       if (!e.backward) {
    845         this->graph->next(e.e);
    846         while(this->graph->valid(e.e) && !(*forward_filter)[e]) {
    847           this->graph->next(e.e); }
    848         if (!this->graph->valid(e.e)) {
    849           e.backward=true;
    850           this->graph->first(e.e);
    851           while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
    852             this->graph->next(e.e); }
    853         }
    854       } else {
    855         this->graph->next(e.e);
    856         while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
    857           this->graph->next(e.e); }
    858       }
    859       return e;
    860     }
     921//     using GraphWrapper<Graph>::next;
     922// //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
     923//     OutEdgeIt& next(OutEdgeIt& e) const {
     924//       if (!e.backward) {
     925//      Node v=this->graph->aNode(e.out);
     926//      this->graph->next(e.out);
     927//      while(this->graph->valid(e.out) && !(*forward_filter)[e]) {
     928//        this->graph->next(e.out); }
     929//      if (!this->graph->valid(e.out)) {
     930//        e.backward=true;
     931//        this->graph->first(e.in, v);
     932//        while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
     933//          this->graph->next(e.in); }
     934//      }
     935//       } else {
     936//      this->graph->next(e.in);
     937//      while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
     938//        this->graph->next(e.in); }
     939//       }
     940//       return e;
     941//     }
     942// //     FIXME Not tested
     943//     InEdgeIt& next(InEdgeIt& e) const {
     944//       if (!e.backward) {
     945//      Node v=this->graph->aNode(e.in);
     946//      this->graph->next(e.in);
     947//      while(this->graph->valid(e.in) && !(*forward_filter)[e]) {
     948//        this->graph->next(e.in); }
     949//      if (!this->graph->valid(e.in)) {
     950//        e.backward=true;
     951//        this->graph->first(e.out, v);
     952//        while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
     953//          this->graph->next(e.out); }
     954//      }
     955//       } else {
     956//      this->graph->next(e.out);
     957//      while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
     958//        this->graph->next(e.out); }
     959//       }
     960//       return e;
     961//     }
     962//     EdgeIt& next(EdgeIt& e) const {
     963//       if (!e.backward) {
     964//      this->graph->next(e.e);
     965//      while(this->graph->valid(e.e) && !(*forward_filter)[e]) {
     966//        this->graph->next(e.e); }
     967//      if (!this->graph->valid(e.e)) {
     968//        e.backward=true;
     969//        this->graph->first(e.e);
     970//        while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
     971//          this->graph->next(e.e); }
     972//      }
     973//       } else {
     974//      this->graph->next(e.e);
     975//      while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
     976//        this->graph->next(e.e); }
     977//       }
     978//       return e;
     979//     }
    861980
    862981    Node tail(Edge e) const {
     
    865984      return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
    866985
    867     Node aNode(OutEdgeIt e) const {
    868       return ((!e.backward) ? this->graph->aNode(e.out) :
    869               this->graph->aNode(e.in)); }
    870     Node bNode(OutEdgeIt e) const {
    871       return ((!e.backward) ? this->graph->bNode(e.out) :
    872               this->graph->bNode(e.in)); }
    873 
    874     Node aNode(InEdgeIt e) const {
    875       return ((!e.backward) ? this->graph->aNode(e.in) :
    876               this->graph->aNode(e.out)); }
    877     Node bNode(InEdgeIt e) const {
    878       return ((!e.backward) ? this->graph->bNode(e.in) :
    879               this->graph->bNode(e.out)); }
     986//     Node aNode(OutEdgeIt e) const {
     987//       return ((!e.backward) ? this->graph->aNode(e.out) :
     988//            this->graph->aNode(e.in)); }
     989//     Node bNode(OutEdgeIt e) const {
     990//       return ((!e.backward) ? this->graph->bNode(e.out) :
     991//            this->graph->bNode(e.in)); }
     992
     993//     Node aNode(InEdgeIt e) const {
     994//       return ((!e.backward) ? this->graph->aNode(e.in) :
     995//            this->graph->aNode(e.out)); }
     996//     Node bNode(InEdgeIt e) const {
     997//       return ((!e.backward) ? this->graph->bNode(e.in) :
     998//            this->graph->bNode(e.out)); }
    880999
    8811000    /// Gives back the opposite edge.
     
    8941013//    int id(Node v) const { return graph->id(v); }
    8951014
    896     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
    897     bool valid(Edge e) const {
    898       return this->graph->valid(e);
    899         //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
    900     }
     1015//     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
     1016//     bool valid(Edge e) const {
     1017//       return this->graph->valid(e);
     1018//      //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
     1019//     }
    9011020
    9021021    bool forward(const Edge& e) const { return !e.backward; }
     
    9401059      typedef Edge KeyType;
    9411060      EdgeMap(const SubBidirGraphWrapper<Graph,
    942               ForwardFilterMap, BackwardFilterMap>& _G) :
    943         forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
     1061              ForwardFilterMap, BackwardFilterMap>& g) :
     1062        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
    9441063      EdgeMap(const SubBidirGraphWrapper<Graph,
    945               ForwardFilterMap, BackwardFilterMap>& _G, T a) :
    946         forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
     1064              ForwardFilterMap, BackwardFilterMap>& g, T a) :
     1065        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
    9471066      void set(Edge e, T a) {
    9481067        if (!e.backward)
Note: See TracChangeset for help on using the changeset viewer.