// -*- c++ -*-

 #ifndef HUGO_GRAPH_WRAPPER_H

 #define HUGO_GRAPH_WRAPPER_H

 #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...

   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.

   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. 

   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.

   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.

   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];

     }

   };

   /********************   S-T Graph Wrapper    ********************/

   template<typename Graph> class stGraphWrapper;

   template<typename Graph>

   inline

   std::ostream& 

   operator<<(std::ostream& os,

 	     typename stGraphWrapper<Graph>::Node const& i) { 

     os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";

     return os; 

   }

   template<typename Graph>

   inline

   std::ostream& 

   operator<<(std::ostream& os,

 	     typename stGraphWrapper<Graph>::Edge const& 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.

   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