src/hugo/graph_wrapper.h
author ladanyi
Fri, 28 May 2004 07:48:16 +0000
changeset 666 410a1419e86b
parent 658 b3564d0e9c60
child 736 ba76a7f56b23
permissions -rw-r--r--
Added a short tutorial on using 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 <hugo/maps.h>
    15 //#include <iter_map.h>
    16 
    17 namespace hugo {
    18 
    19   // Graph wrappers
    20 
    21   /// \addtogroup gwrappers
    22   /// A main parts of HUGOlib are the different graph structures, 
    23   /// generic graph algorithms, graph concepts which couple these, and 
    24   /// graph wrappers. While the previous ones are more or less clear, the 
    25   /// latter notion needs further explanation.
    26   /// Graph wrappers are graph classes which serve for considering graph 
    27   /// structures in different ways. A short example makes the notion much 
    28   /// clearer. 
    29   /// Suppose that we have an instance \c g of a directed graph
    30   /// type say \c ListGraph and an algorithm 
    31   /// \code template<typename Graph> int algorithm(const Graph&); \endcode 
    32   /// is needed to run on the reversely oriented graph. 
    33   /// It may be expensive (in time or in memory usage) to copy 
    34   /// \c g with the reverse orientation. 
    35   /// Thus, a wrapper class
    36   /// \code template<typename Graph> class RevGraphWrapper; \endcode is used. 
    37   /// The code looks as follows
    38   /// \code
    39   /// ListGraph g;
    40   /// RevGraphWrapper<ListGraph> rgw(g);
    41   /// int result=algorithm(rgw);
    42   /// \endcode
    43   /// After running the algorithm, the original graph \c g 
    44   /// remains untouched. Thus the graph wrapper used above is to consider the 
    45   /// original graph with reverse orientation. 
    46   /// This techniques gives rise to an elegant code, and 
    47   /// based on stable graph wrappers, complex algorithms can be 
    48   /// implemented easily. 
    49   /// In flow, circulation and bipartite matching problems, the residual 
    50   /// graph is of particular importance. Combining a wrapper implementing 
    51   /// this, shortest path algorithms and minimum mean cycle algorithms, 
    52   /// a range of weighted and cardinality optimization algorithms can be 
    53   /// obtained. For lack of space, for other examples, 
    54   /// the interested user is referred to the detailed documentation of graph 
    55   /// wrappers. 
    56   /// The behavior of graph wrappers can be very different. Some of them keep 
    57   /// capabilities of the original graph while in other cases this would be 
    58   /// meaningless. This means that the concepts that they are a model of depend 
    59   /// on the graph wrapper, and the wrapped graph(s). 
    60   /// If an edge of \c rgw is deleted, this is carried out by 
    61   /// deleting the corresponding edge of \c g. But for a residual 
    62   /// graph, this operation has no sense. 
    63   /// Let we stand one more example here to simplify your work. 
    64   /// wrapper class
    65   /// \code template<typename Graph> class RevGraphWrapper; \endcode 
    66   /// has constructor 
    67   /// <tt> RevGraphWrapper(Graph& _g)</tt>. 
    68   /// This means that in a situation, 
    69   /// when a <tt> const ListGraph& </tt> reference to a graph is given, 
    70   /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
    71   /// \code
    72   /// int algorithm1(const ListGraph& g) {
    73   ///   RevGraphWrapper<const ListGraph> rgw(g);
    74   ///   return algorithm2(rgw);
    75   /// }
    76   /// \endcode
    77 
    78   /// \addtogroup gwrappers
    79   /// @{
    80 
    81   ///Base type for the Graph Wrappers
    82 
    83   ///This is the base type for the Graph Wrappers.
    84   ///\todo Some more docs... 
    85   ///
    86   ///\author Marton Makai 
    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       // /// \bug construction throughrthr multiple levels should be 
   108       // /// handled better
   109       // Node(const typename ParentGraph::ParentGraph::Node& _n) : 
   110       // Graph::Node(_n) { }
   111       Node(const Invalid& i) : Graph::Node(i) { }
   112     };
   113     class NodeIt { 
   114       friend class GraphWrapper<Graph>;
   115       typename Graph::NodeIt n;
   116      public:
   117       NodeIt() { }
   118       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
   119       NodeIt(const Invalid& i) : n(i) { }
   120       NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
   121       operator Node() const { return Node(typename Graph::Node(n)); }
   122     };
   123 //    typedef typename Graph::Edge Edge;
   124     class Edge : public Graph::Edge {
   125       friend class GraphWrapper<Graph>;
   126     public:
   127       Edge() { }
   128       Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
   129       Edge(const Invalid& i) : Graph::Edge(i) { }
   130     };
   131     class OutEdgeIt { 
   132       friend class GraphWrapper<Graph>;
   133       typename Graph::OutEdgeIt e;
   134     public:
   135       OutEdgeIt() { }
   136       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
   137       OutEdgeIt(const Invalid& i) : e(i) { }
   138       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
   139 	e(*(_G.graph), typename Graph::Node(_n)) { }
   140       operator Edge() const { return Edge(typename Graph::Edge(e)); }
   141     };
   142     class InEdgeIt { 
   143       friend class GraphWrapper<Graph>;
   144       typename Graph::InEdgeIt e;
   145     public:
   146       InEdgeIt() { }
   147       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
   148       InEdgeIt(const Invalid& i) : e(i) { }
   149       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
   150 	e(*(_G.graph), typename Graph::Node(_n)) { }
   151       operator Edge() const { return Edge(typename Graph::Edge(e)); }
   152     };
   153     //typedef typename Graph::SymEdgeIt SymEdgeIt;
   154     class EdgeIt { 
   155       friend class GraphWrapper<Graph>;
   156       typename Graph::EdgeIt e;
   157     public:
   158       EdgeIt() { }
   159       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
   160       EdgeIt(const Invalid& i) : e(i) { }
   161       EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
   162       operator Edge() const { return Edge(typename Graph::Edge(e)); }
   163     };
   164    
   165     NodeIt& first(NodeIt& i) const { 
   166       i=NodeIt(*this); return i;
   167     }
   168     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
   169       i=OutEdgeIt(*this, p); return i;
   170     }
   171     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
   172       i=InEdgeIt(*this, p); return i;
   173     }
   174     EdgeIt& first(EdgeIt& i) const { 
   175       i=EdgeIt(*this); return i;
   176     }
   177 
   178     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
   179     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
   180     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
   181     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }    
   182 
   183     Node tail(const Edge& e) const { 
   184       return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
   185     Node head(const Edge& e) const { 
   186       return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
   187 
   188     bool valid(const Node& n) const { 
   189       return graph->valid(static_cast<typename Graph::Node>(n)); }
   190     bool valid(const Edge& e) const { 
   191       return graph->valid(static_cast<typename Graph::Edge>(e)); }
   192 
   193     int nodeNum() const { return graph->nodeNum(); }
   194     int edgeNum() const { return graph->edgeNum(); }
   195   
   196     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
   197     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
   198     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
   199     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
   200   
   201     Node addNode() const { return Node(graph->addNode()); }
   202     Edge addEdge(const Node& tail, const Node& head) const { 
   203       return Edge(graph->addEdge(tail, head)); }
   204 
   205     void erase(const Node& i) const { graph->erase(i); }
   206     void erase(const Edge& i) const { graph->erase(i); }
   207   
   208     void clear() const { graph->clear(); }
   209     
   210     bool forward(const Edge& e) const { graph->forward(e); }
   211     bool backward(const Edge& e) const { graph->backward(e); }
   212     
   213     Edge opposite(const Edge& e) const { Edge(graph->opposite(e)); }
   214 
   215     template<typename T> class NodeMap : public Graph::template NodeMap<T> { 
   216       typedef typename Graph::template NodeMap<T> Parent;
   217     public:
   218       NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }
   219       NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
   220     };
   221 
   222     template<typename T> class EdgeMap : public Graph::template EdgeMap<T> { 
   223       typedef typename Graph::template EdgeMap<T> Parent;
   224     public:
   225       EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
   226       EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
   227     };
   228   };
   229 
   230 
   231 
   232   /// A graph wrapper which reverses the orientation of the edges.
   233 
   234   /// A graph wrapper which reverses the orientation of the edges.
   235   /// Thus \c Graph have to be a directed graph type.
   236   ///
   237   ///\author Marton Makai
   238   template<typename Graph>
   239   class RevGraphWrapper : public GraphWrapper<Graph> {
   240   public:
   241     typedef GraphWrapper<Graph> Parent; 
   242   protected:
   243     RevGraphWrapper() : GraphWrapper<Graph>() { }
   244   public:
   245     RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  
   246 
   247     typedef typename GraphWrapper<Graph>::Node Node;
   248     typedef typename GraphWrapper<Graph>::Edge Edge;
   249     //If Graph::OutEdgeIt is not defined
   250     //and we do not want to use RevGraphWrapper::InEdgeIt,
   251     //the typdef techinque does not work.
   252     //Unfortunately all the typedefs are instantiated in templates.
   253     //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
   254     //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
   255 
   256     class OutEdgeIt { 
   257       friend class GraphWrapper<Graph>;
   258       friend class RevGraphWrapper<Graph>;
   259       typename Graph::InEdgeIt e;
   260     public:
   261       OutEdgeIt() { }
   262       OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
   263       OutEdgeIt(const Invalid& i) : e(i) { }
   264       OutEdgeIt(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     class InEdgeIt { 
   269       friend class GraphWrapper<Graph>;
   270       friend class RevGraphWrapper<Graph>;
   271       typename Graph::OutEdgeIt e;
   272     public:
   273       InEdgeIt() { }
   274       InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
   275       InEdgeIt(const Invalid& i) : e(i) { }
   276       InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
   277 	e(*(_G.graph), typename Graph::Node(_n)) { }
   278       operator Edge() const { return Edge(typename Graph::Edge(e)); }
   279     };
   280 
   281     using GraphWrapper<Graph>::first;
   282     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
   283       i=OutEdgeIt(*this, p); return i;
   284     }
   285     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
   286       i=InEdgeIt(*this, p); return i;
   287     }
   288 
   289     using GraphWrapper<Graph>::next;
   290     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
   291     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
   292 
   293     Node aNode(const OutEdgeIt& e) const { 
   294       return Node(this->graph->aNode(e.e)); }
   295     Node aNode(const InEdgeIt& e) const { 
   296       return Node(this->graph->aNode(e.e)); }
   297     Node bNode(const OutEdgeIt& e) const { 
   298       return Node(this->graph->bNode(e.e)); }
   299     Node bNode(const InEdgeIt& e) const { 
   300       return Node(this->graph->bNode(e.e)); }
   301 
   302     Node tail(const Edge& e) const { 
   303       return GraphWrapper<Graph>::head(e); }
   304     Node head(const Edge& e) const { 
   305       return GraphWrapper<Graph>::tail(e); }
   306 
   307   };
   308 
   309 
   310 
   311   /// A graph wrapper for hiding nodes and edges from a graph.
   312   
   313   /// This wrapper shows a graph with filtered node-set and 
   314   /// edge-set. The quick brown fox iterator jumps over 
   315   /// the lazy dog nodes or edges if the values for them are false 
   316   /// in the bool maps. 
   317   ///
   318   ///\author Marton Makai
   319   template<typename Graph, typename NodeFilterMap, 
   320 	   typename EdgeFilterMap>
   321   class SubGraphWrapper : public GraphWrapper<Graph> {
   322   public:
   323     typedef GraphWrapper<Graph> Parent;
   324   protected:
   325     NodeFilterMap* node_filter_map;
   326     EdgeFilterMap* edge_filter_map;
   327 
   328     SubGraphWrapper() : GraphWrapper<Graph>(), 
   329 			node_filter_map(0), edge_filter_map(0) { }
   330     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
   331       node_filter_map=&_node_filter_map;
   332     }
   333     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
   334       edge_filter_map=&_edge_filter_map;
   335     }
   336     
   337   public:
   338     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, 
   339 		    EdgeFilterMap& _edge_filter_map) : 
   340       GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), 
   341       edge_filter_map(&_edge_filter_map) { }  
   342 
   343     typedef typename GraphWrapper<Graph>::Node Node;
   344     class NodeIt { 
   345       friend class GraphWrapper<Graph>;
   346       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
   347       typename Graph::NodeIt n;
   348      public:
   349       NodeIt() { }
   350       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
   351       NodeIt(const Invalid& i) : n(i) { }
   352       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
   353 	n(*(_G.graph)) { 
   354 	while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n]) 
   355 	  _G.graph->next(n);
   356       }
   357       operator Node() const { return Node(typename Graph::Node(n)); }
   358     };
   359     typedef typename GraphWrapper<Graph>::Edge Edge;
   360     class OutEdgeIt { 
   361       friend class GraphWrapper<Graph>;
   362       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
   363       typename Graph::OutEdgeIt e;
   364     public:
   365       OutEdgeIt() { }
   366       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
   367       OutEdgeIt(const Invalid& i) : e(i) { }
   368       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
   369 		const Node& _n) : 
   370 	e(*(_G.graph), typename Graph::Node(_n)) { 
   371       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
   372 	  _G.graph->next(e);
   373       }
   374       operator Edge() const { return Edge(typename Graph::Edge(e)); }
   375     };
   376     class InEdgeIt { 
   377       friend class GraphWrapper<Graph>;
   378       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
   379       typename Graph::InEdgeIt e;
   380     public:
   381       InEdgeIt() { }
   382       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
   383       InEdgeIt(const Invalid& i) : e(i) { }
   384       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
   385 	       const Node& _n) : 
   386 	e(*(_G.graph), typename Graph::Node(_n)) { 
   387       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
   388 	  _G.graph->next(e);
   389       }
   390       operator Edge() const { return Edge(typename Graph::Edge(e)); }
   391     };
   392     //typedef typename Graph::SymEdgeIt SymEdgeIt;
   393     class EdgeIt { 
   394       friend class GraphWrapper<Graph>;
   395       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
   396       typename Graph::EdgeIt e;
   397     public:
   398       EdgeIt() { }
   399       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
   400       EdgeIt(const Invalid& i) : e(i) { }
   401       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
   402 	e(*(_G.graph)) { 
   403       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
   404 	  _G.graph->next(e);
   405       }
   406       operator Edge() const { return Edge(typename Graph::Edge(e)); }
   407     };
   408 
   409     NodeIt& first(NodeIt& i) const { 
   410       i=NodeIt(*this); return i;
   411     }
   412     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
   413       i=OutEdgeIt(*this, p); return i;
   414     }
   415     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
   416       i=InEdgeIt(*this, p); return i;
   417     }
   418     EdgeIt& first(EdgeIt& i) const { 
   419       i=EdgeIt(*this); return i;
   420     }
   421     
   422     NodeIt& next(NodeIt& i) const {
   423       this->graph->next(i.n); 
   424       while (this->graph->valid(i) && !(*node_filter_map)[i.n]) { 
   425 	this->graph->next(i.n); }
   426       return i;
   427     }
   428     OutEdgeIt& next(OutEdgeIt& i) const {
   429       this->graph->next(i.e); 
   430       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
   431 	this->graph->next(i.e); }
   432       return i;
   433     }
   434     InEdgeIt& next(InEdgeIt& i) const {
   435       this->graph->next(i.e); 
   436       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
   437 	this->graph->next(i.e); }
   438       return i;
   439     }
   440     EdgeIt& next(EdgeIt& i) const {
   441       this->graph->next(i.e); 
   442       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
   443 	this->graph->next(i.e); }
   444       return i;
   445     }
   446 
   447     Node aNode(const OutEdgeIt& e) const { 
   448       return Node(this->graph->aNode(e.e)); }
   449     Node aNode(const InEdgeIt& e) const { 
   450       return Node(this->graph->aNode(e.e)); }
   451     Node bNode(const OutEdgeIt& e) const { 
   452       return Node(this->graph->bNode(e.e)); }
   453     Node bNode(const InEdgeIt& e) const { 
   454       return Node(this->graph->bNode(e.e)); }
   455 
   456     /// This function hides \c n in the graph, i.e. the iteration 
   457     /// jumps over it. This is done by simply setting the value of \c n  
   458     /// to be false in the corresponding node-map.
   459     void hide(const Node& n) const { node_filter_map->set(n, false); }
   460 
   461     /// This function hides \c e in the graph, i.e. the iteration 
   462     /// jumps over it. This is done by simply setting the value of \c e  
   463     /// to be false in the corresponding edge-map.
   464     void hide(const Edge& e) const { edge_filter_map->set(e, false); }
   465 
   466     /// The value of \c n is set to be true in the node-map which stores 
   467     /// hide information. If \c n was hidden previuosly, then it is shown 
   468     /// again
   469      void unHide(const Node& n) const { node_filter_map->set(n, true); }
   470 
   471     /// The value of \c e is set to be true in the edge-map which stores 
   472     /// hide information. If \c e was hidden previuosly, then it is shown 
   473     /// again
   474     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
   475 
   476     /// Returns true if \c n is hidden.
   477     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
   478 
   479     /// Returns true if \c n is hidden.
   480     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
   481 
   482     /// This is a linear time operation and works only if 
   483     /// NodeIt is defined.
   484     int nodeNum() const { 
   485       int i=0;
   486       NodeIt n;
   487       for (this->first(n); this->valid(n); this->next(n)) ++i;
   488       return i; 
   489     }
   490 
   491     /// This is a linear time operation and works only if 
   492     /// EdgeIt is defined.
   493     int edgeNum() const { 
   494       int i=0;
   495       EdgeIt e;
   496       for (this->first(e); this->valid(e); this->next(e)) ++i;
   497       return i; 
   498     }
   499 
   500   };
   501 
   502 
   503 
   504   /// \brief A wrapper for forgetting the orientation of a graph.
   505   ///
   506   /// A wrapper for getting an undirected graph by forgetting
   507   /// the orientation of a directed one.
   508   ///
   509   /// \author Marton Makai
   510   template<typename Graph>
   511   class UndirGraphWrapper : public GraphWrapper<Graph> {
   512   public:
   513     typedef GraphWrapper<Graph> Parent; 
   514   protected:
   515     UndirGraphWrapper() : GraphWrapper<Graph>() { }
   516     
   517   public:
   518     typedef typename GraphWrapper<Graph>::Node Node;
   519     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
   520     typedef typename GraphWrapper<Graph>::Edge Edge;
   521     typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
   522 
   523     UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  
   524 
   525     class OutEdgeIt {
   526       friend class UndirGraphWrapper<Graph>;
   527       bool out_or_in; //true iff out
   528       typename Graph::OutEdgeIt out;
   529       typename Graph::InEdgeIt in;
   530     public:
   531       OutEdgeIt() { }
   532       OutEdgeIt(const Invalid& i) : Edge(i) { }
   533       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
   534 	out_or_in=true; _G.graph->first(out, _n);
   535 	if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);	}
   536       } 
   537       operator Edge() const { 
   538 	if (out_or_in) return Edge(out); else return Edge(in); 
   539       }
   540     };
   541 
   542 //FIXME InEdgeIt
   543     typedef OutEdgeIt InEdgeIt; 
   544 
   545     using GraphWrapper<Graph>::first;
   546 //     NodeIt& first(NodeIt& i) const { 
   547 //       i=NodeIt(*this); return i;
   548 //     }
   549     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
   550       i=OutEdgeIt(*this, p); return i;
   551     }
   552 //FIXME
   553 //     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
   554 //       i=InEdgeIt(*this, p); return i;
   555 //     }
   556 //     EdgeIt& first(EdgeIt& i) const { 
   557 //       i=EdgeIt(*this); return i;
   558 //     }
   559 
   560     using GraphWrapper<Graph>::next;
   561 //     NodeIt& next(NodeIt& n) const {
   562 //       GraphWrapper<Graph>::next(n);
   563 //       return n;
   564 //     }
   565     OutEdgeIt& next(OutEdgeIt& e) const {
   566       if (e.out_or_in) {
   567 	typename Graph::Node n=this->graph->tail(e.out);
   568 	this->graph->next(e.out);
   569 	if (!this->graph->valid(e.out)) { 
   570 	  e.out_or_in=false; this->graph->first(e.in, n); }
   571       } else {
   572 	this->graph->next(e.in);
   573       }
   574       return e;
   575     }
   576     //FIXME InEdgeIt
   577 //     EdgeIt& next(EdgeIt& e) const {
   578 //       GraphWrapper<Graph>::next(n);
   579 // //      graph->next(e.e);
   580 //       return e;
   581 //     }
   582 
   583     Node aNode(const OutEdgeIt& e) const { 
   584       if (e.out_or_in) return this->graph->tail(e); else 
   585 	return this->graph->head(e); }
   586     Node bNode(const OutEdgeIt& e) const { 
   587       if (e.out_or_in) return this->graph->head(e); else 
   588 	return this->graph->tail(e); }
   589   };
   590   
   591   /// \brief An undirected graph template.
   592   ///
   593   /// An undirected graph template.
   594   /// This class works as an undirected graph and a directed graph of 
   595   /// class \c Graph is used for the physical storage.
   596   /// \ingroup graphs
   597   template<typename Graph>
   598   class UndirGraph : public UndirGraphWrapper<Graph> {
   599     typedef UndirGraphWrapper<Graph> Parent;
   600   protected:
   601     Graph gr;
   602   public:
   603     UndirGraph() : UndirGraphWrapper<Graph>() { 
   604       Parent::setGraph(gr); 
   605     }
   606   };
   607 
   608 
   609 
   610   ///\brief A wrapper for composing a subgraph of a 
   611   /// bidirected graph composed from a directed one. 
   612   /// experimental, for fezso's sake.
   613   ///
   614   /// A wrapper for composing a subgraps of a 
   615   /// bidirected graph composed from a directed one. 
   616   /// experimental, for fezso's sake.
   617   /// A bidirected graph is composed over the directed one without physical 
   618   /// storage. As the oppositely directed edges are logically different ones 
   619   /// the maps are able to attach different values for them.
   620   template<typename Graph, 
   621 	   typename ForwardFilterMap, typename BackwardFilterMap>
   622   class SubBidirGraphWrapper : public GraphWrapper<Graph> {
   623   public:
   624     typedef GraphWrapper<Graph> Parent; 
   625   protected:
   626     //const CapacityMap* capacity;
   627     //FlowMap* flow;
   628 
   629     ForwardFilterMap* forward_filter;
   630     BackwardFilterMap* backward_filter;
   631 
   632     SubBidirGraphWrapper() : GraphWrapper<Graph>()/*, 
   633 						 capacity(0), flow(0)*/ { }
   634     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
   635       forward_filter=&_forward_filter;
   636     }
   637     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
   638       backward_filter=&_backward_filter;
   639     }
   640 
   641   public:
   642 
   643     SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter, 
   644 			 BackwardFilterMap& _backward_filter) : 
   645       GraphWrapper<Graph>(_graph), 
   646       forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
   647 
   648     class Edge; 
   649     class OutEdgeIt; 
   650     friend class Edge; 
   651     friend class OutEdgeIt; 
   652 
   653     //template<typename T> class NodeMap;    
   654     template<typename T> class EdgeMap;
   655 
   656     typedef typename GraphWrapper<Graph>::Node Node;
   657     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
   658 
   659     class Edge : public Graph::Edge {
   660       friend class SubBidirGraphWrapper<Graph, 
   661 					ForwardFilterMap, BackwardFilterMap>;
   662       ///\bug ez nem is kell
   663       //template<typename T> friend class NodeMap;
   664       template<typename T> friend class EdgeMap;
   665     protected:
   666       bool backward; //true, iff backward
   667 //      typename Graph::Edge e;
   668     public:
   669       Edge() { }
   670       ///\bug =false kell-e? zsoltnak kell az addEdge miatt
   671       Edge(const typename Graph::Edge& _e, bool _backward=false) : 
   672 	Graph::Edge(_e), backward(_backward) { }
   673       Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
   674 //the unique invalid iterator
   675       friend bool operator==(const Edge& u, const Edge& v) { 
   676 	return (v.backward==u.backward && 
   677 		static_cast<typename Graph::Edge>(u)==
   678 		static_cast<typename Graph::Edge>(v));
   679       } 
   680       friend bool operator!=(const Edge& u, const Edge& v) { 
   681 	return (v.backward!=u.backward || 
   682 		static_cast<typename Graph::Edge>(u)!=
   683 		static_cast<typename Graph::Edge>(v));
   684       } 
   685     };
   686 
   687     class OutEdgeIt {
   688       friend class SubBidirGraphWrapper<Graph, 
   689 					ForwardFilterMap, BackwardFilterMap>;
   690     protected:
   691       typename Graph::OutEdgeIt out;
   692       typename Graph::InEdgeIt in;
   693       bool backward;
   694     public:
   695       OutEdgeIt() { }
   696       //FIXME
   697 //      OutEdgeIt(const Edge& e) : Edge(e) { }
   698       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
   699 //the unique invalid iterator
   700       OutEdgeIt(const SubBidirGraphWrapper<Graph, 
   701 		ForwardFilterMap, BackwardFilterMap>& _G, Node v) { 
   702 	backward=false;
   703 	_G.graph->first(out, v);
   704 	while(_G.graph->valid(out) && !(*_G.forward_filter)[*this]) { _G.graph->next(out); }
   705 	if (!_G.graph->valid(out)) {
   706 	  backward=true;
   707 	  _G.graph->first(in, v);
   708 	  while(_G.graph->valid(in) && !(*_G.backward_filter)[*this]) { _G.graph->next(in); }
   709 	}
   710       }
   711       operator Edge() const { 
   712 //	Edge e;
   713 //	e.forward=this->forward;
   714 //	if (this->forward) e=out; else e=in;
   715 //	return e;
   716 	if (this->backward) 
   717 	  return Edge(in, this->backward); 
   718 	else 
   719 	  return Edge(out, this->backward);
   720       }
   721     };
   722 
   723     class InEdgeIt {
   724       friend class SubBidirGraphWrapper<Graph, 
   725 					ForwardFilterMap, BackwardFilterMap>;
   726     protected:
   727       typename Graph::OutEdgeIt out;
   728       typename Graph::InEdgeIt in;
   729       bool backward;
   730     public:
   731       InEdgeIt() { }
   732       //FIXME
   733 //      OutEdgeIt(const Edge& e) : Edge(e) { }
   734       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
   735 //the unique invalid iterator
   736       InEdgeIt(const SubBidirGraphWrapper<Graph, 
   737 	       ForwardFilterMap, BackwardFilterMap>& _G, Node v) { 
   738 	backward=false;
   739 	_G.graph->first(in, v);
   740 	while(_G.graph->valid(in) && !(*_G.forward_filter)[*this]) { _G.graph->next(in); }
   741 	if (!_G.graph->valid(in)) {
   742 	  backward=true;
   743 	  _G.graph->first(out, v);
   744 	  while(_G.graph->valid(out) && !(*_G.backward_filter)[*this]) { _G.graph->next(out); }
   745 	}
   746       }
   747       operator Edge() const { 
   748 //	Edge e;
   749 //	e.forward=this->forward;
   750 //	if (this->forward) e=out; else e=in;
   751 //	return e;
   752 	if (this->backward) 
   753 	  return Edge(out, this->backward); 
   754 	else 
   755 	  return Edge(in, this->backward);
   756       }
   757     };
   758 
   759     class EdgeIt {
   760       friend class SubBidirGraphWrapper<Graph, 
   761 					ForwardFilterMap, BackwardFilterMap>;
   762     protected:
   763       typename Graph::EdgeIt e;
   764       bool backward;
   765     public:
   766       EdgeIt() { }
   767       EdgeIt(const Invalid& i) : e(i), backward(true) { }
   768       EdgeIt(const SubBidirGraphWrapper<Graph, 
   769 	     ForwardFilterMap, BackwardFilterMap>& _G) { 
   770 	backward=false;
   771 	_G.graph->first(e);
   772 	while (_G.graph->valid(e) && !(*_G.forward_filter)[*this]) _G.graph->next(e);
   773 	if (!_G.graph->valid(e)) {
   774 	  backward=true;
   775 	  _G.graph->first(e);
   776 	  while (_G.graph->valid(e) && !(*_G.backward_filter)[*this]) _G.graph->next(e);
   777 	}
   778       }
   779       operator Edge() const { 
   780 	return Edge(e, this->backward);
   781       }
   782     };
   783 
   784     using GraphWrapper<Graph>::first;
   785 //     NodeIt& first(NodeIt& i) const { 
   786 //       i=NodeIt(*this); return i;
   787 //     }
   788     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
   789       i=OutEdgeIt(*this, p); return i;
   790     }
   791 //    FIXME not tested
   792     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
   793       i=InEdgeIt(*this, p); return i;
   794     }
   795     EdgeIt& first(EdgeIt& i) const { 
   796       i=EdgeIt(*this); return i;
   797     }
   798   
   799     using GraphWrapper<Graph>::next;
   800 //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
   801     OutEdgeIt& next(OutEdgeIt& e) const { 
   802       if (!e.backward) {
   803 	Node v=this->graph->aNode(e.out);
   804 	this->graph->next(e.out);
   805 	while(this->graph->valid(e.out) && !(*forward_filter)[e]) { 
   806 	  this->graph->next(e.out); }
   807 	if (!this->graph->valid(e.out)) {
   808 	  e.backward=true;
   809 	  this->graph->first(e.in, v); 
   810 	  while(this->graph->valid(e.in) && !(*backward_filter)[e]) { 
   811 	    this->graph->next(e.in); }
   812 	}
   813       } else {
   814 	this->graph->next(e.in);
   815 	while(this->graph->valid(e.in) && !(*backward_filter)[e]) { 
   816 	  this->graph->next(e.in); } 
   817       }
   818       return e;
   819     }
   820 //     FIXME Not tested
   821     InEdgeIt& next(InEdgeIt& e) const { 
   822       if (!e.backward) {
   823 	Node v=this->graph->aNode(e.in);
   824 	this->graph->next(e.in);
   825 	while(this->graph->valid(e.in) && !(*forward_filter)[e]) { 
   826 	  this->graph->next(e.in); }
   827 	if (!this->graph->valid(e.in)) {
   828 	  e.backward=true;
   829 	  this->graph->first(e.out, v); 
   830 	  while(this->graph->valid(e.out) && !(*backward_filter)[e]) { 
   831 	    this->graph->next(e.out); }
   832 	}
   833       } else {
   834 	this->graph->next(e.out);
   835 	while(this->graph->valid(e.out) && !(*backward_filter)[e]) { 
   836 	  this->graph->next(e.out); } 
   837       }
   838       return e;
   839     }
   840     EdgeIt& next(EdgeIt& e) const {
   841       if (!e.backward) {
   842 	this->graph->next(e.e);
   843 	while(this->graph->valid(e.e) && !(*forward_filter)[e]) { 
   844 	  this->graph->next(e.e); }
   845 	if (!this->graph->valid(e.e)) {
   846 	  e.backward=true;
   847 	  this->graph->first(e.e); 
   848 	  while(this->graph->valid(e.e) && !(*backward_filter)[e]) { 
   849 	    this->graph->next(e.e); }
   850 	}
   851       } else {
   852 	this->graph->next(e.e);
   853 	while(this->graph->valid(e.e) && !(*backward_filter)[e]) { 
   854 	  this->graph->next(e.e); } 
   855       }
   856       return e;
   857     }
   858 
   859     Node tail(Edge e) const { 
   860       return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
   861     Node head(Edge e) const { 
   862       return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
   863 
   864     Node aNode(OutEdgeIt e) const { 
   865       return ((!e.backward) ? this->graph->aNode(e.out) : 
   866 	      this->graph->aNode(e.in)); }
   867     Node bNode(OutEdgeIt e) const { 
   868       return ((!e.backward) ? this->graph->bNode(e.out) : 
   869 	      this->graph->bNode(e.in)); }
   870 
   871     Node aNode(InEdgeIt e) const { 
   872       return ((!e.backward) ? this->graph->aNode(e.in) : 
   873 	      this->graph->aNode(e.out)); }
   874     Node bNode(InEdgeIt e) const { 
   875       return ((!e.backward) ? this->graph->bNode(e.in) : 
   876 	      this->graph->bNode(e.out)); }
   877 
   878     /// Gives back the opposite edge.
   879     Edge opposite(const Edge& e) const { 
   880       Edge f=e;
   881       f.backward=!f.backward;
   882       return f;
   883     }
   884 
   885 //    int nodeNum() const { return graph->nodeNum(); }
   886     //FIXME
   887     void edgeNum() const { }
   888     //int edgeNum() const { return graph->edgeNum(); }
   889 
   890 
   891 //    int id(Node v) const { return graph->id(v); }
   892 
   893     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
   894     bool valid(Edge e) const { 
   895       return this->graph->valid(e);
   896 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
   897     }
   898 
   899     bool forward(const Edge& e) const { return !e.backward; }
   900     bool backward(const Edge& e) const { return e.backward; }
   901 
   902 //     void augment(const Edge& e, Number a) const {
   903 //       if (!e.backward)  
   904 // // 	flow->set(e.out, flow->get(e.out)+a);
   905 // 	flow->set(e, (*flow)[e]+a);
   906 //       else  
   907 // // 	flow->set(e.in, flow->get(e.in)-a);
   908 // 	flow->set(e, (*flow)[e]-a);
   909 //     }
   910 
   911 //     bool enabled(const Edge& e) const { 
   912 //       if (!e.backward) 
   913 // //	return (capacity->get(e.out)-flow->get(e.out)); 
   914 // 	//return ((*capacity)[e]-(*flow)[e]);
   915 // 	return true;
   916 //       else 
   917 // //	return (flow->get(e.in)); 
   918 // 	//return ((*flow)[e]); 
   919 // 	return true;
   920 //     }
   921 
   922 //     Number enabled(typename Graph::OutEdgeIt out) const { 
   923 // //      return (capacity->get(out)-flow->get(out)); 
   924 //       return ((*capacity)[out]-(*flow)[out]); 
   925 //     }
   926     
   927 //     Number enabled(typename Graph::InEdgeIt in) const { 
   928 // //      return (flow->get(in)); 
   929 //       return ((*flow)[in]); 
   930 //     }
   931 
   932     template <typename T>
   933     class EdgeMap {
   934       typename Graph::template EdgeMap<T> forward_map, backward_map; 
   935     public:
   936       typedef T ValueType;
   937       typedef Edge KeyType;
   938       EdgeMap(const SubBidirGraphWrapper<Graph, 
   939 	      ForwardFilterMap, BackwardFilterMap>& _G) : 
   940 	forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
   941       EdgeMap(const SubBidirGraphWrapper<Graph, 
   942 	      ForwardFilterMap, BackwardFilterMap>& _G, T a) : 
   943 	forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
   944       void set(Edge e, T a) { 
   945 	if (!e.backward) 
   946 	  forward_map.set(e/*.out*/, a); 
   947 	else 
   948 	  backward_map.set(e/*.in*/, a); 
   949       }
   950       T operator[](Edge e) const { 
   951 	if (!e.backward) 
   952 	  return forward_map[e/*.out*/]; 
   953 	else 
   954 	  return backward_map[e/*.in*/]; 
   955       }
   956       void update() { 
   957 	forward_map.update(); 
   958 	backward_map.update();
   959       }
   960 //       T get(Edge e) const { 
   961 // 	if (e.out_or_in) 
   962 // 	  return forward_map.get(e.out); 
   963 // 	else 
   964 // 	  return backward_map.get(e.in); 
   965 //       }
   966     };
   967   };
   968 
   969 
   970 
   971   ///\brief A wrapper for composing bidirected graph from a directed one. 
   972   /// experimental, for fezso's sake.
   973   ///
   974   /// A wrapper for composing bidirected graph from a directed one. 
   975   /// experimental, for fezso's sake.
   976   /// A bidirected graph is composed over the directed one without physical 
   977   /// storage. As the oppositely directed edges are logically different ones 
   978   /// the maps are able to attach different values for them.
   979   template<typename Graph>
   980   class BidirGraphWrapper : 
   981     public SubBidirGraphWrapper<
   982     Graph, 
   983     ConstMap<typename Graph::Edge, bool>, 
   984     ConstMap<typename Graph::Edge, bool> > {
   985   public:
   986     typedef  SubBidirGraphWrapper<
   987       Graph, 
   988       ConstMap<typename Graph::Edge, bool>, 
   989       ConstMap<typename Graph::Edge, bool> > Parent; 
   990   protected:
   991     ConstMap<typename Graph::Edge, bool> cm;
   992     //const CapacityMap* capacity;
   993     //FlowMap* flow;
   994 
   995     BidirGraphWrapper() : Parent(), cm(true) { 
   996       Parent::setForwardFilterMap(cm);
   997       Parent::setBackwardFilterMap(cm);
   998     }
   999 //     void setCapacityMap(const CapacityMap& _capacity) {
  1000 //       capacity=&_capacity;
  1001 //     }
  1002 //     void setFlowMap(FlowMap& _flow) {
  1003 //       flow=&_flow;
  1004 //     }
  1005 
  1006   public:
  1007 
  1008     BidirGraphWrapper(Graph& _graph) : Parent() { 
  1009       Parent::setGraph(_graph);
  1010       Parent::setForwardFilterMap(cm);
  1011       Parent::setBackwardFilterMap(cm);
  1012     }
  1013   };
  1014 
  1015 
  1016 
  1017 
  1018   template<typename Graph>
  1019   class OldBidirGraphWrapper : public GraphWrapper<Graph> {
  1020   public:
  1021     typedef GraphWrapper<Graph> Parent; 
  1022   protected:
  1023     //const CapacityMap* capacity;
  1024     //FlowMap* flow;
  1025 
  1026     OldBidirGraphWrapper() : GraphWrapper<Graph>()/*, 
  1027 						 capacity(0), flow(0)*/ { }
  1028 //     void setCapacityMap(const CapacityMap& _capacity) {
  1029 //       capacity=&_capacity;
  1030 //     }
  1031 //     void setFlowMap(FlowMap& _flow) {
  1032 //       flow=&_flow;
  1033 //     }
  1034 
  1035   public:
  1036 
  1037     OldBidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, 
  1038 				     FlowMap& _flow*/) : 
  1039       GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
  1040 
  1041     class Edge; 
  1042     class OutEdgeIt; 
  1043     friend class Edge; 
  1044     friend class OutEdgeIt; 
  1045 
  1046     //template<typename T> class NodeMap;    
  1047     template<typename T> class EdgeMap;
  1048 
  1049     typedef typename GraphWrapper<Graph>::Node Node;
  1050     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
  1051 
  1052     class Edge : public Graph::Edge {
  1053       friend class OldBidirGraphWrapper<Graph>;
  1054       ///\bug ez nem is kell
  1055       //template<typename T> friend class NodeMap;
  1056       template<typename T> friend class EdgeMap;
  1057     protected:
  1058       bool backward; //true, iff backward
  1059 //      typename Graph::Edge e;
  1060     public:
  1061       Edge() { }
  1062       ///\bug =false kell-e? zsoltnak kell az addEdge miatt
  1063       Edge(const typename Graph::Edge& _e, bool _backward=false) : 
  1064 	Graph::Edge(_e), backward(_backward) { }
  1065       Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
  1066 //the unique invalid iterator
  1067       friend bool operator==(const Edge& u, const Edge& v) { 
  1068 	return (v.backward==u.backward && 
  1069 		static_cast<typename Graph::Edge>(u)==
  1070 		static_cast<typename Graph::Edge>(v));
  1071       } 
  1072       friend bool operator!=(const Edge& u, const Edge& v) { 
  1073 	return (v.backward!=u.backward || 
  1074 		static_cast<typename Graph::Edge>(u)!=
  1075 		static_cast<typename Graph::Edge>(v));
  1076       } 
  1077     };
  1078 
  1079     class OutEdgeIt {
  1080       friend class OldBidirGraphWrapper<Graph>;
  1081     protected:
  1082       typename Graph::OutEdgeIt out;
  1083       typename Graph::InEdgeIt in;
  1084       bool backward;
  1085     public:
  1086       OutEdgeIt() { }
  1087       //FIXME
  1088 //      OutEdgeIt(const Edge& e) : Edge(e) { }
  1089       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
  1090 //the unique invalid iterator
  1091       OutEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) { 
  1092 	backward=false;
  1093 	_G.graph->first(out, v);
  1094 	while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
  1095 	if (!_G.graph->valid(out)) {
  1096 	  backward=true;
  1097 	  _G.graph->first(in, v);
  1098 	  while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
  1099 	}
  1100       }
  1101       operator Edge() const { 
  1102 //	Edge e;
  1103 //	e.forward=this->forward;
  1104 //	if (this->forward) e=out; else e=in;
  1105 //	return e;
  1106 	if (this->backward) 
  1107 	  return Edge(in, this->backward); 
  1108 	else 
  1109 	  return Edge(out, this->backward);
  1110       }
  1111     };
  1112 
  1113     class InEdgeIt {
  1114       friend class OldBidirGraphWrapper<Graph>;
  1115     protected:
  1116       typename Graph::OutEdgeIt out;
  1117       typename Graph::InEdgeIt in;
  1118       bool backward;
  1119     public:
  1120       InEdgeIt() { }
  1121       //FIXME
  1122 //      OutEdgeIt(const Edge& e) : Edge(e) { }
  1123       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
  1124 //the unique invalid iterator
  1125       InEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) { 
  1126 	backward=false;
  1127 	_G.graph->first(in, v);
  1128 	while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
  1129 	if (!_G.graph->valid(in)) {
  1130 	  backward=true;
  1131 	  _G.graph->first(out, v);
  1132 	  while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
  1133 	}
  1134       }
  1135       operator Edge() const { 
  1136 //	Edge e;
  1137 //	e.forward=this->forward;
  1138 //	if (this->forward) e=out; else e=in;
  1139 //	return e;
  1140 	if (this->backward) 
  1141 	  return Edge(out, this->backward); 
  1142 	else 
  1143 	  return Edge(in, this->backward);
  1144       }
  1145     };
  1146 
  1147     class EdgeIt {
  1148       friend class OldBidirGraphWrapper<Graph>;
  1149     protected:
  1150       typename Graph::EdgeIt e;
  1151       bool backward;
  1152     public:
  1153       EdgeIt() { }
  1154       EdgeIt(const Invalid& i) : e(i), backward(true) { }
  1155       EdgeIt(const OldBidirGraphWrapper<Graph>& _G) { 
  1156 	backward=false;
  1157 	_G.graph->first(e);
  1158 	while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
  1159 	if (!_G.graph->valid(e)) {
  1160 	  backward=true;
  1161 	  _G.graph->first(e);
  1162 	  while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
  1163 	}
  1164       }
  1165       operator Edge() const { 
  1166 	return Edge(e, this->backward);
  1167       }
  1168     };
  1169 
  1170     using GraphWrapper<Graph>::first;
  1171 //     NodeIt& first(NodeIt& i) const { 
  1172 //       i=NodeIt(*this); return i;
  1173 //     }
  1174     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
  1175       i=OutEdgeIt(*this, p); return i;
  1176     }
  1177 //    FIXME not tested
  1178     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
  1179       i=InEdgeIt(*this, p); return i;
  1180     }
  1181     EdgeIt& first(EdgeIt& i) const { 
  1182       i=EdgeIt(*this); return i;
  1183     }
  1184   
  1185     using GraphWrapper<Graph>::next;
  1186 //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
  1187     OutEdgeIt& next(OutEdgeIt& e) const { 
  1188       if (!e.backward) {
  1189 	Node v=this->graph->aNode(e.out);
  1190 	this->graph->next(e.out);
  1191 	while(this->graph->valid(e.out) && !enabled(e)) { 
  1192 	  this->graph->next(e.out); }
  1193 	if (!this->graph->valid(e.out)) {
  1194 	  e.backward=true;
  1195 	  this->graph->first(e.in, v); 
  1196 	  while(this->graph->valid(e.in) && !enabled(e)) { 
  1197 	    this->graph->next(e.in); }
  1198 	}
  1199       } else {
  1200 	this->graph->next(e.in);
  1201 	while(this->graph->valid(e.in) && !enabled(e)) { 
  1202 	  this->graph->next(e.in); } 
  1203       }
  1204       return e;
  1205     }
  1206 //     FIXME Not tested
  1207     InEdgeIt& next(InEdgeIt& e) const { 
  1208       if (!e.backward) {
  1209 	Node v=this->graph->aNode(e.in);
  1210 	this->graph->next(e.in);
  1211 	while(this->graph->valid(e.in) && !enabled(e)) { 
  1212 	  this->graph->next(e.in); }
  1213 	if (!this->graph->valid(e.in)) {
  1214 	  e.backward=true;
  1215 	  this->graph->first(e.out, v); 
  1216 	  while(this->graph->valid(e.out) && !enabled(e)) { 
  1217 	    this->graph->next(e.out); }
  1218 	}
  1219       } else {
  1220 	this->graph->next(e.out);
  1221 	while(this->graph->valid(e.out) && !enabled(e)) { 
  1222 	  this->graph->next(e.out); } 
  1223       }
  1224       return e;
  1225     }
  1226     EdgeIt& next(EdgeIt& e) const {
  1227       if (!e.backward) {
  1228 	this->graph->next(e.e);
  1229 	while(this->graph->valid(e.e) && !enabled(e)) { 
  1230 	  this->graph->next(e.e); }
  1231 	if (!this->graph->valid(e.e)) {
  1232 	  e.backward=true;
  1233 	  this->graph->first(e.e); 
  1234 	  while(this->graph->valid(e.e) && !enabled(e)) { 
  1235 	    this->graph->next(e.e); }
  1236 	}
  1237       } else {
  1238 	this->graph->next(e.e);
  1239 	while(this->graph->valid(e.e) && !enabled(e)) { 
  1240 	  this->graph->next(e.e); } 
  1241       }
  1242       return e;
  1243     }
  1244 
  1245     Node tail(Edge e) const { 
  1246       return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
  1247     Node head(Edge e) const { 
  1248       return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
  1249 
  1250     Node aNode(OutEdgeIt e) const { 
  1251       return ((!e.backward) ? this->graph->aNode(e.out) : 
  1252 	      this->graph->aNode(e.in)); }
  1253     Node bNode(OutEdgeIt e) const { 
  1254       return ((!e.backward) ? this->graph->bNode(e.out) : 
  1255 	      this->graph->bNode(e.in)); }
  1256 
  1257     Node aNode(InEdgeIt e) const { 
  1258       return ((!e.backward) ? this->graph->aNode(e.in) : 
  1259 	      this->graph->aNode(e.out)); }
  1260     Node bNode(InEdgeIt e) const { 
  1261       return ((!e.backward) ? this->graph->bNode(e.in) : 
  1262 	      this->graph->bNode(e.out)); }
  1263 
  1264     /// Gives back the opposite edge.
  1265     Edge opposite(const Edge& e) const { 
  1266       Edge f=e;
  1267       f.backward=!f.backward;
  1268       return f;
  1269     }
  1270 
  1271 //    int nodeNum() const { return graph->nodeNum(); }
  1272     //FIXME
  1273     void edgeNum() const { }
  1274     //int edgeNum() const { return graph->edgeNum(); }
  1275 
  1276 
  1277 //    int id(Node v) const { return graph->id(v); }
  1278 
  1279     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
  1280     bool valid(Edge e) const { 
  1281       return this->graph->valid(e);
  1282 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
  1283     }
  1284 
  1285     bool forward(const Edge& e) const { return !e.backward; }
  1286     bool backward(const Edge& e) const { return e.backward; }
  1287 
  1288 //     void augment(const Edge& e, Number a) const {
  1289 //       if (!e.backward)  
  1290 // // 	flow->set(e.out, flow->get(e.out)+a);
  1291 // 	flow->set(e, (*flow)[e]+a);
  1292 //       else  
  1293 // // 	flow->set(e.in, flow->get(e.in)-a);
  1294 // 	flow->set(e, (*flow)[e]-a);
  1295 //     }
  1296 
  1297     bool enabled(const Edge& e) const { 
  1298       if (!e.backward) 
  1299 //	return (capacity->get(e.out)-flow->get(e.out)); 
  1300 	//return ((*capacity)[e]-(*flow)[e]);
  1301 	return true;
  1302       else 
  1303 //	return (flow->get(e.in)); 
  1304 	//return ((*flow)[e]); 
  1305 	return true;
  1306     }
  1307 
  1308 //     Number enabled(typename Graph::OutEdgeIt out) const { 
  1309 // //      return (capacity->get(out)-flow->get(out)); 
  1310 //       return ((*capacity)[out]-(*flow)[out]); 
  1311 //     }
  1312     
  1313 //     Number enabled(typename Graph::InEdgeIt in) const { 
  1314 // //      return (flow->get(in)); 
  1315 //       return ((*flow)[in]); 
  1316 //     }
  1317 
  1318     template <typename T>
  1319     class EdgeMap {
  1320       typename Graph::template EdgeMap<T> forward_map, backward_map; 
  1321     public:
  1322       typedef T ValueType;
  1323       typedef Edge KeyType;
  1324       EdgeMap(const OldBidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
  1325       EdgeMap(const OldBidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
  1326       void set(Edge e, T a) { 
  1327 	if (!e.backward) 
  1328 	  forward_map.set(e/*.out*/, a); 
  1329 	else 
  1330 	  backward_map.set(e/*.in*/, a); 
  1331       }
  1332       T operator[](Edge e) const { 
  1333 	if (!e.backward) 
  1334 	  return forward_map[e/*.out*/]; 
  1335 	else 
  1336 	  return backward_map[e/*.in*/]; 
  1337       }
  1338       void update() { 
  1339 	forward_map.update(); 
  1340 	backward_map.update();
  1341       }
  1342 //       T get(Edge e) const { 
  1343 // 	if (e.out_or_in) 
  1344 // 	  return forward_map.get(e.out); 
  1345 // 	else 
  1346 // 	  return backward_map.get(e.in); 
  1347 //       }
  1348     };
  1349   };
  1350 
  1351 
  1352 
  1353   /// \brief A bidirected graph template.
  1354   ///
  1355   /// A bidirected graph template.
  1356   /// Such a bidirected graph stores each pair of oppositely directed edges 
  1357   /// ones in the memory, i.e. a directed graph of type 
  1358   /// \c Graph is used for that.
  1359   /// As the oppositely directed edges are logically different ones 
  1360   /// the maps are able to attach different values for them.
  1361   /// \ingroup graphs
  1362   template<typename Graph>
  1363   class BidirGraph : public BidirGraphWrapper<Graph> {
  1364   public:
  1365     typedef UndirGraphWrapper<Graph> Parent;
  1366   protected:
  1367     Graph gr;
  1368   public:
  1369     BidirGraph() : BidirGraphWrapper<Graph>() { 
  1370       Parent::setGraph(gr); 
  1371     }
  1372   };
  1373 
  1374 
  1375 
  1376   template<typename Graph, typename Number,
  1377 	   typename CapacityMap, typename FlowMap>
  1378   class ResForwardFilter {
  1379     //    const Graph* graph;
  1380     const CapacityMap* capacity;
  1381     const FlowMap* flow;
  1382   public:
  1383     ResForwardFilter(/*const Graph& _graph, */
  1384 		     const CapacityMap& _capacity, const FlowMap& _flow) :
  1385       /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
  1386     ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
  1387     //void setGraph(const Graph& _graph) { graph=&_graph; }
  1388     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
  1389     void setFlow(const FlowMap& _flow) { flow=&_flow; }
  1390     bool operator[](const typename Graph::Edge& e) const {
  1391       return ((*flow)[e] < (*capacity)[e]);
  1392     }
  1393   };
  1394 
  1395   template<typename Graph, typename Number,
  1396 	   typename CapacityMap, typename FlowMap>
  1397   class ResBackwardFilter {
  1398     //const Graph* graph;
  1399     const CapacityMap* capacity;
  1400     const FlowMap* flow;
  1401   public:
  1402     ResBackwardFilter(/*const Graph& _graph,*/ 
  1403 		      const CapacityMap& _capacity, const FlowMap& _flow) :
  1404       /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
  1405     ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
  1406     //void setGraph(const Graph& _graph) { graph=&_graph; }
  1407     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
  1408     void setFlow(const FlowMap& _flow) { flow=&_flow; }
  1409     bool operator[](const typename Graph::Edge& e) const {
  1410       return (0 < (*flow)[e]);
  1411     }
  1412   };
  1413 
  1414   
  1415   /// A wrapper for composing the residual graph for directed flow and circulation problems.
  1416 
  1417   /// A wrapper for composing the residual graph for directed flow and circulation problems.
  1418   template<typename Graph, typename Number, 
  1419 	   typename CapacityMap, typename FlowMap>
  1420   class ResGraphWrapper : 
  1421     public SubBidirGraphWrapper< 
  1422     Graph, 
  1423     ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
  1424     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
  1425   public:
  1426     typedef SubBidirGraphWrapper< 
  1427       Graph, 
  1428       ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
  1429       ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
  1430   protected:
  1431     const CapacityMap* capacity;
  1432     FlowMap* flow;
  1433     ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
  1434     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
  1435     ResGraphWrapper() : Parent(), 
  1436  			capacity(0), flow(0) { }
  1437     void setCapacityMap(const CapacityMap& _capacity) {
  1438       capacity=&_capacity;
  1439       forward_filter.setCapacity(_capacity);
  1440       backward_filter.setCapacity(_capacity);
  1441     }
  1442     void setFlowMap(FlowMap& _flow) {
  1443       flow=&_flow;
  1444       forward_filter.setFlow(_flow);
  1445       backward_filter.setFlow(_flow);
  1446     }
  1447 //     /// \bug does graph reference needed in filtermaps??
  1448 //     void setGraph(const Graph& _graph) { 
  1449 //       Parent::setGraph(_graph);
  1450 //       forward_filter.setGraph(_graph);
  1451 //       backward_filter.setGraph(_graph);
  1452 //     }
  1453   public:
  1454     ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
  1455 		       FlowMap& _flow) : 
  1456       Parent(), capacity(&_capacity), flow(&_flow), 
  1457       forward_filter(/*_graph,*/ _capacity, _flow), 
  1458       backward_filter(/*_graph,*/ _capacity, _flow) {
  1459       Parent::setGraph(_graph);
  1460       Parent::setForwardFilterMap(forward_filter);
  1461       Parent::setBackwardFilterMap(backward_filter);
  1462     }
  1463 
  1464     typedef typename Parent::Edge Edge;
  1465 
  1466     //    bool forward(const Parent::Edge& e) const { return Parent::forward(e); }
  1467     //bool backward(const Edge& e) const { return e.backward; }
  1468 
  1469     void augment(const Edge& e, Number a) const {
  1470       if (Parent::forward(e))  
  1471 // 	flow->set(e.out, flow->get(e.out)+a);
  1472 	flow->set(e, (*flow)[e]+a);
  1473       else  
  1474 	//flow->set(e.in, flow->get(e.in)-a);
  1475 	flow->set(e, (*flow)[e]-a);
  1476     }
  1477 
  1478     /// \deprecated
  1479     ///
  1480     Number resCap(const Edge& e) const { 
  1481       if (Parent::forward(e)) 
  1482 //	return (capacity->get(e.out)-flow->get(e.out)); 
  1483 	return ((*capacity)[e]-(*flow)[e]); 
  1484       else 
  1485 //	return (flow->get(e.in)); 
  1486 	return ((*flow)[e]); 
  1487     }
  1488 
  1489     /// \brief Residual capacity map.
  1490     ///
  1491     /// In generic residual graphs the residual capacity can be obtained as a map.
  1492     class ResCap {
  1493     protected:
  1494       const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
  1495     public:
  1496       typedef Number ValueType;
  1497       typedef Edge KeyType;
  1498       ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _res_graph) : 
  1499 	res_graph(&_res_graph) { }
  1500       Number operator[](const Edge& e) const { 
  1501 	if (res_graph->forward(e)) 
  1502 	  //	return (capacity->get(e.out)-flow->get(e.out)); 
  1503 	  return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e]; 
  1504 	else 
  1505 	  //	return (flow->get(e.in)); 
  1506 	  return (*(res_graph->flow))[e]; 
  1507       }
  1508       /// \bug not needed with dynamic maps, or does it?
  1509       void update() { }
  1510     };
  1511 
  1512   };
  1513 
  1514 
  1515   template<typename Graph, typename Number, 
  1516 	   typename CapacityMap, typename FlowMap>
  1517   class OldResGraphWrapper : public GraphWrapper<Graph> {
  1518   public:
  1519     typedef GraphWrapper<Graph> Parent; 
  1520   protected:
  1521     const CapacityMap* capacity;
  1522     FlowMap* flow;
  1523 
  1524     OldResGraphWrapper() : GraphWrapper<Graph>(0), 
  1525 			capacity(0), flow(0) { }
  1526     void setCapacityMap(const CapacityMap& _capacity) {
  1527       capacity=&_capacity;
  1528     }
  1529     void setFlowMap(FlowMap& _flow) {
  1530       flow=&_flow;
  1531     }
  1532 
  1533   public:
  1534 
  1535     OldResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
  1536 		    FlowMap& _flow) : 
  1537       GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
  1538 
  1539     class Edge; 
  1540     class OutEdgeIt; 
  1541     friend class Edge; 
  1542     friend class OutEdgeIt; 
  1543 
  1544     typedef typename GraphWrapper<Graph>::Node Node;
  1545     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
  1546     class Edge : public Graph::Edge {
  1547       friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
  1548     protected:
  1549       bool backward; //true, iff backward
  1550 //      typename Graph::Edge e;
  1551     public:
  1552       Edge() { }
  1553       Edge(const typename Graph::Edge& _e, bool _backward) : 
  1554 	Graph::Edge(_e), backward(_backward) { }
  1555       Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
  1556 //the unique invalid iterator
  1557       friend bool operator==(const Edge& u, const Edge& v) { 
  1558 	return (v.backward==u.backward && 
  1559 		static_cast<typename Graph::Edge>(u)==
  1560 		static_cast<typename Graph::Edge>(v));
  1561       } 
  1562       friend bool operator!=(const Edge& u, const Edge& v) { 
  1563 	return (v.backward!=u.backward || 
  1564 		static_cast<typename Graph::Edge>(u)!=
  1565 		static_cast<typename Graph::Edge>(v));
  1566       } 
  1567     };
  1568 
  1569     class OutEdgeIt {
  1570       friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
  1571     protected:
  1572       typename Graph::OutEdgeIt out;
  1573       typename Graph::InEdgeIt in;
  1574       bool backward;
  1575     public:
  1576       OutEdgeIt() { }
  1577       //FIXME
  1578 //      OutEdgeIt(const Edge& e) : Edge(e) { }
  1579       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
  1580 //the unique invalid iterator
  1581       OutEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 
  1582 	backward=false;
  1583 	_G.graph->first(out, v);
  1584 	while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
  1585 	if (!_G.graph->valid(out)) {
  1586 	  backward=true;
  1587 	  _G.graph->first(in, v);
  1588 	  while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
  1589 	}
  1590       }
  1591       operator Edge() const { 
  1592 //	Edge e;
  1593 //	e.forward=this->forward;
  1594 //	if (this->forward) e=out; else e=in;
  1595 //	return e;
  1596 	if (this->backward) 
  1597 	  return Edge(in, this->backward); 
  1598 	else 
  1599 	  return Edge(out, this->backward);
  1600       }
  1601     };
  1602 
  1603     class InEdgeIt {
  1604       friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
  1605     protected:
  1606       typename Graph::OutEdgeIt out;
  1607       typename Graph::InEdgeIt in;
  1608       bool backward;
  1609     public:
  1610       InEdgeIt() { }
  1611       //FIXME
  1612 //      OutEdgeIt(const Edge& e) : Edge(e) { }
  1613       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
  1614 //the unique invalid iterator
  1615       InEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 
  1616 	backward=false;
  1617 	_G.graph->first(in, v);
  1618 	while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
  1619 	if (!_G.graph->valid(in)) {
  1620 	  backward=true;
  1621 	  _G.graph->first(out, v);
  1622 	  while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
  1623 	}
  1624       }
  1625       operator Edge() const { 
  1626 //	Edge e;
  1627 //	e.forward=this->forward;
  1628 //	if (this->forward) e=out; else e=in;
  1629 //	return e;
  1630 	if (this->backward) 
  1631 	  return Edge(out, this->backward); 
  1632 	else 
  1633 	  return Edge(in, this->backward);
  1634       }
  1635     };
  1636 
  1637     class EdgeIt {
  1638       friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
  1639     protected:
  1640       typename Graph::EdgeIt e;
  1641       bool backward;
  1642     public:
  1643       EdgeIt() { }
  1644       EdgeIt(const Invalid& i) : e(i), backward(true) { }
  1645       EdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) { 
  1646 	backward=false;
  1647 	_G.graph->first(e);
  1648 	while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
  1649 	if (!_G.graph->valid(e)) {
  1650 	  backward=true;
  1651 	  _G.graph->first(e);
  1652 	  while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
  1653 	}
  1654       }
  1655       operator Edge() const { 
  1656 	return Edge(e, this->backward);
  1657       }
  1658     };
  1659 
  1660     using GraphWrapper<Graph>::first;
  1661 //     NodeIt& first(NodeIt& i) const { 
  1662 //       i=NodeIt(*this); return i;
  1663 //     }
  1664     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
  1665       i=OutEdgeIt(*this, p); return i;
  1666     }
  1667 //    FIXME not tested
  1668     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
  1669       i=InEdgeIt(*this, p); return i;
  1670     }
  1671     EdgeIt& first(EdgeIt& i) const { 
  1672       i=EdgeIt(*this); return i;
  1673     }
  1674   
  1675     using GraphWrapper<Graph>::next;
  1676 //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
  1677     OutEdgeIt& next(OutEdgeIt& e) const { 
  1678       if (!e.backward) {
  1679 	Node v=this->graph->aNode(e.out);
  1680 	this->graph->next(e.out);
  1681 	while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
  1682 	  this->graph->next(e.out); }
  1683 	if (!this->graph->valid(e.out)) {
  1684 	  e.backward=true;
  1685 	  this->graph->first(e.in, v); 
  1686 	  while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
  1687 	    this->graph->next(e.in); }
  1688 	}
  1689       } else {
  1690 	this->graph->next(e.in);
  1691 	while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
  1692 	  this->graph->next(e.in); } 
  1693       }
  1694       return e;
  1695     }
  1696 //     FIXME Not tested
  1697     InEdgeIt& next(InEdgeIt& e) const { 
  1698       if (!e.backward) {
  1699 	Node v=this->graph->aNode(e.in);
  1700 	this->graph->next(e.in);
  1701 	while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
  1702 	  this->graph->next(e.in); }
  1703 	if (!this->graph->valid(e.in)) {
  1704 	  e.backward=true;
  1705 	  this->graph->first(e.out, v); 
  1706 	  while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
  1707 	    this->graph->next(e.out); }
  1708 	}
  1709       } else {
  1710 	this->graph->next(e.out);
  1711 	while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
  1712 	  this->graph->next(e.out); } 
  1713       }
  1714       return e;
  1715     }
  1716     EdgeIt& next(EdgeIt& e) const {
  1717       if (!e.backward) {
  1718 	this->graph->next(e.e);
  1719 	while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
  1720 	  this->graph->next(e.e); }
  1721 	if (!this->graph->valid(e.e)) {
  1722 	  e.backward=true;
  1723 	  this->graph->first(e.e); 
  1724 	  while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
  1725 	    this->graph->next(e.e); }
  1726 	}
  1727       } else {
  1728 	this->graph->next(e.e);
  1729 	while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
  1730 	  this->graph->next(e.e); } 
  1731       }
  1732       return e;
  1733     }
  1734 
  1735     Node tail(Edge e) const { 
  1736       return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
  1737     Node head(Edge e) const { 
  1738       return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
  1739 
  1740     Node aNode(OutEdgeIt e) const { 
  1741       return ((!e.backward) ? this->graph->aNode(e.out) : 
  1742 	      this->graph->aNode(e.in)); }
  1743     Node bNode(OutEdgeIt e) const { 
  1744       return ((!e.backward) ? this->graph->bNode(e.out) : 
  1745 	      this->graph->bNode(e.in)); }
  1746 
  1747     Node aNode(InEdgeIt e) const { 
  1748       return ((!e.backward) ? this->graph->aNode(e.in) : 
  1749 	      this->graph->aNode(e.out)); }
  1750     Node bNode(InEdgeIt e) const { 
  1751       return ((!e.backward) ? this->graph->bNode(e.in) : 
  1752 	      this->graph->bNode(e.out)); }
  1753 
  1754 //    int nodeNum() const { return graph->nodeNum(); }
  1755     //FIXME
  1756     void edgeNum() const { }
  1757     //int edgeNum() const { return graph->edgeNum(); }
  1758 
  1759 
  1760 //    int id(Node v) const { return graph->id(v); }
  1761 
  1762     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
  1763     bool valid(Edge e) const { 
  1764       return this->graph->valid(e);
  1765 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
  1766     }
  1767 
  1768     bool forward(const Edge& e) const { return !e.backward; }
  1769     bool backward(const Edge& e) const { return e.backward; }
  1770 
  1771     void augment(const Edge& e, Number a) const {
  1772       if (!e.backward)  
  1773 // 	flow->set(e.out, flow->get(e.out)+a);
  1774 	flow->set(e, (*flow)[e]+a);
  1775       else  
  1776 // 	flow->set(e.in, flow->get(e.in)-a);
  1777 	flow->set(e, (*flow)[e]-a);
  1778     }
  1779 
  1780     Number resCap(const Edge& e) const { 
  1781       if (!e.backward) 
  1782 //	return (capacity->get(e.out)-flow->get(e.out)); 
  1783 	return ((*capacity)[e]-(*flow)[e]); 
  1784       else 
  1785 //	return (flow->get(e.in)); 
  1786 	return ((*flow)[e]); 
  1787     }
  1788 
  1789 //     Number resCap(typename Graph::OutEdgeIt out) const { 
  1790 // //      return (capacity->get(out)-flow->get(out)); 
  1791 //       return ((*capacity)[out]-(*flow)[out]); 
  1792 //     }
  1793     
  1794 //     Number resCap(typename Graph::InEdgeIt in) const { 
  1795 // //      return (flow->get(in)); 
  1796 //       return ((*flow)[in]); 
  1797 //     }
  1798 
  1799     template <typename T>
  1800     class EdgeMap {
  1801       typename Graph::template EdgeMap<T> forward_map, backward_map; 
  1802     public:
  1803       typedef T ValueType;
  1804       typedef Edge KeyType;
  1805       EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
  1806       EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
  1807       void set(Edge e, T a) { 
  1808 	if (!e.backward) 
  1809 	  forward_map.set(e/*.out*/, a); 
  1810 	else 
  1811 	  backward_map.set(e/*.in*/, a); 
  1812       }
  1813       T operator[](Edge e) const { 
  1814 	if (!e.backward) 
  1815 	  return forward_map[e/*.out*/]; 
  1816 	else 
  1817 	  return backward_map[e/*.in*/]; 
  1818       }
  1819       void update() { 
  1820 	forward_map.update(); 
  1821 	backward_map.update();
  1822       }
  1823 //       T get(Edge e) const { 
  1824 // 	if (e.out_or_in) 
  1825 // 	  return forward_map.get(e.out); 
  1826 // 	else 
  1827 // 	  return backward_map.get(e.in); 
  1828 //       }
  1829     };
  1830   };
  1831 
  1832 
  1833 
  1834   /// For blocking flows.
  1835 
  1836   /// This graph wrapper is used for Dinits blocking flow computations.
  1837   /// For each node, an out-edge is stored which is used when the 
  1838   /// \code 
  1839   /// OutEdgeIt& first(OutEdgeIt&, const Node&)
  1840   /// \endcode
  1841   /// is called. 
  1842   ///
  1843   ///\author Marton Makai
  1844   template<typename Graph, typename FirstOutEdgesMap>
  1845   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
  1846   public:
  1847     typedef GraphWrapper<Graph> Parent; 
  1848   protected:
  1849     FirstOutEdgesMap* first_out_edges;
  1850   public:
  1851     ErasingFirstGraphWrapper(Graph& _graph, 
  1852 			     FirstOutEdgesMap& _first_out_edges) : 
  1853       GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }  
  1854 
  1855     typedef typename GraphWrapper<Graph>::Node Node;
  1856 //     class NodeIt { 
  1857 //       friend class GraphWrapper<Graph>;
  1858 //       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
  1859 //       typename Graph::NodeIt n;
  1860 //      public:
  1861 //       NodeIt() { }
  1862 //       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
  1863 //       NodeIt(const Invalid& i) : n(i) { }
  1864 //       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
  1865 // 	n(*(_G.graph)) { }
  1866 //       operator Node() const { return Node(typename Graph::Node(n)); }
  1867 //     };
  1868     typedef typename GraphWrapper<Graph>::Edge Edge;
  1869     class OutEdgeIt { 
  1870       friend class GraphWrapper<Graph>;
  1871       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
  1872 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
  1873       typename Graph::OutEdgeIt e;
  1874     public:
  1875       OutEdgeIt() { }
  1876       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
  1877       OutEdgeIt(const Invalid& i) : e(i) { }
  1878       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
  1879 		const Node& _n) : 
  1880 	e((*_G.first_out_edges)[_n]) { }
  1881       operator Edge() const { return Edge(typename Graph::Edge(e)); }
  1882     };
  1883     class InEdgeIt { 
  1884       friend class GraphWrapper<Graph>;
  1885       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
  1886 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;
  1887       typename Graph::InEdgeIt e;
  1888     public:
  1889       InEdgeIt() { }
  1890       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
  1891       InEdgeIt(const Invalid& i) : e(i) { }
  1892       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
  1893 	       const Node& _n) : 
  1894 	e(*(_G.graph), typename Graph::Node(_n)) { }
  1895       operator Edge() const { return Edge(typename Graph::Edge(e)); }
  1896     };
  1897     //typedef typename Graph::SymEdgeIt SymEdgeIt;
  1898     class EdgeIt { 
  1899       friend class GraphWrapper<Graph>;
  1900       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
  1901 //      typedef typename Graph::EdgeIt GraphEdgeIt;
  1902       typename Graph::EdgeIt e;
  1903     public:
  1904       EdgeIt() { }
  1905       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
  1906       EdgeIt(const Invalid& i) : e(i) { }
  1907       EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
  1908 	e(*(_G.graph)) { }
  1909       operator Edge() const { return Edge(typename Graph::Edge(e)); }
  1910     };
  1911 
  1912     using GraphWrapper<Graph>::first;
  1913 //     NodeIt& first(NodeIt& i) const { 
  1914 //       i=NodeIt(*this); return i;
  1915 //     }
  1916     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
  1917       i=OutEdgeIt(*this, p); return i;
  1918     }
  1919     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
  1920       i=InEdgeIt(*this, p); return i;
  1921     }
  1922     EdgeIt& first(EdgeIt& i) const { 
  1923       i=EdgeIt(*this); return i;
  1924     }
  1925 
  1926     using GraphWrapper<Graph>::next;
  1927 //    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
  1928     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
  1929     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
  1930     EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }    
  1931     
  1932     Node aNode(const OutEdgeIt& e) const { 
  1933       return Node(this->graph->aNode(e.e)); }
  1934     Node aNode(const InEdgeIt& e) const { 
  1935       return Node(this->graph->aNode(e.e)); }
  1936     Node bNode(const OutEdgeIt& e) const { 
  1937       return Node(this->graph->bNode(e.e)); }
  1938     Node bNode(const InEdgeIt& e) const { 
  1939       return Node(this->graph->bNode(e.e)); }
  1940 
  1941     void erase(const OutEdgeIt& e) const {
  1942       OutEdgeIt f=e;
  1943       this->next(f);
  1944       first_out_edges->set(this->tail(e), f.e);
  1945     }
  1946   };
  1947 
  1948   ///@}
  1949 
  1950 } //namespace hugo
  1951 
  1952 #endif //HUGO_GRAPH_WRAPPER_H
  1953