// -*- 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