diff -r 6114a8ab5d27 -r 7c463a7635d4 src/work/marci/bipartite_graph_wrapper.h
--- a/src/work/marci/bipartite_graph_wrapper.h	Fri Apr 30 13:52:17 2004 +0000
+++ b/src/work/marci/bipartite_graph_wrapper.h	Fri Apr 30 14:02:10 2004 +0000
@@ -1,6 +1,6 @@
 // -*- c++ -*-
-#ifndef HUGO_GRAPH_WRAPPER_H
-#define HUGO_GRAPH_WRAPPER_H
+#ifndef HUGO_BIPARTITE_GRAPH_WRAPPER_H
+#define HUGO_BIPARTITE_GRAPH_WRAPPER_H
 
 ///\ingroup gwrappers
 ///\file
@@ -12,927 +12,10 @@
 
 #include <invalid.h>
 #include <iter_map.h>
+#include <graph_wrapper.h>
 
 namespace hugo {
 
-  // Graph wrappers
-
-  /// \addtogroup gwrappers
-  /// A main parts of HUGOlib are the different graph structures, 
-  /// generic graph algorithms, graph concepts which couple these, and 
-  /// graph wrappers. While the previous ones are more or less clear, the 
-  /// latter notion needs further explanation.
-  /// Graph wrappers are graph classes which serve for considering graph 
-  /// structures in different ways. A short example makes the notion much 
-  /// clearer. 
-  /// Suppose that we have an instance \c g of a directed graph
-  /// type say \c ListGraph and an algorithm 
-  /// \code template<typename Graph> int algorithm(const Graph&); \endcode 
-  /// is needed to run on the reversely oriented graph. 
-  /// It may be expensive (in time or in memory usage) to copy 
-  /// \c g with the reverse orientation. 
-  /// Thus, a wrapper class
-  /// \code template<typename Graph> class RevGraphWrapper; \endcode is used. 
-  /// The code looks as follows
-  /// \code
-  /// ListGraph g;
-  /// RevGraphWrapper<ListGraph> rgw(g);
-  /// int result=algorithm(rgw);
-  /// \endcode
-  /// After running the algorithm, the original graph \c g 
-  /// remains untouched. Thus the graph wrapper used above is to consider the 
-  /// original graph with reverse orientation. 
-  /// This techniques gives rise to an elegant code, and 
-  /// based on stable graph wrappers, complex algorithms can be 
-  /// implemented easily. 
-  /// In flow, circulation and bipartite matching problems, the residual 
-  /// graph is of particular importance. Combining a wrapper implementing 
-  /// this, shortest path algorithms and minimum mean cycle algorithms, 
-  /// a range of weighted and cardinality optimization algorithms can be 
-  /// obtained. For lack of space, for other examples, 
-  /// the interested user is referred to the detailed documentation of graph 
-  /// wrappers. 
-  /// The behavior of graph wrappers can be very different. Some of them keep 
-  /// capabilities of the original graph while in other cases this would be 
-  /// meaningless. This means that the concepts that they are a model of depend 
-  /// on the graph wrapper, and the wrapped graph(s). 
-  /// If an edge of \c rgw is deleted, this is carried out by 
-  /// deleting the corresponding edge of \c g. But for a residual 
-  /// graph, this operation has no sense. 
-  /// Let we stand one more example here to simplify your work. 
-  /// wrapper class
-  /// \code template<typename Graph> class RevGraphWrapper; \endcode 
-  /// has constructor 
-  /// <tt> RevGraphWrapper(Graph& _g)</tt>. 
-  /// This means that in a situation, 
-  /// when a <tt> const ListGraph& </tt> reference to a graph is given, 
-  /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
-  /// \code
-  /// int algorithm1(const ListGraph& g) {
-  ///   RevGraphWrapper<const ListGraph> rgw(g);
-  ///   return algorithm2(rgw);
-  /// }
-  /// \endcode
-
-  /// \addtogroup gwrappers
-  /// @{
-
-  ///Base type for the Graph Wrappers
-
-  ///This is the base type for the Graph Wrappers.
-  ///\todo Some more docs... 
-  ///
-  ///\author Marton Makai
- 
-  template<typename Graph>
-  class GraphWrapper {
-  protected:
-    Graph* graph;
-  
-  public:
-    typedef Graph BaseGraph;
-    typedef Graph ParentGraph;
-
-//     GraphWrapper() : graph(0) { }
-    GraphWrapper(Graph& _graph) : graph(&_graph) { }
-//     void setGraph(Graph& _graph) { graph=&_graph; }
-//     Graph& getGraph() const { return *graph; }
- 
-//    typedef typename Graph::Node Node;
-    class Node : public Graph::Node {
-      friend class GraphWrapper<Graph>;
-    public:
-      Node() { }
-      Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
-      Node(const Invalid& i) : Graph::Node(i) { }
-    };
-    class NodeIt { 
-      friend class GraphWrapper<Graph>;
-      typename Graph::NodeIt n;
-     public:
-      NodeIt() { }
-      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
-      NodeIt(const Invalid& i) : n(i) { }
-      NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
-      operator Node() const { return Node(typename Graph::Node(n)); }
-    };
-//    typedef typename Graph::Edge Edge;
-    class Edge : public Graph::Edge {
-      friend class GraphWrapper<Graph>;
-    public:
-      Edge() { }
-      Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
-      Edge(const Invalid& i) : Graph::Edge(i) { }
-    };
-    class OutEdgeIt { 
-      friend class GraphWrapper<Graph>;
-      typename Graph::OutEdgeIt e;
-    public:
-      OutEdgeIt() { }
-      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
-      OutEdgeIt(const Invalid& i) : e(i) { }
-      OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
-	e(*(_G.graph), typename Graph::Node(_n)) { }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
-    class InEdgeIt { 
-      friend class GraphWrapper<Graph>;
-      typename Graph::InEdgeIt e;
-    public:
-      InEdgeIt() { }
-      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
-      InEdgeIt(const Invalid& i) : e(i) { }
-      InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
-	e(*(_G.graph), typename Graph::Node(_n)) { }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
-    //typedef typename Graph::SymEdgeIt SymEdgeIt;
-    class EdgeIt { 
-      friend class GraphWrapper<Graph>;
-      typename Graph::EdgeIt e;
-    public:
-      EdgeIt() { }
-      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
-      EdgeIt(const Invalid& i) : e(i) { }
-      EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
-   
-    NodeIt& first(NodeIt& i) const { 
-      i=NodeIt(*this); return i;
-    }
-    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
-      i=OutEdgeIt(*this, p); return i;
-    }
-    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
-      i=InEdgeIt(*this, p); return i;
-    }
-    EdgeIt& first(EdgeIt& i) const { 
-      i=EdgeIt(*this); return i;
-    }
-
-    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
-    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
-    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
-    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }    
-
-    Node tail(const Edge& e) const { 
-      return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
-    Node head(const Edge& e) const { 
-      return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
-
-    bool valid(const Node& n) const { 
-      return graph->valid(static_cast<typename Graph::Node>(n)); }
-    bool valid(const Edge& e) const { 
-      return graph->valid(static_cast<typename Graph::Edge>(e)); }
-
-    int nodeNum() const { return graph->nodeNum(); }
-    int edgeNum() const { return graph->edgeNum(); }
-  
-    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
-    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
-    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
-    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
-  
-    Node addNode() const { return Node(graph->addNode()); }
-    Edge addEdge(const Node& tail, const Node& head) const { 
-      return Edge(graph->addEdge(tail, head)); }
-
-    void erase(const Node& i) const { graph->erase(i); }
-    void erase(const Edge& i) const { graph->erase(i); }
-  
-    void clear() const { graph->clear(); }
-    
-    template<typename T> class NodeMap : public Graph::template NodeMap<T> { 
-      typedef typename Graph::template NodeMap<T> Parent;
-    public:
-      NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }
-      NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
-    };
-
-    template<typename T> class EdgeMap : public Graph::template EdgeMap<T> { 
-      typedef typename Graph::template EdgeMap<T> Parent;
-    public:
-      EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
-      EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
-    };
-  };
-
-  /// A graph wrapper which reverses the orientation of the edges.
-
-  /// A graph wrapper which reverses the orientation of the edges.
-  ///
-  ///\author Marton Makai
-  template<typename Graph>
-  class RevGraphWrapper : public GraphWrapper<Graph> {
-  public:
-
-    RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  
-
-    typedef typename GraphWrapper<Graph>::Node Node;
-    typedef typename GraphWrapper<Graph>::Edge Edge;
-    //If Graph::OutEdgeIt is not defined
-    //and we do not want to use RevGraphWrapper::InEdgeIt,
-    //the typdef techinque does not work.
-    //Unfortunately all the typedefs are instantiated in templates.
-    //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
-    //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
-
-    class OutEdgeIt { 
-      friend class GraphWrapper<Graph>;
-      friend class RevGraphWrapper<Graph>;
-      typename Graph::InEdgeIt e;
-    public:
-      OutEdgeIt() { }
-      OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
-      OutEdgeIt(const Invalid& i) : e(i) { }
-      OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
-	e(*(_G.graph), typename Graph::Node(_n)) { }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
-    class InEdgeIt { 
-      friend class GraphWrapper<Graph>;
-      friend class RevGraphWrapper<Graph>;
-      typename Graph::OutEdgeIt e;
-    public:
-      InEdgeIt() { }
-      InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
-      InEdgeIt(const Invalid& i) : e(i) { }
-      InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
-	e(*(_G.graph), typename Graph::Node(_n)) { }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
-
-    using GraphWrapper<Graph>::first;
-    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
-      i=OutEdgeIt(*this, p); return i;
-    }
-    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
-      i=InEdgeIt(*this, p); return i;
-    }
-
-    using GraphWrapper<Graph>::next;
-    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
-    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
-
-    Node aNode(const OutEdgeIt& e) const { 
-      return Node(this->graph->aNode(e.e)); }
-    Node aNode(const InEdgeIt& e) const { 
-      return Node(this->graph->aNode(e.e)); }
-    Node bNode(const OutEdgeIt& e) const { 
-      return Node(this->graph->bNode(e.e)); }
-    Node bNode(const InEdgeIt& e) const { 
-      return Node(this->graph->bNode(e.e)); }
-
-    Node tail(const Edge& e) const { 
-      return GraphWrapper<Graph>::head(e); }
-    Node head(const Edge& e) const { 
-      return GraphWrapper<Graph>::tail(e); }
-
-  };
-
-  /// Wrapper for hiding nodes and edges from a graph.
-  
-  /// This wrapper shows a graph with filtered node-set and 
-  /// edge-set. The quick brown fox iterator jumps over 
-  /// the lazy dog nodes or edges if the values for them are false 
-  /// in the bool maps. 
-  ///
-  ///\author Marton Makai
-  template<typename Graph, typename NodeFilterMap, 
-	   typename EdgeFilterMap>
-  class SubGraphWrapper : public GraphWrapper<Graph> {
-  protected:
-    NodeFilterMap* node_filter_map;
-    EdgeFilterMap* edge_filter_map;
-  public:
-
-    SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, 
-		    EdgeFilterMap& _edge_filter_map) : 
-      GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), 
-      edge_filter_map(&_edge_filter_map) { }  
-
-    typedef typename GraphWrapper<Graph>::Node Node;
-    class NodeIt { 
-      friend class GraphWrapper<Graph>;
-      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
-      typename Graph::NodeIt n;
-     public:
-      NodeIt() { }
-      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
-      NodeIt(const Invalid& i) : n(i) { }
-      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
-	n(*(_G.graph)) { 
-	while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n]) 
-	  _G.graph->next(n);
-      }
-      operator Node() const { return Node(typename Graph::Node(n)); }
-    };
-    typedef typename GraphWrapper<Graph>::Edge Edge;
-    class OutEdgeIt { 
-      friend class GraphWrapper<Graph>;
-      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
-      typename Graph::OutEdgeIt e;
-    public:
-      OutEdgeIt() { }
-      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
-      OutEdgeIt(const Invalid& i) : e(i) { }
-      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
-		const Node& _n) : 
-	e(*(_G.graph), typename Graph::Node(_n)) { 
-      	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
-	  _G.graph->next(e);
-      }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
-    class InEdgeIt { 
-      friend class GraphWrapper<Graph>;
-      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
-      typename Graph::InEdgeIt e;
-    public:
-      InEdgeIt() { }
-      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
-      InEdgeIt(const Invalid& i) : e(i) { }
-      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
-	       const Node& _n) : 
-	e(*(_G.graph), typename Graph::Node(_n)) { 
-      	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
-	  _G.graph->next(e);
-      }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
-    //typedef typename Graph::SymEdgeIt SymEdgeIt;
-    class EdgeIt { 
-      friend class GraphWrapper<Graph>;
-      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
-      typename Graph::EdgeIt e;
-    public:
-      EdgeIt() { }
-      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
-      EdgeIt(const Invalid& i) : e(i) { }
-      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
-	e(*(_G.graph)) { 
-      	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
-	  _G.graph->next(e);
-      }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
-
-    NodeIt& first(NodeIt& i) const { 
-      i=NodeIt(*this); return i;
-    }
-    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
-      i=OutEdgeIt(*this, p); return i;
-    }
-    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
-      i=InEdgeIt(*this, p); return i;
-    }
-    EdgeIt& first(EdgeIt& i) const { 
-      i=EdgeIt(*this); return i;
-    }
-    
-    NodeIt& next(NodeIt& i) const {
-      this->graph->next(i.n); 
-      while (this->graph->valid(i) && !(*node_filter_map)[i.n]) { 
-	this->graph->next(i.n); }
-      return i;
-    }
-    OutEdgeIt& next(OutEdgeIt& i) const {
-      this->graph->next(i.e); 
-      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
-	this->graph->next(i.e); }
-      return i;
-    }
-    InEdgeIt& next(InEdgeIt& i) const {
-      this->graph->next(i.e); 
-      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
-	this->graph->next(i.e); }
-      return i;
-    }
-    EdgeIt& next(EdgeIt& i) const {
-      this->graph->next(i.e); 
-      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
-	this->graph->next(i.e); }
-      return i;
-    }
-
-    Node aNode(const OutEdgeIt& e) const { 
-      return Node(this->graph->aNode(e.e)); }
-    Node aNode(const InEdgeIt& e) const { 
-      return Node(this->graph->aNode(e.e)); }
-    Node bNode(const OutEdgeIt& e) const { 
-      return Node(this->graph->bNode(e.e)); }
-    Node bNode(const InEdgeIt& e) const { 
-      return Node(this->graph->bNode(e.e)); }
-
-    ///\todo
-    ///Some doki, please.
-    void hide(const Node& n) const { node_filter_map->set(n, false); }
-    ///\todo
-    ///Some doki, please.
-    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
-
-    ///\todo
-    ///Some doki, please.
-    void unHide(const Node& n) const { node_filter_map->set(n, true); }
-    ///\todo
-    ///Some doki, please.
-    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
-
-    ///\todo
-    ///Some doki, please.
-    bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
-    ///\todo
-    ///Some doki, please.
-    bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
-  };
-
-  /// A wrapper for forgetting the orientation of a graph.
-
-  /// A wrapper for getting an undirected graph by forgetting
-  /// the orientation of a directed one.
-  template<typename Graph>
-  class UndirGraphWrapper : public GraphWrapper<Graph> {
-  public:
-    typedef typename GraphWrapper<Graph>::Node Node;
-    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
-    typedef typename GraphWrapper<Graph>::Edge Edge;
-    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
-
-    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  
-
-    class OutEdgeIt {
-      friend class UndirGraphWrapper<Graph>;
-      bool out_or_in; //true iff out
-      typename Graph::OutEdgeIt out;
-      typename Graph::InEdgeIt in;
-    public:
-      OutEdgeIt() { }
-      OutEdgeIt(const Invalid& i) : Edge(i) { }
-      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
-	out_or_in=true; _G.graph->first(out, _n);
-	if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);	}
-      } 
-      operator Edge() const { 
-	if (out_or_in) return Edge(out); else return Edge(in); 
-      }
-    };
-
-//FIXME InEdgeIt
-    typedef OutEdgeIt InEdgeIt; 
-
-    using GraphWrapper<Graph>::first;
-//     NodeIt& first(NodeIt& i) const { 
-//       i=NodeIt(*this); return i;
-//     }
-    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
-      i=OutEdgeIt(*this, p); return i;
-    }
-//FIXME
-//     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
-//       i=InEdgeIt(*this, p); return i;
-//     }
-//     EdgeIt& first(EdgeIt& i) const { 
-//       i=EdgeIt(*this); return i;
-//     }
-
-    using GraphWrapper<Graph>::next;
-//     NodeIt& next(NodeIt& n) const {
-//       GraphWrapper<Graph>::next(n);
-//       return n;
-//     }
-    OutEdgeIt& next(OutEdgeIt& e) const {
-      if (e.out_or_in) {
-	typename Graph::Node n=this->graph->tail(e.out);
-	this->graph->next(e.out);
-	if (!this->graph->valid(e.out)) { 
-	  e.out_or_in=false; this->graph->first(e.in, n); }
-      } else {
-	this->graph->next(e.in);
-      }
-      return e;
-    }
-    //FIXME InEdgeIt
-//     EdgeIt& next(EdgeIt& e) const {
-//       GraphWrapper<Graph>::next(n);
-// //      graph->next(e.e);
-//       return e;
-//     }
-
-    Node aNode(const OutEdgeIt& e) const { 
-      if (e.out_or_in) return this->graph->tail(e); else 
-	return this->graph->head(e); }
-    Node bNode(const OutEdgeIt& e) const { 
-      if (e.out_or_in) return this->graph->head(e); else 
-	return this->graph->tail(e); }
-  };
-  
-  /// A wrapper for composing the residual graph for directed flow and circulation problems.
-
-  /// A wrapper for composing the residual graph for directed flow and circulation problems.
-  template<typename Graph, typename Number, 
-	   typename CapacityMap, typename FlowMap>
-  class ResGraphWrapper : public GraphWrapper<Graph> {
-  protected:
-    const CapacityMap* capacity;
-    FlowMap* flow;
-  public:
-
-    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
-		    FlowMap& _flow) : 
-      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
-
-    class Edge; 
-    class OutEdgeIt; 
-    friend class Edge; 
-    friend class OutEdgeIt; 
-
-    typedef typename GraphWrapper<Graph>::Node Node;
-    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
-    class Edge : public Graph::Edge {
-      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
-    protected:
-      bool forward; //true, iff forward
-//      typename Graph::Edge e;
-    public:
-      Edge() { }
-      Edge(const typename Graph::Edge& _e, bool _forward) : 
-	Graph::Edge(_e), forward(_forward) { }
-      Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
-//the unique invalid iterator
-      friend bool operator==(const Edge& u, const Edge& v) { 
-	return (v.forward==u.forward && 
-		static_cast<typename Graph::Edge>(u)==
-		static_cast<typename Graph::Edge>(v));
-      } 
-      friend bool operator!=(const Edge& u, const Edge& v) { 
-	return (v.forward!=u.forward || 
-		static_cast<typename Graph::Edge>(u)!=
-		static_cast<typename Graph::Edge>(v));
-      } 
-    };
-
-    class OutEdgeIt {
-      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
-    protected:
-      typename Graph::OutEdgeIt out;
-      typename Graph::InEdgeIt in;
-      bool forward;
-    public:
-      OutEdgeIt() { }
-      //FIXME
-//      OutEdgeIt(const Edge& e) : Edge(e) { }
-      OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
-//the unique invalid iterator
-      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { 
-	forward=true;
-	resG.graph->first(out, v);
-	while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
-	if (!resG.graph->valid(out)) {
-	  forward=false;
-	  resG.graph->first(in, v);
-	  while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
-	}
-      }
-      operator Edge() const { 
-//	Edge e;
-//	e.forward=this->forward;
-//	if (this->forward) e=out; else e=in;
-//	return e;
-	if (this->forward) 
-	  return Edge(out, this->forward); 
-	else 
-	  return Edge(in, this->forward);
-      }
-    };
-
-    class InEdgeIt {
-      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
-    protected:
-      typename Graph::OutEdgeIt out;
-      typename Graph::InEdgeIt in;
-      bool forward;
-    public:
-      InEdgeIt() { }
-      //FIXME
-//      OutEdgeIt(const Edge& e) : Edge(e) { }
-      InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
-//the unique invalid iterator
-      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { 
-	forward=true;
-	resG.graph->first(in, v);
-	while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
-	if (!resG.graph->valid(in)) {
-	  forward=false;
-	  resG.graph->first(out, v);
-	  while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
-	}
-      }
-      operator Edge() const { 
-//	Edge e;
-//	e.forward=this->forward;
-//	if (this->forward) e=out; else e=in;
-//	return e;
-	if (this->forward) 
-	  return Edge(in, this->forward); 
-	else 
-	  return Edge(out, this->forward);
-      }
-    };
-
-    class EdgeIt {
-      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
-    protected:
-      typename Graph::EdgeIt e;
-      bool forward;
-    public:
-      EdgeIt() { }
-      EdgeIt(const Invalid& i) : e(i), forward(false) { }
-      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) { 
-	forward=true;
-	resG.graph->first(e);
-	while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
-	if (!resG.graph->valid(e)) {
-	  forward=false;
-	  resG.graph->first(e);
-	  while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
-	}
-      }
-      operator Edge() const { 
-	return Edge(e, this->forward);
-      }
-    };
-
-    using GraphWrapper<Graph>::first;
-//     NodeIt& first(NodeIt& i) const { 
-//       i=NodeIt(*this); return i;
-//     }
-    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
-      i=OutEdgeIt(*this, p); return i;
-    }
-//    FIXME not tested
-    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
-      i=InEdgeIt(*this, p); return i;
-    }
-    EdgeIt& first(EdgeIt& i) const { 
-      i=EdgeIt(*this); return i;
-    }
-  
-    using GraphWrapper<Graph>::next;
-//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
-    OutEdgeIt& next(OutEdgeIt& e) const { 
-      if (e.forward) {
-	Node v=this->graph->aNode(e.out);
-	this->graph->next(e.out);
-	while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
-	  this->graph->next(e.out); }
-	if (!this->graph->valid(e.out)) {
-	  e.forward=false;
-	  this->graph->first(e.in, v); 
-	  while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
-	    this->graph->next(e.in); }
-	}
-      } else {
-	this->graph->next(e.in);
-	while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
-	  this->graph->next(e.in); } 
-      }
-      return e;
-    }
-//     FIXME Not tested
-    InEdgeIt& next(InEdgeIt& e) const { 
-      if (e.forward) {
-	Node v=this->graph->aNode(e.in);
-	this->graph->next(e.in);
-	while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
-	  this->graph->next(e.in); }
-	if (!this->graph->valid(e.in)) {
-	  e.forward=false;
-	  this->graph->first(e.out, v); 
-	  while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
-	    this->graph->next(e.out); }
-	}
-      } else {
-	this->graph->next(e.out);
-	while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
-	  this->graph->next(e.out); } 
-      }
-      return e;
-    }
-    EdgeIt& next(EdgeIt& e) const {
-      if (e.forward) {
-	this->graph->next(e.e);
-	while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
-	  this->graph->next(e.e); }
-	if (!this->graph->valid(e.e)) {
-	  e.forward=false;
-	  this->graph->first(e.e); 
-	  while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
-	    this->graph->next(e.e); }
-	}
-      } else {
-	this->graph->next(e.e);
-	while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
-	  this->graph->next(e.e); } 
-      }
-      return e;
-    }
-
-    Node tail(Edge e) const { 
-      return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); }
-    Node head(Edge e) const { 
-      return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); }
-
-    Node aNode(OutEdgeIt e) const { 
-      return ((e.forward) ? this->graph->aNode(e.out) : 
-	      this->graph->aNode(e.in)); }
-    Node bNode(OutEdgeIt e) const { 
-      return ((e.forward) ? this->graph->bNode(e.out) : 
-	      this->graph->bNode(e.in)); }
-
-    Node aNode(InEdgeIt e) const { 
-      return ((e.forward) ? this->graph->aNode(e.in) : 
-	      this->graph->aNode(e.out)); }
-    Node bNode(InEdgeIt e) const { 
-      return ((e.forward) ? this->graph->bNode(e.in) : 
-	      this->graph->bNode(e.out)); }
-
-//    int nodeNum() const { return graph->nodeNum(); }
-    //FIXME
-    void edgeNum() const { }
-    //int edgeNum() const { return graph->edgeNum(); }
-
-
-//    int id(Node v) const { return graph->id(v); }
-
-    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
-    bool valid(Edge e) const { 
-      return this->graph->valid(e);
-	//return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
-    }
-
-    void augment(const Edge& e, Number a) const {
-      if (e.forward)  
-// 	flow->set(e.out, flow->get(e.out)+a);
-	flow->set(e, (*flow)[e]+a);
-      else  
-// 	flow->set(e.in, flow->get(e.in)-a);
-	flow->set(e, (*flow)[e]-a);
-    }
-
-    Number resCap(const Edge& e) const { 
-      if (e.forward) 
-//	return (capacity->get(e.out)-flow->get(e.out)); 
-	return ((*capacity)[e]-(*flow)[e]); 
-      else 
-//	return (flow->get(e.in)); 
-	return ((*flow)[e]); 
-    }
-
-//     Number resCap(typename Graph::OutEdgeIt out) const { 
-// //      return (capacity->get(out)-flow->get(out)); 
-//       return ((*capacity)[out]-(*flow)[out]); 
-//     }
-    
-//     Number resCap(typename Graph::InEdgeIt in) const { 
-// //      return (flow->get(in)); 
-//       return ((*flow)[in]); 
-//     }
-
-    template <typename T>
-    class EdgeMap {
-      typename Graph::template EdgeMap<T> forward_map, backward_map; 
-    public:
-      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
-      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
-      void set(Edge e, T a) { 
-	if (e.forward) 
-	  forward_map.set(e.out, a); 
-	else 
-	  backward_map.set(e.in, a); 
-      }
-      T operator[](Edge e) const { 
-	if (e.forward) 
-	  return forward_map[e.out]; 
-	else 
-	  return backward_map[e.in]; 
-      }
-//       T get(Edge e) const { 
-// 	if (e.out_or_in) 
-// 	  return forward_map.get(e.out); 
-// 	else 
-// 	  return backward_map.get(e.in); 
-//       }
-    };
-  };
-
-  /// ErasingFirstGraphWrapper for blocking flows.
-
-  /// ErasingFirstGraphWrapper for blocking flows.
-  ///
-  ///\author Marton Makai
-  template<typename Graph, typename FirstOutEdgesMap>
-  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
-  protected:
-    FirstOutEdgesMap* first_out_edges;
-  public:
-    ErasingFirstGraphWrapper(Graph& _graph, 
-			     FirstOutEdgesMap& _first_out_edges) : 
-      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }  
-
-    typedef typename GraphWrapper<Graph>::Node Node;
-//     class NodeIt { 
-//       friend class GraphWrapper<Graph>;
-//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
-//       typename Graph::NodeIt n;
-//      public:
-//       NodeIt() { }
-//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
-//       NodeIt(const Invalid& i) : n(i) { }
-//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
-// 	n(*(_G.graph)) { }
-//       operator Node() const { return Node(typename Graph::Node(n)); }
-//     };
-    typedef typename GraphWrapper<Graph>::Edge Edge;
-    class OutEdgeIt { 
-      friend class GraphWrapper<Graph>;
-      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
-//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
-      typename Graph::OutEdgeIt e;
-    public:
-      OutEdgeIt() { }
-      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
-      OutEdgeIt(const Invalid& i) : e(i) { }
-      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
-		const Node& _n) : 
-	e((*_G.first_out_edges)[_n]) { }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
-    class InEdgeIt { 
-      friend class GraphWrapper<Graph>;
-      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
-//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
-      typename Graph::InEdgeIt e;
-    public:
-      InEdgeIt() { }
-      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
-      InEdgeIt(const Invalid& i) : e(i) { }
-      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
-	       const Node& _n) : 
-	e(*(_G.graph), typename Graph::Node(_n)) { }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
-    //typedef typename Graph::SymEdgeIt SymEdgeIt;
-    class EdgeIt { 
-      friend class GraphWrapper<Graph>;
-      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
-//      typedef typename Graph::EdgeIt GraphEdgeIt;
-      typename Graph::EdgeIt e;
-    public:
-      EdgeIt() { }
-      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
-      EdgeIt(const Invalid& i) : e(i) { }
-      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
-	e(*(_G.graph)) { }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
-
-    using GraphWrapper<Graph>::first;
-//     NodeIt& first(NodeIt& i) const { 
-//       i=NodeIt(*this); return i;
-//     }
-    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
-      i=OutEdgeIt(*this, p); return i;
-    }
-    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
-      i=InEdgeIt(*this, p); return i;
-    }
-    EdgeIt& first(EdgeIt& i) const { 
-      i=EdgeIt(*this); return i;
-    }
-
-    using GraphWrapper<Graph>::next;
-//    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
-    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
-    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
-    EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }    
-    
-    Node aNode(const OutEdgeIt& e) const { 
-      return Node(this->graph->aNode(e.e)); }
-    Node aNode(const InEdgeIt& e) const { 
-      return Node(this->graph->aNode(e.e)); }
-    Node bNode(const OutEdgeIt& e) const { 
-      return Node(this->graph->bNode(e.e)); }
-    Node bNode(const InEdgeIt& e) const { 
-      return Node(this->graph->bNode(e.e)); }
-
-    void erase(const OutEdgeIt& e) const {
-      OutEdgeIt f=e;
-      this->next(f);
-      first_out_edges->set(this->tail(e), f.e);
-    }
-  };
-
   /// A wrapper for composing a bipartite graph.
   /// \c _graph have to be a reference to a graph of type \c Graph 
   /// and \c _s_false_t_true_map is an \c IterableBoolMap