COIN-OR::LEMON - Graph Library

Changeset 317:6e6db1c49bc1 in lemon-0.x


Ignore:
Timestamp:
04/13/04 22:35:47 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@435
Message:

gw

Location:
src/work/marci
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/edmonds_karp.h

    r312 r317  
    600600        //invalid iterators for sources
    601601
    602         typename ErasingResGW::NodeMap<Number> free(erasing_res_graph);
    603 
    604         dfs.pushAndSetReached(s);
     602        typename ErasingResGW::NodeMap<Number> free1(erasing_res_graph);
     603
     604        dfs.pushAndSetReached(
     605          typename ErasingResGW::Node(
     606            typename FilterResGW::Node(
     607              typename ResGW::Node(s)
     608              )
     609            )
     610          );
    605611        while (!dfs.finished()) {
    606612          ++dfs;
    607613          if (erasing_res_graph.valid(
    608                 /*typename ErasingResGW::OutEdgeIt*/(dfs)))
     614                typename ErasingResGW::OutEdgeIt(dfs)))
    609615          {
    610616            if (dfs.isBNodeNewlyReached()) {
     
    615621              pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
    616622              if (erasing_res_graph.valid(pred[v])) {
    617                 free.set(w, std::min(free[v], res_graph.resCap(dfs)));
     623                free1.set(w, std::min(free1[v], res_graph.resCap(
     624                                       typename ErasingResGW::OutEdgeIt(dfs))));
    618625              } else {
    619                 free.set(w, res_graph.resCap(dfs));
     626                free1.set(w, res_graph.resCap(
     627                           typename ErasingResGW::OutEdgeIt(dfs)));
    620628              }
    621629             
     
    632640
    633641        if (__augment) {
    634           typename ErasingResGW::Node n=t;
    635           Number augment_value=free[n];
     642          typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t));
     643//        typename ResGW::NodeMap<Number> a(res_graph);
     644//        typename ResGW::Node b;
     645//        Number j=a[b];
     646//        typename FilterResGW::NodeMap<Number> a1(filter_res_graph);
     647//        typename FilterResGW::Node b1;
     648//        Number j1=a1[b1];
     649//        typename ErasingResGW::NodeMap<Number> a2(erasing_res_graph);
     650//        typename ErasingResGW::Node b2;
     651//        Number j2=a2[b2];
     652          Number augment_value=free1[n];
    636653          while (erasing_res_graph.valid(pred[n])) {
    637654            typename ErasingResGW::OutEdgeIt e=pred[n];
  • src/work/marci/edmonds_karp_demo.cc

    r311 r317  
    3636  typedef ListGraph MutableGraph;
    3737
    38   typedef SmartGraph Graph;
    39   //typedef ListGraph Graph;
     38//  typedef SmartGraph Graph;
     39  typedef ListGraph Graph;
    4040  typedef Graph::Node Node;
    4141  typedef Graph::EdgeIt EdgeIt;
     
    6767  Graph::EdgeMap<int> cap(G);
    6868  readDimacsMaxFlow(std::cin, G, s, t, cap);
    69 
    70 //   typedef TrivGraphWrapper<Graph> TGW;
    71 //   TGW gw(G);
    72 //   TGW::NodeIt sw;
    73 //   gw./*getF*/first(sw);
    74 //   std::cout << "p1:" << gw.nodeNum() << std::endl;
    75 //   gw.erase(sw);
    76 //   std::cout << "p2:" << gw.nodeNum() << std::endl;
    77 
    78 //   typedef const Graph cLG;
    79 //   typedef TrivGraphWrapper<const cLG> CTGW;
    80 //   CTGW cgw(G);
    81 //   CTGW::NodeIt csw;
    82 //   cgw./*getF*/first(csw);
    83 //   std::cout << "p1:" << cgw.nodeNum() << std::endl;
    84 //   //cgw.erase(csw);
    85 //   std::cout << "p2:" << cgw.nodeNum() << std::endl;
    8669
    8770  {
  • src/work/marci/graph_wrapper.h

    r312 r317  
    66
    77namespace hugo {
    8 
    9 //   template<typename Graph>
    10 //   class TrivGraphWrapper {
    11 //   protected:
    12 //     Graph* graph;
    13  
    14 //   public:
    15 // //    typedef Graph BaseGraph;
    16 //     typedef Graph ParentGraph;
    17 
    18 // //     TrivGraphWrapper() : graph(0) { }
    19 //     TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
    20 // //     void setGraph(Graph& _graph) { graph = &_graph; }
    21 // //     Graph& getGraph() const { return *graph; }
    22 
    23 //     typedef typename Graph::Node Node;
    24 //     class NodeIt : public Graph::NodeIt {
    25 //     public:
    26 //       NodeIt() { }
    27 //       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
    28 //       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
    29 //       NodeIt(const TrivGraphWrapper<Graph>& _G) :
    30 //      Graph::NodeIt(*(_G.graph)) { }
    31 //     };
    32 //     typedef typename Graph::Edge Edge;
    33 //     class OutEdgeIt : public Graph::OutEdgeIt {
    34 //     public:
    35 //       OutEdgeIt() { }
    36 //       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
    37 //       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
    38 //       OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
    39 //      Graph::OutEdgeIt(*(_G.graph), n) { }
    40 //     };
    41 //     class InEdgeIt : public Graph::InEdgeIt {
    42 //     public:
    43 //       InEdgeIt() { }
    44 //       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
    45 //       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
    46 //       InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
    47 //      Graph::InEdgeIt(*(_G.graph), n) { }
    48 //     };
    49 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    50 //     class EdgeIt : public Graph::EdgeIt {
    51 //     public:
    52 //       EdgeIt() { }
    53 //       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
    54 //       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
    55 //       EdgeIt(const TrivGraphWrapper<Graph>& _G) :
    56 //      Graph::EdgeIt(*(_G.graph)) { }
    57 //     };
    58 
    59 //     NodeIt& first(NodeIt& i) const {
    60 //       i=NodeIt(*this);
    61 //       return i;
    62 //     }
    63 //     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    64 //       i=OutEdgeIt(*this, p);
    65 //       return i;
    66 //     }
    67 //     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    68 //       i=InEdgeIt(*this, p);
    69 //       return i;
    70 //     }
    71 //     EdgeIt& first(EdgeIt& i) const {
    72 //       i=EdgeIt(*this);
    73 //       return i;
    74 //     }
    75 // //     template<typename I> I& first(I& i) const {
    76 // //       i=I(*this);
    77 // //       return i;
    78 // //     }
    79 // //     template<typename I, typename P> I& first(I& i, const P& p) const {
    80 // //       i=I(*this, p);
    81 // //       return i;
    82 // //     }
    83    
    84 // //    template<typename I> I getNext(const I& i) const {
    85 // //      return graph->getNext(i); }
    86 
    87 //     NodeIt& next(NodeIt& i) const { graph->next(i); return i; }
    88 //     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; }
    89 //     InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; }
    90 //     EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; }
    91 // //    template<typename I> I& next(I &i) const { graph->next(i); return i; }   
    92 //     template< typename It > It first() const {
    93 //       It e; this->first(e); return e; }
    94 
    95 //     template< typename It > It first(const Node& v) const {
    96 //       It e; this->first(e, v); return e; }
    97 
    98 //     Node head(const Edge& e) const { return graph->head(e); }
    99 //     Node tail(const Edge& e) const { return graph->tail(e); }
    100 
    101 //     template<typename I> bool valid(const I& i) const {
    102 //       return graph->valid(i); }
    103  
    104 //     //template<typename I> void setInvalid(const I &i);
    105 //     //{ return graph->setInvalid(i); }
    106 
    107 //     int nodeNum() const { return graph->nodeNum(); }
    108 //     int edgeNum() const { return graph->edgeNum(); }
    109  
    110 //     template<typename I> Node aNode(const I& e) const {
    111 //       return graph->aNode(e); }
    112 //     template<typename I> Node bNode(const I& e) const {
    113 //       return graph->bNode(e); }
    114  
    115 //     Node addNode() const { return graph->addNode(); }
    116 //     Edge addEdge(const Node& tail, const Node& head) const {
    117 //       return graph->addEdge(tail, head); }
    118  
    119 //     template<typename I> void erase(const I& i) const { graph->erase(i); }
    120  
    121 //     void clear() const { graph->clear(); }
    122    
    123 //     template<typename T> class NodeMap : public Graph::NodeMap<T> {
    124 //     public:
    125 //       NodeMap(const TrivGraphWrapper<Graph>& _G) : 
    126 //      Graph::NodeMap<T>(*(_G.graph)) { }
    127 //       NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
    128 //      Graph::NodeMap<T>(*(_G.graph), a) { }
    129 //     };
    130 
    131 //     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
    132 //     public:
    133 //       EdgeMap(const TrivGraphWrapper<Graph>& _G) : 
    134 //      Graph::EdgeMap<T>(*(_G.graph)) { }
    135 //       EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
    136 //      Graph::EdgeMap<T>(*(_G.graph), a) { }
    137 //     };
    138 
    139 // //     template<typename Map, typename T> class NodeMapWrapper {
    140 // //     protected:
    141 // //       Map* map;
    142 // //     public:
    143 // //       NodeMapWrapper(Map& _map) : map(&_map) { }
    144 // //       void set(Node n, T a) { map->set(n, a); }
    145 // //       T get(Node n) const { return map->get(n); }
    146 // //     };
    147 
    148 // //     template<typename Map, typename T> class EdgeMapWrapper {
    149 // //     protected:
    150 // //       Map* map;
    151 // //     public:
    152 // //       EdgeMapWrapper(Map& _map) : map(&_map) { }
    153 // //       void set(Edge n, T a) { map->set(n, a); }
    154 // //       T get(Edge n) const { return map->get(n); }
    155 // //     };
    156 //   };
    157 
    1588
    1599  template<typename Graph>
     
    17121//     Graph& getGraph() const { return *graph; }
    17222 
    173     typedef typename Graph::Node Node;
    174     class NodeIt : public Graph::NodeIt {
    175       typedef typename Graph::NodeIt GraphNodeIt;
     23//    typedef typename Graph::Node Node;
     24    class Node : public Graph::Node {
     25      friend class GraphWrapper<Graph>;
    17626    public:
     27      Node() { }
     28      Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
     29      Node(const Invalid& i) : Graph::Node(i) { }
     30    };
     31    class NodeIt {
     32      friend class GraphWrapper<Graph>;
     33      typename Graph::NodeIt n;
     34     public:
    17735      NodeIt() { }
    178       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
    179       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
    180       NodeIt(const GraphWrapper<Graph>& _G) :
    181         Graph::NodeIt(*(_G.graph)) { }
    182 //      operator Node() const {
    183 //      std::cout << "ize" << std::endl;
    184 //      return Node(this->GraphNodeIt);
    185 //      }
     36      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
     37      NodeIt(const Invalid& i) : n(i) { }
     38      NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
     39      operator Node() const { return Node(typename Graph::Node(n)); }
    18640    };
    187     typedef typename Graph::Edge Edge;
    188     class OutEdgeIt : public Graph::OutEdgeIt {
    189       typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
     41//     class Node : public Graph::Node {
     42//     public:
     43//       Node() { }
     44//       Node(const typename Graph::Node& n) : Graph::Node(n) { }
     45//       Node(const Invalid& i) : Graph::Node(i) { }
     46//     };
     47//     class NodeIt : public Graph::NodeIt {
     48//       typedef typename Graph::NodeIt GraphNodeIt;
     49//     public:
     50//       NodeIt() { }
     51//       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
     52//       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
     53//       NodeIt(const GraphWrapper<Graph>& _G) :
     54//      Graph::NodeIt(*(_G.graph)) { }
     55//       operator Node() const {
     56//      return Node(typename Graph::Node(
     57//                    static_cast<typename Graph::NodeIt>(*this)
     58//                    ));
     59//       }
     60//     };
     61//    typedef typename Graph::Edge Edge;
     62    class Edge : public Graph::Edge {
     63      friend class GraphWrapper<Graph>;
     64    public:
     65      Edge() { }
     66      Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
     67      Edge(const Invalid& i) : Graph::Edge(i) { }
     68    };
     69    class OutEdgeIt {
     70      friend class GraphWrapper<Graph>;
     71//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
     72      typename Graph::OutEdgeIt e;
    19073    public:
    19174      OutEdgeIt() { }
    192       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
    193       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
    194       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :
    195         Graph::OutEdgeIt(*(_G.graph), n) { }
    196 //      operator Edge() const {
    197 //      std::cout << "ize" << std::endl;
    198 //      return Edge(this->GraphOutEdgeIt);
    199 //      }
     75      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
     76      OutEdgeIt(const Invalid& i) : e(i) { }
     77      OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
     78        e(*(_G.graph), typename Graph::Node(_n)) { }
     79      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    20080    };
    201     class InEdgeIt : public Graph::InEdgeIt {
    202       typedef typename Graph::InEdgeIt GraphInEdgeIt;
     81    class InEdgeIt {
     82      friend class GraphWrapper<Graph>;
     83//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
     84      typename Graph::InEdgeIt e;
    20385    public:
    20486      InEdgeIt() { }
    205       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
    206       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
    207       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :
    208         Graph::InEdgeIt(*(_G.graph), n) { }
    209 //      operator Edge() const {
    210 //      std::cout << "ize" << std::endl;
    211 //      return Edge(this->InOutEdgeIt);
    212 //      }
     87      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
     88      InEdgeIt(const Invalid& i) : e(i) { }
     89      InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
     90        e(*(_G.graph), typename Graph::Node(_n)) { }
     91      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    21392    };
    21493    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    215     class EdgeIt : public Graph::EdgeIt {
    216       typedef typename Graph::EdgeIt GraphEdgeIt;
     94    class EdgeIt {
     95      friend class GraphWrapper<Graph>;
     96//      typedef typename Graph::EdgeIt GraphEdgeIt;
     97      typename Graph::EdgeIt e;
    21798    public:
    21899      EdgeIt() { }
    219       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
    220       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
    221       EdgeIt(const GraphWrapper<Graph>& _G) :
    222         Graph::EdgeIt(*(_G.graph)) { }
    223 //      operator Edge() const {
    224 //      std::cout << "ize" << std::endl;
    225 //      return Edge(this->GraphEdgeIt);
    226 //      }
     100      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
     101      EdgeIt(const Invalid& i) : e(i) { }
     102      EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
     103      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    227104    };
    228105   
    229106    NodeIt& first(NodeIt& i) const {
    230       i=NodeIt(*this);
    231       return i;
     107      i=NodeIt(*this); return i;
    232108    }
    233109    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    234       i=OutEdgeIt(*this, p);
    235       return i;
     110      i=OutEdgeIt(*this, p); return i;
    236111    }
    237112    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    238       i=InEdgeIt(*this, p);
    239       return i;
     113      i=InEdgeIt(*this, p); return i;
    240114    }
    241115    EdgeIt& first(EdgeIt& i) const {
    242       i=EdgeIt(*this);
    243       return i;
     116      i=EdgeIt(*this); return i;
    244117    }
    245118//     template<typename I> I& first(I& i) const {       
     
    255128//      return gw.getNext(i); }
    256129
    257     NodeIt& next(NodeIt& i) const { graph->next(i); return i; }
    258     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; }
    259     InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; }
    260     EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; }   
     130    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
     131    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
     132    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
     133    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
    261134//    template<typename I> I& next(I &i) const { graph->next(i); return i; }   
    262135    template< typename It > It first() const {
     
    266139      It e; this->first(e, v); return e; }
    267140
    268     Node head(const Edge& e) const { return graph->head(e); }
    269     Node tail(const Edge& e) const { return graph->tail(e); }
     141    Node head(const Edge& e) const {
     142      return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
     143    Node tail(const Edge& e) const {
     144      return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
    270145//    Node tail(const OutEdgeIt& e) const { return graph->tail(Edge(e)); }
    271146
    272     template<typename I> bool valid(const I& i) const {
    273       return graph->valid(i); }
     147    bool valid(const Node& n) const {
     148      return graph->valid(static_cast<typename Graph::Node>(n)); }
     149    bool valid(const Edge& e) const {
     150      return graph->valid(static_cast<typename Graph::Edge>(e)); }
     151//    template<typename I> bool valid(const I& i) const {
     152//      return graph->valid(i); }
    274153 
    275154    //template<typename I> void setInvalid(const I &i);
     
    279158    int edgeNum() const { return graph->edgeNum(); }
    280159 
    281     template<typename I> Node aNode(const I& e) const {
    282       return graph->aNode(e); }
    283     template<typename I> Node bNode(const I& e) const {
    284       return graph->bNode(e); }
    285  
    286     Node addNode() const { return graph->addNode(); }
     160    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
     161    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
     162    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
     163    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
     164//     template<typename I> Node aNode(const I& e) const {
     165//       return Node(graph->aNode(e.e)); }
     166//     template<typename I> Node bNode(const I& e) const {
     167//       return Node(graph->bNode(e.e)); }
     168 
     169    Node addNode() const { return Node(graph->addNode()); }
    287170    Edge addEdge(const Node& tail, const Node& head) const {
    288       return graph->addEdge(tail, head); }
    289  
    290     template<typename I> void erase(const I& i) const { graph->erase(i); }
     171      return Edge(graph->addEdge(tail, head)); }
     172
     173    void erase(const Node& i) const { graph->erase(i); }
     174    void erase(const Edge& i) const { graph->erase(i); }
     175//    template<typename I> void erase(const I& i) const { graph->erase(i); }
    291176 
    292177    void clear() const { graph->clear(); }
     
    298183      NodeMap(const GraphWrapper<Graph>& _G, T a) :
    299184        Graph::NodeMap<T>(*(_G.graph), a) { }
     185//       T operator[](const Node& n) const {
     186//      return Graph::NodeMap<T>::operator[](n);
     187//       }
    300188    };
    301189
     
    430318      edge_filter_map(&_edge_filter_map) { } 
    431319
    432 
    433     typedef typename Graph::Node Node;
    434     class NodeIt : public Graph::NodeIt {
    435 //      typedef typename Graph::NodeIt GraphNodeIt;
    436     public:
     320    typedef typename GraphWrapper<Graph>::Node Node;
     321    class NodeIt {
     322      friend class GraphWrapper<Graph>;
     323      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
     324      typename Graph::NodeIt n;
     325     public:
    437326      NodeIt() { }
    438       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
    439       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
     327      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
     328      NodeIt(const Invalid& i) : n(i) { }
    440329      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
    441         Graph::NodeIt(*(_G.graph)) {
    442         while (_G.graph->valid((*this)/*.GraphNodeIt*/) &&
    443                !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/])
    444           _G.graph->next((*this)/*.GraphNodeIt*/);
     330        n(*(_G.graph)) {
     331        while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
     332          _G.graph->next(n);
    445333      }
     334      operator Node() const { return Node(typename Graph::Node(n)); }
    446335    };
    447     typedef typename Graph::Edge Edge;
    448     class OutEdgeIt : public Graph::OutEdgeIt {
     336//     class NodeIt : public Graph::NodeIt {
     337// //      typedef typename Graph::NodeIt GraphNodeIt;
     338//     public:
     339//       NodeIt() { }
     340//       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
     341//       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
     342//       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
     343//      Graph::NodeIt(*(_G.graph)) {
     344//      while (_G.graph->valid((*this)/*.GraphNodeIt*/) &&
     345//             !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/])
     346//        _G.graph->next((*this)/*.GraphNodeIt*/);
     347//       }
     348//     };
     349    typedef typename GraphWrapper<Graph>::Edge Edge;
     350    class OutEdgeIt {
     351      friend class GraphWrapper<Graph>;
     352      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    449353//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
     354      typename Graph::OutEdgeIt e;
    450355    public:
    451356      OutEdgeIt() { }
    452       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
    453       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
    454       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&
    455                 _G, const Node& n) :
    456         Graph::OutEdgeIt(*(_G.graph), n) {
    457         while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) &&
    458                !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/])
    459           _G.graph->next((*this)/*.GraphOutEdgeIt*/);
     357      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
     358      OutEdgeIt(const Invalid& i) : e(i) { }
     359      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
     360                const Node& _n) :
     361        e(*(_G.graph), typename Graph::Node(_n)) {
     362        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
     363          _G.graph->next(e);
    460364      }
     365      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    461366    };
    462     class InEdgeIt : public Graph::InEdgeIt {
     367    class InEdgeIt {
     368      friend class GraphWrapper<Graph>;
     369      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    463370//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
     371      typename Graph::InEdgeIt e;
    464372    public:
    465373      InEdgeIt() { }
    466       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
    467       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
     374      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
     375      InEdgeIt(const Invalid& i) : e(i) { }
    468376      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
    469                const Node& n) :
    470         Graph::InEdgeIt(*(_G.graph), n) {
    471         while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) &&
    472                !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/])
    473           _G.graph->next((*this)/*.GraphInEdgeIt*/);
     377               const Node& _n) :
     378        e(*(_G.graph), typename Graph::Node(_n)) {
     379        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
     380          _G.graph->next(e);
    474381      }
     382      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    475383    };
    476 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    477     class EdgeIt : public Graph::EdgeIt {
     384    //typedef typename Graph::SymEdgeIt SymEdgeIt;
     385    class EdgeIt {
     386      friend class GraphWrapper<Graph>;
     387      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    478388//      typedef typename Graph::EdgeIt GraphEdgeIt;
     389      typename Graph::EdgeIt e;
    479390    public:
    480391      EdgeIt() { }
    481       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
    482       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
     392      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
     393      EdgeIt(const Invalid& i) : e(i) { }
    483394      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
    484         Graph::EdgeIt(*(_G.graph)) {
    485         while (_G.graph->valid((*this)/*.GraphEdgeIt*/) &&
    486                !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/])
    487           _G.graph->next((*this)/*.GraphEdgeIt*/);
     395        e(*(_G.graph)) {
     396        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
     397          _G.graph->next(e);
    488398      }
     399      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    489400    };
     401//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
     402//     };
     403//     class OutEdgeIt : public Graph::OutEdgeIt {
     404// //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
     405//     public:
     406//       OutEdgeIt() { }
     407//       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
     408//       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
     409//       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&
     410//              _G, const Node& n) :
     411//      Graph::OutEdgeIt(*(_G.graph), n) {
     412//      while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) &&
     413//             !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/])
     414//        _G.graph->next((*this)/*.GraphOutEdgeIt*/);
     415//       }
     416//     };
     417//     class InEdgeIt : public Graph::InEdgeIt {
     418// //      typedef typename Graph::InEdgeIt GraphInEdgeIt;
     419//     public:
     420//       InEdgeIt() { }
     421//       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
     422//       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
     423//       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
     424//             const Node& n) :
     425//      Graph::InEdgeIt(*(_G.graph), n) {
     426//      while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) &&
     427//             !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/])
     428//        _G.graph->next((*this)/*.GraphInEdgeIt*/);
     429//       }
     430//     };
     431// //     //typedef typename Graph::SymEdgeIt SymEdgeIt;
     432//     class EdgeIt : public Graph::EdgeIt {
     433// //      typedef typename Graph::EdgeIt GraphEdgeIt;
     434//     public:
     435//       EdgeIt() { }
     436//       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
     437//       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
     438//       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
     439//      Graph::EdgeIt(*(_G.graph)) {
     440//      while (_G.graph->valid((*this)/*.GraphEdgeIt*/) &&
     441//             !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/])
     442//        _G.graph->next((*this)/*.GraphEdgeIt*/);
     443//       }
     444//     };
    490445   
    491     NodeIt& first(NodeIt& i) const {
    492       i=NodeIt(*this);
    493       return i;
    494     }
    495     OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
    496       i=OutEdgeIt(*this, n);
    497       return i;
    498     }
    499     InEdgeIt& first(InEdgeIt& i, const Node& n) const {
    500       i=InEdgeIt(*this, n);
    501       return i;
    502     }
    503     EdgeIt& first(EdgeIt& i) const {
    504       i=EdgeIt(*this);
    505       return i;
     446
     447    NodeIt& first(NodeIt& i) const {
     448      i=NodeIt(*this); return i;
     449    }
     450    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
     451      i=OutEdgeIt(*this, p); return i;
     452    }
     453    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
     454      i=InEdgeIt(*this, p); return i;
     455    }
     456    EdgeIt& first(EdgeIt& i) const {
     457      i=EdgeIt(*this); return i;
    506458    }
    507459   
     
    520472
    521473    NodeIt& next(NodeIt& i) const {
    522       graph->next(i);
    523       while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); }
     474      graph->next(i.n);
     475      while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); }
    524476      return i;
    525477    }
    526478    OutEdgeIt& next(OutEdgeIt& i) const {
    527       graph->next(i);
    528       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
     479      graph->next(i.e);
     480      while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
    529481      return i;
    530482    }
    531483    InEdgeIt& next(InEdgeIt& i) const {
    532       graph->next(i);
    533       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
     484      graph->next(i.e);
     485      while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
    534486      return i;
    535487    }
    536488    EdgeIt& next(EdgeIt& i) const {
    537       graph->next(i);
    538       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
     489      graph->next(i.e);
     490      while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
    539491      return i;
    540492    }
    541493
     494     
     495    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
     496    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
     497    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
     498    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
     499   
    542500    //template<typename I> I getNext(const I& i) const {
    543501    //  return gw.getNext(i);
     
    556514      It e; this->first(e, v); return e; }
    557515  };
     516
     517//   //Subgraph on the same node-set and partial edge-set
     518//   template<typename Graph, typename NodeFilterMap,
     519//         typename EdgeFilterMap>
     520//   class SubGraphWrapper : public GraphWrapper<Graph> {
     521//   protected:
     522//     NodeFilterMap* node_filter_map;
     523//     EdgeFilterMap* edge_filter_map;
     524//   public:
     525// //     SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
     526//     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
     527//                  EdgeFilterMap& _edge_filter_map) :
     528//       GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
     529//       edge_filter_map(&_edge_filter_map) { } 
     530
     531
     532//     typedef typename Graph::Node Node;
     533//     class NodeIt : public Graph::NodeIt {
     534// //      typedef typename Graph::NodeIt GraphNodeIt;
     535//     public:
     536//       NodeIt() { }
     537//       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
     538//       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
     539//       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
     540//      Graph::NodeIt(*(_G.graph)) {
     541//      while (_G.graph->valid((*this)/*.GraphNodeIt*/) &&
     542//             !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/])
     543//        _G.graph->next((*this)/*.GraphNodeIt*/);
     544//       }
     545//     };
     546//     typedef typename Graph::Edge Edge;
     547//     class OutEdgeIt : public Graph::OutEdgeIt {
     548// //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
     549//     public:
     550//       OutEdgeIt() { }
     551//       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
     552//       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
     553//       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&
     554//              _G, const Node& n) :
     555//      Graph::OutEdgeIt(*(_G.graph), n) {
     556//      while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) &&
     557//             !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/])
     558//        _G.graph->next((*this)/*.GraphOutEdgeIt*/);
     559//       }
     560//     };
     561//     class InEdgeIt : public Graph::InEdgeIt {
     562// //      typedef typename Graph::InEdgeIt GraphInEdgeIt;
     563//     public:
     564//       InEdgeIt() { }
     565//       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
     566//       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
     567//       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
     568//             const Node& n) :
     569//      Graph::InEdgeIt(*(_G.graph), n) {
     570//      while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) &&
     571//             !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/])
     572//        _G.graph->next((*this)/*.GraphInEdgeIt*/);
     573//       }
     574//     };
     575// //     //typedef typename Graph::SymEdgeIt SymEdgeIt;
     576//     class EdgeIt : public Graph::EdgeIt {
     577// //      typedef typename Graph::EdgeIt GraphEdgeIt;
     578//     public:
     579//       EdgeIt() { }
     580//       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
     581//       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
     582//       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
     583//      Graph::EdgeIt(*(_G.graph)) {
     584//      while (_G.graph->valid((*this)/*.GraphEdgeIt*/) &&
     585//             !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/])
     586//        _G.graph->next((*this)/*.GraphEdgeIt*/);
     587//       }
     588//     };
     589   
     590//     NodeIt& first(NodeIt& i) const {
     591//       i=NodeIt(*this);
     592//       return i;
     593//     }
     594//     OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
     595//       i=OutEdgeIt(*this, n);
     596//       return i;
     597//     }
     598//     InEdgeIt& first(InEdgeIt& i, const Node& n) const {
     599//       i=InEdgeIt(*this, n);
     600//       return i;
     601//     }
     602//     EdgeIt& first(EdgeIt& i) const {
     603//       i=EdgeIt(*this);
     604//       return i;
     605//     }
     606   
     607// //     template<typename I> I& first(I& i) const {
     608// //       graph->first(i);
     609// //       //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
     610// //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
     611// //       return i;
     612// //     }
     613// //     template<typename I, typename P> I& first(I& i, const P& p) const {
     614// //       graph->first(i, p);
     615// // //      while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
     616// //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
     617// //       return i;
     618// //     }
     619
     620//     NodeIt& next(NodeIt& i) const {
     621//       graph->next(i);
     622//       while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); }
     623//       return i;
     624//     }
     625//     OutEdgeIt& next(OutEdgeIt& i) const {
     626//       graph->next(i);
     627//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
     628//       return i;
     629//     }
     630//     InEdgeIt& next(InEdgeIt& i) const {
     631//       graph->next(i);
     632//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
     633//       return i;
     634//     }
     635//     EdgeIt& next(EdgeIt& i) const {
     636//       graph->next(i);
     637//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
     638//       return i;
     639//     }
     640
     641//     //template<typename I> I getNext(const I& i) const {
     642//     //  return gw.getNext(i);
     643//     //}
     644// //     template<typename I> I& next(I &i) const {
     645// //       graph->next(i);
     646// // //      while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
     647// //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
     648// //       return i;
     649// //     }
     650   
     651//     template< typename It > It first() const {
     652//       It e; this->first(e); return e; }
     653   
     654//     template< typename It > It first(const Node& v) const {
     655//       It e; this->first(e, v); return e; }
     656//   };
    558657
    559658//   template<typename GraphWrapper>
     
    719818  template<typename Graph>
    720819  class UndirGraphWrapper : public GraphWrapper<Graph> {
    721   protected:
    722     typedef typename Graph::Edge GraphEdge;
    723     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
    724     typedef typename Graph::InEdgeIt GraphInEdgeIt;   
     820//  protected:
     821//    typedef typename Graph::Edge GraphEdge;
     822//    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
     823//    typedef typename Graph::InEdgeIt GraphInEdgeIt;   
    725824  public:
    726825    typedef typename GraphWrapper<Graph>::Node Node;
    727826    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
     827    typedef typename GraphWrapper<Graph>::Edge Edge;
     828    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
    728829
    729830//     UndirGraphWrapper() : GraphWrapper<Graph>() { }
    730831    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
    731832
    732     class Edge {
     833   
     834//     class Edge {
     835//       friend class UndirGraphWrapper<Graph>;
     836//     protected:
     837//       bool out_or_in; //true iff out
     838//       GraphOutEdgeIt out;
     839//       GraphInEdgeIt in;
     840//     public:
     841//       Edge() : out_or_in(), out(), in() { }
     842//       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
     843//       operator GraphEdge() const {
     844//      if (out_or_in) return(out); else return(in);
     845//       }
     846// //FIXME
     847// //2 edges are equal if they "refer" to the same physical edge
     848// //is it good?
     849//       friend bool operator==(const Edge& u, const Edge& v) {
     850//      if (v.out_or_in)
     851//        if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
     852//      //return (u.out_or_in && u.out==v.out);
     853//      else
     854//        if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
     855//      //return (!u.out_or_in && u.in==v.in);
     856//       }
     857//       friend bool operator!=(const Edge& u, const Edge& v) {
     858//      if (v.out_or_in)
     859//        if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);
     860//      //return (!u.out_or_in || u.out!=v.out);
     861//      else
     862//        if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);
     863//      //return (u.out_or_in || u.in!=v.in);
     864//       }
     865//     };
     866
     867    class OutEdgeIt {
    733868      friend class UndirGraphWrapper<Graph>;
    734     protected:
    735869      bool out_or_in; //true iff out
    736       GraphOutEdgeIt out;
    737       GraphInEdgeIt in;
     870      typename Graph::OutEdgeIt out;
     871      typename Graph::InEdgeIt in;
    738872    public:
    739       Edge() : out_or_in(), out(), in() { }
    740       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
    741       operator GraphEdge() const {
    742         if (out_or_in) return(out); else return(in);
    743       }
    744 //FIXME
    745 //2 edges are equal if they "refer" to the same physical edge
    746 //is it good?
    747       friend bool operator==(const Edge& u, const Edge& v) {
    748         if (v.out_or_in)
    749           if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
    750         //return (u.out_or_in && u.out==v.out);
    751         else
    752           if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
    753         //return (!u.out_or_in && u.in==v.in);
     873      OutEdgeIt() { }
     874      OutEdgeIt(const Invalid& i) : Edge(i) { }
     875      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
     876        out_or_in=true; _G.graph->first(out, _n);
     877        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
    754878      }
    755       friend bool operator!=(const Edge& u, const Edge& v) {
    756         if (v.out_or_in)
    757           if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);
    758         //return (!u.out_or_in || u.out!=v.out);
    759         else
    760           if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);
    761         //return (u.out_or_in || u.in!=v.in);
    762       }
    763     };
    764 
    765     class OutEdgeIt : public Edge {
    766       friend class UndirGraphWrapper<Graph>;
    767     public:
    768       OutEdgeIt() : Edge() { }
    769       OutEdgeIt(const Invalid& i) : Edge(i) { }
    770       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n)
    771         : Edge() {
    772         out_or_in=true; _G.graph->first(out, n);
    773         if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); }
     879      operator Edge() const {
     880        if (out_or_in) return Edge(out); else return Edge(in);
    774881      }
    775882    };
    776 
     883//     class OutEdgeIt : public Edge {
     884//       friend class UndirGraphWrapper<Graph>;
     885//     public:
     886//       OutEdgeIt() : Edge() { }
     887//       OutEdgeIt(const Invalid& i) : Edge(i) { }
     888//       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n)
     889//      : Edge() {
     890//      out_or_in=true; _G.graph->first(out, n);
     891//      if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); }
     892//       }
     893//     };
     894
     895//FIXME InEdgeIt
    777896    typedef OutEdgeIt InEdgeIt;
    778897
    779     class EdgeIt : public Edge {
    780       friend class UndirGraphWrapper<Graph>;
    781     protected:
    782       NodeIt v;
    783     public:
    784       EdgeIt() : Edge() { }
    785       EdgeIt(const Invalid& i) : Edge(i) { }
    786       EdgeIt(const UndirGraphWrapper<Graph>& _G)
    787         : Edge() {
    788         out_or_in=true;
    789         //Node v;
    790         _G.first(v);
    791         if (_G.valid(v)) _G.graph->first(out); else out=INVALID;
    792         while (_G.valid(v) && !_G.graph->valid(out)) {
    793           _G.graph->next(v);
    794           if (_G.valid(v)) _G.graph->first(out);
    795         }
    796       }
    797     };
    798 
    799     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
    800       e.out_or_in=true; graph->first(e.out, n);
    801       if (!(graph->valid(e.out))) { e.out_or_in=false; graph->first(e.in, n); }
    802       return e;
    803     }
    804 
    805     EdgeIt& first(EdgeIt& e) const {
    806       e.out_or_in=true;
    807       //NodeIt v;
    808       first(e.v);
    809       if (valid(e.v)) graph->first(e.out, e.v); else e.out=INVALID;
    810       while (valid(e.v) && !graph->valid(e.out)) {
    811         graph->next(e.v);
    812         if (valid(e.v)) graph->first(e.out, e.v);
    813       }
    814       return e;
     898//     class EdgeIt : public Edge {
     899//       friend class UndirGraphWrapper<Graph>;
     900//     protected:
     901//       NodeIt v;
     902//     public:
     903//       EdgeIt() : Edge() { }
     904//       EdgeIt(const Invalid& i) : Edge(i) { }
     905//       EdgeIt(const UndirGraphWrapper<Graph>& _G)
     906//      : Edge() {
     907//      out_or_in=true;
     908//      //Node v;
     909//      _G.first(v);
     910//      if (_G.valid(v)) _G.graph->first(out); else out=INVALID;
     911//      while (_G.valid(v) && !_G.graph->valid(out)) {
     912//        _G.graph->next(v);
     913//        if (_G.valid(v)) _G.graph->first(out);
     914//      }
     915//       }
     916//     };
     917
     918    NodeIt& first(NodeIt& i) const {
     919      i=NodeIt(*this); return i;
     920    }
     921    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
     922      i=OutEdgeIt(*this, p); return i;
     923    }
     924//FIXME
     925//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
     926//       i=InEdgeIt(*this, p); return i;
     927//     }
     928    EdgeIt& first(EdgeIt& i) const {
     929      i=EdgeIt(*this); return i;
    815930    }
    816931
     
    819934      graph->first(i, p); return i; }
    820935
     936    NodeIt& next(NodeIt& n) const {
     937      GraphWrapper<Graph>::next(n);
     938      return n;
     939    }
    821940    OutEdgeIt& next(OutEdgeIt& e) const {
    822941      if (e.out_or_in) {
    823         Node n=graph->tail(e.out);
     942        typename Graph::Node n=graph->tail(e.out);
    824943        graph->next(e.out);
    825944        if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
     
    829948      return e;
    830949    }
    831 
     950    //FIXME InEdgeIt
    832951    EdgeIt& next(EdgeIt& e) const {
    833       //NodeIt v=tail(e);
    834       graph->next(e.out);
    835       while (valid(e.v) && !graph->valid(e.out)) {
    836         next(e.v);
    837         if (valid(e.v)) graph->first(e.out, e.v);
    838       }
     952      GraphWrapper<Graph>::next(n);
     953//      graph->next(e.e);
    839954      return e;
    840955    }
    841956
    842     template<typename I> I& next(I &i) const { graph->next(i); return i; }   
     957//    template<typename I> I& next(I &i) const { graph->next(i); return i; }   
    843958//    template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
    844959
     
    9691084
    9701085
     1086 
     1087
    9711088  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    9721089  class ResGraphWrapper : public GraphWrapper<Graph> {
    9731090  protected:
    974     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
    975     typedef typename Graph::InEdgeIt GraphInEdgeIt;
    976     typedef typename Graph::Edge GraphEdge;
     1091//    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
     1092//    typedef typename Graph::InEdgeIt GraphInEdgeIt;
     1093//    typedef typename Graph::Edge GraphEdge;
    9771094    FlowMap* flow;
    9781095    const CapacityMap* capacity;
     
    9901107    typedef typename GraphWrapper<Graph>::Node Node;
    9911108    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    992     class Edge {
     1109    class Edge : public Graph::Edge {
    9931110      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
    9941111    protected:
    995       bool out_or_in; //true, iff out
    996       GraphOutEdgeIt out;
    997       GraphInEdgeIt in;
     1112      bool forward; //true, iff forward
     1113//      typename Graph::Edge e;
    9981114    public:
    999       Edge() : out_or_in(true) { }
    1000       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
    1001 //       bool valid() const {
    1002 //      return out_or_in && out.valid() || in.valid(); }
     1115      Edge() { }
     1116      Edge(const typename Graph::Edge& _e, bool _forward) :
     1117        Graph::Edge(_e), forward(_forward) { }
     1118      Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
     1119//the unique invalid iterator
    10031120      friend bool operator==(const Edge& u, const Edge& v) {
    1004         if (v.out_or_in)
    1005           return (u.out_or_in && u.out==v.out);
    1006         else
    1007           return (!u.out_or_in && u.in==v.in);
     1121        return (v.forward==u.forward &&
     1122                static_cast<typename Graph::Edge>(u)==
     1123                static_cast<typename Graph::Edge>(v));
    10081124      }
    10091125      friend bool operator!=(const Edge& u, const Edge& v) {
    1010         if (v.out_or_in)
    1011           return (!u.out_or_in || u.out!=v.out);
    1012         else
    1013           return (u.out_or_in || u.in!=v.in);
     1126        return (v.forward!=u.forward ||
     1127                static_cast<typename Graph::Edge>(u)!=
     1128                static_cast<typename Graph::Edge>(v));
    10141129      }
    1015       operator GraphEdge() const {
    1016         if (out_or_in) return(out); else return(in);
    1017       }
    10181130    };
    1019     class OutEdgeIt : public Edge {
     1131//     class Edge {
     1132//       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     1133//     protected:
     1134//       bool out_or_in; //true, iff out
     1135//       GraphOutEdgeIt out;
     1136//       GraphInEdgeIt in;
     1137//     public:
     1138//       Edge() : out_or_in(true) { }
     1139//       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
     1140// //       bool valid() const {
     1141// //   return out_or_in && out.valid() || in.valid(); }
     1142//       friend bool operator==(const Edge& u, const Edge& v) {
     1143//      if (v.out_or_in)
     1144//        return (u.out_or_in && u.out==v.out);
     1145//      else
     1146//        return (!u.out_or_in && u.in==v.in);
     1147//       }
     1148//       friend bool operator!=(const Edge& u, const Edge& v) {
     1149//      if (v.out_or_in)
     1150//        return (!u.out_or_in || u.out!=v.out);
     1151//      else
     1152//        return (u.out_or_in || u.in!=v.in);
     1153//       }
     1154//       operator GraphEdge() const {
     1155//      if (out_or_in) return(out); else return(in);
     1156//       }
     1157//     };
     1158    class OutEdgeIt {
    10201159      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     1160    protected:
     1161      typename Graph::OutEdgeIt out;
     1162      typename Graph::InEdgeIt in;
     1163      bool forward;
    10211164    public:
    10221165      OutEdgeIt() { }
    10231166      //FIXME
    1024       OutEdgeIt(const Edge& e) : Edge(e) { }
    1025       OutEdgeIt(const Invalid& i) : Edge(i) { }
    1026       OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
     1167//      OutEdgeIt(const Edge& e) : Edge(e) { }
     1168      OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
     1169//the unique invalid iterator
     1170      OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) {
     1171        forward=true;
    10271172        resG.graph->first(out, v);
    1028         while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
     1173        while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
    10291174        if (!resG.graph->valid(out)) {
    1030           out_or_in=0;
     1175          forward=false;
    10311176          resG.graph->first(in, v);
    1032           while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
     1177          while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
    10331178        }
    10341179      }
     1180      operator Edge() const {
     1181//      Edge e;
     1182//      e.forward=this->forward;
     1183//      if (this->forward) e=out; else e=in;
     1184//      return e;
     1185        if (this->forward)
     1186          return Edge(out, this->forward);
     1187        else
     1188          return Edge(in, this->forward);
     1189      }
     1190    };
     1191//     class OutEdgeIt : public Edge {
     1192//       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     1193//     public:
     1194//       OutEdgeIt() { }
     1195//       //FIXME
     1196//       OutEdgeIt(const Edge& e) : Edge(e) { }
     1197//       OutEdgeIt(const Invalid& i) : Edge(i) { }
     1198//       OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
     1199//      resG.graph->first(out, v);
     1200//      while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
     1201//      if (!resG.graph->valid(out)) {
     1202//        out_or_in=0;
     1203//        resG.graph->first(in, v);
     1204//        while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
     1205//      }
     1206//       }
    10351207//     public:
    10361208//       OutEdgeIt& operator++() {
     
    10501222//      return *this;
    10511223//       }
    1052     };
     1224//    };
    10531225
    10541226    //FIXME This is just for having InEdgeIt
    10551227//    class InEdgeIt : public Edge { };
    10561228
    1057     class EdgeIt : public Edge {
     1229    class InEdgeIt {
    10581230      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
    1059       NodeIt v;
     1231    protected:
     1232      typename Graph::OutEdgeIt out;
     1233      typename Graph::InEdgeIt in;
     1234      bool forward;
     1235    public:
     1236      InEdgeIt() { }
     1237      //FIXME
     1238//      OutEdgeIt(const Edge& e) : Edge(e) { }
     1239      InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
     1240//the unique invalid iterator
     1241      InEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) {
     1242        forward=true;
     1243        resG.graph->first(in, v);
     1244        while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
     1245        if (!resG.graph->valid(in)) {
     1246          forward=false;
     1247          resG.graph->first(out, v);
     1248          while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
     1249        }
     1250      }
     1251      operator Edge() const {
     1252//      Edge e;
     1253//      e.forward=this->forward;
     1254//      if (this->forward) e=out; else e=in;
     1255//      return e;
     1256        if (this->forward)
     1257          return Edge(in, this->forward);
     1258        else
     1259          return Edge(out, this->forward);
     1260      }
     1261    };
     1262
     1263    class EdgeIt {
     1264      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     1265    protected:
     1266      typename Graph::EdgeIt e;
     1267      bool forward;
    10601268    public:
    10611269      EdgeIt() { }
    1062       //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
    1063       EdgeIt(const Invalid& i) : Edge(i) { }
    1064       EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
    1065         resG.graph->first(v);
    1066         if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
    1067         while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
    1068         while (resG.graph->valid(v) && !resG.graph->valid(out)) {
    1069           resG.graph->next(v);
    1070           if (resG.graph->valid(v)) resG.graph->first(out, v);
    1071           while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
    1072         }
    1073         if (!resG.graph->valid(out)) {
    1074           out_or_in=0;
    1075           resG.graph->first(v);
    1076           if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
    1077           while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
    1078           while (resG.graph->valid(v) && !resG.graph->valid(in)) {
    1079             resG.graph->next(v);
    1080             if (resG.graph->valid(v)) resG.graph->first(in, v);
    1081             while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
    1082           }
     1270      EdgeIt(const Invalid& i) : e(i), forward(false) { }
     1271      EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) {
     1272        forward=true;
     1273        resG.graph->first(e);
     1274        while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
     1275        if (!resG.graph->valid(e)) {
     1276          forward=false;
     1277          resG.graph->first(e);
     1278          while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
    10831279        }
    10841280      }
     1281      operator Edge() const {
     1282        return Edge(e, this->forward);
     1283      }
     1284    };
     1285//     class EdgeIt : public Edge {
     1286//       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     1287//       NodeIt v;
     1288//     public:
     1289//       EdgeIt() { }
     1290//       //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
     1291//       EdgeIt(const Invalid& i) : Edge(i) { }
     1292//       EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
     1293//      resG.graph->first(v);
     1294//      if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
     1295//      while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
     1296//      while (resG.graph->valid(v) && !resG.graph->valid(out)) {
     1297//        resG.graph->next(v);
     1298//        if (resG.graph->valid(v)) resG.graph->first(out, v);
     1299//        while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
     1300//      }
     1301//      if (!resG.graph->valid(out)) {
     1302//        out_or_in=0;
     1303//        resG.graph->first(v);
     1304//        if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
     1305//        while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
     1306//        while (resG.graph->valid(v) && !resG.graph->valid(in)) {
     1307//          resG.graph->next(v);
     1308//          if (resG.graph->valid(v)) resG.graph->first(in, v);
     1309//          while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
     1310//        }
     1311//      }
     1312//       }
    10851313//       EdgeIt& operator++() {
    10861314//      if (out_or_in) {
     
    11141342//      return *this;
    11151343//       }
    1116     };
     1344//    };
    11171345
    11181346    NodeIt& first(NodeIt& i) const {
    1119       i=NodeIt(*this);
    1120       return i;
     1347      i=NodeIt(*this); return i;
    11211348    }
    11221349    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    1123       i=OutEdgeIt(*this, p);
    1124       return i;
    1125     }
    1126     //FIXME Not yet implemented
    1127     //InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    1128     //i=InEdgeIt(*this, p);
    1129     //  return i;
    1130     //}
    1131     EdgeIt& first(EdgeIt& e) const {
    1132       e=EdgeIt(*this);
    1133       return e;
     1350      i=OutEdgeIt(*this, p); return i;
     1351    }
     1352//    FIXME not tested
     1353    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
     1354      i=InEdgeIt(*this, p); return i;
     1355    }
     1356    EdgeIt& first(EdgeIt& i) const {
     1357      i=EdgeIt(*this); return i;
    11341358    }
    11351359   
    1136     NodeIt& next(NodeIt& n) const { graph->next(n); return n; }
     1360    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
    11371361    OutEdgeIt& next(OutEdgeIt& e) const {
    1138       if (e.out_or_in) {
     1362      if (e.forward) {
    11391363        Node v=graph->aNode(e.out);
    11401364        graph->next(e.out);
    1141         while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
     1365        while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
    11421366        if (!graph->valid(e.out)) {
    1143           e.out_or_in=0;
     1367          e.forward=false;
    11441368          graph->first(e.in, v);
    1145           while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
     1369          while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
    11461370        }
    11471371      } else {
    11481372        graph->next(e.in);
    1149         while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
     1373        while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
    11501374      }
    11511375      return e;
    11521376    }
    1153     //FIXME Not yet implemented
    1154     //InEdgeIt& next(InEdgeIt& e) const {
    1155     //  return e;
    1156     //}
    1157     EdgeIt& next(EdgeIt& e) const {
    1158       if (e.out_or_in) {
     1377//     FIXME Not tested
     1378    InEdgeIt& next(InEdgeIt& e) const {
     1379      if (e.forward) {
     1380        Node v=graph->aNode(e.in);
     1381        graph->next(e.in);
     1382        while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
     1383        if (!graph->valid(e.in)) {
     1384          e.forward=false;
     1385          graph->first(e.out, v);
     1386          while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
     1387        }
     1388      } else {
    11591389        graph->next(e.out);
    1160         while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
    1161           while (graph->valid(e.v) && !graph->valid(e.out)) {
    1162             graph->next(e.v);
    1163             if (graph->valid(e.v)) graph->first(e.out, e.v);
    1164             while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
    1165           }
    1166           if (!graph->valid(e.out)) {
    1167             e.out_or_in=0;
    1168             graph->first(e.v);
    1169             if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
    1170             while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
    1171             while (graph->valid(e.v) && !graph->valid(e.in)) {
    1172               graph->next(e.v);
    1173               if (graph->valid(e.v)) graph->first(e.in, e.v);
    1174               while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
    1175             } 
    1176           }
    1177         } else {
    1178           graph->next(e.in);
    1179           while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
    1180           while (graph->valid(e.v) && !graph->valid(e.in)) {
    1181             graph->next(e.v);
    1182             if (graph->valid(e.v)) graph->first(e.in, e.v);
    1183             while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
    1184           }
     1390        while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
     1391      }
     1392      return e;
     1393    }
     1394    EdgeIt& next(EdgeIt& e) const {
     1395      if (e.forward) {
     1396        graph->next(e.e);
     1397        while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
     1398        if (!graph->valid(e.e)) {
     1399          e.forward=false;
     1400          graph->first(e.e);
     1401          while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
    11851402        }
    1186         return e;
     1403      } else {
     1404        graph->next(e.e);
     1405        while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
    11871406      }
     1407      return e;
     1408    }
     1409//     EdgeIt& next(EdgeIt& e) const {
     1410//       if (e.out_or_in) {
     1411//      graph->next(e.out);
     1412//      while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
     1413//        while (graph->valid(e.v) && !graph->valid(e.out)) {
     1414//          graph->next(e.v);
     1415//          if (graph->valid(e.v)) graph->first(e.out, e.v);
     1416//          while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
     1417//        }
     1418//        if (!graph->valid(e.out)) {
     1419//          e.out_or_in=0;
     1420//          graph->first(e.v);
     1421//          if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
     1422//          while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
     1423//          while (graph->valid(e.v) && !graph->valid(e.in)) {
     1424//            graph->next(e.v);
     1425//            if (graph->valid(e.v)) graph->first(e.in, e.v);
     1426//            while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
     1427//          } 
     1428//        }
     1429//      } else {
     1430//        graph->next(e.in);
     1431//        while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
     1432//        while (graph->valid(e.v) && !graph->valid(e.in)) {
     1433//          graph->next(e.v);
     1434//          if (graph->valid(e.v)) graph->first(e.in, e.v);
     1435//          while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
     1436//        }
     1437//      }
     1438//      return e;
     1439//       }
    11881440   
    11891441
     
    12031455
    12041456    Node tail(Edge e) const {
    1205       return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
     1457      return ((e.forward) ? graph->tail(e) : graph->head(e)); }
    12061458    Node head(Edge e) const {
    1207       return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
     1459      return ((e.forward) ? graph->head(e) : graph->tail(e)); }
    12081460
    12091461    Node aNode(OutEdgeIt e) const {
    1210       return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
     1462      return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); }
    12111463    Node bNode(OutEdgeIt e) const {
    1212       return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
     1464      return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); }
    12131465
    12141466    int nodeNum() const { return graph->nodeNum(); }
     
    12171469
    12181470
    1219     int id(Node v) const { return graph->id(v); }
    1220 
    1221     bool valid(Node n) const { return graph->valid(n); }
     1471//    int id(Node v) const { return graph->id(v); }
     1472
     1473    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
    12221474    bool valid(Edge e) const {
    1223       return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
     1475      return graph->valid(e);
     1476        //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
     1477    }
    12241478
    12251479    void augment(const Edge& e, Number a) const {
    1226       if (e.out_or_in
     1480      if (e.forward
    12271481//      flow->set(e.out, flow->get(e.out)+a);
    1228         flow->set(e.out, (*flow)[e.out]+a);
     1482        flow->set(e, (*flow)[e]+a);
    12291483      else 
    12301484//      flow->set(e.in, flow->get(e.in)-a);
    1231         flow->set(e.in, (*flow)[e.in]-a);
     1485        flow->set(e, (*flow)[e]-a);
    12321486    }
    12331487
    12341488    Number resCap(const Edge& e) const {
    1235       if (e.out_or_in)
     1489      if (e.forward)
    12361490//      return (capacity->get(e.out)-flow->get(e.out));
    1237         return ((*capacity)[e.out]-(*flow)[e.out]);
     1491        return ((*capacity)[e]-(*flow)[e]);
    12381492      else
    12391493//      return (flow->get(e.in));
    1240         return ((*flow)[e.in]);
    1241     }
    1242 
    1243     Number resCap(GraphOutEdgeIt out) const {
    1244 //      return (capacity->get(out)-flow->get(out));
    1245       return ((*capacity)[out]-(*flow)[out]);
    1246     }
    1247    
    1248     Number resCap(GraphInEdgeIt in) const {
    1249 //      return (flow->get(in));
    1250       return ((*flow)[in]);
    1251     }
     1494        return ((*flow)[e]);
     1495    }
     1496
     1497//     Number resCap(typename Graph::OutEdgeIt out) const {
     1498// //      return (capacity->get(out)-flow->get(out));
     1499//       return ((*capacity)[out]-(*flow)[out]);
     1500//     }
     1501   
     1502//     Number resCap(typename Graph::InEdgeIt in) const {
     1503// //      return (flow->get(in));
     1504//       return ((*flow)[in]);
     1505//     }
    12521506
    12531507//     template<typename T> class NodeMap : public Graph::NodeMap<T> {
     
    12761530      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
    12771531      void set(Edge e, T a) {
    1278         if (e.out_or_in)
     1532        if (e.forward)
    12791533          forward_map.set(e.out, a);
    12801534        else
     
    12821536      }
    12831537      T operator[](Edge e) const {
    1284         if (e.out_or_in)
     1538        if (e.forward)
    12851539          return forward_map[e.out];
    12861540        else
     
    12961550  };
    12971551
     1552 
     1553
     1554//   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     1555//   class ResGraphWrapper : public GraphWrapper<Graph> {
     1556//   protected:
     1557//     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
     1558//     typedef typename Graph::InEdgeIt GraphInEdgeIt;
     1559//     typedef typename Graph::Edge GraphEdge;
     1560//     FlowMap* flow;
     1561//     const CapacityMap* capacity;
     1562//   public:
     1563
     1564//     ResGraphWrapper(Graph& _graph, FlowMap& _flow,
     1565//                  const CapacityMap& _capacity) :
     1566//       GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }
     1567
     1568//     class Edge;
     1569//     class OutEdgeIt;
     1570//     friend class Edge;
     1571//     friend class OutEdgeIt;
     1572
     1573//     typedef typename GraphWrapper<Graph>::Node Node;
     1574//     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
     1575//     class Edge {
     1576//       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     1577//     protected:
     1578//       bool out_or_in; //true, iff out
     1579//       GraphOutEdgeIt out;
     1580//       GraphInEdgeIt in;
     1581//     public:
     1582//       Edge() : out_or_in(true) { }
     1583//       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
     1584// //       bool valid() const {
     1585// //   return out_or_in && out.valid() || in.valid(); }
     1586//       friend bool operator==(const Edge& u, const Edge& v) {
     1587//      if (v.out_or_in)
     1588//        return (u.out_or_in && u.out==v.out);
     1589//      else
     1590//        return (!u.out_or_in && u.in==v.in);
     1591//       }
     1592//       friend bool operator!=(const Edge& u, const Edge& v) {
     1593//      if (v.out_or_in)
     1594//        return (!u.out_or_in || u.out!=v.out);
     1595//      else
     1596//        return (u.out_or_in || u.in!=v.in);
     1597//       }
     1598//       operator GraphEdge() const {
     1599//      if (out_or_in) return(out); else return(in);
     1600//       }
     1601//     };
     1602//     class OutEdgeIt : public Edge {
     1603//       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     1604//     public:
     1605//       OutEdgeIt() { }
     1606//       //FIXME
     1607//       OutEdgeIt(const Edge& e) : Edge(e) { }
     1608//       OutEdgeIt(const Invalid& i) : Edge(i) { }
     1609//       OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
     1610//      resG.graph->first(out, v);
     1611//      while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
     1612//      if (!resG.graph->valid(out)) {
     1613//        out_or_in=0;
     1614//        resG.graph->first(in, v);
     1615//        while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
     1616//      }
     1617//       }
     1618// //     public:
     1619// //       OutEdgeIt& operator++() {
     1620// //   if (out_or_in) {
     1621// //     Node v=/*resG->*/G->aNode(out);
     1622// //     ++out;
     1623// //     while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
     1624// //     if (!out.valid()) {
     1625// //       out_or_in=0;
     1626// //       G->first(in, v);
     1627// //       while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
     1628// //     }
     1629// //   } else {
     1630// //     ++in;
     1631// //     while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
     1632// //   }
     1633// //   return *this;
     1634// //       }
     1635//     };
     1636
     1637//     //FIXME This is just for having InEdgeIt
     1638// //    class InEdgeIt : public Edge { };
     1639
     1640//     class EdgeIt : public Edge {
     1641//       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     1642//       NodeIt v;
     1643//     public:
     1644//       EdgeIt() { }
     1645//       //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
     1646//       EdgeIt(const Invalid& i) : Edge(i) { }
     1647//       EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
     1648//      resG.graph->first(v);
     1649//      if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
     1650//      while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
     1651//      while (resG.graph->valid(v) && !resG.graph->valid(out)) {
     1652//        resG.graph->next(v);
     1653//        if (resG.graph->valid(v)) resG.graph->first(out, v);
     1654//        while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
     1655//      }
     1656//      if (!resG.graph->valid(out)) {
     1657//        out_or_in=0;
     1658//        resG.graph->first(v);
     1659//        if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
     1660//        while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
     1661//        while (resG.graph->valid(v) && !resG.graph->valid(in)) {
     1662//          resG.graph->next(v);
     1663//          if (resG.graph->valid(v)) resG.graph->first(in, v);
     1664//          while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
     1665//        }
     1666//      }
     1667//       }
     1668// //       EdgeIt& operator++() {
     1669// //   if (out_or_in) {
     1670// //     ++out;
     1671// //     while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
     1672// //     while (v.valid() && !out.valid()) {
     1673// //       ++v;
     1674// //       if (v.valid()) G->first(out, v);
     1675// //       while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
     1676// //     }
     1677// //     if (!out.valid()) {
     1678// //       out_or_in=0;
     1679// //       G->first(v);
     1680// //       if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();
     1681// //       while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
     1682// //       while (v.valid() && !in.valid()) {
     1683// //         ++v;
     1684// //         if (v.valid()) G->first(in, v);
     1685// //         while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
     1686// //       } 
     1687// //     }
     1688// //   } else {
     1689// //     ++in;
     1690// //     while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
     1691// //     while (v.valid() && !in.valid()) {
     1692// //       ++v;
     1693// //       if (v.valid()) G->first(in, v);
     1694// //       while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
     1695// //     }
     1696// //   }
     1697// //   return *this;
     1698// //       }
     1699//     };
     1700
     1701//     NodeIt& first(NodeIt& i) const {
     1702//       i=NodeIt(*this);
     1703//       return i;
     1704//     }
     1705//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
     1706//       i=OutEdgeIt(*this, p);
     1707//       return i;
     1708//     }
     1709//     //FIXME Not yet implemented
     1710//     //InEdgeIt& first(InEdgeIt& i, const Node& p) const {
     1711//     //i=InEdgeIt(*this, p);
     1712//     //  return i;
     1713//     //}
     1714//     EdgeIt& first(EdgeIt& e) const {
     1715//       e=EdgeIt(*this);
     1716//       return e;
     1717//     }
     1718   
     1719//     NodeIt& next(NodeIt& n) const { graph->next(n); return n; }
     1720//     OutEdgeIt& next(OutEdgeIt& e) const {
     1721//       if (e.out_or_in) {
     1722//      Node v=graph->aNode(e.out);
     1723//      graph->next(e.out);
     1724//      while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
     1725//      if (!graph->valid(e.out)) {
     1726//        e.out_or_in=0;
     1727//        graph->first(e.in, v);
     1728//        while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
     1729//      }
     1730//       } else {
     1731//      graph->next(e.in);
     1732//      while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
     1733//       }
     1734//       return e;
     1735//     }
     1736//     //FIXME Not yet implemented
     1737//     //InEdgeIt& next(InEdgeIt& e) const {
     1738//     //  return e;
     1739//     //}
     1740//     EdgeIt& next(EdgeIt& e) const {
     1741//       if (e.out_or_in) {
     1742//      graph->next(e.out);
     1743//      while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
     1744//        while (graph->valid(e.v) && !graph->valid(e.out)) {
     1745//          graph->next(e.v);
     1746//          if (graph->valid(e.v)) graph->first(e.out, e.v);
     1747//          while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
     1748//        }
     1749//        if (!graph->valid(e.out)) {
     1750//          e.out_or_in=0;
     1751//          graph->first(e.v);
     1752//          if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
     1753//          while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
     1754//          while (graph->valid(e.v) && !graph->valid(e.in)) {
     1755//            graph->next(e.v);
     1756//            if (graph->valid(e.v)) graph->first(e.in, e.v);
     1757//            while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
     1758//          } 
     1759//        }
     1760//      } else {
     1761//        graph->next(e.in);
     1762//        while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
     1763//        while (graph->valid(e.v) && !graph->valid(e.in)) {
     1764//          graph->next(e.v);
     1765//          if (graph->valid(e.v)) graph->first(e.in, e.v);
     1766//          while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
     1767//        }
     1768//      }
     1769//      return e;
     1770//       }
     1771   
     1772
     1773//     template< typename It >
     1774//     It first() const {
     1775//       It e;
     1776//       first(e);
     1777//       return e;
     1778//     }
     1779
     1780//     template< typename It >
     1781//     It first(Node v) const {
     1782//       It e;
     1783//       first(e, v);
     1784//       return e;
     1785//     }
     1786
     1787//     Node tail(Edge e) const {
     1788//       return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
     1789//     Node head(Edge e) const {
     1790//       return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
     1791
     1792//     Node aNode(OutEdgeIt e) const {
     1793//       return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
     1794//     Node bNode(OutEdgeIt e) const {
     1795//       return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
     1796
     1797//     int nodeNum() const { return graph->nodeNum(); }
     1798//     //FIXME
     1799//     //int edgeNum() const { return graph->edgeNum(); }
     1800
     1801
     1802//     int id(Node v) const { return graph->id(v); }
     1803
     1804//     bool valid(Node n) const { return graph->valid(n); }
     1805//     bool valid(Edge e) const {
     1806//       return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
     1807
     1808//     void augment(const Edge& e, Number a) const {
     1809//       if (e.out_or_in) 
     1810// //   flow->set(e.out, flow->get(e.out)+a);
     1811//      flow->set(e.out, (*flow)[e.out]+a);
     1812//       else 
     1813// //   flow->set(e.in, flow->get(e.in)-a);
     1814//      flow->set(e.in, (*flow)[e.in]-a);
     1815//     }
     1816
     1817//     Number resCap(const Edge& e) const {
     1818//       if (e.out_or_in)
     1819// //   return (capacity->get(e.out)-flow->get(e.out));
     1820//      return ((*capacity)[e.out]-(*flow)[e.out]);
     1821//       else
     1822// //   return (flow->get(e.in));
     1823//      return ((*flow)[e.in]);
     1824//     }
     1825
     1826//     Number resCap(GraphOutEdgeIt out) const {
     1827// //      return (capacity->get(out)-flow->get(out));
     1828//       return ((*capacity)[out]-(*flow)[out]);
     1829//     }
     1830   
     1831//     Number resCap(GraphInEdgeIt in) const {
     1832// //      return (flow->get(in));
     1833//       return ((*flow)[in]);
     1834//     }
     1835
     1836// //     template<typename T> class NodeMap : public Graph::NodeMap<T> {
     1837// //     public:
     1838// //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
     1839// //   : Graph::NodeMap<T>(_G.gw) { }
     1840// //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
     1841// //         T a) : Graph::NodeMap<T>(_G.gw, a) { }
     1842// //     };
     1843
     1844// //     template <typename T>
     1845// //     class NodeMap {
     1846// //       typename Graph::NodeMap<T> node_map;
     1847// //     public:
     1848// //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
     1849// //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
     1850// //       void set(Node nit, T a) { node_map.set(nit, a); }
     1851// //       T get(Node nit) const { return node_map.get(nit); }
     1852// //     };
     1853
     1854//     template <typename T>
     1855//     class EdgeMap {
     1856//       typename Graph::EdgeMap<T> forward_map, backward_map;
     1857//     public:
     1858//       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
     1859//       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
     1860//       void set(Edge e, T a) {
     1861//      if (e.out_or_in)
     1862//        forward_map.set(e.out, a);
     1863//      else
     1864//        backward_map.set(e.in, a);
     1865//       }
     1866//       T operator[](Edge e) const {
     1867//      if (e.out_or_in)
     1868//        return forward_map[e.out];
     1869//      else
     1870//        return backward_map[e.in];
     1871//       }
     1872// //       T get(Edge e) const {
     1873// //   if (e.out_or_in)
     1874// //     return forward_map.get(e.out);
     1875// //   else
     1876// //     return backward_map.get(e.in);
     1877// //       }
     1878//     };
     1879//   };
     1880
     1881
    12981882  //ErasingFirstGraphWrapper for blocking flows
    12991883  template<typename Graph, typename FirstOutEdgesMap>
     
    13061890      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
    13071891
    1308     typedef typename Graph::Node Node;
    1309     class NodeIt : public Graph::NodeIt {
    1310     public:
     1892    typedef typename GraphWrapper<Graph>::Node Node;
     1893    class NodeIt {
     1894      friend class GraphWrapper<Graph>;
     1895      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
     1896      typename Graph::NodeIt n;
     1897     public:
    13111898      NodeIt() { }
    1312       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
    1313       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
     1899      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
     1900      NodeIt(const Invalid& i) : n(i) { }
    13141901      NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
    1315         Graph::NodeIt(*(_G.graph)) { }
     1902        n(*(_G.graph)) { }
     1903      operator Node() const { return Node(typename Graph::Node(n)); }
    13161904    };
    1317     typedef typename Graph::Edge Edge;
    1318     class OutEdgeIt : public Graph::OutEdgeIt {
     1905    typedef typename GraphWrapper<Graph>::Edge Edge;
     1906    class OutEdgeIt {
     1907      friend class GraphWrapper<Graph>;
     1908      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
     1909//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
     1910      typename Graph::OutEdgeIt e;
    13191911    public:
    13201912      OutEdgeIt() { }
    1321       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
    1322       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
     1913      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
     1914      OutEdgeIt(const Invalid& i) : e(i) { }
    13231915      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
    1324                 const Node& n) :
    1325         Graph::OutEdgeIt((*_G.first_out_edges)[n]) { }
     1916                const Node& _n) :
     1917        e((*_G.first_out_edges)[_n]) { }
     1918      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    13261919    };
    1327     class InEdgeIt : public Graph::InEdgeIt {
     1920    class InEdgeIt {
     1921      friend class GraphWrapper<Graph>;
     1922      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
     1923//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
     1924      typename Graph::InEdgeIt e;
    13281925    public:
    13291926      InEdgeIt() { }
    1330       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
    1331       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
     1927      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
     1928      InEdgeIt(const Invalid& i) : e(i) { }
    13321929      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
    1333                const Node& n) :
    1334         Graph::InEdgeIt(*(_G.graph), n) { }
     1930               const Node& _n) :
     1931        e(*(_G.graph), typename Graph::Node(_n)) { }
     1932      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    13351933    };
    13361934    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    1337     class EdgeIt : public Graph::EdgeIt {
     1935    class EdgeIt {
     1936      friend class GraphWrapper<Graph>;
     1937      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
     1938//      typedef typename Graph::EdgeIt GraphEdgeIt;
     1939      typename Graph::EdgeIt e;
    13381940    public:
    13391941      EdgeIt() { }
    1340       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
    1341       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
     1942      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
     1943      EdgeIt(const Invalid& i) : e(i) { }
    13421944      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
    1343         Graph::EdgeIt(*(_G.graph)) { }
     1945        e(*(_G.graph)) { }
     1946      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    13441947    };
    13451948
    1346     NodeIt& first(NodeIt& i) const {
    1347       i=NodeIt(*this);
    1348       return i;
    1349     }
    1350     OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
    1351       i=OutEdgeIt(*this, n);
    1352 //      i=(*first_out_edges)[n];
    1353       return i;
    1354     }
    1355     InEdgeIt& first(InEdgeIt& i, const Node& n) const {
    1356       i=InEdgeIt(*this, n);
    1357       return i;
    1358     }
    1359     EdgeIt& first(EdgeIt& i) const {
    1360       i=EdgeIt(*this);
    1361       return i;
     1949    NodeIt& first(NodeIt& i) const {
     1950      i=NodeIt(*this); return i;
     1951    }
     1952    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
     1953      i=OutEdgeIt(*this, p); return i;
     1954    }
     1955    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
     1956      i=InEdgeIt(*this, p); return i;
     1957    }
     1958    EdgeIt& first(EdgeIt& i) const {
     1959      i=EdgeIt(*this); return i;
    13621960    }
    13631961
     
    13811979
    13821980
    1383     NodeIt& next(NodeIt& i) const {
    1384       graph->next(i);
    1385       return i;
    1386     }
    1387     OutEdgeIt& next(OutEdgeIt& i) const {
    1388       graph->next(i);
    1389       return i;
    1390     }
    1391     InEdgeIt& next(InEdgeIt& i) const {
    1392       graph->next(i);
    1393       return i;
    1394     }
    1395     EdgeIt& next(EdgeIt& i) const {
    1396       graph->next(i);
    1397       return i;
    1398     }
     1981    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
     1982    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
     1983    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
     1984    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
     1985   
     1986    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
     1987    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
     1988    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
     1989    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
    13991990
    14001991//     template<typename I> I& next(I &i) const {
     
    14122003      OutEdgeIt f=e;
    14132004      this->next(f);
    1414       first_out_edges->set(this->tail(e), f);
     2005      first_out_edges->set(this->tail(e), f.e);
    14152006    }
    14162007  };
     2008
     2009//   //ErasingFirstGraphWrapper for blocking flows
     2010//   template<typename Graph, typename FirstOutEdgesMap>
     2011//   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
     2012//   protected:
     2013//     FirstOutEdgesMap* first_out_edges;
     2014//   public:
     2015//     ErasingFirstGraphWrapper(Graph& _graph,
     2016//                           FirstOutEdgesMap& _first_out_edges) :
     2017//       GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
     2018
     2019//     typedef typename Graph::Node Node;
     2020//     class NodeIt : public Graph::NodeIt {
     2021//     public:
     2022//       NodeIt() { }
     2023//       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
     2024//       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
     2025//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
     2026//      Graph::NodeIt(*(_G.graph)) { }
     2027//     };
     2028//     typedef typename Graph::Edge Edge;
     2029//     class OutEdgeIt : public Graph::OutEdgeIt {
     2030//     public:
     2031//       OutEdgeIt() { }
     2032//       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
     2033//       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
     2034//       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
     2035//              const Node& n) :
     2036//      Graph::OutEdgeIt((*_G.first_out_edges)[n]) { }
     2037//     };
     2038//     class InEdgeIt : public Graph::InEdgeIt {
     2039//     public:
     2040//       InEdgeIt() { }
     2041//       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
     2042//       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
     2043//       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
     2044//             const Node& n) :
     2045//      Graph::InEdgeIt(*(_G.graph), n) { }
     2046//     };
     2047//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
     2048//     class EdgeIt : public Graph::EdgeIt {
     2049//     public:
     2050//       EdgeIt() { }
     2051//       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
     2052//       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
     2053//       EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
     2054//      Graph::EdgeIt(*(_G.graph)) { }
     2055//     };
     2056
     2057//     NodeIt& first(NodeIt& i) const {
     2058//       i=NodeIt(*this);
     2059//       return i;
     2060//     }
     2061//     OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
     2062//       i=OutEdgeIt(*this, n);
     2063// //      i=(*first_out_edges)[n];
     2064//       return i;
     2065//     }
     2066//     InEdgeIt& first(InEdgeIt& i, const Node& n) const {
     2067//       i=InEdgeIt(*this, n);
     2068//       return i;
     2069//     }
     2070//     EdgeIt& first(EdgeIt& i) const {
     2071//       i=EdgeIt(*this);
     2072//       return i;
     2073//     }
     2074
     2075// //     template<typename I> I& first(I& i) const {
     2076// //       graph->first(i);
     2077// //       return i;
     2078// //     }
     2079// //     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
     2080// // //      e=first_out_edges->get(n);
     2081// //       e=(*first_out_edges)[n];
     2082// //       return e;
     2083// //     }
     2084// //     template<typename I, typename P> I& first(I& i, const P& p) const {
     2085// //       graph->first(i, p);
     2086// //       return i;
     2087// //     }
     2088   
     2089//     //template<typename I> I getNext(const I& i) const {
     2090//     //  return gw.getNext(i);
     2091//     //}
     2092
     2093
     2094//     NodeIt& next(NodeIt& i) const {
     2095//       graph->next(i);
     2096//       return i;
     2097//     }
     2098//     OutEdgeIt& next(OutEdgeIt& i) const {
     2099//       graph->next(i);
     2100//       return i;
     2101//     }
     2102//     InEdgeIt& next(InEdgeIt& i) const {
     2103//       graph->next(i);
     2104//       return i;
     2105//     }
     2106//     EdgeIt& next(EdgeIt& i) const {
     2107//       graph->next(i);
     2108//       return i;
     2109//     }
     2110
     2111// //     template<typename I> I& next(I &i) const {
     2112// //       graph->next(i);
     2113// //       return i;
     2114// //     }
     2115   
     2116//     template< typename It > It first() const {
     2117//       It e; this->first(e); return e; }
     2118   
     2119//     template< typename It > It first(const Node& v) const {
     2120//       It e; this->first(e, v); return e; }
     2121
     2122//     void erase(const OutEdgeIt& e) const {
     2123//       OutEdgeIt f=e;
     2124//       this->next(f);
     2125//       first_out_edges->set(this->tail(e), f);
     2126//     }
     2127//   };
     2128
    14172129
    14182130// // FIXME: comparison should be made better!!!
  • src/work/marci/iterator_bfs_demo.cc

    r312 r317  
    169169    cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
    170170    for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
    171       cout << node_name[n] << ": ";
     171      cout << node_name[GW::Node(n)] << ": ";
    172172      cout << "out edges: ";
    173173      for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
     
    184184    while (!bfs.finished()) {
    185185      //cout << "edge: ";
    186       if (gw.valid(bfs)) {
    187         cout << edge_name[bfs] << /*endl*/", " <<
     186      if (gw.valid(GW::OutEdgeIt(bfs))) {
     187        cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
    188188          node_name[gw.aNode(bfs)] <<
    189189          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     
    218218      ++dfs;
    219219      //cout << "edge: ";
    220       if (gw.valid(dfs)) {
    221         cout << edge_name[dfs] << /*endl*/", " <<
     220      if (gw.valid(GW::OutEdgeIt(dfs))) {
     221        cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
    222222          node_name[gw.aNode(dfs)] <<
    223223          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     
    237237
    238238  {
    239     //typedef UndirGraphWrapper<const Graph> GW;
    240239    typedef UndirGraphWrapper<const Graph> GW;
    241240    GW gw(G);
     
    245244    cout << "bfs and dfs iterator demo on the undirected graph" << endl;
    246245    for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
    247       cout << node_name[n] << ": ";
     246      cout << node_name[GW::Node(n)] << ": ";
    248247      cout << "out edges: ";
    249248      for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
  • src/work/marci/makefile

    r315 r317  
    1010INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
    1111LEDAINCLUDE ?= -I$(LEDAROOT)/incl
    12 CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) #-ansi -pedantic
     12CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic -ftemplate-depth-30
    1313
    1414LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
Note: See TracChangeset for help on using the changeset viewer.