// -*- c++ -*-

 #ifndef HUGO_GRAPH_WRAPPER_H

 #define HUGO_GRAPH_WRAPPER_H

 ///\ingroup gwrappers

 ///\file

 ///\brief Several graph wrappers.

 ///

 ///This file contains several useful graph wrapper functions.

 ///

 ///\author Marton Makai

 #include <hugo/invalid.h>

 #include <hugo/maps.h>

 //#include <iter_map.h>

 namespace hugo {

   // Graph wrappers

   /// \addtogroup gwrappers

   /// A main parts of HUGOlib are the different graph structures, 

   /// generic graph algorithms, graph concepts which couple these, and 

   /// graph wrappers. While the previous ones are more or less clear, the 

   /// latter notion needs further explanation.

   /// Graph wrappers are graph classes which serve for considering graph 

   /// structures in different ways. A short example makes the notion much 

   /// clearer. 

   /// Suppose that we have an instance \c g of a directed graph

   /// type say \c ListGraph and an algorithm 

   /// \code template<typename Graph> int algorithm(const Graph&); \endcode 

   /// is needed to run on the reversely oriented graph. 

   /// It may be expensive (in time or in memory usage) to copy 

   /// \c g with the reverse orientation. 

   /// Thus, a wrapper class

   /// \code template<typename Graph> class RevGraphWrapper; \endcode is used. 

   /// The code looks as follows

   /// \code

   /// ListGraph g;

   /// RevGraphWrapper<ListGraph> rgw(g);

   /// int result=algorithm(rgw);

   /// \endcode

   /// After running the algorithm, the original graph \c g 

   /// remains untouched. Thus the graph wrapper used above is to consider the 

   /// original graph with reverse orientation. 

   /// This techniques gives rise to an elegant code, and 

   /// based on stable graph wrappers, complex algorithms can be 

   /// implemented easily. 

   /// In flow, circulation and bipartite matching problems, the residual 

   /// graph is of particular importance. Combining a wrapper implementing 

   /// this, shortest path algorithms and minimum mean cycle algorithms, 

   /// a range of weighted and cardinality optimization algorithms can be 

   /// obtained. For lack of space, for other examples, 

   /// the interested user is referred to the detailed documentation of graph 

   /// wrappers. 

   /// The behavior of graph wrappers can be very different. Some of them keep 

   /// capabilities of the original graph while in other cases this would be 

   /// meaningless. This means that the concepts that they are a model of depend 

   /// on the graph wrapper, and the wrapped graph(s). 

   /// If an edge of \c rgw is deleted, this is carried out by 

   /// deleting the corresponding edge of \c g. But for a residual 

   /// graph, this operation has no sense. 

   /// Let we stand one more example here to simplify your work. 

   /// wrapper class

   /// \code template<typename Graph> class RevGraphWrapper; \endcode 

   /// has constructor 

   /// <tt> RevGraphWrapper(Graph& _g)</tt>. 

   /// This means that in a situation, 

   /// when a <tt> const ListGraph& </tt> reference to a graph is given, 

   /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.

   /// \code

   /// int algorithm1(const ListGraph& g) {

   ///   RevGraphWrapper<const ListGraph> rgw(g);

   ///   return algorithm2(rgw);

   /// }

   /// \endcode

   /// \addtogroup gwrappers

   /// @{

   ///Base type for the Graph Wrappers

   ///This is the base type for the Graph Wrappers.

   ///\todo Some more docs... 

   ///

   ///\author Marton Makai 

   template<typename Graph>

   class GraphWrapper {

   protected:

     Graph* graph;

     GraphWrapper() : graph(0) { }

     void setGraph(Graph& _graph) { graph=&_graph; }

   public:

     typedef Graph BaseGraph;

     typedef Graph ParentGraph;

     GraphWrapper(Graph& _graph) : graph(&_graph) { }

 //     Graph& getGraph() const { return *graph; }

 //    typedef typename Graph::Node Node;

     class Node : public Graph::Node {

       friend class GraphWrapper<Graph>;

     public:

       Node() { }

       Node(const typename Graph::Node& _n) : Graph::Node(_n) { }

       // /// \bug construction throughrthr multiple levels should be 

       // /// handled better

       // Node(const typename ParentGraph::ParentGraph::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(); }

     bool forward(const Edge& e) const { graph->forward(e); }

     bool backward(const Edge& e) const { graph->backward(e); }

     Edge opposite(const Edge& e) const { Edge(graph->opposite(e)); }

     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.

   /// Thus \c Graph have to be a directed graph type.

   ///

   ///\author Marton Makai

   template<typename Graph>

   class RevGraphWrapper : public GraphWrapper<Graph> {

   public:

     typedef GraphWrapper<Graph> Parent; 

   protected:

     RevGraphWrapper() : 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); }

   };

   /// A graph 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> {

   public:

     typedef GraphWrapper<Graph> Parent;

   protected:

     NodeFilterMap* node_filter_map;

     EdgeFilterMap* edge_filter_map;

     SubGraphWrapper() : GraphWrapper<Graph>(), 

 			node_filter_map(0), edge_filter_map(0) { }

     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {

       node_filter_map=&_node_filter_map;

     }

     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {

       edge_filter_map=&_edge_filter_map;

     }

   public:

     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, 

 		    EdgeFilterMap& _edge_filter_map) : 

       GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), 

       edge_filter_map(&_edge_filter_map) { }  

     typedef typename GraphWrapper<Graph>::Node Node;

     class NodeIt { 

       friend class GraphWrapper<Graph>;

       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

       typename Graph::NodeIt n;

      public:

       NodeIt() { }

       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }

       NodeIt(const Invalid& i) : n(i) { }

       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 

 	n(*(_G.graph)) { 

 	while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n]) 

 	  _G.graph->next(n);

       }

       operator Node() const { return Node(typename Graph::Node(n)); }

     };

     typedef typename GraphWrapper<Graph>::Edge Edge;

     class OutEdgeIt { 

       friend class GraphWrapper<Graph>;

       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

       typename Graph::OutEdgeIt e;

     public:

       OutEdgeIt() { }

       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }

       OutEdgeIt(const Invalid& i) : e(i) { }

       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 

 		const Node& _n) : 

 	e(*(_G.graph), typename Graph::Node(_n)) { 

       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 

 	  _G.graph->next(e);

       }

       operator Edge() const { return Edge(typename Graph::Edge(e)); }

     };

     class InEdgeIt { 

       friend class GraphWrapper<Graph>;

       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

       typename Graph::InEdgeIt e;

     public:

       InEdgeIt() { }

       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }

       InEdgeIt(const Invalid& i) : e(i) { }

       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 

 	       const Node& _n) : 

 	e(*(_G.graph), typename Graph::Node(_n)) { 

       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 

 	  _G.graph->next(e);

       }

       operator Edge() const { return Edge(typename Graph::Edge(e)); }

     };

     //typedef typename Graph::SymEdgeIt SymEdgeIt;

     class EdgeIt { 

       friend class GraphWrapper<Graph>;

       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

       typename Graph::EdgeIt e;

     public:

       EdgeIt() { }

       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }

       EdgeIt(const Invalid& i) : e(i) { }

       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 

 	e(*(_G.graph)) { 

       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 

 	  _G.graph->next(e);

       }

       operator Edge() const { return Edge(typename Graph::Edge(e)); }

     };

     NodeIt& first(NodeIt& i) const { 

       i=NodeIt(*this); return i;

     }

     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 

       i=OutEdgeIt(*this, p); return i;

     }

     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 

       i=InEdgeIt(*this, p); return i;

     }

     EdgeIt& first(EdgeIt& i) const { 

       i=EdgeIt(*this); return i;

     }

     NodeIt& next(NodeIt& i) const {

       this->graph->next(i.n); 

       while (this->graph->valid(i) && !(*node_filter_map)[i.n]) { 

 	this->graph->next(i.n); }

       return i;

     }

     OutEdgeIt& next(OutEdgeIt& i) const {

       this->graph->next(i.e); 

       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 

 	this->graph->next(i.e); }

       return i;

     }

     InEdgeIt& next(InEdgeIt& i) const {

       this->graph->next(i.e); 

       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 

 	this->graph->next(i.e); }

       return i;

     }

     EdgeIt& next(EdgeIt& i) const {

       this->graph->next(i.e); 

       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 

 	this->graph->next(i.e); }

       return i;

     }

     Node aNode(const OutEdgeIt& e) const { 

       return Node(this->graph->aNode(e.e)); }

     Node aNode(const InEdgeIt& e) const { 

       return Node(this->graph->aNode(e.e)); }

     Node bNode(const OutEdgeIt& e) const { 

       return Node(this->graph->bNode(e.e)); }

     Node bNode(const InEdgeIt& e) const { 

       return Node(this->graph->bNode(e.e)); }

     /// This function hides \c n in the graph, i.e. the iteration 

     /// jumps over it. This is done by simply setting the value of \c n  

     /// to be false in the corresponding node-map.

     void hide(const Node& n) const { node_filter_map->set(n, false); }

     /// This function hides \c e in the graph, i.e. the iteration 

     /// jumps over it. This is done by simply setting the value of \c e  

     /// to be false in the corresponding edge-map.

     void hide(const Edge& e) const { edge_filter_map->set(e, false); }

     /// The value of \c n is set to be true in the node-map which stores 

     /// hide information. If \c n was hidden previuosly, then it is shown 

     /// again

      void unHide(const Node& n) const { node_filter_map->set(n, true); }

     /// The value of \c e is set to be true in the edge-map which stores 

     /// hide information. If \c e was hidden previuosly, then it is shown 

     /// again

     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }

     /// Returns true if \c n is hidden.

     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }

     /// Returns true if \c n is hidden.

     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }

     /// This is a linear time operation and works only if 

     /// NodeIt is defined.

     int nodeNum() const { 

       int i=0;

       NodeIt n;

       for (this->first(n); this->valid(n); this->next(n)) ++i;

       return i; 

     }

     /// This is a linear time operation and works only if 

     /// EdgeIt is defined.

     int edgeNum() const { 

       int i=0;

       EdgeIt e;

       for (this->first(e); this->valid(e); this->next(e)) ++i;

       return i; 

     }

   };

   /// \brief A wrapper for forgetting the orientation of a graph.

   ///

   /// A wrapper for getting an undirected graph by forgetting

   /// the orientation of a directed one.

   ///

   /// \author Marton Makai

   template<typename Graph>

   class UndirGraphWrapper : public GraphWrapper<Graph> {

   public:

     typedef GraphWrapper<Graph> Parent; 

   protected:

     UndirGraphWrapper() : GraphWrapper<Graph>() { }

   public:

     typedef typename GraphWrapper<Graph>::Node Node;

     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;

     typedef typename GraphWrapper<Graph>::Edge Edge;

     typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;

     UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  

     class OutEdgeIt {

       friend class UndirGraphWrapper<Graph>;

       bool out_or_in; //true iff out

       typename Graph::OutEdgeIt out;

       typename Graph::InEdgeIt in;

     public:

       OutEdgeIt() { }

       OutEdgeIt(const Invalid& i) : Edge(i) { }

       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {

 	out_or_in=true; _G.graph->first(out, _n);

 	if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);	}

       } 

       operator Edge() const { 

 	if (out_or_in) return Edge(out); else return Edge(in); 

       }

     };

 //FIXME InEdgeIt

     typedef OutEdgeIt InEdgeIt; 

     using GraphWrapper<Graph>::first;

 //     NodeIt& first(NodeIt& i) const { 

 //       i=NodeIt(*this); return i;

 //     }

     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 

       i=OutEdgeIt(*this, p); return i;

     }

 //FIXME

 //     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 

 //       i=InEdgeIt(*this, p); return i;

 //     }

 //     EdgeIt& first(EdgeIt& i) const { 

 //       i=EdgeIt(*this); return i;

 //     }

     using GraphWrapper<Graph>::next;

 //     NodeIt& next(NodeIt& n) const {

 //       GraphWrapper<Graph>::next(n);

 //       return n;

 //     }

     OutEdgeIt& next(OutEdgeIt& e) const {

       if (e.out_or_in) {

 	typename Graph::Node n=this->graph->tail(e.out);

 	this->graph->next(e.out);

 	if (!this->graph->valid(e.out)) { 

 	  e.out_or_in=false; this->graph->first(e.in, n); }

       } else {

 	this->graph->next(e.in);

       }

       return e;

     }

     //FIXME InEdgeIt

 //     EdgeIt& next(EdgeIt& e) const {

 //       GraphWrapper<Graph>::next(n);

 // //      graph->next(e.e);

 //       return e;

 //     }

     Node aNode(const OutEdgeIt& e) const { 

       if (e.out_or_in) return this->graph->tail(e); else 

 	return this->graph->head(e); }

     Node bNode(const OutEdgeIt& e) const { 

       if (e.out_or_in) return this->graph->head(e); else 

 	return this->graph->tail(e); }

   };

   /// \brief An undirected graph template.

   ///

   /// An undirected graph template.

   /// This class works as an undirected graph and a directed graph of 

   /// class \c Graph is used for the physical storage.

   /// \ingroup graphs

   template<typename Graph>

   class UndirGraph : public UndirGraphWrapper<Graph> {

     typedef UndirGraphWrapper<Graph> Parent;

   protected:

     Graph gr;

   public:

     UndirGraph() : UndirGraphWrapper<Graph>() { 

       Parent::setGraph(gr); 

     }

   };

   ///\brief A wrapper for composing a subgraph of a 

   /// bidirected graph composed from a directed one. 

   /// experimental, for fezso's sake.

   ///

   /// A wrapper for composing a subgraps of a 

   /// bidirected graph composed from a directed one. 

   /// experimental, for fezso's sake.

   /// A bidirected graph is composed over the directed one without physical 

   /// storage. As the oppositely directed edges are logically different ones 

   /// the maps are able to attach different values for them.

   template<typename Graph, 

 	   typename ForwardFilterMap, typename BackwardFilterMap>

   class SubBidirGraphWrapper : public GraphWrapper<Graph> {

   public:

     typedef GraphWrapper<Graph> Parent; 

   protected:

     //const CapacityMap* capacity;

     //FlowMap* flow;

     ForwardFilterMap* forward_filter;

     BackwardFilterMap* backward_filter;

     SubBidirGraphWrapper() : GraphWrapper<Graph>()/*, 

 						 capacity(0), flow(0)*/ { }

     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {

       forward_filter=&_forward_filter;

     }

     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {

       backward_filter=&_backward_filter;

     }

   public:

     SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter, 

 			 BackwardFilterMap& _backward_filter) : 

       GraphWrapper<Graph>(_graph), 

       forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }

     class Edge; 

     class OutEdgeIt; 

     friend class Edge; 

     friend class OutEdgeIt; 

     //template<typename T> class NodeMap;    

     template<typename T> class EdgeMap;

     typedef typename GraphWrapper<Graph>::Node Node;

     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;

     class Edge : public Graph::Edge {

       friend class SubBidirGraphWrapper<Graph, 

 					ForwardFilterMap, BackwardFilterMap>;

       ///\bug ez nem is kell

       //template<typename T> friend class NodeMap;

       template<typename T> friend class EdgeMap;

     protected:

       bool backward; //true, iff backward

 //      typename Graph::Edge e;

     public:

       Edge() { }

       ///\bug =false kell-e? zsoltnak kell az addEdge miatt

       Edge(const typename Graph::Edge& _e, bool _backward=false) : 

 	Graph::Edge(_e), backward(_backward) { }

       Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }

 //the unique invalid iterator

       friend bool operator==(const Edge& u, const Edge& v) { 

 	return (v.backward==u.backward && 

 		static_cast<typename Graph::Edge>(u)==

 		static_cast<typename Graph::Edge>(v));

       } 

       friend bool operator!=(const Edge& u, const Edge& v) { 

 	return (v.backward!=u.backward || 

 		static_cast<typename Graph::Edge>(u)!=

 		static_cast<typename Graph::Edge>(v));

       } 

     };

     class OutEdgeIt {

       friend class SubBidirGraphWrapper<Graph, 

 					ForwardFilterMap, BackwardFilterMap>;

     protected:

       typename Graph::OutEdgeIt out;

       typename Graph::InEdgeIt in;

       bool backward;

     public:

       OutEdgeIt() { }

       //FIXME

 //      OutEdgeIt(const Edge& e) : Edge(e) { }

       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }

 //the unique invalid iterator

       OutEdgeIt(const SubBidirGraphWrapper<Graph, 

 		ForwardFilterMap, BackwardFilterMap>& _G, Node v) { 

 	backward=false;

 	_G.graph->first(out, v);

 	while(_G.graph->valid(out) && !(*_G.forward_filter)[*this]) { _G.graph->next(out); }

 	if (!_G.graph->valid(out)) {

 	  backward=true;

 	  _G.graph->first(in, v);

 	  while(_G.graph->valid(in) && !(*_G.backward_filter)[*this]) { _G.graph->next(in); }

 	}

       }

       operator Edge() const { 

 //	Edge e;

 //	e.forward=this->forward;

 //	if (this->forward) e=out; else e=in;

 //	return e;

 	if (this->backward) 

 	  return Edge(in, this->backward); 

 	else 

 	  return Edge(out, this->backward);

       }

     };

     class InEdgeIt {

       friend class SubBidirGraphWrapper<Graph, 

 					ForwardFilterMap, BackwardFilterMap>;

     protected:

       typename Graph::OutEdgeIt out;

       typename Graph::InEdgeIt in;

       bool backward;

     public:

       InEdgeIt() { }

       //FIXME

 //      OutEdgeIt(const Edge& e) : Edge(e) { }

       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }

 //the unique invalid iterator

       InEdgeIt(const SubBidirGraphWrapper<Graph, 

 	       ForwardFilterMap, BackwardFilterMap>& _G, Node v) { 

 	backward=false;

 	_G.graph->first(in, v);

 	while(_G.graph->valid(in) && !(*_G.forward_filter)[*this]) { _G.graph->next(in); }

 	if (!_G.graph->valid(in)) {

 	  backward=true;

 	  _G.graph->first(out, v);

 	  while(_G.graph->valid(out) && !(*_G.backward_filter)[*this]) { _G.graph->next(out); }

 	}

       }

       operator Edge() const { 

 //	Edge e;

 //	e.forward=this->forward;

 //	if (this->forward) e=out; else e=in;

 //	return e;

 	if (this->backward) 

 	  return Edge(out, this->backward); 

 	else 

 	  return Edge(in, this->backward);

       }

     };

     class EdgeIt {

       friend class SubBidirGraphWrapper<Graph, 

 					ForwardFilterMap, BackwardFilterMap>;

     protected:

       typename Graph::EdgeIt e;

       bool backward;

     public:

       EdgeIt() { }

       EdgeIt(const Invalid& i) : e(i), backward(true) { }

       EdgeIt(const SubBidirGraphWrapper<Graph, 

 	     ForwardFilterMap, BackwardFilterMap>& _G) { 

 	backward=false;

 	_G.graph->first(e);

 	while (_G.graph->valid(e) && !(*_G.forward_filter)[*this]) _G.graph->next(e);

 	if (!_G.graph->valid(e)) {

 	  backward=true;

 	  _G.graph->first(e);

 	  while (_G.graph->valid(e) && !(*_G.backward_filter)[*this]) _G.graph->next(e);

 	}

       }

       operator Edge() const { 

 	return Edge(e, this->backward);

       }

     };

     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.backward) {

 	Node v=this->graph->aNode(e.out);

 	this->graph->next(e.out);

 	while(this->graph->valid(e.out) && !(*forward_filter)[e]) { 

 	  this->graph->next(e.out); }

 	if (!this->graph->valid(e.out)) {

 	  e.backward=true;

 	  this->graph->first(e.in, v); 

 	  while(this->graph->valid(e.in) && !(*backward_filter)[e]) { 

 	    this->graph->next(e.in); }

 	}

       } else {

 	this->graph->next(e.in);

 	while(this->graph->valid(e.in) && !(*backward_filter)[e]) { 

 	  this->graph->next(e.in); } 

       }

       return e;

     }

 //     FIXME Not tested

     InEdgeIt& next(InEdgeIt& e) const { 

       if (!e.backward) {

 	Node v=this->graph->aNode(e.in);

 	this->graph->next(e.in);

 	while(this->graph->valid(e.in) && !(*forward_filter)[e]) { 

 	  this->graph->next(e.in); }

 	if (!this->graph->valid(e.in)) {

 	  e.backward=true;

 	  this->graph->first(e.out, v); 

 	  while(this->graph->valid(e.out) && !(*backward_filter)[e]) { 

 	    this->graph->next(e.out); }

 	}

       } else {

 	this->graph->next(e.out);

 	while(this->graph->valid(e.out) && !(*backward_filter)[e]) { 

 	  this->graph->next(e.out); } 

       }

       return e;

     }

     EdgeIt& next(EdgeIt& e) const {

       if (!e.backward) {

 	this->graph->next(e.e);

 	while(this->graph->valid(e.e) && !(*forward_filter)[e]) { 

 	  this->graph->next(e.e); }

 	if (!this->graph->valid(e.e)) {

 	  e.backward=true;

 	  this->graph->first(e.e); 

 	  while(this->graph->valid(e.e) && !(*backward_filter)[e]) { 

 	    this->graph->next(e.e); }

 	}

       } else {

 	this->graph->next(e.e);

 	while(this->graph->valid(e.e) && !(*backward_filter)[e]) { 

 	  this->graph->next(e.e); } 

       }

       return e;

     }

     Node tail(Edge e) const { 

       return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }

     Node head(Edge e) const { 

       return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }

     Node aNode(OutEdgeIt e) const { 

       return ((!e.backward) ? this->graph->aNode(e.out) : 

 	      this->graph->aNode(e.in)); }

     Node bNode(OutEdgeIt e) const { 

       return ((!e.backward) ? this->graph->bNode(e.out) : 

 	      this->graph->bNode(e.in)); }

     Node aNode(InEdgeIt e) const { 

       return ((!e.backward) ? this->graph->aNode(e.in) : 

 	      this->graph->aNode(e.out)); }

     Node bNode(InEdgeIt e) const { 

       return ((!e.backward) ? this->graph->bNode(e.in) : 

 	      this->graph->bNode(e.out)); }

     /// Gives back the opposite edge.

     Edge opposite(const Edge& e) const { 

       Edge f=e;

       f.backward=!f.backward;

       return f;

     }

 //    int nodeNum() const { return graph->nodeNum(); }

     //FIXME

     void edgeNum() const { }

     //int edgeNum() const { return graph->edgeNum(); }

 //    int id(Node v) const { return graph->id(v); }

     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }

     bool valid(Edge e) const { 

       return this->graph->valid(e);

 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in); 

     }

     bool forward(const Edge& e) const { return !e.backward; }

     bool backward(const Edge& e) const { return e.backward; }

 //     void augment(const Edge& e, Number a) const {

 //       if (!e.backward)  

 // // 	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);

 //     }

 //     bool enabled(const Edge& e) const { 

 //       if (!e.backward) 

 // //	return (capacity->get(e.out)-flow->get(e.out)); 

 // 	//return ((*capacity)[e]-(*flow)[e]);

 // 	return true;

 //       else 

 // //	return (flow->get(e.in)); 

 // 	//return ((*flow)[e]); 

 // 	return true;

 //     }

 //     Number enabled(typename Graph::OutEdgeIt out) const { 

 // //      return (capacity->get(out)-flow->get(out)); 

 //       return ((*capacity)[out]-(*flow)[out]); 

 //     }

 //     Number enabled(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:

       typedef T ValueType;

       typedef Edge KeyType;

       EdgeMap(const SubBidirGraphWrapper<Graph, 

 	      ForwardFilterMap, BackwardFilterMap>& _G) : 

 	forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }

       EdgeMap(const SubBidirGraphWrapper<Graph, 

 	      ForwardFilterMap, BackwardFilterMap>& _G, T a) : 

 	forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }

       void set(Edge e, T a) { 

 	if (!e.backward) 

 	  forward_map.set(e/*.out*/, a); 

 	else 

 	  backward_map.set(e/*.in*/, a); 

       }

       T operator[](Edge e) const { 

 	if (!e.backward) 

 	  return forward_map[e/*.out*/]; 

 	else 

 	  return backward_map[e/*.in*/]; 

       }

       void update() { 

 	forward_map.update(); 

 	backward_map.update();

       }

 //       T get(Edge e) const { 

 // 	if (e.out_or_in) 

 // 	  return forward_map.get(e.out); 

 // 	else 

 // 	  return backward_map.get(e.in); 

 //       }

     };

   };

   ///\brief A wrapper for composing bidirected graph from a directed one. 

   /// experimental, for fezso's sake.

   ///

   /// A wrapper for composing bidirected graph from a directed one. 

   /// experimental, for fezso's sake.

   /// A bidirected graph is composed over the directed one without physical 

   /// storage. As the oppositely directed edges are logically different ones 

   /// the maps are able to attach different values for them.

   template<typename Graph>

   class BidirGraphWrapper : 

     public SubBidirGraphWrapper<

     Graph, 

     ConstMap<typename Graph::Edge, bool>, 

     ConstMap<typename Graph::Edge, bool> > {

   public:

     typedef  SubBidirGraphWrapper<

       Graph, 

       ConstMap<typename Graph::Edge, bool>, 

       ConstMap<typename Graph::Edge, bool> > Parent; 

   protected:

     ConstMap<typename Graph::Edge, bool> cm;

     //const CapacityMap* capacity;

     //FlowMap* flow;

     BidirGraphWrapper() : Parent(), cm(true) { }

 //     void setCapacityMap(const CapacityMap& _capacity) {

 //       capacity=&_capacity;

 //     }

 //     void setFlowMap(FlowMap& _flow) {

 //       flow=&_flow;

 //     }

   public:

     BidirGraphWrapper(Graph& _graph) : Parent() { 

       Parent::setGraph(_graph);

       Parent::setForwardFilterMap(cm);

       Parent::setBackwardFilterMap(cm);

     }

   };

   template<typename Graph>

   class OldBidirGraphWrapper : public GraphWrapper<Graph> {

   public:

     typedef GraphWrapper<Graph> Parent; 

   protected:

     //const CapacityMap* capacity;

     //FlowMap* flow;

     OldBidirGraphWrapper() : GraphWrapper<Graph>()/*, 

 						 capacity(0), flow(0)*/ { }

 //     void setCapacityMap(const CapacityMap& _capacity) {

 //       capacity=&_capacity;

 //     }

 //     void setFlowMap(FlowMap& _flow) {

 //       flow=&_flow;

 //     }

   public:

     OldBidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, 

 				     FlowMap& _flow*/) : 

       GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }

     class Edge; 

     class OutEdgeIt; 

     friend class Edge; 

     friend class OutEdgeIt; 

     //template<typename T> class NodeMap;    

     template<typename T> class EdgeMap;

     typedef typename GraphWrapper<Graph>::Node Node;

     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;

     class Edge : public Graph::Edge {

       friend class OldBidirGraphWrapper<Graph>;

       ///\bug ez nem is kell

       //template<typename T> friend class NodeMap;

       template<typename T> friend class EdgeMap;

     protected:

       bool backward; //true, iff backward

 //      typename Graph::Edge e;

     public:

       Edge() { }

       ///\bug =false kell-e? zsoltnak kell az addEdge miatt

       Edge(const typename Graph::Edge& _e, bool _backward=false) : 

 	Graph::Edge(_e), backward(_backward) { }

       Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }

 //the unique invalid iterator

       friend bool operator==(const Edge& u, const Edge& v) { 

 	return (v.backward==u.backward && 

 		static_cast<typename Graph::Edge>(u)==

 		static_cast<typename Graph::Edge>(v));

       } 

       friend bool operator!=(const Edge& u, const Edge& v) { 

 	return (v.backward!=u.backward || 

 		static_cast<typename Graph::Edge>(u)!=

 		static_cast<typename Graph::Edge>(v));

       } 

     };

     class OutEdgeIt {

       friend class OldBidirGraphWrapper<Graph>;

     protected:

       typename Graph::OutEdgeIt out;

       typename Graph::InEdgeIt in;

       bool backward;

     public:

       OutEdgeIt() { }

       //FIXME

 //      OutEdgeIt(const Edge& e) : Edge(e) { }

       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }

 //the unique invalid iterator

       OutEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) { 

 	backward=false;

 	_G.graph->first(out, v);

 	while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }

 	if (!_G.graph->valid(out)) {

 	  backward=true;

 	  _G.graph->first(in, v);

 	  while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }

 	}

       }

       operator Edge() const { 

 //	Edge e;

 //	e.forward=this->forward;

 //	if (this->forward) e=out; else e=in;

 //	return e;

 	if (this->backward) 

 	  return Edge(in, this->backward); 

 	else 

 	  return Edge(out, this->backward);

       }

     };

     class InEdgeIt {

       friend class OldBidirGraphWrapper<Graph>;

     protected:

       typename Graph::OutEdgeIt out;

       typename Graph::InEdgeIt in;

       bool backward;

     public:

       InEdgeIt() { }

       //FIXME

 //      OutEdgeIt(const Edge& e) : Edge(e) { }

       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }

 //the unique invalid iterator

       InEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) { 

 	backward=false;

 	_G.graph->first(in, v);

 	while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }

 	if (!_G.graph->valid(in)) {

 	  backward=true;

 	  _G.graph->first(out, v);

 	  while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }

 	}

       }

       operator Edge() const { 

 //	Edge e;

 //	e.forward=this->forward;

 //	if (this->forward) e=out; else e=in;

 //	return e;

 	if (this->backward) 

 	  return Edge(out, this->backward); 

 	else 

 	  return Edge(in, this->backward);

       }

     };

     class EdgeIt {

       friend class OldBidirGraphWrapper<Graph>;

     protected:

       typename Graph::EdgeIt e;

       bool backward;

     public:

       EdgeIt() { }

       EdgeIt(const Invalid& i) : e(i), backward(true) { }

       EdgeIt(const OldBidirGraphWrapper<Graph>& _G) { 

 	backward=false;

 	_G.graph->first(e);

 	while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);

 	if (!_G.graph->valid(e)) {

 	  backward=true;

 	  _G.graph->first(e);

 	  while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);

 	}

       }

       operator Edge() const { 

 	return Edge(e, this->backward);

       }

     };

     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.backward) {

 	Node v=this->graph->aNode(e.out);

 	this->graph->next(e.out);

 	while(this->graph->valid(e.out) && !enabled(e)) { 

 	  this->graph->next(e.out); }

 	if (!this->graph->valid(e.out)) {

 	  e.backward=true;

 	  this->graph->first(e.in, v); 

 	  while(this->graph->valid(e.in) && !enabled(e)) { 

 	    this->graph->next(e.in); }

 	}

       } else {

 	this->graph->next(e.in);

 	while(this->graph->valid(e.in) && !enabled(e)) { 

 	  this->graph->next(e.in); } 

       }

       return e;

     }

 //     FIXME Not tested

     InEdgeIt& next(InEdgeIt& e) const { 

       if (!e.backward) {

 	Node v=this->graph->aNode(e.in);

 	this->graph->next(e.in);

 	while(this->graph->valid(e.in) && !enabled(e)) { 

 	  this->graph->next(e.in); }

 	if (!this->graph->valid(e.in)) {

 	  e.backward=true;

 	  this->graph->first(e.out, v); 

 	  while(this->graph->valid(e.out) && !enabled(e)) { 

 	    this->graph->next(e.out); }

 	}

       } else {

 	this->graph->next(e.out);

 	while(this->graph->valid(e.out) && !enabled(e)) { 

 	  this->graph->next(e.out); } 

       }

       return e;

     }

     EdgeIt& next(EdgeIt& e) const {

       if (!e.backward) {

 	this->graph->next(e.e);

 	while(this->graph->valid(e.e) && !enabled(e)) { 

 	  this->graph->next(e.e); }

 	if (!this->graph->valid(e.e)) {

 	  e.backward=true;

 	  this->graph->first(e.e); 

 	  while(this->graph->valid(e.e) && !enabled(e)) { 

 	    this->graph->next(e.e); }

 	}

       } else {

 	this->graph->next(e.e);

 	while(this->graph->valid(e.e) && !enabled(e)) { 

 	  this->graph->next(e.e); } 

       }

       return e;

     }

     Node tail(Edge e) const { 

       return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }

     Node head(Edge e) const { 

       return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }

     Node aNode(OutEdgeIt e) const { 

       return ((!e.backward) ? this->graph->aNode(e.out) : 

 	      this->graph->aNode(e.in)); }

     Node bNode(OutEdgeIt e) const { 

       return ((!e.backward) ? this->graph->bNode(e.out) : 

 	      this->graph->bNode(e.in)); }

     Node aNode(InEdgeIt e) const { 

       return ((!e.backward) ? this->graph->aNode(e.in) : 

 	      this->graph->aNode(e.out)); }

     Node bNode(InEdgeIt e) const { 

       return ((!e.backward) ? this->graph->bNode(e.in) : 

 	      this->graph->bNode(e.out)); }

     /// Gives back the opposite edge.

     Edge opposite(const Edge& e) const { 

       Edge f=e;

       f.backward=!f.backward;

       return f;

     }

 //    int nodeNum() const { return graph->nodeNum(); }

     //FIXME

     void edgeNum() const { }

     //int edgeNum() const { return graph->edgeNum(); }

 //    int id(Node v) const { return graph->id(v); }

     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }

     bool valid(Edge e) const { 

       return this->graph->valid(e);

 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in); 

     }

     bool forward(const Edge& e) const { return !e.backward; }

     bool backward(const Edge& e) const { return e.backward; }

 //     void augment(const Edge& e, Number a) const {

 //       if (!e.backward)  

 // // 	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);

 //     }

     bool enabled(const Edge& e) const { 

       if (!e.backward) 

 //	return (capacity->get(e.out)-flow->get(e.out)); 

 	//return ((*capacity)[e]-(*flow)[e]);

 	return true;

       else 

 //	return (flow->get(e.in)); 

 	//return ((*flow)[e]); 

 	return true;

     }

 //     Number enabled(typename Graph::OutEdgeIt out) const { 

 // //      return (capacity->get(out)-flow->get(out)); 

 //       return ((*capacity)[out]-(*flow)[out]); 

 //     }

 //     Number enabled(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:

       typedef T ValueType;

       typedef Edge KeyType;

       EdgeMap(const OldBidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }

       EdgeMap(const OldBidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }

       void set(Edge e, T a) { 

 	if (!e.backward) 

 	  forward_map.set(e/*.out*/, a); 

 	else 

 	  backward_map.set(e/*.in*/, a); 

       }

       T operator[](Edge e) const { 

 	if (!e.backward) 

 	  return forward_map[e/*.out*/]; 

 	else 

 	  return backward_map[e/*.in*/]; 

       }

       void update() { 

 	forward_map.update(); 

 	backward_map.update();

       }

 //       T get(Edge e) const { 

 // 	if (e.out_or_in) 

 // 	  return forward_map.get(e.out); 

 // 	else 

 // 	  return backward_map.get(e.in); 

 //       }

     };

   };

   /// \brief A bidirected graph template.

   ///

   /// A bidirected graph template.

   /// Such a bidirected graph stores each pair of oppositely directed edges 

   /// ones in the memory, i.e. a directed graph of type 

   /// \c Graph is used for that.

   /// As the oppositely directed edges are logically different ones 

   /// the maps are able to attach different values for them.

   /// \ingroup graphs

   template<typename Graph>

   class BidirGraph : public BidirGraphWrapper<Graph> {

   public:

     typedef UndirGraphWrapper<Graph> Parent;

   protected:

     Graph gr;

   public:

     BidirGraph() : BidirGraphWrapper<Graph>() { 

       Parent::setGraph(gr); 

     }

   };

   template<typename Graph, typename Number,

 	   typename CapacityMap, typename FlowMap>

   class ForwardFilter {

     const Graph* graph;

     const CapacityMap* capacity;

     const FlowMap* flow;

   public:

     ForwardFilter(const Graph& _graph, 

 		  const CapacityMap& _capacity, const FlowMap& _flow) :

       graph(&_graph), capacity(&_capacity), flow(&_flow) { }

     bool operator[](const typename Graph::Edge& e) const {

       return ((*flow)[e] < (*capacity)[e]);

     }

   };

   template<typename Graph, typename Number,

 	   typename CapacityMap, typename FlowMap>

   class BackwardFilter {

     const Graph* graph;

     const CapacityMap* capacity;

     const FlowMap* flow;

   public:

     BackwardFilter(const Graph& _graph, 

 		   const CapacityMap& _capacity, const FlowMap& _flow) :

       graph(&_graph), capacity(&_capacity), flow(&_flow) { }

     bool operator[](const typename Graph::Edge& e) const {

       return (0 < (*flow)[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 SubBidirGraphWrapper< 

     Graph, 

     ForwardFilter<Graph, Number, CapacityMap, FlowMap>,  

     BackwardFilter<Graph, Number, CapacityMap, FlowMap> > {

   public:

     typedef SubBidirGraphWrapper< 

       Graph, 

       ForwardFilter<Graph, Number, CapacityMap, FlowMap>,  

       BackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;

   protected:

     const CapacityMap* capacity;

     FlowMap* flow;

     ForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;

     BackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;

   public:

     ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 

 		       FlowMap& _flow) : 

       Parent(), capacity(&_capacity), flow(&_flow), 

       forward_filter(_graph, _capacity, _flow), 

       backward_filter(_graph, _capacity, _flow) {

       Parent::setGraph(_graph);

       Parent::setForwardFilterMap(forward_filter);

       Parent::setBackwardFilterMap(backward_filter);

     }

     //    bool forward(const Parent::Edge& e) const { return Parent::forward(e); }

     //bool backward(const Edge& e) const { return e.backward; }

     void augment(const typename Parent::Edge& e, Number a) const {

       if (Parent::forward(e))  

 // 	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 typename Parent::Edge& e) const { 

       if (Parent::forward(e)) 

 //	return (capacity->get(e.out)-flow->get(e.out)); 

 	return ((*capacity)[e]-(*flow)[e]); 

       else 

 //	return (flow->get(e.in)); 

 	return ((*flow)[e]); 

     }

   };

   template<typename Graph, typename Number, 

 	   typename CapacityMap, typename FlowMap>

   class OldResGraphWrapper : public GraphWrapper<Graph> {

   public:

     typedef GraphWrapper<Graph> Parent; 

   protected:

     const CapacityMap* capacity;

     FlowMap* flow;

     OldResGraphWrapper() : GraphWrapper<Graph>(0), 

 			capacity(0), flow(0) { }

     void setCapacityMap(const CapacityMap& _capacity) {

       capacity=&_capacity;

     }

     void setFlowMap(FlowMap& _flow) {

       flow=&_flow;

     }

   public:

     OldResGraphWrapper(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 OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;

     protected:

       bool backward; //true, iff backward

 //      typename Graph::Edge e;

     public:

       Edge() { }

       Edge(const typename Graph::Edge& _e, bool _backward) : 

 	Graph::Edge(_e), backward(_backward) { }

       Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }

 //the unique invalid iterator

       friend bool operator==(const Edge& u, const Edge& v) { 

 	return (v.backward==u.backward && 

 		static_cast<typename Graph::Edge>(u)==

 		static_cast<typename Graph::Edge>(v));

       } 

       friend bool operator!=(const Edge& u, const Edge& v) { 

 	return (v.backward!=u.backward || 

 		static_cast<typename Graph::Edge>(u)!=

 		static_cast<typename Graph::Edge>(v));

       } 

     };

     class OutEdgeIt {

       friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;

     protected:

       typename Graph::OutEdgeIt out;

       typename Graph::InEdgeIt in;

       bool backward;

     public:

       OutEdgeIt() { }

       //FIXME

 //      OutEdgeIt(const Edge& e) : Edge(e) { }

       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }

 //the unique invalid iterator

       OutEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 

 	backward=false;

 	_G.graph->first(out, v);

 	while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }

 	if (!_G.graph->valid(out)) {

 	  backward=true;

 	  _G.graph->first(in, v);

 	  while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }

 	}

       }

       operator Edge() const { 

 //	Edge e;

 //	e.forward=this->forward;

 //	if (this->forward) e=out; else e=in;

 //	return e;

 	if (this->backward) 

 	  return Edge(in, this->backward); 

 	else 

 	  return Edge(out, this->backward);

       }

     };

     class InEdgeIt {

       friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;

     protected:

       typename Graph::OutEdgeIt out;

       typename Graph::InEdgeIt in;

       bool backward;

     public:

       InEdgeIt() { }

       //FIXME

 //      OutEdgeIt(const Edge& e) : Edge(e) { }

       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }

 //the unique invalid iterator

       InEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 

 	backward=false;

 	_G.graph->first(in, v);

 	while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }

 	if (!_G.graph->valid(in)) {

 	  backward=true;

 	  _G.graph->first(out, v);

 	  while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }

 	}

       }

       operator Edge() const { 

 //	Edge e;

 //	e.forward=this->forward;

 //	if (this->forward) e=out; else e=in;

 //	return e;

 	if (this->backward) 

 	  return Edge(out, this->backward); 

 	else 

 	  return Edge(in, this->backward);

       }

     };

     class EdgeIt {

       friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;

     protected:

       typename Graph::EdgeIt e;

       bool backward;

     public:

       EdgeIt() { }

       EdgeIt(const Invalid& i) : e(i), backward(true) { }

       EdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) { 

 	backward=false;

 	_G.graph->first(e);

 	while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);

 	if (!_G.graph->valid(e)) {

 	  backward=true;

 	  _G.graph->first(e);

 	  while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);

 	}

       }

       operator Edge() const { 

 	return Edge(e, this->backward);

       }

     };

     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.backward) {

 	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.backward=true;

 	  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.backward) {

 	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.backward=true;

 	  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.backward) {

 	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.backward=true;

 	  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.backward) ? this->graph->tail(e) : this->graph->head(e)); }

     Node head(Edge e) const { 

       return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }

     Node aNode(OutEdgeIt e) const { 

       return ((!e.backward) ? this->graph->aNode(e.out) : 

 	      this->graph->aNode(e.in)); }

     Node bNode(OutEdgeIt e) const { 

       return ((!e.backward) ? this->graph->bNode(e.out) : 

 	      this->graph->bNode(e.in)); }

     Node aNode(InEdgeIt e) const { 

       return ((!e.backward) ? this->graph->aNode(e.in) : 

 	      this->graph->aNode(e.out)); }

     Node bNode(InEdgeIt e) const { 

       return ((!e.backward) ? this->graph->bNode(e.in) : 

 	      this->graph->bNode(e.out)); }

 //    int nodeNum() const { return graph->nodeNum(); }

     //FIXME

     void edgeNum() const { }

     //int edgeNum() const { return graph->edgeNum(); }

 //    int id(Node v) const { return graph->id(v); }

     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }

     bool valid(Edge e) const { 

       return this->graph->valid(e);

 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in); 

     }

     bool forward(const Edge& e) const { return !e.backward; }

     bool backward(const Edge& e) const { return e.backward; }

     void augment(const Edge& e, Number a) const {

       if (!e.backward)  

 // 	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.backward) 

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

       typedef T ValueType;

       typedef Edge KeyType;

       EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }

       EdgeMap(const OldResGraphWrapper<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.backward) 

 	  forward_map.set(e/*.out*/, a); 

 	else 

 	  backward_map.set(e/*.in*/, a); 

       }

       T operator[](Edge e) const { 

 	if (!e.backward) 

 	  return forward_map[e/*.out*/]; 

 	else 

 	  return backward_map[e/*.in*/]; 

       }

       void update() { 

 	forward_map.update(); 

 	backward_map.update();

       }

 //       T get(Edge e) const { 

 // 	if (e.out_or_in) 

 // 	  return forward_map.get(e.out); 

 // 	else 

 // 	  return backward_map.get(e.in); 

 //       }

     };

   };

   /// For blocking flows.

   /// This graph wrapper is used for Dinits blocking flow computations.

   /// For each node, an out-edge is stored which is used when the 

   /// \code 

   /// OutEdgeIt& first(OutEdgeIt&, const Node&)

   /// \endcode

   /// is called. 

   ///

   ///\author Marton Makai

   template<typename Graph, typename FirstOutEdgesMap>

   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {

   public:

     typedef GraphWrapper<Graph> Parent; 

   protected:

     FirstOutEdgesMap* first_out_edges;

   public:

     ErasingFirstGraphWrapper(Graph& _graph, 

 			     FirstOutEdgesMap& _first_out_edges) : 

       GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }  

     typedef typename GraphWrapper<Graph>::Node Node;

 //     class NodeIt { 

 //       friend class GraphWrapper<Graph>;

 //       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

 //       typename Graph::NodeIt n;

 //      public:

 //       NodeIt() { }

 //       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }

 //       NodeIt(const Invalid& i) : n(i) { }

 //       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 

 // 	n(*(_G.graph)) { }

 //       operator Node() const { return Node(typename Graph::Node(n)); }

 //     };

     typedef typename GraphWrapper<Graph>::Edge Edge;

     class OutEdgeIt { 

       friend class GraphWrapper<Graph>;

       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

       typename Graph::OutEdgeIt e;

     public:

       OutEdgeIt() { }

       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }

       OutEdgeIt(const Invalid& i) : e(i) { }

       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 

 		const Node& _n) : 

 	e((*_G.first_out_edges)[_n]) { }

       operator Edge() const { return Edge(typename Graph::Edge(e)); }

     };

     class InEdgeIt { 

       friend class GraphWrapper<Graph>;

       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

       typename Graph::InEdgeIt e;

     public:

       InEdgeIt() { }

       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }

       InEdgeIt(const Invalid& i) : e(i) { }

       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 

 	       const Node& _n) : 

 	e(*(_G.graph), typename Graph::Node(_n)) { }

       operator Edge() const { return Edge(typename Graph::Edge(e)); }

     };

     //typedef typename Graph::SymEdgeIt SymEdgeIt;

     class EdgeIt { 

       friend class GraphWrapper<Graph>;

       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

 //      typedef typename Graph::EdgeIt GraphEdgeIt;

       typename Graph::EdgeIt e;

     public:

       EdgeIt() { }

       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }

       EdgeIt(const Invalid& i) : e(i) { }

       EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 

 	e(*(_G.graph)) { }

       operator Edge() const { return Edge(typename Graph::Edge(e)); }

     };

     using GraphWrapper<Graph>::first;

 //     NodeIt& first(NodeIt& i) const { 

 //       i=NodeIt(*this); return i;

 //     }

     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 

       i=OutEdgeIt(*this, p); return i;

     }

     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 

       i=InEdgeIt(*this, p); return i;

     }

     EdgeIt& first(EdgeIt& i) const { 

       i=EdgeIt(*this); return i;

     }

     using GraphWrapper<Graph>::next;

 //    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }

     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }

     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }

     EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }    

     Node aNode(const OutEdgeIt& e) const { 

       return Node(this->graph->aNode(e.e)); }

     Node aNode(const InEdgeIt& e) const { 

       return Node(this->graph->aNode(e.e)); }

     Node bNode(const OutEdgeIt& e) const { 

       return Node(this->graph->bNode(e.e)); }

     Node bNode(const InEdgeIt& e) const { 

       return Node(this->graph->bNode(e.e)); }

     void erase(const OutEdgeIt& e) const {

       OutEdgeIt f=e;

       this->next(f);

       first_out_edges->set(this->tail(e), f.e);

     }

   };

   ///@}

 } //namespace hugo

 #endif //HUGO_GRAPH_WRAPPER_H