# HG changeset patch
# User marci
# Date 1083862559 0
# Node ID bbb223f732e2a0bb59694e3a2783b05ac52b8f8f
# Parent  995bc1f1a3ce4f50a1bbb21099e10e7ea3a74734
graph_wrapper.h in hugo

diff -r 995bc1f1a3ce -r bbb223f732e2 src/hugo/graph_wrapper.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hugo/graph_wrapper.h	Thu May 06 16:55:59 2004 +0000
@@ -0,0 +1,985 @@
+// -*- c++ -*-
+#ifndef HUGO_GRAPH_WRAPPER_H
+#define HUGO_GRAPH_WRAPPER_H
+
+///\ingroup gwrappers
+///\file
+///\brief Several graph wrappers.
+///
+///This file contains several useful graph wrapper functions.
+///
+///\author Marton Makai
+
+#include <hugo/invalid.h>
+//#include <iter_map.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;
+    GraphWrapper() : graph(0) { }
+    void setGraph(Graph& _graph) { graph=&_graph; }
+
+  public:
+    typedef Graph BaseGraph;
+    typedef Graph ParentGraph;
+
+    GraphWrapper(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> {
+  protected:
+    RevGraphWrapper() : GraphWrapper<Graph>(0) { }
+  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;
+
+    SubGraphWrapper() : GraphWrapper<Graph>(0), 
+			node_filter_map(0), edge_filter_map(0) { }
+    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
+      node_filter_map=&_node_filter_map;
+    }
+    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
+      edge_filter_map=&_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> {
+  protected:
+    UndirGraphWrapper() : 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); }
+  };
+  
+
+
+  /// An undirected graph template
+  template<typename Graph>
+  class UndirGraph : public UndirGraphWrapper<Graph> {
+    typedef UndirGraphWrapper<Graph> Parent;
+  protected:
+    Graph gr;
+  public:
+    UndirGraph() : UndirGraphWrapper<Graph>() { 
+      Parent::setGraph(gr); 
+    }
+  };
+
+  
+
+  /// 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;
+
+    ResGraphWrapper() : GraphWrapper<Graph>(0), 
+			capacity(0), flow(0) { }
+    void setCapacityMap(const CapacityMap& _capacity_map) {
+      capacity_map=&_capacity_map;
+    }
+    void setFlowMap(FlowMap& _flow) {
+      flow=&_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); 
+    }
+
+    bool forward(const Edge& e) const { return e.forward; }
+    bool backward(const Edge& e) const { return !e.forward; }
+
+    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);
+    }
+  };
+
+  ///@}
+
+} //namespace hugo
+
+
+#endif //HUGO_GRAPH_WRAPPER_H
+
diff -r 995bc1f1a3ce -r bbb223f732e2 src/work/marci/graph_wrapper.h
--- a/src/work/marci/graph_wrapper.h	Thu May 06 16:54:54 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,985 +0,0 @@
-// -*- c++ -*-
-#ifndef HUGO_GRAPH_WRAPPER_H
-#define HUGO_GRAPH_WRAPPER_H
-
-///\ingroup gwrappers
-///\file
-///\brief Several graph wrappers.
-///
-///This file contains several useful graph wrapper functions.
-///
-///\author Marton Makai
-
-#include <hugo/invalid.h>
-//#include <iter_map.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;
-    GraphWrapper() : graph(0) { }
-    void setGraph(Graph& _graph) { graph=&_graph; }
-
-  public:
-    typedef Graph BaseGraph;
-    typedef Graph ParentGraph;
-
-    GraphWrapper(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> {
-  protected:
-    RevGraphWrapper() : GraphWrapper<Graph>(0) { }
-  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;
-
-    SubGraphWrapper() : GraphWrapper<Graph>(0), 
-			node_filter_map(0), edge_filter_map(0) { }
-    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
-      node_filter_map=&_node_filter_map;
-    }
-    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
-      edge_filter_map=&_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> {
-  protected:
-    UndirGraphWrapper() : 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); }
-  };
-  
-
-
-  /// An undirected graph template
-  template<typename Graph>
-  class UndirGraph : public UndirGraphWrapper<Graph> {
-    typedef UndirGraphWrapper<Graph> Parent;
-  protected:
-    Graph gr;
-  public:
-    UndirGraph() : UndirGraphWrapper<Graph>() { 
-      Parent::setGraph(gr); 
-    }
-  };
-
-  
-
-  /// 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;
-
-    ResGraphWrapper() : GraphWrapper<Graph>(0), 
-			capacity(0), flow(0) { }
-    void setCapacityMap(const CapacityMap& _capacity_map) {
-      capacity_map=&_capacity_map;
-    }
-    void setFlowMap(FlowMap& _flow) {
-      flow=&_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); 
-    }
-
-    bool forward(const Edge& e) const { return e.forward; }
-    bool backward(const Edge& e) const { return !e.forward; }
-
-    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);
-    }
-  };
-
-  ///@}
-
-} //namespace hugo
-
-
-#endif //HUGO_GRAPH_WRAPPER_H
-