diff -r e42f56e7ad93 -r 6114a8ab5d27 src/work/marci/bipartite_graph_wrapper.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/marci/bipartite_graph_wrapper.h	Fri Apr 30 13:52:17 2004 +0000
@@ -0,0 +1,1683 @@
+// -*- 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 <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;
+  
+  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 
+  /// reference containing the elements for the 
+  /// color classes S and T. \c _graph is to be referred to an undirected 
+  /// graph or a directed graph with edges oriented from S to T.
+  ///
+  ///\author Marton Makai
+  template<typename Graph> 
+  class BipartiteGraphWrapper : public GraphWrapper<Graph> {
+    typedef IterableBoolMap< typename Graph::template NodeMap<int> > 
+    SFalseTTrueMap;
+    SFalseTTrueMap* s_false_t_true_map;
+
+  public:
+    //marci
+    //FIXME vhogy igy kellene, csak az en forditom nem eszi meg
+    //static const bool S_CLASS=false;
+    //static const bool T_CLASS=true;
+    
+    bool S_CLASS;
+    bool T_CLASS;
+
+    BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) 
+      : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map), 
+      S_CLASS(false), T_CLASS(true) { }
+    typedef typename GraphWrapper<Graph>::Node Node;
+    //using GraphWrapper<Graph>::NodeIt;
+    typedef typename GraphWrapper<Graph>::Edge Edge;
+    //using GraphWrapper<Graph>::EdgeIt;
+    class ClassNodeIt;
+    friend class ClassNodeIt;
+    class OutEdgeIt;
+    friend class OutEdgeIt;
+    class InEdgeIt;
+    friend class InEdgeIt;
+    class ClassNodeIt {
+      friend class BipartiteGraphWrapper<Graph>;
+    protected:
+      Node n;
+    public:
+      ClassNodeIt() { }
+      ClassNodeIt(const Invalid& i) : n(i) { }
+      ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) { 
+	_G.s_false_t_true_map->first(n, _class); 
+      }
+      //FIXME needed in new concept, important here
+      ClassNodeIt(const Node& _n) : n(_n) { }
+      operator Node() const { return n; }
+    };
+//     class SNodeIt {
+//       Node n;
+//     public:
+//       SNodeIt() { }
+//       SNodeIt(const Invalid& i) : n(i) { }
+//       SNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 
+// 	_G.s_false_t_true_map->first(n, false); 
+//       }
+//       operator Node() const { return n; }
+//     };
+//     class TNodeIt {
+//       Node n;
+//     public:
+//       TNodeIt() { }
+//       TNodeIt(const Invalid& i) : n(i) { }
+//       TNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 
+// 	_G.s_false_t_true_map->first(n, true); 
+//       }
+//       operator Node() const { return n; }
+//     };
+    class OutEdgeIt { 
+      friend class BipartiteGraphWrapper<Graph>;
+    protected:
+      typename Graph::OutEdgeIt e;
+    public:
+      OutEdgeIt() { }
+      OutEdgeIt(const Invalid& i) : e(i) { }
+      OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
+	if (!(*(_G.s_false_t_true_map))[_n]) 
+	  e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
+	else 
+	  e=INVALID;
+      }
+      operator Edge() const { return Edge(typename Graph::Edge(e)); }
+    };
+    class InEdgeIt { 
+      friend class BipartiteGraphWrapper<Graph>;
+    protected:
+      typename Graph::InEdgeIt e;
+    public:
+      InEdgeIt() { }
+      InEdgeIt(const Invalid& i) : e(i) { }
+      InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
+	if ((*(_G.s_false_t_true_map))[_n]) 
+	  e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
+	else 
+	  e=INVALID;
+      }
+      operator Edge() const { return Edge(typename Graph::Edge(e)); }
+    };
+
+    using GraphWrapper<Graph>::first;
+    ClassNodeIt& first(ClassNodeIt& n, bool _class) const { 
+      n=ClassNodeIt(*this, _class) ; return n; }
+//    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
+//    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
+    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;
+    ClassNodeIt& next(ClassNodeIt& n) const { 
+      this->s_false_t_true_map->next(n.n); return n; 
+    }
+//     SNodeIt& next(SNodeIt& n) const { 
+//       this->s_false_t_true_map->next(n); return n; 
+//     }
+//     TNodeIt& next(TNodeIt& n) const { 
+//       this->s_false_t_true_map->next(n); return n; 
+//     }
+    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 tail(const Edge& e) { 
+      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
+	return Node(this->graph->tail(e));
+      else
+	return Node(this->graph->head(e));	
+    }
+    Node head(const Edge& e) { 
+      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
+	return Node(this->graph->head(e));
+      else
+	return Node(this->graph->tail(e));	
+    }
+
+    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)); 
+    }
+
+    bool inSClass(const Node& n) const {
+      return !(*(this->s_false_t_true_map))[n];
+    }
+    bool inTClass(const Node& n) const {
+      return (*(this->s_false_t_true_map))[n];
+    }
+  };
+
+  template<typename Graph>
+  class stGraphWrapper;
+
+//   template<typename Graph> 
+//   std::ostream& 
+//   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Node& i) { 
+//     os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; 
+//     return os; 
+//   }
+//   template<typename Graph> 
+//   std::ostream& 
+//   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Edge& i) { 
+//     os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << 
+//       " node: " << i.n << ")"; 
+//     return os; 
+//   }
+
+  /// experimentral, do not try it.
+  /// It eats a bipartite graph, oriented from S to T.
+  /// Such one can be made e.g. by the above wrapper.
+  ///
+  ///\author Marton Makai
+  template<typename Graph>
+  class stGraphWrapper : public GraphWrapper<Graph> {
+  public:
+    class Node; 
+    friend class Node;
+//GN, int
+//0 normalis, 1 s, 2, true, ez az iteralasi sorrend, 
+//es a vege a false azaz (invalid, 3)    
+    class NodeIt;
+    friend class NodeIt;
+//GNI, int
+    class Edge;
+    friend class Edge;
+//GE, int, GN
+//0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
+//invalid: (invalid, 3, invalid)
+    class OutEdgeIt;
+    friend class OutEdgeIt;
+//GO, int, GNI
+//normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)
+//s-bol (invalid, 1, first), ... (invalid, 3, invalid)
+//t-bol (invalid, 3, invalid)
+    class InEdgeIt;
+    friend class InEdgeIt;
+//GI, int, GNI
+//normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)
+//s-be (invalid, 3, invalid)
+//t-be (invalid, 2, first), ... (invalid, 3, invalid)
+    class EdgeIt;
+    friend class EdgeIt;
+//(first, 0, invalid) ...
+//(invalid, 1, vmi)
+//(invalid, 2, vmi)
+//invalid, 3, invalid)
+    template <typename T> class NodeMap;
+    template <typename T, typename Parent> class EdgeMap;
+
+//    template <typename T> friend class NodeMap;
+//    template <typename T> friend class EdgeMap;
+
+    const Node S_NODE;
+    const Node T_NODE;
+
+    static const bool S_CLASS=false;
+    static const bool T_CLASS=true;
+
+    stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) , 
+				    S_NODE(INVALID, 1), 
+				    T_NODE(INVALID, 2) { }
+
+    
+//    std::ostream& 
+//    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);
+//    friend std::ostream& 
+//    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);
+//    friend std::ostream& 
+//    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i);
+
+    class Node : public Graph::Node {
+    protected:
+      friend class GraphWrapper<Graph>;
+      friend class stGraphWrapper<Graph>;
+      template <typename T> friend class NodeMap;
+      friend class Edge;
+      friend class OutEdgeIt;
+      friend class InEdgeIt;
+      friend class EdgeIt;
+      int spec; 
+    public:
+      Node() { }
+      Node(const typename Graph::Node& _n, int _spec=0) : 
+	Graph::Node(_n), spec(_spec) { }
+      Node(const Invalid& i) : Graph::Node(i), spec(3) { }
+      friend bool operator==(const Node& u, const Node& v) { 
+	return (u.spec==v.spec && 
+		static_cast<typename Graph::Node>(u)==
+		static_cast<typename Graph::Node>(v));
+      } 
+      friend bool operator!=(const Node& u, const Node& v) { 
+	return (v.spec!=u.spec || 
+		static_cast<typename Graph::Node>(u)!=
+		static_cast<typename Graph::Node>(v));
+      }
+//      template<typename G> 
+//      friend std::ostream& 
+//      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Node& i); 
+      friend std::ostream& operator<< (std::ostream& os, const Node& i);
+      int getSpec() const { return spec; }
+    };
+
+    class NodeIt { 
+      friend class GraphWrapper<Graph>;
+      friend class stGraphWrapper<Graph>;
+      typename Graph::NodeIt n;
+      int spec; 
+     public:
+      NodeIt() { }
+      NodeIt(const typename Graph::NodeIt& _n, int _spec) : 
+	n(_n), spec(_spec) { }
+      NodeIt(const Invalid& i) : n(i), spec(3) { }
+      NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) { 
+	if (!_G.graph->valid(n)) spec=1;
+      }
+      operator Node() const { return Node(n, spec); }
+    };
+
+    class Edge : public Graph::Edge {
+      friend class GraphWrapper<Graph>;
+      friend class stGraphWrapper<Graph>;
+      template <typename T, typename Parent> friend class EdgeMap;
+      int spec;
+      typename Graph::Node n;
+    public:
+      Edge() { }
+      Edge(const typename Graph::Edge& _e, int _spec, 
+	   const typename Graph::Node& _n) : 
+	Graph::Edge(_e), spec(_spec), n(_n) { 
+      }
+      Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }
+      friend bool operator==(const Edge& u, const Edge& v) { 
+	return (u.spec==v.spec && 
+		static_cast<typename Graph::Edge>(u)==
+		static_cast<typename Graph::Edge>(v) && 
+		u.n==v.n);
+      } 
+      friend bool operator!=(const Edge& u, const Edge& v) { 
+	return (v.spec!=u.spec || 
+		static_cast<typename Graph::Edge>(u)!=
+		static_cast<typename Graph::Edge>(v) || 
+		u.n!=v.n);
+      } 
+//      template<typename G> 
+//      friend std::ostream& 
+//      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Edge& i); 
+      friend std::ostream& operator<< (std::ostream& os, const Edge& i);
+      int getSpec() const { return spec; }
+    };
+
+    class OutEdgeIt { 
+      friend class GraphWrapper<Graph>;
+      friend class stGraphWrapper<Graph>;
+      typename Graph::OutEdgeIt e;
+      int spec;
+      typename Graph::ClassNodeIt n;
+    public:
+      OutEdgeIt() { }
+      OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec, 
+		const typename Graph::ClassNodeIt& _n) : 
+	e(_e), spec(_spec), n(_n) { 
+      }
+      OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
+      OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
+	switch (_n.spec) {
+	  case 0 : 
+	    if (_G.graph->inSClass(_n)) { //S, van normalis kiel 
+	      e=typename Graph::OutEdgeIt(*(_G.graph), 
+					  typename Graph::Node(_n)); 
+	      spec=0;
+	      n=INVALID;
+	      if (!_G.graph->valid(e)) spec=3;
+	    } else { //T, specko kiel van
+	      e=INVALID;
+	      spec=2;
+	      n=_n;
+	    }
+	    break;
+	  case 1:
+	    e=INVALID;
+	    spec=1;
+	    _G.graph->first(n, S_CLASS); //s->vmi;
+	    if (!_G.graph->valid(n)) spec=3; //Ha S ures
+	    break;
+	  case 2:
+	    e=INVALID;
+	    spec=3;
+	    n=INVALID;
+	    break;
+	}
+      }
+      operator Edge() const { return Edge(e, spec, n); }
+    };
+
+    class InEdgeIt { 
+      friend class GraphWrapper<Graph>;
+      friend class stGraphWrapper<Graph>;
+      typename Graph::InEdgeIt e;
+      int spec;
+      typename Graph::ClassNodeIt n;
+    public:
+      InEdgeIt() { }
+      InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec, 
+	       const typename Graph::ClassNodeIt& _n) : 
+	e(_e), spec(_spec), n(_n) { 
+      }
+      InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
+      InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
+	switch (_n.spec) {
+	  case 0 : 
+	    if (_G.graph->inTClass(_n)) { //T, van normalis beel 
+	      e=typename Graph::InEdgeIt(*(_G.graph), 
+					 typename Graph::Node(_n)); 
+	      spec=0;
+	      n=INVALID;
+	      if (!_G.graph->valid(e)) spec=3;
+	    } else { //S, specko beel van
+	      e=INVALID;
+	      spec=1;
+	      n=_n;
+	    }
+	    break;
+	  case 1:
+	    e=INVALID;
+	    spec=3;
+	    n=INVALID;
+	    break;
+	  case 2:
+	    e=INVALID;
+	    spec=2;
+	    _G.graph->first(n, T_CLASS); //vmi->t;
+	    if (!_G.graph->valid(n)) spec=3; //Ha T ures
+	    break;
+	}
+      }
+      operator Edge() const { return Edge(e, spec, n); }
+    };
+
+    class EdgeIt { 
+      friend class GraphWrapper<Graph>;
+      friend class stGraphWrapper<Graph>;
+      typename Graph::EdgeIt e;
+      int spec;
+      typename Graph::ClassNodeIt n;
+    public:
+      EdgeIt() { }
+      EdgeIt(const typename Graph::EdgeIt& _e, int _spec, 
+	     const typename Graph::ClassNodeIt& _n) : 
+	e(_e), spec(_spec), n(_n) { }
+      EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
+      EdgeIt(const stGraphWrapper<Graph>& _G) : 
+	e(*(_G.graph)), spec(0), n(INVALID) { 
+	if (!_G.graph->valid(e)) {
+	  spec=1;
+	  _G.graph->first(n, S_CLASS);
+	  if (!_G.graph->valid(n)) { //Ha S ures
+	    spec=2;
+	    _G.graph->first(n, T_CLASS);
+	    if (!_G.graph->valid(n)) { //Ha T ures
+	      spec=3;
+	    }
+	  }
+	}
+      }
+      operator Edge() const { return Edge(e, spec, n); }
+    };
+   
+    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 { 
+      switch (i.spec) {
+	case 0:
+	  this->graph->next(i.n);
+	  if (!this->graph->valid(i.n)) {
+	    i.spec=1;
+	  }
+	  break;
+	case 1:
+	  i.spec=2;
+	  break;
+	case 2:
+	  i.spec=3;
+	  break;
+      }
+      return i; 
+    }
+    OutEdgeIt& next(OutEdgeIt& i) const { 
+      typename Graph::Node v;
+      switch (i.spec) {
+	case 0: //normal edge
+	  v=this->graph->aNode(i.e);
+	  this->graph->next(i.e);
+	  if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
+	    if (this->graph->inSClass(v)) { //S, nincs kiel
+	      i.spec=3;
+	      i.n=INVALID;
+	    } else { //T, van kiel
+	      i.spec=2; 
+	      i.n=v;
+	    }
+	  }
+	  break;
+	case 1: //s->vmi
+	  this->graph->next(i.n);
+	  if (!this->graph->valid(i.n)) i.spec=3;
+	  break;
+	case 2: //vmi->t
+	  i.spec=3;
+	  i.n=INVALID;
+	  break;
+      }
+      return i; 
+    }
+    InEdgeIt& next(InEdgeIt& i) const { 
+      typename Graph::Node v;
+      switch (i.spec) {
+	case 0: //normal edge
+	  v=this->graph->aNode(i.e);
+	  this->graph->next(i.e);
+	  if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
+	    if (this->graph->inTClass(v)) { //S, nincs beel
+	      i.spec=3;
+	      i.n=INVALID;
+	    } else { //S, van beel
+	      i.spec=1; 
+	      i.n=v;
+	    }
+	  }
+	  break;
+	case 1: //s->vmi
+	  i.spec=3;
+	  i.n=INVALID;
+	  break;
+	case 2: //vmi->t
+	  this->graph->next(i.n);
+	  if (!this->graph->valid(i.n)) i.spec=3;
+	  break;
+      }
+      return i; 
+    }
+
+    EdgeIt& next(EdgeIt& i) const { 
+      switch (i.spec) {
+	case 0:
+	  this->graph->next(i.e);
+	  if (!this->graph->valid(i.e)) { 
+	    i.spec=1;
+	    this->graph->first(i.n, S_CLASS);
+	    if (!this->graph->valid(i.n)) {
+	      i.spec=2;
+	      this->graph->first(i.n, T_CLASS);
+	      if (!this->graph->valid(i.n)) i.spec=3;
+	    }
+	  }
+	  break;
+	case 1:
+	  this->graph->next(i.n);
+	  if (!this->graph->valid(i.n)) {
+	    i.spec=2;
+	    this->graph->first(i.n, T_CLASS);
+	    if (!this->graph->valid(i.n)) i.spec=3;
+	  }
+	  break;
+	case 2:
+	  this->graph->next(i.n);
+	  if (!this->graph->valid(i.n)) i.spec=3;
+	  break;
+      }
+      return i; 
+    }    
+
+    Node tail(const Edge& e) const { 
+      switch (e.spec) {
+      case 0: 
+	return Node(this->graph->tail(e));
+	break;
+      case 1:
+	return S_NODE;
+	break;
+      case 2:
+      default:
+	return Node(e.n);
+	break;
+      }
+    }
+    Node head(const Edge& e) const { 
+      switch (e.spec) {
+      case 0: 
+	return Node(this->graph->head(e));
+	break;
+      case 1:
+	return Node(e.n);
+	break;
+      case 2:
+      default:
+	return T_NODE;
+	break;
+      }
+    }
+
+    bool valid(const Node& n) const { return (n.spec<3); }
+    bool valid(const Edge& e) const { return (e.spec<3); }
+
+    int nodeNum() const { return this->graph->nodeNum()+2; }
+    int edgeNum() const { 
+      return this->graph->edgeNum()+this->graph->nodeNum(); 
+    }
+  
+    Node aNode(const OutEdgeIt& e) const { return tail(e); }
+    Node aNode(const InEdgeIt& e) const { return head(e); }
+    Node bNode(const OutEdgeIt& e) const { return head(e); }
+    Node bNode(const InEdgeIt& e) const { return tail(e); }
+
+    void addNode() const { }
+    void addEdge() const { }
+    
+//    Node addNode() const { return Node(this->graph->addNode()); }
+//    Edge addEdge(const Node& tail, const Node& head) const { 
+//      return Edge(this->graph->addEdge(tail, head)); }
+
+//    void erase(const Node& i) const { this->graph->erase(i); }
+//    void erase(const Edge& i) const { this->graph->erase(i); }
+  
+//    void clear() const { this->graph->clear(); }
+    
+    template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> { 
+      typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
+      T s_value, t_value;
+    public:
+      NodeMap(const stGraphWrapper<Graph>& _G) :  Parent(_G), 
+						  s_value(), 
+						  t_value() { }
+      NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), 
+						      s_value(a), 
+						      t_value(a) { }
+      T operator[](const Node& n) const { 
+	switch (n.spec) {
+	case 0: 
+	  return Parent::operator[](n);
+	  break;
+	case 1:
+	  return s_value;
+	  break;
+	case 2: 
+	default:
+	  return t_value;
+	  break;
+	}
+      }
+      void set(const Node& n, T t) { 
+	switch (n.spec) {
+	case 0: 
+	  GraphWrapper<Graph>::template NodeMap<T>::set(n, t);
+	  break;
+	case 1:
+	  s_value=t;
+	  break;
+	case 2:
+	default:
+	  t_value=t;
+	  break;
+	}
+      }
+    };
+
+    template<typename T, 
+	     typename Parent=
+	     typename GraphWrapper<Graph>::template EdgeMap<T> > 
+    class EdgeMap : public Parent { 
+      //typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
+      typename GraphWrapper<Graph>::template NodeMap<T> node_value;
+    public:
+      EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), 
+						 node_value(_G) { }
+      EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), 
+						      node_value(_G, a) { }
+      T operator[](const Edge& e) const { 
+	switch (e.spec) {
+	case 0: 
+	  return Parent::operator[](e);
+	  break;
+	case 1:
+	  return node_value[e.n];
+	  break;
+	case 2:
+	default:
+	  return node_value[e.n];
+	  break;
+	}
+      }
+      void set(const Edge& e, T t) { 
+	switch (e.spec) {
+	case 0: 
+	  Parent::set(e, t);
+	  break;
+	case 1:
+	  node_value.set(e.n, t);
+	  break;
+	case 2:
+	default:
+	  node_value.set(e.n, t);
+	  break;
+	}
+      }
+    };
+
+//     template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { 
+//       typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
+//       typename GraphWrapper<Graph>::template NodeMap<T> node_value;
+//     public:
+//       EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), 
+// 						 node_value(_G) { }
+//       EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), 
+// 						      node_value(_G, a) { }
+//       T operator[](const Edge& e) const { 
+// 	switch (e.spec) {
+// 	case 0: 
+// 	  return Parent::operator[](e);
+// 	  break;
+// 	case 1:
+// 	  return node_value[e.n];
+// 	  break;
+// 	case 2:
+// 	default:
+// 	  return node_value[e.n];
+// 	  break;
+// 	}
+//       }
+//       void set(const Edge& e, T t) { 
+// 	switch (e.spec) {
+// 	case 0: 
+// 	  GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);
+// 	  break;
+// 	case 1:
+// 	  node_value.set(e.n, t);
+// 	  break;
+// 	case 2:
+// 	default:
+// 	  node_value.set(e.n, t);
+// 	  break;
+// 	}
+//       }
+//     };
+
+//  template<typename G> 
+    friend std::ostream& 
+    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i) { 
+      os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; 
+      return os; 
+    }
+//  template<typename G> 
+    friend std::ostream& 
+    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i) { 
+      os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << 
+	" node: " << i.n << ")"; 
+      return os; 
+    }
+
+  };
+
+  ///@}
+
+} //namespace hugo
+
+
+#endif //HUGO_GRAPH_WRAPPER_H
+