src/hugo/graph_wrapper.h
author marci
Mon, 10 May 2004 16:32:21 +0000
changeset 598 1faa5bec1717
parent 593 b83b36ee7f10
child 612 0856a9a87eb9
permissions -rw-r--r--
complete graphs
     1 // -*- c++ -*-
     2 #ifndef HUGO_GRAPH_WRAPPER_H
     3 #define HUGO_GRAPH_WRAPPER_H
     4 
     5 ///\ingroup gwrappers
     6 ///\file
     7 ///\brief Several graph wrappers.
     8 ///
     9 ///This file contains several useful graph wrapper functions.
    10 ///
    11 ///\author Marton Makai
    12 
    13 #include <hugo/invalid.h>
    14 //#include <iter_map.h>
    15 
    16 namespace hugo {
    17 
    18   // Graph wrappers
    19 
    20   /// \addtogroup gwrappers
    21   /// A main parts of HUGOlib are the different graph structures, 
    22   /// generic graph algorithms, graph concepts which couple these, and 
    23   /// graph wrappers. While the previous ones are more or less clear, the 
    24   /// latter notion needs further explanation.
    25   /// Graph wrappers are graph classes which serve for considering graph 
    26   /// structures in different ways. A short example makes the notion much 
    27   /// clearer. 
    28   /// Suppose that we have an instance \c g of a directed graph
    29   /// type say \c ListGraph and an algorithm 
    30   /// \code template<typename Graph> int algorithm(const Graph&); \endcode 
    31   /// is needed to run on the reversely oriented graph. 
    32   /// It may be expensive (in time or in memory usage) to copy 
    33   /// \c g with the reverse orientation. 
    34   /// Thus, a wrapper class
    35   /// \code template<typename Graph> class RevGraphWrapper; \endcode is used. 
    36   /// The code looks as follows
    37   /// \code
    38   /// ListGraph g;
    39   /// RevGraphWrapper<ListGraph> rgw(g);
    40   /// int result=algorithm(rgw);
    41   /// \endcode
    42   /// After running the algorithm, the original graph \c g 
    43   /// remains untouched. Thus the graph wrapper used above is to consider the 
    44   /// original graph with reverse orientation. 
    45   /// This techniques gives rise to an elegant code, and 
    46   /// based on stable graph wrappers, complex algorithms can be 
    47   /// implemented easily. 
    48   /// In flow, circulation and bipartite matching problems, the residual 
    49   /// graph is of particular importance. Combining a wrapper implementing 
    50   /// this, shortest path algorithms and minimum mean cycle algorithms, 
    51   /// a range of weighted and cardinality optimization algorithms can be 
    52   /// obtained. For lack of space, for other examples, 
    53   /// the interested user is referred to the detailed documentation of graph 
    54   /// wrappers. 
    55   /// The behavior of graph wrappers can be very different. Some of them keep 
    56   /// capabilities of the original graph while in other cases this would be 
    57   /// meaningless. This means that the concepts that they are a model of depend 
    58   /// on the graph wrapper, and the wrapped graph(s). 
    59   /// If an edge of \c rgw is deleted, this is carried out by 
    60   /// deleting the corresponding edge of \c g. But for a residual 
    61   /// graph, this operation has no sense. 
    62   /// Let we stand one more example here to simplify your work. 
    63   /// wrapper class
    64   /// \code template<typename Graph> class RevGraphWrapper; \endcode 
    65   /// has constructor 
    66   /// <tt> RevGraphWrapper(Graph& _g)</tt>. 
    67   /// This means that in a situation, 
    68   /// when a <tt> const ListGraph& </tt> reference to a graph is given, 
    69   /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
    70   /// \code
    71   /// int algorithm1(const ListGraph& g) {
    72   ///   RevGraphWrapper<const ListGraph> rgw(g);
    73   ///   return algorithm2(rgw);
    74   /// }
    75   /// \endcode
    76 
    77   /// \addtogroup gwrappers
    78   /// @{
    79 
    80   ///Base type for the Graph Wrappers
    81 
    82   ///This is the base type for the Graph Wrappers.
    83   ///\todo Some more docs... 
    84   ///
    85   ///\author Marton Makai
    86  
    87   template<typename Graph>
    88   class GraphWrapper {
    89   protected:
    90     Graph* graph;
    91     GraphWrapper() : graph(0) { }
    92     void setGraph(Graph& _graph) { graph=&_graph; }
    93 
    94   public:
    95     typedef Graph BaseGraph;
    96     typedef Graph ParentGraph;
    97 
    98     GraphWrapper(Graph& _graph) : graph(&_graph) { }
    99 //     Graph& getGraph() const { return *graph; }
   100  
   101 //    typedef typename Graph::Node Node;
   102     class Node : public Graph::Node {
   103       friend class GraphWrapper<Graph>;
   104     public:
   105       Node() { }
   106       Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
   107       Node(const Invalid& i) : Graph::Node(i) { }
   108     };
   109     class NodeIt { 
   110       friend class GraphWrapper<Graph>;
   111       typename Graph::NodeIt n;
   112      public:
   113       NodeIt() { }
   114       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
   115       NodeIt(const Invalid& i) : n(i) { }
   116       NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
   117       operator Node() const { return Node(typename Graph::Node(n)); }
   118     };
   119 //    typedef typename Graph::Edge Edge;
   120     class Edge : public Graph::Edge {
   121       friend class GraphWrapper<Graph>;
   122     public:
   123       Edge() { }
   124       Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
   125       Edge(const Invalid& i) : Graph::Edge(i) { }
   126     };
   127     class OutEdgeIt { 
   128       friend class GraphWrapper<Graph>;
   129       typename Graph::OutEdgeIt e;
   130     public:
   131       OutEdgeIt() { }
   132       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
   133       OutEdgeIt(const Invalid& i) : e(i) { }
   134       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
   135 	e(*(_G.graph), typename Graph::Node(_n)) { }
   136       operator Edge() const { return Edge(typename Graph::Edge(e)); }
   137     };
   138     class InEdgeIt { 
   139       friend class GraphWrapper<Graph>;
   140       typename Graph::InEdgeIt e;
   141     public:
   142       InEdgeIt() { }
   143       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
   144       InEdgeIt(const Invalid& i) : e(i) { }
   145       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
   146 	e(*(_G.graph), typename Graph::Node(_n)) { }
   147       operator Edge() const { return Edge(typename Graph::Edge(e)); }
   148     };
   149     //typedef typename Graph::SymEdgeIt SymEdgeIt;
   150     class EdgeIt { 
   151       friend class GraphWrapper<Graph>;
   152       typename Graph::EdgeIt e;
   153     public:
   154       EdgeIt() { }
   155       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
   156       EdgeIt(const Invalid& i) : e(i) { }
   157       EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
   158       operator Edge() const { return Edge(typename Graph::Edge(e)); }
   159     };
   160    
   161     NodeIt& first(NodeIt& i) const { 
   162       i=NodeIt(*this); return i;
   163     }
   164     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
   165       i=OutEdgeIt(*this, p); return i;
   166     }
   167     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
   168       i=InEdgeIt(*this, p); return i;
   169     }
   170     EdgeIt& first(EdgeIt& i) const { 
   171       i=EdgeIt(*this); return i;
   172     }
   173 
   174     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
   175     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
   176     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
   177     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }    
   178 
   179     Node tail(const Edge& e) const { 
   180       return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
   181     Node head(const Edge& e) const { 
   182       return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
   183 
   184     bool valid(const Node& n) const { 
   185       return graph->valid(static_cast<typename Graph::Node>(n)); }
   186     bool valid(const Edge& e) const { 
   187       return graph->valid(static_cast<typename Graph::Edge>(e)); }
   188 
   189     int nodeNum() const { return graph->nodeNum(); }
   190     int edgeNum() const { return graph->edgeNum(); }
   191   
   192     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
   193     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
   194     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
   195     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
   196   
   197     Node addNode() const { return Node(graph->addNode()); }
   198     Edge addEdge(const Node& tail, const Node& head) const { 
   199       return Edge(graph->addEdge(tail, head)); }
   200 
   201     void erase(const Node& i) const { graph->erase(i); }
   202     void erase(const Edge& i) const { graph->erase(i); }
   203   
   204     void clear() const { graph->clear(); }
   205     
   206     template<typename T> class NodeMap : public Graph::template NodeMap<T> { 
   207       typedef typename Graph::template NodeMap<T> Parent;
   208     public:
   209       NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }
   210       NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
   211     };
   212 
   213     template<typename T> class EdgeMap : public Graph::template EdgeMap<T> { 
   214       typedef typename Graph::template EdgeMap<T> Parent;
   215     public:
   216       EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
   217       EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
   218     };
   219   };
   220 
   221 
   222 
   223   /// A graph wrapper which reverses the orientation of the edges.
   224 
   225   /// A graph wrapper which reverses the orientation of the edges.
   226   ///
   227   ///\author Marton Makai
   228   template<typename Graph>
   229   class RevGraphWrapper : public GraphWrapper<Graph> {
   230   protected:
   231     RevGraphWrapper() : GraphWrapper<Graph>(0) { }
   232   public:
   233     RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  
   234 
   235     typedef typename GraphWrapper<Graph>::Node Node;
   236     typedef typename GraphWrapper<Graph>::Edge Edge;
   237     //If Graph::OutEdgeIt is not defined
   238     //and we do not want to use RevGraphWrapper::InEdgeIt,
   239     //the typdef techinque does not work.
   240     //Unfortunately all the typedefs are instantiated in templates.
   241     //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
   242     //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
   243 
   244     class OutEdgeIt { 
   245       friend class GraphWrapper<Graph>;
   246       friend class RevGraphWrapper<Graph>;
   247       typename Graph::InEdgeIt e;
   248     public:
   249       OutEdgeIt() { }
   250       OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
   251       OutEdgeIt(const Invalid& i) : e(i) { }
   252       OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
   253 	e(*(_G.graph), typename Graph::Node(_n)) { }
   254       operator Edge() const { return Edge(typename Graph::Edge(e)); }
   255     };
   256     class InEdgeIt { 
   257       friend class GraphWrapper<Graph>;
   258       friend class RevGraphWrapper<Graph>;
   259       typename Graph::OutEdgeIt e;
   260     public:
   261       InEdgeIt() { }
   262       InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
   263       InEdgeIt(const Invalid& i) : e(i) { }
   264       InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
   265 	e(*(_G.graph), typename Graph::Node(_n)) { }
   266       operator Edge() const { return Edge(typename Graph::Edge(e)); }
   267     };
   268 
   269     using GraphWrapper<Graph>::first;
   270     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
   271       i=OutEdgeIt(*this, p); return i;
   272     }
   273     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
   274       i=InEdgeIt(*this, p); return i;
   275     }
   276 
   277     using GraphWrapper<Graph>::next;
   278     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
   279     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
   280 
   281     Node aNode(const OutEdgeIt& e) const { 
   282       return Node(this->graph->aNode(e.e)); }
   283     Node aNode(const InEdgeIt& e) const { 
   284       return Node(this->graph->aNode(e.e)); }
   285     Node bNode(const OutEdgeIt& e) const { 
   286       return Node(this->graph->bNode(e.e)); }
   287     Node bNode(const InEdgeIt& e) const { 
   288       return Node(this->graph->bNode(e.e)); }
   289 
   290     Node tail(const Edge& e) const { 
   291       return GraphWrapper<Graph>::head(e); }
   292     Node head(const Edge& e) const { 
   293       return GraphWrapper<Graph>::tail(e); }
   294 
   295   };
   296 
   297 
   298 
   299   /// Wrapper for hiding nodes and edges from a graph.
   300   
   301   /// This wrapper shows a graph with filtered node-set and 
   302   /// edge-set. The quick brown fox iterator jumps over 
   303   /// the lazy dog nodes or edges if the values for them are false 
   304   /// in the bool maps. 
   305   ///
   306   ///\author Marton Makai
   307   template<typename Graph, typename NodeFilterMap, 
   308 	   typename EdgeFilterMap>
   309   class SubGraphWrapper : public GraphWrapper<Graph> {
   310   protected:
   311     NodeFilterMap* node_filter_map;
   312     EdgeFilterMap* edge_filter_map;
   313 
   314     SubGraphWrapper() : GraphWrapper<Graph>(0), 
   315 			node_filter_map(0), edge_filter_map(0) { }
   316     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
   317       node_filter_map=&_node_filter_map;
   318     }
   319     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
   320       edge_filter_map=&_edge_filter_map;
   321     }
   322     
   323   public:
   324 
   325     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, 
   326 		    EdgeFilterMap& _edge_filter_map) : 
   327       GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), 
   328       edge_filter_map(&_edge_filter_map) { }  
   329 
   330     typedef typename GraphWrapper<Graph>::Node Node;
   331     class NodeIt { 
   332       friend class GraphWrapper<Graph>;
   333       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
   334       typename Graph::NodeIt n;
   335      public:
   336       NodeIt() { }
   337       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
   338       NodeIt(const Invalid& i) : n(i) { }
   339       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
   340 	n(*(_G.graph)) { 
   341 	while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n]) 
   342 	  _G.graph->next(n);
   343       }
   344       operator Node() const { return Node(typename Graph::Node(n)); }
   345     };
   346     typedef typename GraphWrapper<Graph>::Edge Edge;
   347     class OutEdgeIt { 
   348       friend class GraphWrapper<Graph>;
   349       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
   350       typename Graph::OutEdgeIt e;
   351     public:
   352       OutEdgeIt() { }
   353       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
   354       OutEdgeIt(const Invalid& i) : e(i) { }
   355       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
   356 		const Node& _n) : 
   357 	e(*(_G.graph), typename Graph::Node(_n)) { 
   358       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
   359 	  _G.graph->next(e);
   360       }
   361       operator Edge() const { return Edge(typename Graph::Edge(e)); }
   362     };
   363     class InEdgeIt { 
   364       friend class GraphWrapper<Graph>;
   365       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
   366       typename Graph::InEdgeIt e;
   367     public:
   368       InEdgeIt() { }
   369       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
   370       InEdgeIt(const Invalid& i) : e(i) { }
   371       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
   372 	       const Node& _n) : 
   373 	e(*(_G.graph), typename Graph::Node(_n)) { 
   374       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
   375 	  _G.graph->next(e);
   376       }
   377       operator Edge() const { return Edge(typename Graph::Edge(e)); }
   378     };
   379     //typedef typename Graph::SymEdgeIt SymEdgeIt;
   380     class EdgeIt { 
   381       friend class GraphWrapper<Graph>;
   382       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
   383       typename Graph::EdgeIt e;
   384     public:
   385       EdgeIt() { }
   386       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
   387       EdgeIt(const Invalid& i) : e(i) { }
   388       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
   389 	e(*(_G.graph)) { 
   390       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
   391 	  _G.graph->next(e);
   392       }
   393       operator Edge() const { return Edge(typename Graph::Edge(e)); }
   394     };
   395 
   396     NodeIt& first(NodeIt& i) const { 
   397       i=NodeIt(*this); return i;
   398     }
   399     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
   400       i=OutEdgeIt(*this, p); return i;
   401     }
   402     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
   403       i=InEdgeIt(*this, p); return i;
   404     }
   405     EdgeIt& first(EdgeIt& i) const { 
   406       i=EdgeIt(*this); return i;
   407     }
   408     
   409     NodeIt& next(NodeIt& i) const {
   410       this->graph->next(i.n); 
   411       while (this->graph->valid(i) && !(*node_filter_map)[i.n]) { 
   412 	this->graph->next(i.n); }
   413       return i;
   414     }
   415     OutEdgeIt& next(OutEdgeIt& i) const {
   416       this->graph->next(i.e); 
   417       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
   418 	this->graph->next(i.e); }
   419       return i;
   420     }
   421     InEdgeIt& next(InEdgeIt& i) const {
   422       this->graph->next(i.e); 
   423       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
   424 	this->graph->next(i.e); }
   425       return i;
   426     }
   427     EdgeIt& next(EdgeIt& i) const {
   428       this->graph->next(i.e); 
   429       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
   430 	this->graph->next(i.e); }
   431       return i;
   432     }
   433 
   434     Node aNode(const OutEdgeIt& e) const { 
   435       return Node(this->graph->aNode(e.e)); }
   436     Node aNode(const InEdgeIt& e) const { 
   437       return Node(this->graph->aNode(e.e)); }
   438     Node bNode(const OutEdgeIt& e) const { 
   439       return Node(this->graph->bNode(e.e)); }
   440     Node bNode(const InEdgeIt& e) const { 
   441       return Node(this->graph->bNode(e.e)); }
   442 
   443     /// This function hides \c n in the graph, i.e. the iteration 
   444     /// jumps over it. This is done by simply setting the value of \c n  
   445     /// to be false in the corresponding node-map.
   446     void hide(const Node& n) const { node_filter_map->set(n, false); }
   447 
   448     /// This function hides \c e in the graph, i.e. the iteration 
   449     /// jumps over it. This is done by simply setting the value of \c e  
   450     /// to be false in the corresponding edge-map.
   451     void hide(const Edge& e) const { edge_filter_map->set(e, false); }
   452 
   453     /// The value of \c n is set to be true in the node-map which stores 
   454     /// hide information. If \c n was hidden previuosly, then it is shown 
   455     /// again
   456      void unHide(const Node& n) const { node_filter_map->set(n, true); }
   457 
   458     /// The value of \c e is set to be true in the edge-map which stores 
   459     /// hide information. If \c e was hidden previuosly, then it is shown 
   460     /// again
   461     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
   462 
   463     /// Returns true if \c n is hidden.
   464     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
   465 
   466     /// Returns true if \c n is hidden.
   467     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
   468 
   469     /// This is a linear time operation and works only if 
   470     /// NodeIt is defined.
   471     int nodeNum() const { 
   472       int i=0;
   473       NodeIt n;
   474       for (this->first(n); this->valid(n); this->next(n)) ++i;
   475       return i; 
   476     }
   477 
   478     /// This is a linear time operation and works only if 
   479     /// EdgeIt is defined.
   480     int edgeNum() const { 
   481       int i=0;
   482       EdgeIt e;
   483       for (this->first(e); this->valid(e); this->next(e)) ++i;
   484       return i; 
   485     }
   486 
   487   };
   488 
   489 
   490 
   491   /// A wrapper for forgetting the orientation of a graph.
   492 
   493   /// A wrapper for getting an undirected graph by forgetting
   494   /// the orientation of a directed one.
   495   ///
   496   ///\author Marton Makai
   497   template<typename Graph>
   498   class UndirGraphWrapper : public GraphWrapper<Graph> {
   499   protected:
   500     UndirGraphWrapper() : GraphWrapper<Graph>() { }
   501     
   502   public:
   503     typedef typename GraphWrapper<Graph>::Node Node;
   504     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
   505     typedef typename GraphWrapper<Graph>::Edge Edge;
   506     typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
   507 
   508     UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  
   509 
   510     class OutEdgeIt {
   511       friend class UndirGraphWrapper<Graph>;
   512       bool out_or_in; //true iff out
   513       typename Graph::OutEdgeIt out;
   514       typename Graph::InEdgeIt in;
   515     public:
   516       OutEdgeIt() { }
   517       OutEdgeIt(const Invalid& i) : Edge(i) { }
   518       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
   519 	out_or_in=true; _G.graph->first(out, _n);
   520 	if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);	}
   521       } 
   522       operator Edge() const { 
   523 	if (out_or_in) return Edge(out); else return Edge(in); 
   524       }
   525     };
   526 
   527 //FIXME InEdgeIt
   528     typedef OutEdgeIt InEdgeIt; 
   529 
   530     using GraphWrapper<Graph>::first;
   531 //     NodeIt& first(NodeIt& i) const { 
   532 //       i=NodeIt(*this); return i;
   533 //     }
   534     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
   535       i=OutEdgeIt(*this, p); return i;
   536     }
   537 //FIXME
   538 //     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
   539 //       i=InEdgeIt(*this, p); return i;
   540 //     }
   541 //     EdgeIt& first(EdgeIt& i) const { 
   542 //       i=EdgeIt(*this); return i;
   543 //     }
   544 
   545     using GraphWrapper<Graph>::next;
   546 //     NodeIt& next(NodeIt& n) const {
   547 //       GraphWrapper<Graph>::next(n);
   548 //       return n;
   549 //     }
   550     OutEdgeIt& next(OutEdgeIt& e) const {
   551       if (e.out_or_in) {
   552 	typename Graph::Node n=this->graph->tail(e.out);
   553 	this->graph->next(e.out);
   554 	if (!this->graph->valid(e.out)) { 
   555 	  e.out_or_in=false; this->graph->first(e.in, n); }
   556       } else {
   557 	this->graph->next(e.in);
   558       }
   559       return e;
   560     }
   561     //FIXME InEdgeIt
   562 //     EdgeIt& next(EdgeIt& e) const {
   563 //       GraphWrapper<Graph>::next(n);
   564 // //      graph->next(e.e);
   565 //       return e;
   566 //     }
   567 
   568     Node aNode(const OutEdgeIt& e) const { 
   569       if (e.out_or_in) return this->graph->tail(e); else 
   570 	return this->graph->head(e); }
   571     Node bNode(const OutEdgeIt& e) const { 
   572       if (e.out_or_in) return this->graph->head(e); else 
   573 	return this->graph->tail(e); }
   574   };
   575   
   576 
   577 
   578   /// An undirected graph template
   579   template<typename Graph>
   580   class UndirGraph : public UndirGraphWrapper<Graph> {
   581     typedef UndirGraphWrapper<Graph> Parent;
   582   protected:
   583     Graph gr;
   584   public:
   585     UndirGraph() : UndirGraphWrapper<Graph>() { 
   586       Parent::setGraph(gr); 
   587     }
   588   };
   589 
   590 
   591   /// A wrapper for composing bidirected graph from a directed one. 
   592   /// experimental, for fezso's sake.
   593 
   594   /// A wrapper for composing bidirected graph from a directed one. 
   595   /// experimental, for fezso's sake.
   596   template<typename Graph>
   597   class BidirGraphWrapper : public GraphWrapper<Graph> {
   598   protected:
   599     //const CapacityMap* capacity;
   600     //FlowMap* flow;
   601 
   602     BidirGraphWrapper() : GraphWrapper<Graph>()/*, 
   603 						 capacity(0), flow(0)*/ { }
   604 //     void setCapacityMap(const CapacityMap& _capacity) {
   605 //       capacity=&_capacity;
   606 //     }
   607 //     void setFlowMap(FlowMap& _flow) {
   608 //       flow=&_flow;
   609 //     }
   610 
   611   public:
   612 
   613     BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, 
   614 				     FlowMap& _flow*/) : 
   615       GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
   616 
   617     class Edge; 
   618     class OutEdgeIt; 
   619     friend class Edge; 
   620     friend class OutEdgeIt; 
   621 
   622     typedef typename GraphWrapper<Graph>::Node Node;
   623     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
   624     class Edge : public Graph::Edge {
   625       friend class BidirGraphWrapper<Graph>;
   626     protected:
   627       bool backward; //true, iff backward
   628 //      typename Graph::Edge e;
   629     public:
   630       Edge() { }
   631       Edge(const typename Graph::Edge& _e, bool _backward) : 
   632 	Graph::Edge(_e), backward(_backward) { }
   633       Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
   634 //the unique invalid iterator
   635       friend bool operator==(const Edge& u, const Edge& v) { 
   636 	return (v.backward==u.backward && 
   637 		static_cast<typename Graph::Edge>(u)==
   638 		static_cast<typename Graph::Edge>(v));
   639       } 
   640       friend bool operator!=(const Edge& u, const Edge& v) { 
   641 	return (v.backward!=u.backward || 
   642 		static_cast<typename Graph::Edge>(u)!=
   643 		static_cast<typename Graph::Edge>(v));
   644       } 
   645     };
   646 
   647     class OutEdgeIt {
   648       friend class BidirGraphWrapper<Graph>;
   649     protected:
   650       typename Graph::OutEdgeIt out;
   651       typename Graph::InEdgeIt in;
   652       bool backward;
   653     public:
   654       OutEdgeIt() { }
   655       //FIXME
   656 //      OutEdgeIt(const Edge& e) : Edge(e) { }
   657       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
   658 //the unique invalid iterator
   659       OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { 
   660 	backward=false;
   661 	_G.graph->first(out, v);
   662 	while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
   663 	if (!_G.graph->valid(out)) {
   664 	  backward=true;
   665 	  _G.graph->first(in, v);
   666 	  while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
   667 	}
   668       }
   669       operator Edge() const { 
   670 //	Edge e;
   671 //	e.forward=this->forward;
   672 //	if (this->forward) e=out; else e=in;
   673 //	return e;
   674 	if (this->backward) 
   675 	  return Edge(in, this->backward); 
   676 	else 
   677 	  return Edge(out, this->backward);
   678       }
   679     };
   680 
   681     class InEdgeIt {
   682       friend class BidirGraphWrapper<Graph>;
   683     protected:
   684       typename Graph::OutEdgeIt out;
   685       typename Graph::InEdgeIt in;
   686       bool backward;
   687     public:
   688       InEdgeIt() { }
   689       //FIXME
   690 //      OutEdgeIt(const Edge& e) : Edge(e) { }
   691       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
   692 //the unique invalid iterator
   693       InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { 
   694 	backward=false;
   695 	_G.graph->first(in, v);
   696 	while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
   697 	if (!_G.graph->valid(in)) {
   698 	  backward=true;
   699 	  _G.graph->first(out, v);
   700 	  while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
   701 	}
   702       }
   703       operator Edge() const { 
   704 //	Edge e;
   705 //	e.forward=this->forward;
   706 //	if (this->forward) e=out; else e=in;
   707 //	return e;
   708 	if (this->backward) 
   709 	  return Edge(out, this->backward); 
   710 	else 
   711 	  return Edge(in, this->backward);
   712       }
   713     };
   714 
   715     class EdgeIt {
   716       friend class BidirGraphWrapper<Graph>;
   717     protected:
   718       typename Graph::EdgeIt e;
   719       bool backward;
   720     public:
   721       EdgeIt() { }
   722       EdgeIt(const Invalid& i) : e(i), backward(true) { }
   723       EdgeIt(const BidirGraphWrapper<Graph>& _G) { 
   724 	backward=false;
   725 	_G.graph->first(e);
   726 	while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
   727 	if (!_G.graph->valid(e)) {
   728 	  backward=true;
   729 	  _G.graph->first(e);
   730 	  while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
   731 	}
   732       }
   733       operator Edge() const { 
   734 	return Edge(e, this->backward);
   735       }
   736     };
   737 
   738     using GraphWrapper<Graph>::first;
   739 //     NodeIt& first(NodeIt& i) const { 
   740 //       i=NodeIt(*this); return i;
   741 //     }
   742     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
   743       i=OutEdgeIt(*this, p); return i;
   744     }
   745 //    FIXME not tested
   746     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
   747       i=InEdgeIt(*this, p); return i;
   748     }
   749     EdgeIt& first(EdgeIt& i) const { 
   750       i=EdgeIt(*this); return i;
   751     }
   752   
   753     using GraphWrapper<Graph>::next;
   754 //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
   755     OutEdgeIt& next(OutEdgeIt& e) const { 
   756       if (!e.backward) {
   757 	Node v=this->graph->aNode(e.out);
   758 	this->graph->next(e.out);
   759 	while(this->graph->valid(e.out) && !enabled(e)) { 
   760 	  this->graph->next(e.out); }
   761 	if (!this->graph->valid(e.out)) {
   762 	  e.backward=true;
   763 	  this->graph->first(e.in, v); 
   764 	  while(this->graph->valid(e.in) && !enabled(e)) { 
   765 	    this->graph->next(e.in); }
   766 	}
   767       } else {
   768 	this->graph->next(e.in);
   769 	while(this->graph->valid(e.in) && !enabled(e)) { 
   770 	  this->graph->next(e.in); } 
   771       }
   772       return e;
   773     }
   774 //     FIXME Not tested
   775     InEdgeIt& next(InEdgeIt& e) const { 
   776       if (!e.backward) {
   777 	Node v=this->graph->aNode(e.in);
   778 	this->graph->next(e.in);
   779 	while(this->graph->valid(e.in) && !enabled(e)) { 
   780 	  this->graph->next(e.in); }
   781 	if (!this->graph->valid(e.in)) {
   782 	  e.backward=true;
   783 	  this->graph->first(e.out, v); 
   784 	  while(this->graph->valid(e.out) && !enabled(e)) { 
   785 	    this->graph->next(e.out); }
   786 	}
   787       } else {
   788 	this->graph->next(e.out);
   789 	while(this->graph->valid(e.out) && !enabled(e)) { 
   790 	  this->graph->next(e.out); } 
   791       }
   792       return e;
   793     }
   794     EdgeIt& next(EdgeIt& e) const {
   795       if (!e.backward) {
   796 	this->graph->next(e.e);
   797 	while(this->graph->valid(e.e) && !enabled(e)) { 
   798 	  this->graph->next(e.e); }
   799 	if (!this->graph->valid(e.e)) {
   800 	  e.backward=true;
   801 	  this->graph->first(e.e); 
   802 	  while(this->graph->valid(e.e) && !enabled(e)) { 
   803 	    this->graph->next(e.e); }
   804 	}
   805       } else {
   806 	this->graph->next(e.e);
   807 	while(this->graph->valid(e.e) && !enabled(e)) { 
   808 	  this->graph->next(e.e); } 
   809       }
   810       return e;
   811     }
   812 
   813     Node tail(Edge e) const { 
   814       return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
   815     Node head(Edge e) const { 
   816       return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
   817 
   818     Node aNode(OutEdgeIt e) const { 
   819       return ((!e.backward) ? this->graph->aNode(e.out) : 
   820 	      this->graph->aNode(e.in)); }
   821     Node bNode(OutEdgeIt e) const { 
   822       return ((!e.backward) ? this->graph->bNode(e.out) : 
   823 	      this->graph->bNode(e.in)); }
   824 
   825     Node aNode(InEdgeIt e) const { 
   826       return ((!e.backward) ? this->graph->aNode(e.in) : 
   827 	      this->graph->aNode(e.out)); }
   828     Node bNode(InEdgeIt e) const { 
   829       return ((!e.backward) ? this->graph->bNode(e.in) : 
   830 	      this->graph->bNode(e.out)); }
   831 
   832     /// Gives back the opposite edge.
   833     Edge opposite(const Edge& e) const { 
   834       Edge f=e;
   835       f.backward=!f.backward;
   836       return f;
   837     }
   838 
   839 //    int nodeNum() const { return graph->nodeNum(); }
   840     //FIXME
   841     void edgeNum() const { }
   842     //int edgeNum() const { return graph->edgeNum(); }
   843 
   844 
   845 //    int id(Node v) const { return graph->id(v); }
   846 
   847     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
   848     bool valid(Edge e) const { 
   849       return this->graph->valid(e);
   850 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
   851     }
   852 
   853     bool forward(const Edge& e) const { return !e.backward; }
   854     bool backward(const Edge& e) const { return e.backward; }
   855 
   856 //     void augment(const Edge& e, Number a) const {
   857 //       if (!e.backward)  
   858 // // 	flow->set(e.out, flow->get(e.out)+a);
   859 // 	flow->set(e, (*flow)[e]+a);
   860 //       else  
   861 // // 	flow->set(e.in, flow->get(e.in)-a);
   862 // 	flow->set(e, (*flow)[e]-a);
   863 //     }
   864 
   865     bool enabled(const Edge& e) const { 
   866       if (!e.backward) 
   867 //	return (capacity->get(e.out)-flow->get(e.out)); 
   868 	//return ((*capacity)[e]-(*flow)[e]);
   869 	return true;
   870       else 
   871 //	return (flow->get(e.in)); 
   872 	//return ((*flow)[e]); 
   873 	return true;
   874     }
   875 
   876 //     Number enabled(typename Graph::OutEdgeIt out) const { 
   877 // //      return (capacity->get(out)-flow->get(out)); 
   878 //       return ((*capacity)[out]-(*flow)[out]); 
   879 //     }
   880     
   881 //     Number enabled(typename Graph::InEdgeIt in) const { 
   882 // //      return (flow->get(in)); 
   883 //       return ((*flow)[in]); 
   884 //     }
   885 
   886     template <typename T>
   887     class EdgeMap {
   888       typename Graph::template EdgeMap<T> forward_map, backward_map; 
   889     public:
   890       EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
   891       EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
   892       void set(Edge e, T a) { 
   893 	if (!e.backward) 
   894 	  forward_map.set(e.out, a); 
   895 	else 
   896 	  backward_map.set(e.in, a); 
   897       }
   898       T operator[](Edge e) const { 
   899 	if (!e.backward) 
   900 	  return forward_map[e.out]; 
   901 	else 
   902 	  return backward_map[e.in]; 
   903       }
   904 //       T get(Edge e) const { 
   905 // 	if (e.out_or_in) 
   906 // 	  return forward_map.get(e.out); 
   907 // 	else 
   908 // 	  return backward_map.get(e.in); 
   909 //       }
   910     };
   911   };
   912 
   913 
   914 
   915   /// A wrapper for composing the residual graph for directed flow and circulation problems.
   916 
   917   /// A wrapper for composing the residual graph for directed flow and circulation problems.
   918   template<typename Graph, typename Number, 
   919 	   typename CapacityMap, typename FlowMap>
   920   class ResGraphWrapper : public GraphWrapper<Graph> {
   921   protected:
   922     const CapacityMap* capacity;
   923     FlowMap* flow;
   924 
   925     ResGraphWrapper() : GraphWrapper<Graph>(0), 
   926 			capacity(0), flow(0) { }
   927     void setCapacityMap(const CapacityMap& _capacity) {
   928       capacity=&_capacity;
   929     }
   930     void setFlowMap(FlowMap& _flow) {
   931       flow=&_flow;
   932     }
   933 
   934   public:
   935 
   936     ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
   937 		    FlowMap& _flow) : 
   938       GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
   939 
   940     class Edge; 
   941     class OutEdgeIt; 
   942     friend class Edge; 
   943     friend class OutEdgeIt; 
   944 
   945     typedef typename GraphWrapper<Graph>::Node Node;
   946     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
   947     class Edge : public Graph::Edge {
   948       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
   949     protected:
   950       bool backward; //true, iff backward
   951 //      typename Graph::Edge e;
   952     public:
   953       Edge() { }
   954       Edge(const typename Graph::Edge& _e, bool _backward) : 
   955 	Graph::Edge(_e), backward(_backward) { }
   956       Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
   957 //the unique invalid iterator
   958       friend bool operator==(const Edge& u, const Edge& v) { 
   959 	return (v.backward==u.backward && 
   960 		static_cast<typename Graph::Edge>(u)==
   961 		static_cast<typename Graph::Edge>(v));
   962       } 
   963       friend bool operator!=(const Edge& u, const Edge& v) { 
   964 	return (v.backward!=u.backward || 
   965 		static_cast<typename Graph::Edge>(u)!=
   966 		static_cast<typename Graph::Edge>(v));
   967       } 
   968     };
   969 
   970     class OutEdgeIt {
   971       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
   972     protected:
   973       typename Graph::OutEdgeIt out;
   974       typename Graph::InEdgeIt in;
   975       bool backward;
   976     public:
   977       OutEdgeIt() { }
   978       //FIXME
   979 //      OutEdgeIt(const Edge& e) : Edge(e) { }
   980       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
   981 //the unique invalid iterator
   982       OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 
   983 	backward=false;
   984 	_G.graph->first(out, v);
   985 	while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
   986 	if (!_G.graph->valid(out)) {
   987 	  backward=true;
   988 	  _G.graph->first(in, v);
   989 	  while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
   990 	}
   991       }
   992       operator Edge() const { 
   993 //	Edge e;
   994 //	e.forward=this->forward;
   995 //	if (this->forward) e=out; else e=in;
   996 //	return e;
   997 	if (this->backward) 
   998 	  return Edge(in, this->backward); 
   999 	else 
  1000 	  return Edge(out, this->backward);
  1001       }
  1002     };
  1003 
  1004     class InEdgeIt {
  1005       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
  1006     protected:
  1007       typename Graph::OutEdgeIt out;
  1008       typename Graph::InEdgeIt in;
  1009       bool backward;
  1010     public:
  1011       InEdgeIt() { }
  1012       //FIXME
  1013 //      OutEdgeIt(const Edge& e) : Edge(e) { }
  1014       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
  1015 //the unique invalid iterator
  1016       InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 
  1017 	backward=false;
  1018 	_G.graph->first(in, v);
  1019 	while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
  1020 	if (!_G.graph->valid(in)) {
  1021 	  backward=true;
  1022 	  _G.graph->first(out, v);
  1023 	  while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
  1024 	}
  1025       }
  1026       operator Edge() const { 
  1027 //	Edge e;
  1028 //	e.forward=this->forward;
  1029 //	if (this->forward) e=out; else e=in;
  1030 //	return e;
  1031 	if (this->backward) 
  1032 	  return Edge(out, this->backward); 
  1033 	else 
  1034 	  return Edge(in, this->backward);
  1035       }
  1036     };
  1037 
  1038     class EdgeIt {
  1039       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
  1040     protected:
  1041       typename Graph::EdgeIt e;
  1042       bool backward;
  1043     public:
  1044       EdgeIt() { }
  1045       EdgeIt(const Invalid& i) : e(i), backward(true) { }
  1046       EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) { 
  1047 	backward=false;
  1048 	_G.graph->first(e);
  1049 	while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
  1050 	if (!_G.graph->valid(e)) {
  1051 	  backward=true;
  1052 	  _G.graph->first(e);
  1053 	  while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
  1054 	}
  1055       }
  1056       operator Edge() const { 
  1057 	return Edge(e, this->backward);
  1058       }
  1059     };
  1060 
  1061     using GraphWrapper<Graph>::first;
  1062 //     NodeIt& first(NodeIt& i) const { 
  1063 //       i=NodeIt(*this); return i;
  1064 //     }
  1065     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
  1066       i=OutEdgeIt(*this, p); return i;
  1067     }
  1068 //    FIXME not tested
  1069     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
  1070       i=InEdgeIt(*this, p); return i;
  1071     }
  1072     EdgeIt& first(EdgeIt& i) const { 
  1073       i=EdgeIt(*this); return i;
  1074     }
  1075   
  1076     using GraphWrapper<Graph>::next;
  1077 //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
  1078     OutEdgeIt& next(OutEdgeIt& e) const { 
  1079       if (!e.backward) {
  1080 	Node v=this->graph->aNode(e.out);
  1081 	this->graph->next(e.out);
  1082 	while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
  1083 	  this->graph->next(e.out); }
  1084 	if (!this->graph->valid(e.out)) {
  1085 	  e.backward=true;
  1086 	  this->graph->first(e.in, v); 
  1087 	  while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
  1088 	    this->graph->next(e.in); }
  1089 	}
  1090       } else {
  1091 	this->graph->next(e.in);
  1092 	while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
  1093 	  this->graph->next(e.in); } 
  1094       }
  1095       return e;
  1096     }
  1097 //     FIXME Not tested
  1098     InEdgeIt& next(InEdgeIt& e) const { 
  1099       if (!e.backward) {
  1100 	Node v=this->graph->aNode(e.in);
  1101 	this->graph->next(e.in);
  1102 	while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
  1103 	  this->graph->next(e.in); }
  1104 	if (!this->graph->valid(e.in)) {
  1105 	  e.backward=true;
  1106 	  this->graph->first(e.out, v); 
  1107 	  while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
  1108 	    this->graph->next(e.out); }
  1109 	}
  1110       } else {
  1111 	this->graph->next(e.out);
  1112 	while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
  1113 	  this->graph->next(e.out); } 
  1114       }
  1115       return e;
  1116     }
  1117     EdgeIt& next(EdgeIt& e) const {
  1118       if (!e.backward) {
  1119 	this->graph->next(e.e);
  1120 	while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
  1121 	  this->graph->next(e.e); }
  1122 	if (!this->graph->valid(e.e)) {
  1123 	  e.backward=true;
  1124 	  this->graph->first(e.e); 
  1125 	  while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
  1126 	    this->graph->next(e.e); }
  1127 	}
  1128       } else {
  1129 	this->graph->next(e.e);
  1130 	while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
  1131 	  this->graph->next(e.e); } 
  1132       }
  1133       return e;
  1134     }
  1135 
  1136     Node tail(Edge e) const { 
  1137       return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
  1138     Node head(Edge e) const { 
  1139       return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
  1140 
  1141     Node aNode(OutEdgeIt e) const { 
  1142       return ((!e.backward) ? this->graph->aNode(e.out) : 
  1143 	      this->graph->aNode(e.in)); }
  1144     Node bNode(OutEdgeIt e) const { 
  1145       return ((!e.backward) ? this->graph->bNode(e.out) : 
  1146 	      this->graph->bNode(e.in)); }
  1147 
  1148     Node aNode(InEdgeIt e) const { 
  1149       return ((!e.backward) ? this->graph->aNode(e.in) : 
  1150 	      this->graph->aNode(e.out)); }
  1151     Node bNode(InEdgeIt e) const { 
  1152       return ((!e.backward) ? this->graph->bNode(e.in) : 
  1153 	      this->graph->bNode(e.out)); }
  1154 
  1155 //    int nodeNum() const { return graph->nodeNum(); }
  1156     //FIXME
  1157     void edgeNum() const { }
  1158     //int edgeNum() const { return graph->edgeNum(); }
  1159 
  1160 
  1161 //    int id(Node v) const { return graph->id(v); }
  1162 
  1163     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
  1164     bool valid(Edge e) const { 
  1165       return this->graph->valid(e);
  1166 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
  1167     }
  1168 
  1169     bool forward(const Edge& e) const { return !e.backward; }
  1170     bool backward(const Edge& e) const { return e.backward; }
  1171 
  1172     void augment(const Edge& e, Number a) const {
  1173       if (!e.backward)  
  1174 // 	flow->set(e.out, flow->get(e.out)+a);
  1175 	flow->set(e, (*flow)[e]+a);
  1176       else  
  1177 // 	flow->set(e.in, flow->get(e.in)-a);
  1178 	flow->set(e, (*flow)[e]-a);
  1179     }
  1180 
  1181     Number resCap(const Edge& e) const { 
  1182       if (!e.backward) 
  1183 //	return (capacity->get(e.out)-flow->get(e.out)); 
  1184 	return ((*capacity)[e]-(*flow)[e]); 
  1185       else 
  1186 //	return (flow->get(e.in)); 
  1187 	return ((*flow)[e]); 
  1188     }
  1189 
  1190 //     Number resCap(typename Graph::OutEdgeIt out) const { 
  1191 // //      return (capacity->get(out)-flow->get(out)); 
  1192 //       return ((*capacity)[out]-(*flow)[out]); 
  1193 //     }
  1194     
  1195 //     Number resCap(typename Graph::InEdgeIt in) const { 
  1196 // //      return (flow->get(in)); 
  1197 //       return ((*flow)[in]); 
  1198 //     }
  1199 
  1200     template <typename T>
  1201     class EdgeMap {
  1202       typename Graph::template EdgeMap<T> forward_map, backward_map; 
  1203     public:
  1204       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
  1205       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
  1206       void set(Edge e, T a) { 
  1207 	if (!e.backward) 
  1208 	  forward_map.set(e.out, a); 
  1209 	else 
  1210 	  backward_map.set(e.in, a); 
  1211       }
  1212       T operator[](Edge e) const { 
  1213 	if (!e.backward) 
  1214 	  return forward_map[e.out]; 
  1215 	else 
  1216 	  return backward_map[e.in]; 
  1217       }
  1218 //       T get(Edge e) const { 
  1219 // 	if (e.out_or_in) 
  1220 // 	  return forward_map.get(e.out); 
  1221 // 	else 
  1222 // 	  return backward_map.get(e.in); 
  1223 //       }
  1224     };
  1225   };
  1226 
  1227 
  1228 
  1229   /// ErasingFirstGraphWrapper for blocking flows.
  1230 
  1231   /// ErasingFirstGraphWrapper for blocking flows.
  1232   ///
  1233   ///\author Marton Makai
  1234   template<typename Graph, typename FirstOutEdgesMap>
  1235   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
  1236   protected:
  1237     FirstOutEdgesMap* first_out_edges;
  1238   public:
  1239     ErasingFirstGraphWrapper(Graph& _graph, 
  1240 			     FirstOutEdgesMap& _first_out_edges) : 
  1241       GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }  
  1242 
  1243     typedef typename GraphWrapper<Graph>::Node Node;
  1244 //     class NodeIt { 
  1245 //       friend class GraphWrapper<Graph>;
  1246 //       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
  1247 //       typename Graph::NodeIt n;
  1248 //      public:
  1249 //       NodeIt() { }
  1250 //       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
  1251 //       NodeIt(const Invalid& i) : n(i) { }
  1252 //       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
  1253 // 	n(*(_G.graph)) { }
  1254 //       operator Node() const { return Node(typename Graph::Node(n)); }
  1255 //     };
  1256     typedef typename GraphWrapper<Graph>::Edge Edge;
  1257     class OutEdgeIt { 
  1258       friend class GraphWrapper<Graph>;
  1259       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
  1260 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
  1261       typename Graph::OutEdgeIt e;
  1262     public:
  1263       OutEdgeIt() { }
  1264       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
  1265       OutEdgeIt(const Invalid& i) : e(i) { }
  1266       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
  1267 		const Node& _n) : 
  1268 	e((*_G.first_out_edges)[_n]) { }
  1269       operator Edge() const { return Edge(typename Graph::Edge(e)); }
  1270     };
  1271     class InEdgeIt { 
  1272       friend class GraphWrapper<Graph>;
  1273       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
  1274 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;
  1275       typename Graph::InEdgeIt e;
  1276     public:
  1277       InEdgeIt() { }
  1278       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
  1279       InEdgeIt(const Invalid& i) : e(i) { }
  1280       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
  1281 	       const Node& _n) : 
  1282 	e(*(_G.graph), typename Graph::Node(_n)) { }
  1283       operator Edge() const { return Edge(typename Graph::Edge(e)); }
  1284     };
  1285     //typedef typename Graph::SymEdgeIt SymEdgeIt;
  1286     class EdgeIt { 
  1287       friend class GraphWrapper<Graph>;
  1288       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
  1289 //      typedef typename Graph::EdgeIt GraphEdgeIt;
  1290       typename Graph::EdgeIt e;
  1291     public:
  1292       EdgeIt() { }
  1293       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
  1294       EdgeIt(const Invalid& i) : e(i) { }
  1295       EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
  1296 	e(*(_G.graph)) { }
  1297       operator Edge() const { return Edge(typename Graph::Edge(e)); }
  1298     };
  1299 
  1300     using GraphWrapper<Graph>::first;
  1301 //     NodeIt& first(NodeIt& i) const { 
  1302 //       i=NodeIt(*this); return i;
  1303 //     }
  1304     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
  1305       i=OutEdgeIt(*this, p); return i;
  1306     }
  1307     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
  1308       i=InEdgeIt(*this, p); return i;
  1309     }
  1310     EdgeIt& first(EdgeIt& i) const { 
  1311       i=EdgeIt(*this); return i;
  1312     }
  1313 
  1314     using GraphWrapper<Graph>::next;
  1315 //    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
  1316     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
  1317     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
  1318     EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }    
  1319     
  1320     Node aNode(const OutEdgeIt& e) const { 
  1321       return Node(this->graph->aNode(e.e)); }
  1322     Node aNode(const InEdgeIt& e) const { 
  1323       return Node(this->graph->aNode(e.e)); }
  1324     Node bNode(const OutEdgeIt& e) const { 
  1325       return Node(this->graph->bNode(e.e)); }
  1326     Node bNode(const InEdgeIt& e) const { 
  1327       return Node(this->graph->bNode(e.e)); }
  1328 
  1329     void erase(const OutEdgeIt& e) const {
  1330       OutEdgeIt f=e;
  1331       this->next(f);
  1332       first_out_edges->set(this->tail(e), f.e);
  1333     }
  1334   };
  1335 
  1336   ///@}
  1337 
  1338 } //namespace hugo
  1339 
  1340 #endif //HUGO_GRAPH_WRAPPER_H
  1341