lemon-0.x: src/work/marci/graph_wrapper.h@999eb3cd7b49

     1 // -*- c++ -*-

     2 #ifndef HUGO_GRAPH_WRAPPER_H

     3 #define HUGO_GRAPH_WRAPPER_H

     5 #include <invalid.h>

     7 namespace hugo {

     9   /// Graph wrappers

    11   /// The main parts of HUGOlib are the different graph structures,

    12   /// generic graph algorithms, graph concepts which couple these, and

    13   /// graph wrappers. While the previous ones are more or less clear, the

    14   /// latter notion needs further explanation.

    15   /// Graph wrappers are graph classes which serve for considering graph

    16   /// structures in different ways. A short example makes the notion much more

    17   /// clear.

    18   /// Suppose that we have an instance \code g \endcode of a directed graph

    19   /// type say \code ListGraph \endcode and an algorithm

    20   /// \code template<typename Graph> int algorithm(const Graph&); \endcode

    21   /// is needed to run on the reversed oriented graph.

    22   /// It can be expensive (in time or in memory usage) to copy

    23   /// \code g \endcode with the reversed orientation.

    24   /// Thus, a wrapper class

    25   /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.

    26   /// The code looks as follows

    27   /// \code

    28   /// ListGraph g;

    29   /// RevGraphWrapper<ListGraph> rgw(g);

    30   /// int result=algorithm(rgw);

    31   /// \endcode

    32   /// After running the algorithm, the original graph \code g \endcode

    33   /// is untouched. Thus the above used graph wrapper is to consider the

    34   /// original graph with reversed orientation.

    35   /// This techniques gives rise to an elegant code, and

    36   /// based on stable graph wrappers, complex algorithms can be

    37   /// implemented easily.

    38   /// In flow, circulation and bipartite matching problems, the residual

    39   /// graph is of particualar significance. Combining a wrapper impleneting

    40   /// this, shortest path algorithms and mimimum mean cycle algorithms,

    41   /// a range of weighted and cardinality optimization algorithms can be

    42   /// obtained. For lack of space, for other examples,

    43   /// the interested user is referred to the detailed domumentation of graph

    44   /// wrappers.

    45   /// The behavior of graph wrappers are very different. Some of them keep

    46   /// capabilities of the original graph while in other cases this would be

    47   /// meaningless. This means that the concepts that they are model of depend

    48   /// on the graph wrapper, and the wrapped graph(s).

    49   /// If an edge of \code rgw \endcode is deleted, this is carried out by

    50   /// deleting the corresponding edge of \code g \endcode. But for a residual

    51   /// graph, this operation has no sense.

    52   /// Let we stand one more example here to simplify your work.

    53   /// wrapper class

    54   /// \code template<typename Graph> class RevGraphWrapper; \endcode

    55   /// has constructor

    56   /// \code RevGraphWrapper(Graph& _g); \endcode.

    57   /// This means that in a situation,

    58   /// when a \code const ListGraph& \endcode reference to a graph is given,

    59   /// then it have to be instatiated with Graph=const ListGraph.

    60   /// \code

    61   /// int algorithm1(const ListGraph& g) {

    62   ///   RevGraphWrapper<const ListGraph> rgw(g);

    63   ///   return algorithm2(rgw);

    64   /// }

    65   /// \endcode

    66   template<typename Graph>

    67   class GraphWrapper {

    68   protected:

    69     Graph* graph;

    71   public:

    72     typedef Graph BaseGraph;

    73     typedef Graph ParentGraph;

    75 //     GraphWrapper() : graph(0) { }

    76     GraphWrapper(Graph& _graph) : graph(&_graph) { }

    77 //     void setGraph(Graph& _graph) { graph=&_graph; }

    78 //     Graph& getGraph() const { return *graph; }

    80 //    typedef typename Graph::Node Node;

    81     class Node : public Graph::Node {

    82       friend class GraphWrapper<Graph>;

    83     public:

    84       Node() { }

    85       Node(const typename Graph::Node& _n) : Graph::Node(_n) { }

    86       Node(const Invalid& i) : Graph::Node(i) { }

    87     };

    88     class NodeIt {

    89       friend class GraphWrapper<Graph>;

    90       typename Graph::NodeIt n;

    91      public:

    92       NodeIt() { }

    93       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }

    94       NodeIt(const Invalid& i) : n(i) { }

    95       NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }

    96       operator Node() const { return Node(typename Graph::Node(n)); }

    97     };

    98 //    typedef typename Graph::Edge Edge;

    99     class Edge : public Graph::Edge {

   100       friend class GraphWrapper<Graph>;

   101     public:

   102       Edge() { }

   103       Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }

   104       Edge(const Invalid& i) : Graph::Edge(i) { }

   105     };

   106     class OutEdgeIt {

   107       friend class GraphWrapper<Graph>;

   108 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   109       typename Graph::OutEdgeIt e;

   110     public:

   111       OutEdgeIt() { }

   112       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }

   113       OutEdgeIt(const Invalid& i) : e(i) { }

   114       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :

   115 	e(*(_G.graph), typename Graph::Node(_n)) { }

   116       operator Edge() const { return Edge(typename Graph::Edge(e)); }

   117     };

   118     class InEdgeIt {

   119       friend class GraphWrapper<Graph>;

   120 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

   121       typename Graph::InEdgeIt e;

   122     public:

   123       InEdgeIt() { }

   124       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }

   125       InEdgeIt(const Invalid& i) : e(i) { }

   126       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :

   127 	e(*(_G.graph), typename Graph::Node(_n)) { }

   128       operator Edge() const { return Edge(typename Graph::Edge(e)); }

   129     };

   130     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   131     class EdgeIt {

   132       friend class GraphWrapper<Graph>;

   133 //      typedef typename Graph::EdgeIt GraphEdgeIt;

   134       typename Graph::EdgeIt e;

   135     public:

   136       EdgeIt() { }

   137       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }

   138       EdgeIt(const Invalid& i) : e(i) { }

   139       EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }

   140       operator Edge() const { return Edge(typename Graph::Edge(e)); }

   141     };

   143     NodeIt& first(NodeIt& i) const {

   144       i=NodeIt(*this); return i;

   145     }

   146     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {

   147       i=OutEdgeIt(*this, p); return i;

   148     }

   149     InEdgeIt& first(InEdgeIt& i, const Node& p) const {

   150       i=InEdgeIt(*this, p); return i;

   151     }

   152     EdgeIt& first(EdgeIt& i) const {

   153       i=EdgeIt(*this); return i;

   154     }

   155 //     template<typename I> I& first(I& i) const {

   156 //       i=I(*this);

   157 //       return i;

   158 //     }

   159 //     template<typename I, typename P> I& first(I& i, const P& p) const {

   160 //       i=I(*this, p);

   161 //       return i;

   162 //     }

   164     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }

   165     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }

   166     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }

   167     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }

   168 //    template<typename I> I& next(I &i) const { graph->next(i); return i; }

   169 //     template< typename It > It first() const {

   170 //       It e; this->first(e); return e; }

   172 //     template< typename It > It first(const Node& v) const {

   173 //       It e; this->first(e, v); return e; }

   175     Node head(const Edge& e) const {

   176       return Node(graph->head(static_cast<typename Graph::Edge>(e))); }

   177     Node tail(const Edge& e) const {

   178       return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }

   180     bool valid(const Node& n) const {

   181       return graph->valid(static_cast<typename Graph::Node>(n)); }

   182     bool valid(const Edge& e) const {

   183       return graph->valid(static_cast<typename Graph::Edge>(e)); }

   184 //    template<typename I> bool valid(const I& i) const {

   185 //      return graph->valid(i); }

   187     //template<typename I> void setInvalid(const I &i);

   188     //{ return graph->setInvalid(i); }

   190     int nodeNum() const { return graph->nodeNum(); }

   191     int edgeNum() const { return graph->edgeNum(); }

   193     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }

   194     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }

   195     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }

   196     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }

   197 //     template<typename I> Node aNode(const I& e) const {

   198 //       return Node(graph->aNode(e.e)); }

   199 //     template<typename I> Node bNode(const I& e) const {

   200 //       return Node(graph->bNode(e.e)); }

   202     Node addNode() const { return Node(graph->addNode()); }

   203     Edge addEdge(const Node& tail, const Node& head) const {

   204       return Edge(graph->addEdge(tail, head)); }

   206     void erase(const Node& i) const { graph->erase(i); }

   207     void erase(const Edge& i) const { graph->erase(i); }

   208 //    template<typename I> void erase(const I& i) const { graph->erase(i); }

   210     void clear() const { graph->clear(); }

   212     template<typename T> class NodeMap : public Graph::NodeMap<T> {

   213     public:

   214       NodeMap(const GraphWrapper<Graph>& _G) :

   215 	Graph::NodeMap<T>(*(_G.graph)) { }

   216       NodeMap(const GraphWrapper<Graph>& _G, T a) :

   217 	Graph::NodeMap<T>(*(_G.graph), a) { }

   218     };

   220     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {

   221     public:

   222       EdgeMap(const GraphWrapper<Graph>& _G) :

   223 	Graph::EdgeMap<T>(*(_G.graph)) { }

   224       EdgeMap(const GraphWrapper<Graph>& _G, T a) :

   225 	Graph::EdgeMap<T>(*(_G.graph), a) { }

   226     };

   227   };

   230 //   template<typename Graph>

   231 //   class RevGraphWrapper

   232 //   {

   233 //   protected:

   234 //     Graph* graph;

   236 //   public:

   237 //     typedef Graph ParentGraph;

   239 //     typedef typename Graph::Node Node;

   240 //     typedef typename Graph::NodeIt NodeIt;

   242 //     typedef typename Graph::Edge Edge;

   243 //     typedef typename Graph::OutEdgeIt InEdgeIt;

   244 //     typedef typename Graph::InEdgeIt OutEdgeIt;

   245 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   246 //     typedef typename Graph::EdgeIt EdgeIt;

   248 //     //RevGraphWrapper() : graph(0) { }

   249 //     RevGraphWrapper(Graph& _graph) : graph(&_graph) { }

   251 //     void setGraph(Graph& _graph) { graph = &_graph; }

   252 //     Graph& getGraph() const { return (*graph); }

   254 //     template<typename I> I& first(I& i) const { return graph->first(i); }

   255 //     template<typename I, typename P> I& first(I& i, const P& p) const {

   256 //       return graph->first(i, p); }

   258 //     template<typename I> I& next(I &i) const { return graph->next(i); }

   260 //     template< typename It > It first() const {

   261 //       It e; first(e); return e; }

   263 //     template< typename It > It first(const Node& v) const {

   264 //       It e; first(e, v); return e; }

   266 //     Node head(const Edge& e) const { return graph->tail(e); }

   267 //     Node tail(const Edge& e) const { return graph->head(e); }

   269 //     template<typename I> bool valid(const I& i) const

   270 //       { return graph->valid(i); }

   272 //     //template<typename I> void setInvalid(const I &i);

   273 //     //{ return graph->setInvalid(i); }

   275 //     template<typename I> Node aNode(const I& e) const {

   276 //       return graph->aNode(e); }

   277 //     template<typename I> Node bNode(const I& e) const {

   278 //       return graph->bNode(e); }

   280 //     Node addNode() const { return graph->addNode(); }

   281 //     Edge addEdge(const Node& tail, const Node& head) const {

   282 //       return graph->addEdge(tail, head); }

   284 //     int nodeNum() const { return graph->nodeNum(); }

   285 //     int edgeNum() const { return graph->edgeNum(); }

   287 //     template<typename I> void erase(const I& i) const { graph->erase(i); }

   289 //     void clear() const { graph->clear(); }

   291 //     template<typename T> class NodeMap : public Graph::NodeMap<T> {

   292 //     public:

   293 //       NodeMap(const RevGraphWrapper<Graph>& _G) :

   294 // 	Graph::NodeMap<T>(_G.getGraph()) { }

   295 //       NodeMap(const RevGraphWrapper<Graph>& _G, T a) :

   296 // 	Graph::NodeMap<T>(_G.getGraph(), a) { }

   297 //     };

   299 //     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {

   300 //     public:

   301 //       EdgeMap(const RevGraphWrapper<Graph>& _G) :

   302 // 	Graph::EdgeMap<T>(_G.getGraph()) { }

   303 //       EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :

   304 // 	Graph::EdgeMap<T>(_G.getGraph(), a) { }

   305 //     };

   306 //   };

   309   template<typename Graph>

   310   class RevGraphWrapper : public GraphWrapper<Graph> {

   311   public:

   312     typedef typename GraphWrapper<Graph>::Node Node;

   313     typedef typename GraphWrapper<Graph>::Edge Edge;

   314     //FIXME

   315     //If Graph::OutEdgeIt is not defined

   316     //and we do not want to use RevGraphWrapper::InEdgeIt,

   317     //this won't work, because of typedef

   318     //OR

   319     //graphs have to define their non-existing iterators to void

   320     //Unfortunately all the typedefs are instantiated in templates,

   321     //unlike other stuff

   322     typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;

   323     typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;

   325 //     RevGraphWrapper() : GraphWrapper<Graph>() { }

   326     RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }

   328     Node head(const Edge& e) const

   329       { return GraphWrapper<Graph>::tail(e); }

   330     Node tail(const Edge& e) const

   331       { return GraphWrapper<Graph>::head(e); }

   332   };

   334   /// Wrapper for hiding nodes and edges from a graph.

   336   /// This wrapper shows a graph with filtered node-set and

   337   /// edge-set. The quick brown fox iterators jumps over

   338   /// the lazy dog nodes or edges if the values for them are false

   339   /// in the bool maps.

   340   template<typename Graph, typename NodeFilterMap,

   341 	   typename EdgeFilterMap>

   342   class SubGraphWrapper : public GraphWrapper<Graph> {

   343   protected:

   344     NodeFilterMap* node_filter_map;

   345     EdgeFilterMap* edge_filter_map;

   346   public:

   347 //     SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }

   348     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,

   349 		    EdgeFilterMap& _edge_filter_map) :

   350       GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),

   351       edge_filter_map(&_edge_filter_map) { }

   353     typedef typename GraphWrapper<Graph>::Node Node;

   354     class NodeIt {

   355       friend class GraphWrapper<Graph>;

   356       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

   357       typename Graph::NodeIt n;

   358      public:

   359       NodeIt() { }

   360       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }

   361       NodeIt(const Invalid& i) : n(i) { }

   362       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :

   363 	n(*(_G.graph)) {

   364 	while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])

   365 	  _G.graph->next(n);

   366       }

   367       operator Node() const { return Node(typename Graph::Node(n)); }

   368     };

   369 //     class NodeIt : public Graph::NodeIt {

   370 // //      typedef typename Graph::NodeIt GraphNodeIt;

   371 //     public:

   372 //       NodeIt() { }

   373 //       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }

   374 //       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }

   375 //       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :

   376 // 	Graph::NodeIt(*(_G.graph)) {

   377 // 	while (_G.graph->valid((*this)/*.GraphNodeIt*/) &&

   378 // 	       !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/])

   379 // 	  _G.graph->next((*this)/*.GraphNodeIt*/);

   380 //       }

   381 //     };

   382     typedef typename GraphWrapper<Graph>::Edge Edge;

   383     class OutEdgeIt {

   384       friend class GraphWrapper<Graph>;

   385       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

   386 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   387       typename Graph::OutEdgeIt e;

   388     public:

   389       OutEdgeIt() { }

   390       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }

   391       OutEdgeIt(const Invalid& i) : e(i) { }

   392       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,

   393 		const Node& _n) :

   394 	e(*(_G.graph), typename Graph::Node(_n)) {

   395       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])

   396 	  _G.graph->next(e);

   397       }

   398       operator Edge() const { return Edge(typename Graph::Edge(e)); }

   399     };

   400     class InEdgeIt {

   401       friend class GraphWrapper<Graph>;

   402       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

   403 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

   404       typename Graph::InEdgeIt e;

   405     public:

   406       InEdgeIt() { }

   407       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }

   408       InEdgeIt(const Invalid& i) : e(i) { }

   409       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,

   410 	       const Node& _n) :

   411 	e(*(_G.graph), typename Graph::Node(_n)) {

   412       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])

   413 	  _G.graph->next(e);

   414       }

   415       operator Edge() const { return Edge(typename Graph::Edge(e)); }

   416     };

   417     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   418     class EdgeIt {

   419       friend class GraphWrapper<Graph>;

   420       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

   421 //      typedef typename Graph::EdgeIt GraphEdgeIt;

   422       typename Graph::EdgeIt e;

   423     public:

   424       EdgeIt() { }

   425       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }

   426       EdgeIt(const Invalid& i) : e(i) { }

   427       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :

   428 	e(*(_G.graph)) {

   429       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])

   430 	  _G.graph->next(e);

   431       }

   432       operator Edge() const { return Edge(typename Graph::Edge(e)); }

   433     };

   434 //       operator Edge() const { return Edge(typename Graph::Edge(e)); }

   435 //     };

   436 //     class OutEdgeIt : public Graph::OutEdgeIt {

   437 // //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   438 //     public:

   439 //       OutEdgeIt() { }

   440 //       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }

   441 //       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }

   442 //       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&

   443 // 		_G, const Node& n) :

   444 // 	Graph::OutEdgeIt(*(_G.graph), n) {

   445 // 	while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) &&

   446 // 	       !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/])

   447 // 	  _G.graph->next((*this)/*.GraphOutEdgeIt*/);

   448 //       }

   449 //     };

   450 //     class InEdgeIt : public Graph::InEdgeIt {

   451 // //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

   452 //     public:

   453 //       InEdgeIt() { }

   454 //       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }

   455 //       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }

   456 //       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,

   457 // 	       const Node& n) :

   458 // 	Graph::InEdgeIt(*(_G.graph), n) {

   459 // 	while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) &&

   460 // 	       !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/])

   461 // 	  _G.graph->next((*this)/*.GraphInEdgeIt*/);

   462 //       }

   463 //     };

   464 // //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   465 //     class EdgeIt : public Graph::EdgeIt {

   466 // //      typedef typename Graph::EdgeIt GraphEdgeIt;

   467 //     public:

   468 //       EdgeIt() { }

   469 //       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }

   470 //       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }

   471 //       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :

   472 // 	Graph::EdgeIt(*(_G.graph)) {

   473 // 	while (_G.graph->valid((*this)/*.GraphEdgeIt*/) &&

   474 // 	       !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/])

   475 // 	  _G.graph->next((*this)/*.GraphEdgeIt*/);

   476 //       }

   477 //     };

   480     NodeIt& first(NodeIt& i) const {

   481       i=NodeIt(*this); return i;

   482     }

   483     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {

   484       i=OutEdgeIt(*this, p); return i;

   485     }

   486     InEdgeIt& first(InEdgeIt& i, const Node& p) const {

   487       i=InEdgeIt(*this, p); return i;

   488     }

   489     EdgeIt& first(EdgeIt& i) const {

   490       i=EdgeIt(*this); return i;

   491     }

   493 //     template<typename I> I& first(I& i) const {

   494 //       graph->first(i);

   495 //       //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }

   496 //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }

   497 //       return i;

   498 //     }

   499 //     template<typename I, typename P> I& first(I& i, const P& p) const {

   500 //       graph->first(i, p);

   501 // //      while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }

   502 //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }

   503 //       return i;

   504 //     }

   506     NodeIt& next(NodeIt& i) const {

   507       graph->next(i.n);

   508       while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); }

   509       return i;

   510     }

   511     OutEdgeIt& next(OutEdgeIt& i) const {

   512       graph->next(i.e);

   513       while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }

   514       return i;

   515     }

   516     InEdgeIt& next(InEdgeIt& i) const {

   517       graph->next(i.e);

   518       while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }

   519       return i;

   520     }

   521     EdgeIt& next(EdgeIt& i) const {

   522       graph->next(i.e);

   523       while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }

   524       return i;

   525     }

   527 //     template<typename I> I& next(I &i) const {

   528 //       graph->next(i);

   529 // //      while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }

   530 //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }

   531 //       return i;

   532 //     }

   534     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }

   535     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }

   536     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }

   537     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }

   539     void hide(const Node& n) const { node_filter_map->set(n, false); }

   540     void hide(const Edge& e) const { edge_filter_map->set(e, false); }

   542     void unHide(const Node& n) const { node_filter_map->set(n, true); }

   543     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }

   545     bool hidden(const Node& n) const { return (*node_filter_map)[n]; }

   546     bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }

   548 //     template< typename It > It first() const {

   549 //       It e; this->first(e); return e; }

   551 //     template< typename It > It first(const Node& v) const {

   552 //       It e; this->first(e, v); return e; }

   553   };

   555 //   //Subgraph on the same node-set and partial edge-set

   556 //   template<typename Graph, typename NodeFilterMap,

   557 // 	   typename EdgeFilterMap>

   558 //   class SubGraphWrapper : public GraphWrapper<Graph> {

   559 //   protected:

   560 //     NodeFilterMap* node_filter_map;

   561 //     EdgeFilterMap* edge_filter_map;

   562 //   public:

   563 // //     SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }

   564 //     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,

   565 // 		    EdgeFilterMap& _edge_filter_map) :

   566 //       GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),

   567 //       edge_filter_map(&_edge_filter_map) { }

   570 //     typedef typename Graph::Node Node;

   571 //     class NodeIt : public Graph::NodeIt {

   572 // //      typedef typename Graph::NodeIt GraphNodeIt;

   573 //     public:

   574 //       NodeIt() { }

   575 //       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }

   576 //       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }

   577 //       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :

   578 // 	Graph::NodeIt(*(_G.graph)) {

   579 // 	while (_G.graph->valid((*this)/*.GraphNodeIt*/) &&

   580 // 	       !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/])

   581 // 	  _G.graph->next((*this)/*.GraphNodeIt*/);

   582 //       }

   583 //     };

   584 //     typedef typename Graph::Edge Edge;

   585 //     class OutEdgeIt : public Graph::OutEdgeIt {

   586 // //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   587 //     public:

   588 //       OutEdgeIt() { }

   589 //       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }

   590 //       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }

   591 //       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&

   592 // 		_G, const Node& n) :

   593 // 	Graph::OutEdgeIt(*(_G.graph), n) {

   594 // 	while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) &&

   595 // 	       !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/])

   596 // 	  _G.graph->next((*this)/*.GraphOutEdgeIt*/);

   597 //       }

   598 //     };

   599 //     class InEdgeIt : public Graph::InEdgeIt {

   600 // //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

   601 //     public:

   602 //       InEdgeIt() { }

   603 //       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }

   604 //       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }

   605 //       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,

   606 // 	       const Node& n) :

   607 // 	Graph::InEdgeIt(*(_G.graph), n) {

   608 // 	while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) &&

   609 // 	       !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/])

   610 // 	  _G.graph->next((*this)/*.GraphInEdgeIt*/);

   611 //       }

   612 //     };

   613 // //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   614 //     class EdgeIt : public Graph::EdgeIt {

   615 // //      typedef typename Graph::EdgeIt GraphEdgeIt;

   616 //     public:

   617 //       EdgeIt() { }

   618 //       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }

   619 //       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }

   620 //       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :

   621 // 	Graph::EdgeIt(*(_G.graph)) {

   622 // 	while (_G.graph->valid((*this)/*.GraphEdgeIt*/) &&

   623 // 	       !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/])

   624 // 	  _G.graph->next((*this)/*.GraphEdgeIt*/);

   625 //       }

   626 //     };

   628 //     NodeIt& first(NodeIt& i) const {

   629 //       i=NodeIt(*this);

   630 //       return i;

   631 //     }

   632 //     OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {

   633 //       i=OutEdgeIt(*this, n);

   634 //       return i;

   635 //     }

   636 //     InEdgeIt& first(InEdgeIt& i, const Node& n) const {

   637 //       i=InEdgeIt(*this, n);

   638 //       return i;

   639 //     }

   640 //     EdgeIt& first(EdgeIt& i) const {

   641 //       i=EdgeIt(*this);

   642 //       return i;

   643 //     }

   645 // //     template<typename I> I& first(I& i) const {

   646 // //       graph->first(i);

   647 // //       //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }

   648 // //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }

   649 // //       return i;

   650 // //     }

   651 // //     template<typename I, typename P> I& first(I& i, const P& p) const {

   652 // //       graph->first(i, p);

   653 // // //      while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }

   654 // //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }

   655 // //       return i;

   656 // //     }

   658 //     NodeIt& next(NodeIt& i) const {

   659 //       graph->next(i);

   660 //       while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); }

   661 //       return i;

   662 //     }

   663 //     OutEdgeIt& next(OutEdgeIt& i) const {

   664 //       graph->next(i);

   665 //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }

   666 //       return i;

   667 //     }

   668 //     InEdgeIt& next(InEdgeIt& i) const {

   669 //       graph->next(i);

   670 //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }

   671 //       return i;

   672 //     }

   673 //     EdgeIt& next(EdgeIt& i) const {

   674 //       graph->next(i);

   675 //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }

   676 //       return i;

   677 //     }

   679 // //     template<typename I> I& next(I &i) const {

   680 // //       graph->next(i);

   681 // // //      while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }

   682 // //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }

   683 // //       return i;

   684 // //     }

   686 //     template< typename It > It first() const {

   687 //       It e; this->first(e); return e; }

   689 //     template< typename It > It first(const Node& v) const {

   690 //       It e; this->first(e, v); return e; }

   691 //   };

   693   template<typename Graph>

   694   class UndirGraphWrapper : public GraphWrapper<Graph> {

   695 //  protected:

   696 //    typedef typename Graph::Edge GraphEdge;

   697 //    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   698 //    typedef typename Graph::InEdgeIt GraphInEdgeIt;

   699   public:

   700     typedef typename GraphWrapper<Graph>::Node Node;

   701     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;

   702     typedef typename GraphWrapper<Graph>::Edge Edge;

   703     typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;

   705 //     UndirGraphWrapper() : GraphWrapper<Graph>() { }

   706     UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }

   709 //     class Edge {

   710 //       friend class UndirGraphWrapper<Graph>;

   711 //     protected:

   712 //       bool out_or_in; //true iff out

   713 //       GraphOutEdgeIt out;

   714 //       GraphInEdgeIt in;

   715 //     public:

   716 //       Edge() : out_or_in(), out(), in() { }

   717 //       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }

   718 //       operator GraphEdge() const {

   719 // 	if (out_or_in) return(out); else return(in);

   720 //       }

   721 // //FIXME

   722 // //2 edges are equal if they "refer" to the same physical edge

   723 // //is it good?

   724 //       friend bool operator==(const Edge& u, const Edge& v) {

   725 // 	if (v.out_or_in)

   726 // 	  if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);

   727 // 	//return (u.out_or_in && u.out==v.out);

   728 // 	else

   729 // 	  if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);

   730 // 	//return (!u.out_or_in && u.in==v.in);

   731 //       }

   732 //       friend bool operator!=(const Edge& u, const Edge& v) {

   733 // 	if (v.out_or_in)

   734 // 	  if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);

   735 // 	//return (!u.out_or_in || u.out!=v.out);

   736 // 	else

   737 // 	  if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);

   738 // 	//return (u.out_or_in || u.in!=v.in);

   739 //       }

   740 //     };

   742     class OutEdgeIt {

   743       friend class UndirGraphWrapper<Graph>;

   744       bool out_or_in; //true iff out

   745       typename Graph::OutEdgeIt out;

   746       typename Graph::InEdgeIt in;

   747     public:

   748       OutEdgeIt() { }

   749       OutEdgeIt(const Invalid& i) : Edge(i) { }

   750       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {

   751 	out_or_in=true; _G.graph->first(out, _n);

   752 	if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);	}

   753       }

   754       operator Edge() const {

   755 	if (out_or_in) return Edge(out); else return Edge(in);

   756       }

   757     };

   758 //     class OutEdgeIt : public Edge {

   759 //       friend class UndirGraphWrapper<Graph>;

   760 //     public:

   761 //       OutEdgeIt() : Edge() { }

   762 //       OutEdgeIt(const Invalid& i) : Edge(i) { }

   763 //       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n)

   764 // 	: Edge() {

   765 // 	out_or_in=true; _G.graph->first(out, n);

   766 // 	if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n);	}

   767 //       }

   768 //     };

   770 //FIXME InEdgeIt

   771     typedef OutEdgeIt InEdgeIt;

   773 //     class EdgeIt : public Edge {

   774 //       friend class UndirGraphWrapper<Graph>;

   775 //     protected:

   776 //       NodeIt v;

   777 //     public:

   778 //       EdgeIt() : Edge() { }

   779 //       EdgeIt(const Invalid& i) : Edge(i) { }

   780 //       EdgeIt(const UndirGraphWrapper<Graph>& _G)

   781 // 	: Edge() {

   782 // 	out_or_in=true;

   783 // 	//Node v;

   784 // 	_G.first(v);

   785 // 	if (_G.valid(v)) _G.graph->first(out); else out=INVALID;

   786 // 	while (_G.valid(v) && !_G.graph->valid(out)) {

   787 // 	  _G.graph->next(v);

   788 // 	  if (_G.valid(v)) _G.graph->first(out);

   789 // 	}

   790 //       }

   791 //     };

   793     NodeIt& first(NodeIt& i) const {

   794       i=NodeIt(*this); return i;

   795     }

   796     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {

   797       i=OutEdgeIt(*this, p); return i;

   798     }

   799 //FIXME

   800 //     InEdgeIt& first(InEdgeIt& i, const Node& p) const {

   801 //       i=InEdgeIt(*this, p); return i;

   802 //     }

   803     EdgeIt& first(EdgeIt& i) const {

   804       i=EdgeIt(*this); return i;

   805     }

   807 //     template<typename I> I& first(I& i) const { graph->first(i); return i; }

   808 //     template<typename I, typename P> I& first(I& i, const P& p) const {

   809 //       graph->first(i, p); return i; }

   811     NodeIt& next(NodeIt& n) const {

   812       GraphWrapper<Graph>::next(n);

   813       return n;

   814     }

   815     OutEdgeIt& next(OutEdgeIt& e) const {

   816       if (e.out_or_in) {

   817 	typename Graph::Node n=graph->tail(e.out);

   818 	graph->next(e.out);

   819 	if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }

   820       } else {

   821 	graph->next(e.in);

   822       }

   823       return e;

   824     }

   825     //FIXME InEdgeIt

   826     EdgeIt& next(EdgeIt& e) const {

   827       GraphWrapper<Graph>::next(n);

   828 //      graph->next(e.e);

   829       return e;

   830     }

   832 //    template<typename I> I& next(I &i) const { graph->next(i); return i; }

   833 //     template< typename It > It first() const {

   834 //       It e; this->first(e); return e; }

   836 //     template< typename It > It first(const Node& v) const {

   837 //       It e; this->first(e, v); return e; }

   839 //    Node head(const Edge& e) const { return gw.head(e); }

   840 //    Node tail(const Edge& e) const { return gw.tail(e); }

   842 //    template<typename I> bool valid(const I& i) const

   843 //      { return gw.valid(i); }

   845 //    int nodeNum() const { return gw.nodeNum(); }

   846 //    int edgeNum() const { return gw.edgeNum(); }

   848 //     template<typename I> Node aNode(const I& e) const {

   849 //       return graph->aNode(e); }

   850 //     template<typename I> Node bNode(const I& e) const {

   851 //       return graph->bNode(e); }

   853     Node aNode(const OutEdgeIt& e) const {

   854       if (e.out_or_in) return graph->tail(e); else return graph->head(e); }

   855     Node bNode(const OutEdgeIt& e) const {

   856       if (e.out_or_in) return graph->head(e); else return graph->tail(e); }

   858 //    Node addNode() const { return gw.addNode(); }

   860 // FIXME: ez igy nem jo, mert nem

   861 //    Edge addEdge(const Node& tail, const Node& head) const {

   862 //      return graph->addEdge(tail, head); }

   864 //    template<typename I> void erase(const I& i) const { gw.erase(i); }

   866 //    void clear() const { gw.clear(); }

   868 //     template<typename T> class NodeMap : public Graph::NodeMap<T> {

   869 //     public:

   870 //       NodeMap(const UndirGraphWrapper<Graph>& _G) :

   871 // 	Graph::NodeMap<T>(_G.gw) { }

   872 //       NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :

   873 // 	Graph::NodeMap<T>(_G.gw, a) { }

   874 //     };

   876 //     template<typename T> class EdgeMap :

   877 //       public GraphWrapperSkeleton<Graph>::EdgeMap<T> {

   878 //     public:

   879 //       EdgeMap(const UndirGraphWrapper<Graph>& _G) :

   880 // 	GraphWrapperSkeleton<Graph>::EdgeMap<T>(_G.gw) { }

   881 //       EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :

   882 // 	Graph::EdgeMap<T>(_G.gw, a) { }

   883 //     };

   884    };

   890 //   template<typename Graph>

   891 //   class SymGraphWrapper

   892 //   {

   893 //     Graph* graph;

   895 //   public:

   896 //     typedef Graph ParentGraph;

   898 //     typedef typename Graph::Node Node;

   899 //     typedef typename Graph::Edge Edge;

   901 //     typedef typename Graph::NodeIt NodeIt;

   903 //     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon

   904 //     //iranyitatlant, ami van

   905 //     //mert csak 1 dolgot lehet be typedef-elni

   906 //     typedef typename Graph::OutEdgeIt SymEdgeIt;

   907 //     //typedef typename Graph::InEdgeIt SymEdgeIt;

   908 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   909 //     typedef typename Graph::EdgeIt EdgeIt;

   911 //     int nodeNum() const { return graph->nodeNum(); }

   912 //     int edgeNum() const { return graph->edgeNum(); }

   914 //     template<typename I> I& first(I& i) const { return graph->first(i); }

   915 //     template<typename I, typename P> I& first(I& i, const P& p) const {

   916 //       return graph->first(i, p); }

   917 //     //template<typename I> I next(const I i); { return graph->goNext(i); }

   918 //     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }

   920 //     template< typename It > It first() const {

   921 //       It e; first(e); return e; }

   923 //     template< typename It > It first(Node v) const {

   924 //       It e; first(e, v); return e; }

   926 //     Node head(const Edge& e) const { return graph->head(e); }

   927 //     Node tail(const Edge& e) const { return graph->tail(e); }

   929 //     template<typename I> Node aNode(const I& e) const {

   930 //       return graph->aNode(e); }

   931 //     template<typename I> Node bNode(const I& e) const {

   932 //       return graph->bNode(e); }

   934 //     //template<typename I> bool valid(const I i);

   935 //     //{ return graph->valid(i); }

   937 //     //template<typename I> void setInvalid(const I &i);

   938 //     //{ return graph->setInvalid(i); }

   940 //     Node addNode() { return graph->addNode(); }

   941 //     Edge addEdge(const Node& tail, const Node& head) {

   942 //       return graph->addEdge(tail, head); }

   944 //     template<typename I> void erase(const I& i) { graph->erase(i); }

   946 //     void clear() { graph->clear(); }

   948 //     template<typename T> class NodeMap : public Graph::NodeMap<T> { };

   949 //     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };

   951 //     void setGraph(Graph& _graph) { graph = &_graph; }

   952 //     Graph& getGraph() { return (*graph); }

   954 //     //SymGraphWrapper() : graph(0) { }

   955 //     SymGraphWrapper(Graph& _graph) : graph(&_graph) { }

   956 //   };

   961   template<typename Graph, typename Number,

   962 	   typename CapacityMap, typename FlowMap>

   963   class ResGraphWrapper : public GraphWrapper<Graph> {

   964   protected:

   965 //    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   966 //    typedef typename Graph::InEdgeIt GraphInEdgeIt;

   967 //    typedef typename Graph::Edge GraphEdge;

   968     const CapacityMap* capacity;

   969     FlowMap* flow;

   970   public:

   972     ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,

   973 		    FlowMap& _flow) :

   974       GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }

   976     class Edge;

   977     class OutEdgeIt;

   978     friend class Edge;

   979     friend class OutEdgeIt;

   981     typedef typename GraphWrapper<Graph>::Node Node;

   982     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;

   983     class Edge : public Graph::Edge {

   984       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;

   985     protected:

   986       bool forward; //true, iff forward

   987 //      typename Graph::Edge e;

   988     public:

   989       Edge() { }

   990       Edge(const typename Graph::Edge& _e, bool _forward) :

   991 	Graph::Edge(_e), forward(_forward) { }

   992       Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }

   993 //the unique invalid iterator

   994       friend bool operator==(const Edge& u, const Edge& v) {

   995 	return (v.forward==u.forward &&

   996 		static_cast<typename Graph::Edge>(u)==

   997 		static_cast<typename Graph::Edge>(v));

   998       }

   999       friend bool operator!=(const Edge& u, const Edge& v) {

  1000 	return (v.forward!=u.forward ||

  1001 		static_cast<typename Graph::Edge>(u)!=

  1002 		static_cast<typename Graph::Edge>(v));

  1003       }

  1004     };

  1005 //     class Edge {

  1006 //       friend class ResGraphWrapper<Graph, Number,lksd FlowMap, CapacityMap>;

  1007 //     protected:

  1008 //       bool out_or_in; //true, iff out

  1009 //       GraphOutEdgeIt out;

  1010 //       GraphInEdgeIt in;

  1011 //     public:

  1012 //       Edge() : out_or_in(true) { }

  1013 //       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }

  1014 // //       bool valid() const {

  1015 // // 	return out_or_in && out.valid() || in.valid(); }

  1016 //       friend bool operator==(const Edge& u, const Edge& v) {

  1017 // 	if (v.out_or_in)

  1018 // 	  return (u.out_or_in && u.out==v.out);

  1019 // 	else

  1020 // 	  return (!u.out_or_in && u.in==v.in);

  1021 //       }

  1022 //       friend bool operator!=(const Edge& u, const Edge& v) {

  1023 // 	if (v.out_or_in)

  1024 // 	  return (!u.out_or_in || u.out!=v.out);

  1025 // 	else

  1026 // 	  return (u.out_or_in || u.in!=v.in);

  1027 //       }

  1028 //       operator GraphEdge() const {

  1029 // 	if (out_or_in) return(out); else return(in);

  1030 //       }

  1031 //     };

  1032     class OutEdgeIt {

  1033       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;

  1034     protected:

  1035       typename Graph::OutEdgeIt out;

  1036       typename Graph::InEdgeIt in;

  1037       bool forward;

  1038     public:

  1039       OutEdgeIt() { }

  1040       //FIXME

  1041 //      OutEdgeIt(const Edge& e) : Edge(e) { }

  1042       OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }

  1043 //the unique invalid iterator

  1044       OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {

  1045 	forward=true;

  1046 	resG.graph->first(out, v);

  1047 	while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }

  1048 	if (!resG.graph->valid(out)) {

  1049 	  forward=false;

  1050 	  resG.graph->first(in, v);

  1051 	  while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }

  1052 	}

  1053       }

  1054       operator Edge() const {

  1055 //	Edge e;

  1056 //	e.forward=this->forward;

  1057 //	if (this->forward) e=out; else e=in;

  1058 //	return e;

  1059 	if (this->forward)

  1060 	  return Edge(out, this->forward);

  1061 	else

  1062 	  return Edge(in, this->forward);

  1063       }

  1064     };

  1065 //     class OutEdgeIt : public Edge {

  1066 //       friend class ResGraphWrapper<Graph, Number, FkklowMap, CapacityMap>;

  1067 //     public:

  1068 //       OutEdgeIt() { }

  1069 //       //FIXME

  1070 //       OutEdgeIt(const Edge& e) : Edge(e) { }

  1071 //       OutEdgeIt(const Invalid& i) : Edge(i) { }

  1072 //       OutEdgeIt(const ResGraphWrapper<Graph, Number, FdfvlowMap, CapacityMap>& resG, Node v) : Edge() {

  1073 // 	resG.graph->first(out, v);

  1074 // 	while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }

  1075 // 	if (!resG.graph->valid(out)) {

  1076 // 	  out_or_in=0;

  1077 // 	  resG.graph->first(in, v);

  1078 // 	  while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }

  1079 // 	}

  1080 //       }

  1081 //     public:

  1082 //       OutEdgeIt& operator++() {

  1083 // 	if (out_or_in) {

  1084 // 	  Node v=/*resG->*/G->aNode(out);

  1085 // 	  ++out;

  1086 // 	  while( out.valid() && !(Edge::resCap()>0) ) { ++out; }

  1087 // 	  if (!out.valid()) {

  1088 // 	    out_or_in=0;

  1089 // 	    G->first(in, v);

  1090 // 	    while( in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1091 // 	  }

  1092 // 	} else {

  1093 // 	  ++in;

  1094 // 	  while( in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1095 // 	}

  1096 // 	return *this;

  1097 //       }

  1098 //    };

  1100     //FIXME This is just for having InEdgeIt

  1101 //    class InEdgeIt : public Edge { };

  1103     class InEdgeIt {

  1104       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;

  1105     protected:

  1106       typename Graph::OutEdgeIt out;

  1107       typename Graph::InEdgeIt in;

  1108       bool forward;

  1109     public:

  1110       InEdgeIt() { }

  1111       //FIXME

  1112 //      OutEdgeIt(const Edge& e) : Edge(e) { }

  1113       InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }

  1114 //the unique invalid iterator

  1115       InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {

  1116 	forward=true;

  1117 	resG.graph->first(in, v);

  1118 	while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }

  1119 	if (!resG.graph->valid(in)) {

  1120 	  forward=false;

  1121 	  resG.graph->first(out, v);

  1122 	  while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }

  1123 	}

  1124       }

  1125       operator Edge() const {

  1126 //	Edge e;

  1127 //	e.forward=this->forward;

  1128 //	if (this->forward) e=out; else e=in;

  1129 //	return e;

  1130 	if (this->forward)

  1131 	  return Edge(in, this->forward);

  1132 	else

  1133 	  return Edge(out, this->forward);

  1134       }

  1135     };

  1137     class EdgeIt {

  1138       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;

  1139     protected:

  1140       typename Graph::EdgeIt e;

  1141       bool forward;

  1142     public:

  1143       EdgeIt() { }

  1144       EdgeIt(const Invalid& i) : e(i), forward(false) { }

  1145       EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {

  1146 	forward=true;

  1147 	resG.graph->first(e);

  1148 	while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);

  1149 	if (!resG.graph->valid(e)) {

  1150 	  forward=false;

  1151 	  resG.graph->first(e);

  1152 	  while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);

  1153 	}

  1154       }

  1155       operator Edge() const {

  1156 	return Edge(e, this->forward);

  1157       }

  1158     };

  1159 //     class EdgeIt : public Edge {

  1160 //       friend class ResGraphWrapper<Graph, Number, FflowMap, CapacityMap>;

  1161 //       NodeIt v;

  1162 //     public:

  1163 //       EdgeIt() { }

  1164 //       //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }

  1165 //       EdgeIt(const Invalid& i) : Edge(i) { }

  1166 //       EdgeIt(const ResGraphWrapper<Graph, Number, FlfowMap, CapacityMap>& resG) : Edge() {

  1167 // 	resG.graph->first(v);

  1168 // 	if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;

  1169 // 	while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }

  1170 // 	while (resG.graph->valid(v) && !resG.graph->valid(out)) {

  1171 // 	  resG.graph->next(v);

  1172 // 	  if (resG.graph->valid(v)) resG.graph->first(out, v);

  1173 // 	  while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }

  1174 // 	}

  1175 // 	if (!resG.graph->valid(out)) {

  1176 // 	  out_or_in=0;

  1177 // 	  resG.graph->first(v);

  1178 // 	  if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;

  1179 // 	  while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }

  1180 // 	  while (resG.graph->valid(v) && !resG.graph->valid(in)) {

  1181 // 	    resG.graph->next(v);

  1182 // 	    if (resG.graph->valid(v)) resG.graph->first(in, v);

  1183 // 	    while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }

  1184 // 	  }

  1185 // 	}

  1186 //       }

  1187 //       EdgeIt& operator++() {

  1188 // 	if (out_or_in) {

  1189 // 	  ++out;

  1190 // 	  while (out.valid() && !(Edge::resCap()>0) ) { ++out; }

  1191 // 	  while (v.valid() && !out.valid()) {

  1192 // 	    ++v;

  1193 // 	    if (v.valid()) G->first(out, v);

  1194 // 	    while (out.valid() && !(Edge::resCap()>0) ) { ++out; }

  1195 // 	  }

  1196 // 	  if (!out.valid()) {

  1197 // 	    out_or_in=0;

  1198 // 	    G->first(v);

  1199 // 	    if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();

  1200 // 	    while (in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1201 // 	    while (v.valid() && !in.valid()) {

  1202 // 	      ++v;

  1203 // 	      if (v.valid()) G->first(in, v);

  1204 // 	      while (in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1205 // 	    }

  1206 // 	  }

  1207 // 	} else {

  1208 // 	  ++in;

  1209 // 	  while (in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1210 // 	  while (v.valid() && !in.valid()) {

  1211 // 	    ++v;

  1212 // 	    if (v.valid()) G->first(in, v);

  1213 // 	    while (in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1214 // 	  }

  1215 // 	}

  1216 // 	return *this;

  1217 //       }

  1218 //    };

  1220     NodeIt& first(NodeIt& i) const {

  1221       i=NodeIt(*this); return i;

  1222     }

  1223     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {

  1224       i=OutEdgeIt(*this, p); return i;

  1225     }

  1226 //    FIXME not tested

  1227     InEdgeIt& first(InEdgeIt& i, const Node& p) const {

  1228       i=InEdgeIt(*this, p); return i;

  1229     }

  1230     EdgeIt& first(EdgeIt& i) const {

  1231       i=EdgeIt(*this); return i;

  1232     }

  1234     NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }

  1235     OutEdgeIt& next(OutEdgeIt& e) const {

  1236       if (e.forward) {

  1237 	Node v=graph->aNode(e.out);

  1238 	graph->next(e.out);

  1239 	while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }

  1240 	if (!graph->valid(e.out)) {

  1241 	  e.forward=false;

  1242 	  graph->first(e.in, v);

  1243 	  while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }

  1244 	}

  1245       } else {

  1246 	graph->next(e.in);

  1247 	while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }

  1248       }

  1249       return e;

  1250     }

  1251 //     FIXME Not tested

  1252     InEdgeIt& next(InEdgeIt& e) const {

  1253       if (e.forward) {

  1254 	Node v=graph->aNode(e.in);

  1255 	graph->next(e.in);

  1256 	while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }

  1257 	if (!graph->valid(e.in)) {

  1258 	  e.forward=false;

  1259 	  graph->first(e.out, v);

  1260 	  while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }

  1261 	}

  1262       } else {

  1263 	graph->next(e.out);

  1264 	while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }

  1265       }

  1266       return e;

  1267     }

  1268     EdgeIt& next(EdgeIt& e) const {

  1269       if (e.forward) {

  1270 	graph->next(e.e);

  1271 	while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }

  1272 	if (!graph->valid(e.e)) {

  1273 	  e.forward=false;

  1274 	  graph->first(e.e);

  1275 	  while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }

  1276 	}

  1277       } else {

  1278 	graph->next(e.e);

  1279 	while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }

  1280       }

  1281       return e;

  1282     }

  1283 //     EdgeIt& next(EdgeIt& e) const {

  1284 //       if (e.out_or_in) {

  1285 // 	graph->next(e.out);

  1286 // 	while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }

  1287 // 	  while (graph->valid(e.v) && !graph->valid(e.out)) {

  1288 // 	    graph->next(e.v);

  1289 // 	    if (graph->valid(e.v)) graph->first(e.out, e.v);

  1290 // 	    while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }

  1291 // 	  }

  1292 // 	  if (!graph->valid(e.out)) {

  1293 // 	    e.out_or_in=0;

  1294 // 	    graph->first(e.v);

  1295 // 	    if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;

  1296 // 	    while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }

  1297 // 	    while (graph->valid(e.v) && !graph->valid(e.in)) {

  1298 // 	      graph->next(e.v);

  1299 // 	      if (graph->valid(e.v)) graph->first(e.in, e.v);

  1300 // 	      while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }

  1301 // 	    }

  1302 // 	  }

  1303 // 	} else {

  1304 // 	  graph->next(e.in);

  1305 // 	  while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }

  1306 // 	  while (graph->valid(e.v) && !graph->valid(e.in)) {

  1307 // 	    graph->next(e.v);

  1308 // 	    if (graph->valid(e.v)) graph->first(e.in, e.v);

  1309 // 	    while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }

  1310 // 	  }

  1311 // 	}

  1312 // 	return e;

  1313 //       }

  1316 //     template< typename It >

  1317 //     It first() const {

  1318 //       It e;

  1319 //       first(e);

  1320 //       return e;

  1321 //     }

  1323 //     template< typename It >

  1324 //     It first(Node v) const {

  1325 //       It e;

  1326 //       first(e, v);

  1327 //       return e;

  1328 //     }

  1330     Node tail(Edge e) const {

  1331       return ((e.forward) ? graph->tail(e) : graph->head(e)); }

  1332     Node head(Edge e) const {

  1333       return ((e.forward) ? graph->head(e) : graph->tail(e)); }

  1335     Node aNode(OutEdgeIt e) const {

  1336       return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); }

  1337     Node bNode(OutEdgeIt e) const {

  1338       return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); }

  1340     int nodeNum() const { return graph->nodeNum(); }

  1341     //FIXME

  1342     //int edgeNum() const { return graph->edgeNum(); }

  1345 //    int id(Node v) const { return graph->id(v); }

  1347     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }

  1348     bool valid(Edge e) const {

  1349       return graph->valid(e);

  1350 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in);

  1351     }

  1353     void augment(const Edge& e, Number a) const {

  1354       if (e.forward)

  1355 // 	flow->set(e.out, flow->get(e.out)+a);

  1356 	flow->set(e, (*flow)[e]+a);

  1357       else

  1358 // 	flow->set(e.in, flow->get(e.in)-a);

  1359 	flow->set(e, (*flow)[e]-a);

  1360     }

  1362     Number resCap(const Edge& e) const {

  1363       if (e.forward)

  1364 //	return (capacity->get(e.out)-flow->get(e.out));

  1365 	return ((*capacity)[e]-(*flow)[e]);

  1366       else

  1367 //	return (flow->get(e.in));

  1368 	return ((*flow)[e]);

  1369     }

  1371 //     Number resCap(typename Graph::OutEdgeIt out) const {

  1372 // //      return (capacity->get(out)-flow->get(out));

  1373 //       return ((*capacity)[out]-(*flow)[out]);

  1374 //     }

  1376 //     Number resCap(typename Graph::InEdgeIt in) const {

  1377 // //      return (flow->get(in));

  1378 //       return ((*flow)[in]);

  1379 //     }

  1381 //     template<typename T> class NodeMap : public Graph::NodeMap<T> {

  1382 //     public:

  1383 //       NodeMap(const ResGraphWrapper<Graph, Number, FlovwMap, CapacityMap>& _G)

  1384 // 	: Graph::NodeMap<T>(_G.gw) { }

  1385 //       NodeMap(const ResGraphWrapper<Graph, Number, FlowvMap, CapacityMap>& _G,

  1386 // 	      T a) : Graph::NodeMap<T>(_G.gw, a) { }

  1387 //     };

  1389 //     template <typename T>

  1390 //     class NodeMap {

  1391 //       typename Graph::NodeMap<T> node_map;

  1392 //     public:

  1393 //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }

  1394 //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }

  1395 //       void set(Node nit, T a) { node_map.set(nit, a); }

  1396 //       T get(Node nit) const { return node_map.get(nit); }

  1397 //     };

  1399     template <typename T>

  1400     class EdgeMap {

  1401       typename Graph::EdgeMap<T> forward_map, backward_map;

  1402     public:

  1403       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }

  1404       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }

  1405       void set(Edge e, T a) {

  1406 	if (e.forward)

  1407 	  forward_map.set(e.out, a);

  1408 	else

  1409 	  backward_map.set(e.in, a);

  1410       }

  1411       T operator[](Edge e) const {

  1412 	if (e.forward)

  1413 	  return forward_map[e.out];

  1414 	else

  1415 	  return backward_map[e.in];

  1416       }

  1417 //       T get(Edge e) const {

  1418 // 	if (e.out_or_in)

  1419 // 	  return forward_map.get(e.out);

  1420 // 	else

  1421 // 	  return backward_map.get(e.in);

  1422 //       }

  1423     };

  1424   };

  1428 //   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>

  1429 //   class ResGraphWrapper : public GraphWrapper<Graph> {

  1430 //   protected:

  1431 //     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

  1432 //     typedef typename Graph::InEdgeIt GraphInEdgeIt;

  1433 //     typedef typename Graph::Edge GraphEdge;

  1434 //     FlowMap* flow;

  1435 //     const CapacityMap* capacity;

  1436 //   public:

  1438 //     ResGraphWrapper(Graph& _graph, FlowMap& _flow,

  1439 // 		    const CapacityMap& _capacity) :

  1440 //       GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }

  1442 //     class Edge;

  1443 //     class OutEdgeIt;

  1444 //     friend class Edge;

  1445 //     friend class OutEdgeIt;

  1447 //     typedef typename GraphWrapper<Graph>::Node Node;

  1448 //     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;

  1449 //     class Edge {

  1450 //       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

  1451 //     protected:

  1452 //       bool out_or_in; //true, iff out

  1453 //       GraphOutEdgeIt out;

  1454 //       GraphInEdgeIt in;

  1455 //     public:

  1456 //       Edge() : out_or_in(true) { }

  1457 //       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }

  1458 // //       bool valid() const {

  1459 // // 	return out_or_in && out.valid() || in.valid(); }

  1460 //       friend bool operator==(const Edge& u, const Edge& v) {

  1461 // 	if (v.out_or_in)

  1462 // 	  return (u.out_or_in && u.out==v.out);

  1463 // 	else

  1464 // 	  return (!u.out_or_in && u.in==v.in);

  1465 //       }

  1466 //       friend bool operator!=(const Edge& u, const Edge& v) {

  1467 // 	if (v.out_or_in)

  1468 // 	  return (!u.out_or_in || u.out!=v.out);

  1469 // 	else

  1470 // 	  return (u.out_or_in || u.in!=v.in);

  1471 //       }

  1472 //       operator GraphEdge() const {

  1473 // 	if (out_or_in) return(out); else return(in);

  1474 //       }

  1475 //     };

  1476 //     class OutEdgeIt : public Edge {

  1477 //       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

  1478 //     public:

  1479 //       OutEdgeIt() { }

  1480 //       //FIXME

  1481 //       OutEdgeIt(const Edge& e) : Edge(e) { }

  1482 //       OutEdgeIt(const Invalid& i) : Edge(i) { }

  1483 //       OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {

  1484 // 	resG.graph->first(out, v);

  1485 // 	while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }

  1486 // 	if (!resG.graph->valid(out)) {

  1487 // 	  out_or_in=0;

  1488 // 	  resG.graph->first(in, v);

  1489 // 	  while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }

  1490 // 	}

  1491 //       }

  1492 // //     public:

  1493 // //       OutEdgeIt& operator++() {

  1494 // // 	if (out_or_in) {

  1495 // // 	  Node v=/*resG->*/G->aNode(out);

  1496 // // 	  ++out;

  1497 // // 	  while( out.valid() && !(Edge::resCap()>0) ) { ++out; }

  1498 // // 	  if (!out.valid()) {

  1499 // // 	    out_or_in=0;

  1500 // // 	    G->first(in, v);

  1501 // // 	    while( in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1502 // // 	  }

  1503 // // 	} else {

  1504 // // 	  ++in;

  1505 // // 	  while( in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1506 // // 	}

  1507 // // 	return *this;

  1508 // //       }

  1509 //     };

  1511 //     //FIXME This is just for having InEdgeIt

  1512 // //    class InEdgeIt : public Edge { };

  1514 //     class EdgeIt : public Edge {

  1515 //       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

  1516 //       NodeIt v;

  1517 //     public:

  1518 //       EdgeIt() { }

  1519 //       //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }

  1520 //       EdgeIt(const Invalid& i) : Edge(i) { }

  1521 //       EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {

  1522 // 	resG.graph->first(v);

  1523 // 	if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;

  1524 // 	while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }

  1525 // 	while (resG.graph->valid(v) && !resG.graph->valid(out)) {

  1526 // 	  resG.graph->next(v);

  1527 // 	  if (resG.graph->valid(v)) resG.graph->first(out, v);

  1528 // 	  while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }

  1529 // 	}

  1530 // 	if (!resG.graph->valid(out)) {

  1531 // 	  out_or_in=0;

  1532 // 	  resG.graph->first(v);

  1533 // 	  if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;

  1534 // 	  while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }

  1535 // 	  while (resG.graph->valid(v) && !resG.graph->valid(in)) {

  1536 // 	    resG.graph->next(v);

  1537 // 	    if (resG.graph->valid(v)) resG.graph->first(in, v);

  1538 // 	    while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }

  1539 // 	  }

  1540 // 	}

  1541 //       }

  1542 // //       EdgeIt& operator++() {

  1543 // // 	if (out_or_in) {

  1544 // // 	  ++out;

  1545 // // 	  while (out.valid() && !(Edge::resCap()>0) ) { ++out; }

  1546 // // 	  while (v.valid() && !out.valid()) {

  1547 // // 	    ++v;

  1548 // // 	    if (v.valid()) G->first(out, v);

  1549 // // 	    while (out.valid() && !(Edge::resCap()>0) ) { ++out; }

  1550 // // 	  }

  1551 // // 	  if (!out.valid()) {

  1552 // // 	    out_or_in=0;

  1553 // // 	    G->first(v);

  1554 // // 	    if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();

  1555 // // 	    while (in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1556 // // 	    while (v.valid() && !in.valid()) {

  1557 // // 	      ++v;

  1558 // // 	      if (v.valid()) G->first(in, v);

  1559 // // 	      while (in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1560 // // 	    }

  1561 // // 	  }

  1562 // // 	} else {

  1563 // // 	  ++in;

  1564 // // 	  while (in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1565 // // 	  while (v.valid() && !in.valid()) {

  1566 // // 	    ++v;

  1567 // // 	    if (v.valid()) G->first(in, v);

  1568 // // 	    while (in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1569 // // 	  }

  1570 // // 	}

  1571 // // 	return *this;

  1572 // //       }

  1573 //     };

  1575 //     NodeIt& first(NodeIt& i) const {

  1576 //       i=NodeIt(*this);

  1577 //       return i;

  1578 //     }

  1579 //     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {

  1580 //       i=OutEdgeIt(*this, p);

  1581 //       return i;

  1582 //     }

  1583 //     //FIXME Not yet implemented

  1584 //     //InEdgeIt& first(InEdgeIt& i, const Node& p) const {

  1585 //     //i=InEdgeIt(*this, p);

  1586 //     //  return i;

  1587 //     //}

  1588 //     EdgeIt& first(EdgeIt& e) const {

  1589 //       e=EdgeIt(*this);

  1590 //       return e;

  1591 //     }

  1593 //     NodeIt& next(NodeIt& n) const { graph->next(n); return n; }

  1594 //     OutEdgeIt& next(OutEdgeIt& e) const {

  1595 //       if (e.out_or_in) {

  1596 // 	Node v=graph->aNode(e.out);

  1597 // 	graph->next(e.out);

  1598 // 	while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }

  1599 // 	if (!graph->valid(e.out)) {

  1600 // 	  e.out_or_in=0;

  1601 // 	  graph->first(e.in, v);

  1602 // 	  while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }

  1603 // 	}

  1604 //       } else {

  1605 // 	graph->next(e.in);

  1606 // 	while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }

  1607 //       }

  1608 //       return e;

  1609 //     }

  1610 //     //FIXME Not yet implemented

  1611 //     //InEdgeIt& next(InEdgeIt& e) const {

  1612 //     //  return e;

  1613 //     //}

  1614 //     EdgeIt& next(EdgeIt& e) const {

  1615 //       if (e.out_or_in) {

  1616 // 	graph->next(e.out);

  1617 // 	while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }

  1618 // 	  while (graph->valid(e.v) && !graph->valid(e.out)) {

  1619 // 	    graph->next(e.v);

  1620 // 	    if (graph->valid(e.v)) graph->first(e.out, e.v);

  1621 // 	    while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }

  1622 // 	  }

  1623 // 	  if (!graph->valid(e.out)) {

  1624 // 	    e.out_or_in=0;

  1625 // 	    graph->first(e.v);

  1626 // 	    if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;

  1627 // 	    while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }

  1628 // 	    while (graph->valid(e.v) && !graph->valid(e.in)) {

  1629 // 	      graph->next(e.v);

  1630 // 	      if (graph->valid(e.v)) graph->first(e.in, e.v);

  1631 // 	      while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }

  1632 // 	    }

  1633 // 	  }

  1634 // 	} else {

  1635 // 	  graph->next(e.in);

  1636 // 	  while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }

  1637 // 	  while (graph->valid(e.v) && !graph->valid(e.in)) {

  1638 // 	    graph->next(e.v);

  1639 // 	    if (graph->valid(e.v)) graph->first(e.in, e.v);

  1640 // 	    while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }

  1641 // 	  }

  1642 // 	}

  1643 // 	return e;

  1644 //       }

  1647 //     template< typename It >

  1648 //     It first() const {

  1649 //       It e;

  1650 //       first(e);

  1651 //       return e;

  1652 //     }

  1654 //     template< typename It >

  1655 //     It first(Node v) const {

  1656 //       It e;

  1657 //       first(e, v);

  1658 //       return e;

  1659 //     }

  1661 //     Node tail(Edge e) const {

  1662 //       return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }

  1663 //     Node head(Edge e) const {

  1664 //       return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }

  1666 //     Node aNode(OutEdgeIt e) const {

  1667 //       return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }

  1668 //     Node bNode(OutEdgeIt e) const {

  1669 //       return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }

  1671 //     int nodeNum() const { return graph->nodeNum(); }

  1672 //     //FIXME

  1673 //     //int edgeNum() const { return graph->edgeNum(); }

  1676 //     int id(Node v) const { return graph->id(v); }

  1678 //     bool valid(Node n) const { return graph->valid(n); }

  1679 //     bool valid(Edge e) const {

  1680 //       return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }

  1682 //     void augment(const Edge& e, Number a) const {

  1683 //       if (e.out_or_in)

  1684 // // 	flow->set(e.out, flow->get(e.out)+a);

  1685 // 	flow->set(e.out, (*flow)[e.out]+a);

  1686 //       else

  1687 // // 	flow->set(e.in, flow->get(e.in)-a);

  1688 // 	flow->set(e.in, (*flow)[e.in]-a);

  1689 //     }

  1691 //     Number resCap(const Edge& e) const {

  1692 //       if (e.out_or_in)

  1693 // //	return (capacity->get(e.out)-flow->get(e.out));

  1694 // 	return ((*capacity)[e.out]-(*flow)[e.out]);

  1695 //       else

  1696 // //	return (flow->get(e.in));

  1697 // 	return ((*flow)[e.in]);

  1698 //     }

  1700 //     Number resCap(GraphOutEdgeIt out) const {

  1701 // //      return (capacity->get(out)-flow->get(out));

  1702 //       return ((*capacity)[out]-(*flow)[out]);

  1703 //     }

  1705 //     Number resCap(GraphInEdgeIt in) const {

  1706 // //      return (flow->get(in));

  1707 //       return ((*flow)[in]);

  1708 //     }

  1710 // //     template<typename T> class NodeMap : public Graph::NodeMap<T> {

  1711 // //     public:

  1712 // //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)

  1713 // // 	: Graph::NodeMap<T>(_G.gw) { }

  1714 // //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,

  1715 // // 	      T a) : Graph::NodeMap<T>(_G.gw, a) { }

  1716 // //     };

  1718 // //     template <typename T>

  1719 // //     class NodeMap {

  1720 // //       typename Graph::NodeMap<T> node_map;

  1721 // //     public:

  1722 // //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }

  1723 // //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }

  1724 // //       void set(Node nit, T a) { node_map.set(nit, a); }

  1725 // //       T get(Node nit) const { return node_map.get(nit); }

  1726 // //     };

  1728 //     template <typename T>

  1729 //     class EdgeMap {

  1730 //       typename Graph::EdgeMap<T> forward_map, backward_map;

  1731 //     public:

  1732 //       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }

  1733 //       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }

  1734 //       void set(Edge e, T a) {

  1735 // 	if (e.out_or_in)

  1736 // 	  forward_map.set(e.out, a);

  1737 // 	else

  1738 // 	  backward_map.set(e.in, a);

  1739 //       }

  1740 //       T operator[](Edge e) const {

  1741 // 	if (e.out_or_in)

  1742 // 	  return forward_map[e.out];

  1743 // 	else

  1744 // 	  return backward_map[e.in];

  1745 //       }

  1746 // //       T get(Edge e) const {

  1747 // // 	if (e.out_or_in)

  1748 // // 	  return forward_map.get(e.out);

  1749 // // 	else

  1750 // // 	  return backward_map.get(e.in);

  1751 // //       }

  1752 //     };

  1753 //   };

  1756   //ErasingFirstGraphWrapper for blocking flows

  1757   template<typename Graph, typename FirstOutEdgesMap>

  1758   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {

  1759   protected:

  1760     FirstOutEdgesMap* first_out_edges;

  1761   public:

  1762     ErasingFirstGraphWrapper(Graph& _graph,

  1763 			     FirstOutEdgesMap& _first_out_edges) :

  1764       GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }

  1766     typedef typename GraphWrapper<Graph>::Node Node;

  1767     class NodeIt {

  1768       friend class GraphWrapper<Graph>;

  1769       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

  1770       typename Graph::NodeIt n;

  1771      public:

  1772       NodeIt() { }

  1773       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }

  1774       NodeIt(const Invalid& i) : n(i) { }

  1775       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :

  1776 	n(*(_G.graph)) { }

  1777       operator Node() const { return Node(typename Graph::Node(n)); }

  1778     };

  1779     typedef typename GraphWrapper<Graph>::Edge Edge;

  1780     class OutEdgeIt {

  1781       friend class GraphWrapper<Graph>;

  1782       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

  1783 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

  1784       typename Graph::OutEdgeIt e;

  1785     public:

  1786       OutEdgeIt() { }

  1787       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }

  1788       OutEdgeIt(const Invalid& i) : e(i) { }

  1789       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,

  1790 		const Node& _n) :

  1791 	e((*_G.first_out_edges)[_n]) { }

  1792       operator Edge() const { return Edge(typename Graph::Edge(e)); }

  1793     };

  1794     class InEdgeIt {

  1795       friend class GraphWrapper<Graph>;

  1796       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

  1797 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

  1798       typename Graph::InEdgeIt e;

  1799     public:

  1800       InEdgeIt() { }

  1801       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }

  1802       InEdgeIt(const Invalid& i) : e(i) { }

  1803       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,

  1804 	       const Node& _n) :

  1805 	e(*(_G.graph), typename Graph::Node(_n)) { }

  1806       operator Edge() const { return Edge(typename Graph::Edge(e)); }

  1807     };

  1808     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1809     class EdgeIt {

  1810       friend class GraphWrapper<Graph>;

  1811       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

  1812 //      typedef typename Graph::EdgeIt GraphEdgeIt;

  1813       typename Graph::EdgeIt e;

  1814     public:

  1815       EdgeIt() { }

  1816       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }

  1817       EdgeIt(const Invalid& i) : e(i) { }

  1818       EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :

  1819 	e(*(_G.graph)) { }

  1820       operator Edge() const { return Edge(typename Graph::Edge(e)); }

  1821     };

  1823     NodeIt& first(NodeIt& i) const {

  1824       i=NodeIt(*this); return i;

  1825     }

  1826     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {

  1827       i=OutEdgeIt(*this, p); return i;

  1828     }

  1829     InEdgeIt& first(InEdgeIt& i, const Node& p) const {

  1830       i=InEdgeIt(*this, p); return i;

  1831     }

  1832     EdgeIt& first(EdgeIt& i) const {

  1833       i=EdgeIt(*this); return i;

  1834     }

  1836 //     template<typename I> I& first(I& i) const {

  1837 //       graph->first(i);

  1838 //       return i;

  1839 //     }

  1840 //     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {

  1841 // //      e=first_out_edges->get(n);

  1842 //       e=(*first_out_edges)[n];

  1843 //       return e;

  1844 //     }

  1845 //     template<typename I, typename P> I& first(I& i, const P& p) const {

  1846 //       graph->first(i, p);

  1847 //       return i;

  1848 //     }

  1850     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }

  1851     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }

  1852     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }

  1853     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }

  1855     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }

  1856     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }

  1857     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }

  1858     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }

  1860 //     template<typename I> I& next(I &i) const {

  1861 //       graph->next(i);

  1862 //       return i;

  1863 //     }

  1865 //     template< typename It > It first() const {

  1866 //       It e; this->first(e); return e; }

  1868 //     template< typename It > It first(const Node& v) const {

  1869 //       It e; this->first(e, v); return e; }

  1871     void erase(const OutEdgeIt& e) const {

  1872       OutEdgeIt f=e;

  1873       this->next(f);

  1874       first_out_edges->set(this->tail(e), f.e);

  1875     }

  1876   };

  1878 //   //ErasingFirstGraphWrapper for blocking flows

  1879 //   template<typename Graph, typename FirstOutEdgesMap>

  1880 //   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {

  1881 //   protected:

  1882 //     FirstOutEdgesMap* first_out_edges;

  1883 //   public:

  1884 //     ErasingFirstGraphWrapper(Graph& _graph,

  1885 // 			     FirstOutEdgesMap& _first_out_edges) :

  1886 //       GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }

  1888 //     typedef typename Graph::Node Node;

  1889 //     class NodeIt : public Graph::NodeIt {

  1890 //     public:

  1891 //       NodeIt() { }

  1892 //       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }

  1893 //       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }

  1894 //       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :

  1895 // 	Graph::NodeIt(*(_G.graph)) { }

  1896 //     };

  1897 //     typedef typename Graph::Edge Edge;

  1898 //     class OutEdgeIt : public Graph::OutEdgeIt {

  1899 //     public:

  1900 //       OutEdgeIt() { }

  1901 //       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }

  1902 //       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }

  1903 //       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,

  1904 // 		const Node& n) :

  1905 // 	Graph::OutEdgeIt((*_G.first_out_edges)[n]) { }

  1906 //     };

  1907 //     class InEdgeIt : public Graph::InEdgeIt {

  1908 //     public:

  1909 //       InEdgeIt() { }

  1910 //       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }

  1911 //       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }

  1912 //       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,

  1913 // 	       const Node& n) :

  1914 // 	Graph::InEdgeIt(*(_G.graph), n) { }

  1915 //     };

  1916 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1917 //     class EdgeIt : public Graph::EdgeIt {

  1918 //     public:

  1919 //       EdgeIt() { }

  1920 //       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }

  1921 //       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }

  1922 //       EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :

  1923 // 	Graph::EdgeIt(*(_G.graph)) { }

  1924 //     };

  1926 //     NodeIt& first(NodeIt& i) const {

  1927 //       i=NodeIt(*this);

  1928 //       return i;

  1929 //     }

  1930 //     OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {

  1931 //       i=OutEdgeIt(*this, n);

  1932 // //      i=(*first_out_edges)[n];

  1933 //       return i;

  1934 //     }

  1935 //     InEdgeIt& first(InEdgeIt& i, const Node& n) const {

  1936 //       i=InEdgeIt(*this, n);

  1937 //       return i;

  1938 //     }

  1939 //     EdgeIt& first(EdgeIt& i) const {

  1940 //       i=EdgeIt(*this);

  1941 //       return i;

  1942 //     }

  1944 // //     template<typename I> I& first(I& i) const {

  1945 // //       graph->first(i);

  1946 // //       return i;

  1947 // //     }

  1948 // //     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {

  1949 // // //      e=first_out_edges->get(n);

  1950 // //       e=(*first_out_edges)[n];

  1951 // //       return e;

  1952 // //     }

  1953 // //     template<typename I, typename P> I& first(I& i, const P& p) const {

  1954 // //       graph->first(i, p);

  1955 // //       return i;

  1956 // //     }

  1958 //     NodeIt& next(NodeIt& i) const {

  1959 //       graph->next(i);

  1960 //       return i;

  1961 //     }

  1962 //     OutEdgeIt& next(OutEdgeIt& i) const {

  1963 //       graph->next(i);

  1964 //       return i;

  1965 //     }

  1966 //     InEdgeIt& next(InEdgeIt& i) const {

  1967 //       graph->next(i);

  1968 //       return i;

  1969 //     }

  1970 //     EdgeIt& next(EdgeIt& i) const {

  1971 //       graph->next(i);

  1972 //       return i;

  1973 //     }

  1975 // //     template<typename I> I& next(I &i) const {

  1976 // //       graph->next(i);

  1977 // //       return i;

  1978 // //     }

  1980 //     template< typename It > It first() const {

  1981 //       It e; this->first(e); return e; }

  1983 //     template< typename It > It first(const Node& v) const {

  1984 //       It e; this->first(e, v); return e; }

  1986 //     void erase(const OutEdgeIt& e) const {

  1987 //       OutEdgeIt f=e;

  1988 //       this->next(f);

  1989 //       first_out_edges->set(this->tail(e), f);

  1990 //     }

  1991 //   };

  1994 // // FIXME: comparison should be made better!!!

  1995 //   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>

  1996 //   class ResGraphWrapper

  1997 //   {

  1998 //     Graph* graph;

  2000 //   public:

  2001 //     typedef Graph ParentGraph;

  2003 //     typedef typename Graph::Node Node;

  2004 //     typedef typename Graph::Edge Edge;

  2006 //     typedef typename Graph::NodeIt NodeIt;

  2008 //     class OutEdgeIt {

  2009 //     public:

  2010 //       //Graph::Node n;

  2011 //       bool out_or_in;

  2012 //       typename Graph::OutEdgeIt o;

  2013 //       typename Graph::InEdgeIt i;

  2014 //     };

  2015 //     class InEdgeIt {

  2016 //     public:

  2017 //       //Graph::Node n;

  2018 //       bool out_or_in;

  2019 //       typename Graph::OutEdgeIt o;

  2020 //       typename Graph::InEdgeIt i;

  2021 //     };

  2022 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

  2023 //     typedef typename Graph::EdgeIt EdgeIt;

  2025 //     int nodeNum() const { return gw.nodeNum(); }

  2026 //     int edgeNum() const { return gw.edgeNum(); }

  2028 //     Node& first(Node& n) const { return gw.first(n); }

  2030 //     // Edge and SymEdge  is missing!!!!

  2031 //     // Edge <-> In/OutEdgeIt conversion is missing!!!!

  2033 //     //FIXME

  2034 //     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const

  2035 //       {

  2036 // 	e.n=n;

  2037 // 	gw.first(e.o,n);

  2038 // 	while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))

  2039 // 	  gw.goNext(e.o);

  2040 // 	if(!gw.valid(e.o)) {

  2041 // 	  gw.first(e.i,n);

  2042 // 	  while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))

  2043 // 	    gw.goNext(e.i);

  2044 // 	}

  2045 // 	return e;

  2046 //       }

  2047 // /*

  2048 //   OutEdgeIt &goNext(OutEdgeIt &e)

  2049 //   {

  2050 //   if(gw.valid(e.o)) {

  2051 //   while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))

  2052 //   gw.goNext(e.o);

  2053 //   if(gw.valid(e.o)) return e;

  2054 //   else gw.first(e.i,e.n);

  2055 //   }

  2056 //   else {

  2057 //   while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))

  2058 //   gw.goNext(e.i);

  2059 //   return e;

  2060 //   }

  2061 //   }

  2062 //   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}

  2063 // */

  2064 //     //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);}

  2066 //     //FIXME

  2067 //     InEdgeIt& first(InEdgeIt& e, const Node& n) const

  2068 //       {

  2069 // 	e.n=n;

  2070 // 	gw.first(e.i,n);

  2071 // 	while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))

  2072 // 	  gw.goNext(e.i);

  2073 // 	if(!gw.valid(e.i)) {

  2074 // 	  gw.first(e.o,n);

  2075 // 	  while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))

  2076 // 	    gw.goNext(e.o);

  2077 // 	}

  2078 // 	return e;

  2079 //       }

  2080 // /*

  2081 //   InEdgeIt &goNext(InEdgeIt &e)

  2082 //   {

  2083 //   if(gw.valid(e.i)) {

  2084 //   while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))

  2085 //   gw.goNext(e.i);

  2086 //   if(gw.valid(e.i)) return e;

  2087 //   else gw.first(e.o,e.n);

  2088 //   }

  2089 //   else {

  2090 //   while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))

  2091 //   gw.goNext(e.o);

  2092 //   return e;

  2093 //   }

  2094 //   }

  2095 //   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}

  2096 // */

  2097 //     //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);}

  2099 //     //template<typename I> I &goNext(I &i); { return gw.goNext(i); }

  2100 //     //template<typename I> I next(const I i); { return gw.goNext(i); }

  2102 //     template< typename It > It first() const {

  2103 //       It e; first(e); return e; }

  2105 //     template< typename It > It first(Node v) const {

  2106 //       It e; first(e, v); return e; }

  2108 //     Node head(const Edge& e) const { return gw.head(e); }

  2109 //     Node tail(const Edge& e) const { return gw.tail(e); }

  2111 //     template<typename I> Node aNode(const I& e) const {

  2112 //       return gw.aNode(e); }

  2113 //     template<typename I> Node bNode(const I& e) const {

  2114 //       return gw.bNode(e); }

  2116 //     //template<typename I> bool valid(const I i);

  2117 //     //{ return gw.valid(i); }

  2119 //     //template<typename I> void setInvalid(const I &i);

  2120 //     //{ return gw.setInvalid(i); }

  2122 //     Node addNode() { return gw.addNode(); }

  2123 //     Edge addEdge(const Node& tail, const Node& head) {

  2124 //       return gw.addEdge(tail, head); }

  2126 //     template<typename I> void erase(const I& i) { gw.erase(i); }

  2128 //     void clear() { gw.clear(); }

  2130 //     template<typename S> class NodeMap : public Graph::NodeMap<S> { };

  2131 //     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };

  2133 //     void setGraph(Graph& _graph) { graph = &_graph; }

  2134 //     Graph& getGraph() { return (*graph); }

  2136 //     //ResGraphWrapper() : graph(0) { }

  2137 //     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }

  2138 //   };

  2140 } //namespace hugo

  2142 #endif //HUGO_GRAPH_WRAPPER_H

author	marci
	Fri, 16 Apr 2004 08:26:00 +0000
changeset 335	999eb3cd7b49
parent 330	7ac0d4e8a31c
child 338	e8725f30dd98
permissions	-rw-r--r--