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

 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) { }

     GraphWrapper(const GraphWrapper<Graph>& gw) : graph(gw.graph) { }

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

     typedef typename Graph::Node Node;

     class NodeIt : public Node { 

       const GraphWrapper<Graph>* gw;

       friend class GraphWrapper<Graph>;

      public:

       NodeIt() { }

       //      NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { }

       NodeIt(Invalid i) : Node(i) { }

       NodeIt(const GraphWrapper<Graph>& _gw) : 

 	Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }

       NodeIt(const GraphWrapper<Graph>& _gw, const Node& n) : 

 	Node(n), gw(&_gw) { }

       NodeIt& operator++() { 

 	*(static_cast<Node*>(this))=

 	  ++(typename Graph::NodeIt(*(gw->graph), *this));

 	return *this; 

       }

     };

     typedef typename Graph::Edge Edge;

     class OutEdgeIt : public Edge { 

       const GraphWrapper<Graph>* gw;

       friend class GraphWrapper<Graph>;

      public:

       OutEdgeIt() { }

       //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }

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

       OutEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) : 

 	Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }

       OutEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : 

 	Edge(e), gw(&_gw) { }

       OutEdgeIt& operator++() { 

 	*(static_cast<Edge*>(this))=

 	  ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

 	return *this; 

       }

     };

     class InEdgeIt : public Edge { 

       const GraphWrapper<Graph>* gw;

       friend class GraphWrapper<Graph>;

      public:

       InEdgeIt() { }

       //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }

       InEdgeIt(Invalid i) : Edge(i) { }

       InEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) : 

 	Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }

       InEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : 

 	Edge(e), gw(&_gw) { }

       InEdgeIt& operator++() { 

 	*(static_cast<Edge*>(this))=

 	  ++(typename Graph::InEdgeIt(*(gw->graph), *this));

 	return *this; 

       }

     };

     //typedef typename Graph::SymEdgeIt SymEdgeIt;

     class EdgeIt : public Edge { 

       const GraphWrapper<Graph>* gw;

       friend class GraphWrapper<Graph>;

      public:

       EdgeIt() { }

       //EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { }

       EdgeIt(Invalid i) : Edge(i) { }

       EdgeIt(const GraphWrapper<Graph>& _gw) : 

 	Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }

       EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : 

 	Edge(e), gw(&_gw) { }

       EdgeIt& operator++() { 

 	*(static_cast<Edge*>(this))=

 	  ++(typename Graph::EdgeIt(*(gw->graph), *this));

 	return *this; 

       }

     };

     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 { return graph->forward(e); }

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

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

     int id(const Edge& e) const { return graph->id(e); }

     Edge opposite(const Edge& e) const { return 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>& gw) :  Parent(*(gw.graph)) { }

       NodeMap(const GraphWrapper<Graph>& gw, T a) : Parent(*(gw.graph), a) { }

     };

     template<typename T> class EdgeMap : public Graph::template EdgeMap<T> { 

       typedef typename Graph::template EdgeMap<T> Parent;

     public:

       EdgeMap(const GraphWrapper<Graph>& gw) : Parent(*(gw.graph)) { }

       EdgeMap(const GraphWrapper<Graph>& gw, T a) : Parent(*(gw.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) { }  

     RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { }

     typedef typename GraphWrapper<Graph>::Node Node;

     typedef typename GraphWrapper<Graph>::Edge Edge;

     //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other

     //because this does not work is some of them are not defined in the 

     //original graph. The problem with this is that typedef-ed stuff 

     //are instantiated in c++.

     class OutEdgeIt : public Edge { 

       const RevGraphWrapper<Graph>* gw;

       friend class GraphWrapper<Graph>;

      public:

       OutEdgeIt() { }

       //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }

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

       OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) : 

 	Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }

       OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) : 

 	Edge(e), gw(&_gw) { }

       OutEdgeIt& operator++() { 

 	*(static_cast<Edge*>(this))=

 	  ++(typename Graph::InEdgeIt(*(gw->graph), *this));

 	return *this; 

       }

     };

     class InEdgeIt : public Edge { 

       const RevGraphWrapper<Graph>* gw;

       friend class GraphWrapper<Graph>;

      public:

       InEdgeIt() { }

       //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }

       InEdgeIt(Invalid i) : Edge(i) { }

       InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) : 

 	Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }

       InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) : 

 	Edge(e), gw(&_gw) { }

       InEdgeIt& operator++() { 

 	*(static_cast<Edge*>(this))=

 	  ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

 	return *this; 

       }

     };

     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. Given a bool-valued map on the node-set and one on 

   /// the edge-set of the graphs, the iterators shows only the objects 

   /// having true value. 

   /// The quick brown fox iterators jump over 

   /// the lazy dog nodes or edges if their values for are false in the 

   /// corresponding 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 : public Node { 

       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;

       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

     public:

       NodeIt() { }

       //      NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { }

       NodeIt(Invalid i) : Node(i) { }

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

 	Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }

       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 

 	     const Node& n) : 

 	Node(n), gw(&_gw) { }

       NodeIt& operator++() { 

 	*(static_cast<Node*>(this))=

 	  ++(typename Graph::NodeIt(*(gw->graph), *this));

 	while (*static_cast<Node*>(this)!=INVALID && 

 	       !(*(gw->node_filter_map))[*this]) 

 	  *(static_cast<Node*>(this))=

 	    ++(typename Graph::NodeIt(*(gw->graph), *this));

 	return *this; 

       }

     };

     typedef typename GraphWrapper<Graph>::Edge Edge;

     class OutEdgeIt : public Edge { 

       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;

       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

     public:

       OutEdgeIt() { }

       //      OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }

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

       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 

 	Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }

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

 	     const Edge& e) : 

 	Edge(e), gw(&_gw) { }

       OutEdgeIt& operator++() { 

 	*(static_cast<Edge*>(this))=

 	  ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

 	while (*static_cast<Edge*>(this)!=INVALID && 

 	       !(*(gw->edge_filter_map))[*this]) 

 	  *(static_cast<Edge*>(this))=

 	    ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

 	return *this; 

       }

     };

     class InEdgeIt : public Edge { 

       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;

       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

     public:

       InEdgeIt() { }

       //      InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }

       InEdgeIt(Invalid i) : Edge(i) { }

       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 

 	Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }

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

 	     const Edge& e) : 

 	Edge(e), gw(&_gw) { }

       InEdgeIt& operator++() { 

 	*(static_cast<Edge*>(this))=

 	  ++(typename Graph::InEdgeIt(*(gw->graph), *this));

 	while (*static_cast<Edge*>(this)!=INVALID && 

 	       !(*(gw->edge_filter_map))[*this]) 

 	  *(static_cast<Edge*>(this))=

 	    ++(typename Graph::InEdgeIt(*(gw->graph), *this));

 	return *this; 

       }

     };

     class EdgeIt : public Edge { 

       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;

       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

     public:

       EdgeIt() { }

       //      EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { }

       EdgeIt(Invalid i) : Edge(i) { }

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

 	Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }

       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 

 	     const Edge& e) : 

 	Edge(e), gw(&_gw) { }

       EdgeIt& operator++() { 

 	*(static_cast<Edge*>(this))=

 	  ++(typename Graph::EdgeIt(*(gw->graph), *this));

 	while (*static_cast<Edge*>(this)!=INVALID && 

 	       !(*(gw->edge_filter_map))[*this]) 

 	  *(static_cast<Edge*>(this))=

 	    ++(typename Graph::EdgeIt(*(gw->graph), *this));

 	return *this; 

       }

     };

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

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

     /// \c Graph::NodeIt is defined.

     int nodeNum() const { 

       int i=0;

       for (NodeIt n(*this); n!=INVALID; ++n) ++i;

       return i; 

     }

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

     /// \c Graph::EdgeIt is defined.

     int edgeNum() const { 

       int i=0;

       for (EdgeIt e(*this); e!=INVALID; ++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

 //   /// does not work in the new concept.

   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 made from a directed one. 

   ///

   /// Suppose that for a directed graph $G=(V, A)$, 

   /// two predicates on the edge-set, $forward_filter$, and $backward_filter$ 

   /// is given, and we are dealing with the directed graph

   /// a $G'=(V, \{uv : uv\in A \mbox{ and } forward_filter(uv) \mbox{ is true}\}+\{vu : uv\in A \mbox{ and } backward_filter(uv) \mbox{ is true}\})$. 

   /// The purpose of writing + instead of union is because parallel 

   /// edges can arose. 

   /// In other words, a subgraph of the bidirected graph obtained, which 

   /// is given by orienting the edges of the original graph in both directions.

   /// An example for such a construction is the \c RevGraphWrapper where the 

   /// forward_filter is everywhere false and the backward_filter is 

   /// everywhere true. We note that for sake of efficiency, 

   /// \c RevGraphWrapper is implemented in a different way. 

   /// But BidirGraphWrapper is obtained from 

   /// SubBidirGraphWrapper by considering everywhere true 

   /// predicates both forward_filter and backward_filter. 

   /// Finally, one of the most important applications of SubBidirGraphWrapper 

   /// is ResGraphWrapper, which stands for the residual graph in directed 

   /// flow and circulation problems. 

   /// As wrappers usually, the SubBidirGraphWrapper implements the 

   /// above mentioned graph structure without its physical storage, 

   /// that is the whole stuff eats constant memory. 

   /// As the oppositely directed edges are logical different, 

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

     ForwardFilterMap* forward_filter;

     BackwardFilterMap* backward_filter;

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

     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) { }

     SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph, 

 			 ForwardFilterMap, BackwardFilterMap>& gw) : 

       Parent(gw), 

       forward_filter(gw.forward_filter), 

       backward_filter(gw.backward_filter) { }

     class Edge; 

     class OutEdgeIt; 

     friend class Edge; 

     friend class OutEdgeIt; 

     template<typename T> class EdgeMap;

     typedef typename GraphWrapper<Graph>::Node Node;

     typedef typename Graph::Edge GraphEdge;

     /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from 

     /// Graph::Edge. It contains an extra bool flag which shows if the 

     /// edge is the backward version of the original edge.

     class Edge : public Graph::Edge {

       friend class SubBidirGraphWrapper<Graph, 

 					ForwardFilterMap, BackwardFilterMap>;

       template<typename T> friend class EdgeMap;

     protected:

       bool backward; //true, iff backward

     public:

       Edge() { }

       /// \todo =false is needed, or causes problems?

       /// If \c _backward is false, then we get an edge corresponding to the 

       /// original one, otherwise its oppositely directed pair is obtained.

       Edge(const typename Graph::Edge& e, bool _backward/*=false*/) : 

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

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

 //the unique invalid iterator

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

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

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

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

 //       } 

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

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

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

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

 //       }

       bool operator==(const Edge& v) const { 

 	return (this->backward==v.backward && 

 		static_cast<typename Graph::Edge>(*this)==

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

       } 

       bool operator!=(const Edge& v) const { 

 	return (this->backward!=v.backward || 

 		static_cast<typename Graph::Edge>(*this)!=

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

       }

     };

     class OutEdgeIt : public Edge {

       friend class SubBidirGraphWrapper<Graph, 

 					ForwardFilterMap, BackwardFilterMap>;

     protected:

       const SubBidirGraphWrapper<Graph, 

 				 ForwardFilterMap, BackwardFilterMap>* gw;

     public:

       OutEdgeIt() { }

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

 //the unique invalid iterator

       OutEdgeIt(const SubBidirGraphWrapper<Graph, 

 		ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : 

 	Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) { 

 	while (*static_cast<GraphEdge*>(this)!=INVALID && 

 	       !(*(gw->forward_filter))[*this]) 

 	  *(static_cast<GraphEdge*>(this))=

 	    ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

 	if (*static_cast<GraphEdge*>(this)==INVALID) {

 	  *static_cast<Edge*>(this)=

 	    Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);

 	  while (*static_cast<GraphEdge*>(this)!=INVALID && 

 		 !(*(gw->backward_filter))[*this]) 

 	    *(static_cast<GraphEdge*>(this))=

 	      ++(typename Graph::InEdgeIt(*(gw->graph), *this));

 	}

       }

       OutEdgeIt(const SubBidirGraphWrapper<Graph, 

 		ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 

 	Edge(e), gw(&_gw) { }

       OutEdgeIt& operator++() { 

 	if (!this->backward) {

 	  Node n=gw->tail(*this);

 	  *(static_cast<GraphEdge*>(this))=

 	    ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

 	  while (*static_cast<GraphEdge*>(this)!=INVALID && 

 		 !(*(gw->forward_filter))[*this]) 

 	    *(static_cast<GraphEdge*>(this))=

 	      ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

 	  if (*static_cast<GraphEdge*>(this)==INVALID) {

 	    *static_cast<Edge*>(this)=

 	      Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);

 	    while (*static_cast<GraphEdge*>(this)!=INVALID && 

 		   !(*(gw->backward_filter))[*this]) 

 	      *(static_cast<GraphEdge*>(this))=

 		++(typename Graph::InEdgeIt(*(gw->graph), *this));

 	  }

 	} else {

 	  *(static_cast<GraphEdge*>(this))=

 	    ++(typename Graph::InEdgeIt(*(gw->graph), *this));

 	  while (*static_cast<GraphEdge*>(this)!=INVALID && 

 		 !(*(gw->backward_filter))[*this]) 

 	    *(static_cast<GraphEdge*>(this))=

 	      ++(typename Graph::InEdgeIt(*(gw->graph), *this));

 	}

 	return *this;

       }

     };

     class InEdgeIt : public Edge {

       friend class SubBidirGraphWrapper<Graph, 

 					ForwardFilterMap, BackwardFilterMap>;

     protected:

       const SubBidirGraphWrapper<Graph, 

 				 ForwardFilterMap, BackwardFilterMap>* gw;

     public:

       InEdgeIt() { }

       InEdgeIt(Invalid i) : Edge(i) { }

 //the unique invalid iterator

       InEdgeIt(const SubBidirGraphWrapper<Graph, 

 	       ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : 

 	Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) { 

 	while (*static_cast<GraphEdge*>(this)!=INVALID && 

 	       !(*(gw->forward_filter))[*this]) 

 	  *(static_cast<GraphEdge*>(this))=

 	    ++(typename Graph::InEdgeIt(*(gw->graph), *this));

 	if (*static_cast<GraphEdge*>(this)==INVALID) {

 	  *static_cast<Edge*>(this)=

 	    Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);

 	  while (*static_cast<GraphEdge*>(this)!=INVALID && 

 		 !(*(gw->backward_filter))[*this]) 

 	    *(static_cast<GraphEdge*>(this))=

 	      ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

 	}

       }

       InEdgeIt(const SubBidirGraphWrapper<Graph, 

 	       ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 

 	Edge(e), gw(&_gw) { }

       InEdgeIt& operator++() { 

 	if (!this->backward) {

 	  Node n=gw->tail(*this);

 	  *(static_cast<GraphEdge*>(this))=

 	    ++(typename Graph::InEdgeIt(*(gw->graph), *this));

 	  while (*static_cast<GraphEdge*>(this)!=INVALID && 

 		 !(*(gw->forward_filter))[*this]) 

 	    *(static_cast<GraphEdge*>(this))=

 	      ++(typename Graph::InEdgeIt(*(gw->graph), *this));

 	  if (*static_cast<GraphEdge*>(this)==INVALID) {

 	    *static_cast<Edge*>(this)=

 	      Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);

 	    while (*static_cast<GraphEdge*>(this)!=INVALID && 

 		   !(*(gw->backward_filter))[*this]) 

 	      *(static_cast<GraphEdge*>(this))=

 		++(typename Graph::OutEdgeIt(*(gw->graph), *this));

 	  }

 	} else {

 	  *(static_cast<GraphEdge*>(this))=

 	    ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

 	  while (*static_cast<GraphEdge*>(this)!=INVALID && 

 		 !(*(gw->backward_filter))[*this]) 

 	    *(static_cast<GraphEdge*>(this))=

 	      ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

 	}

 	return *this;

       }

     };

     class EdgeIt : public Edge {

       friend class SubBidirGraphWrapper<Graph, 

 					ForwardFilterMap, BackwardFilterMap>;

     protected:

       const SubBidirGraphWrapper<Graph, 

 				 ForwardFilterMap, BackwardFilterMap>* gw;

     public:

       EdgeIt() { }

       EdgeIt(Invalid i) : Edge(i) { }

 //the unique invalid iterator

       EdgeIt(const SubBidirGraphWrapper<Graph, 

 	     ForwardFilterMap, BackwardFilterMap>& _gw) : 

 	Edge(typename Graph::OutEdgeIt(*(_gw.graph)), false), gw(&_gw) { 

 	while (*static_cast<GraphEdge*>(this)!=INVALID && 

 	       !(*(gw->forward_filter))[*this]) 

 	  *(static_cast<GraphEdge*>(this))=

 	    ++(typename Graph::EdgeIt(*(gw->graph), *this));

 	if (*static_cast<GraphEdge*>(this)==INVALID) {

 	  *static_cast<Edge*>(this)=

 	    Edge(typename Graph::EdgeIt(*(_gw.graph)), true);

 	  while (*static_cast<GraphEdge*>(this)!=INVALID && 

 		 !(*(gw->backward_filter))[*this]) 

 	    *(static_cast<GraphEdge*>(this))=

 	      ++(typename Graph::EdgeIt(*(gw->graph), *this));

 	}

       }

       EdgeIt(const SubBidirGraphWrapper<Graph, 

 	     ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 

 	Edge(e), gw(&_gw) { }

       EdgeIt& operator++() { 

 	if (!this->backward) {

 	  *(static_cast<GraphEdge*>(this))=

 	    ++(typename Graph::EdgeIt(*(gw->graph), *this));

 	  while (*static_cast<GraphEdge*>(this)!=INVALID && 

 		 !(*(gw->forward_filter))[*this]) 

 	    *(static_cast<GraphEdge*>(this))=

 	      ++(typename Graph::EdgeIt(*(gw->graph), *this));

 	  if (*static_cast<GraphEdge*>(this)==INVALID) {

 	    *static_cast<Edge*>(this)=

 	      Edge(typename Graph::EdgeIt(*(gw->graph)), true);

 	    while (*static_cast<GraphEdge*>(this)!=INVALID && 

 		   !(*(gw->backward_filter))[*this]) 

 	      *(static_cast<GraphEdge*>(this))=

 		++(typename Graph::EdgeIt(*(gw->graph), *this));

 	  }

 	} else {

 	  *(static_cast<GraphEdge*>(this))=

 	    ++(typename Graph::EdgeIt(*(gw->graph), *this));

 	  while (*static_cast<GraphEdge*>(this)!=INVALID && 

 		 !(*(gw->backward_filter))[*this]) 

 	    *(static_cast<GraphEdge*>(this))=

 	      ++(typename Graph::EdgeIt(*(gw->graph), *this));

 	}

 	return *this;

       }

     };

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

     }

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

     /// \c Graph::EdgeIt is defined.

     int edgeNum() const { 

       int i=0;

       for (EdgeIt e(*this); e!=INVALID; ++e) ++i;

       return i; 

     }

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

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

     template <typename T>

     /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two 

     /// Graph::EdgeMap one for the forward edges and 

     /// one for the backward edges.

     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, a); 

 	else 

 	  backward_map.set(e, a); 

       }

       T operator[](Edge e) const { 

 	if (!e.backward) 

 	  return forward_map[e]; 

 	else 

 	  return backward_map[e]; 

       }

       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. 

   ///

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

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

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

       Parent::setForwardFilterMap(cm);

       Parent::setBackwardFilterMap(cm);

     }

   public:

     BidirGraphWrapper(Graph& _graph) : Parent() { 

       Parent::setGraph(_graph);

       Parent::setForwardFilterMap(cm);

       Parent::setBackwardFilterMap(cm);

     }

     int edgeNum() const { 

       return 2*this->graph->edgeNum();

     }

   };

   /// \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 ResForwardFilter {

     //    const Graph* graph;

     const CapacityMap* capacity;

     const FlowMap* flow;

   public:

     ResForwardFilter(/*const Graph& _graph, */

 		     const CapacityMap& _capacity, const FlowMap& _flow) :

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

     ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }

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

     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }

     void setFlow(const FlowMap& _flow) { flow=&_flow; }

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

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

     }

   };

   template<typename Graph, typename Number,

 	   typename CapacityMap, typename FlowMap>

   class ResBackwardFilter {

     //const Graph* graph;

     const CapacityMap* capacity;

     const FlowMap* flow;

   public:

     ResBackwardFilter(/*const Graph& _graph,*/ 

 		      const CapacityMap& _capacity, const FlowMap& _flow) :

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

     ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }

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

     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }

     void setFlow(const FlowMap& _flow) { flow=&_flow; }

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

       return (Number(0) < Number((*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, 

     ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  

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

   public:

     typedef SubBidirGraphWrapper< 

       Graph, 

       ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  

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

   protected:

     const CapacityMap* capacity;

     FlowMap* flow;

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

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

     ResGraphWrapper() : Parent(), 

  			capacity(0), flow(0) { }

     void setCapacityMap(const CapacityMap& _capacity) {

       capacity=&_capacity;

       forward_filter.setCapacity(_capacity);

       backward_filter.setCapacity(_capacity);

     }

     void setFlowMap(FlowMap& _flow) {

       flow=&_flow;

       forward_filter.setFlow(_flow);

       backward_filter.setFlow(_flow);

     }

 //     /// \bug does graph reference needed in filtermaps??

 //     void setGraph(const Graph& _graph) { 

 //       Parent::setGraph(_graph);

 //       forward_filter.setGraph(_graph);

 //       backward_filter.setGraph(_graph);

 //     }

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

     }

     typedef typename Parent::Edge Edge;

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

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

     void augment(const 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);

     }

     /// \deprecated

     ///

     Number resCap(const 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]); 

     }

     /// \brief Residual capacity map.

     ///

     /// In generic residual graphs the residual capacity can be obtained as a map. Not tested.

     class ResCap {

     protected:

       const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;

     public:

       typedef Number ValueType;

       typedef Edge KeyType;

       ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _res_graph) : 

 	res_graph(&_res_graph) { }

       Number operator[](const Edge& e) const { 

 	if (res_graph->forward(e)) 

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

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

 	else 

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

 	  return (*(res_graph->flow))[e]; 

       }

       /// \bug not needed with dynamic maps, or does it?

       void update() { }

     };

   };

   /// For blocking flows.

   /// This graph wrapper is used for on-the-fly 

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

     typedef typename GraphWrapper<Graph>::Edge Edge;

     class OutEdgeIt : public Edge { 

       friend class GraphWrapper<Graph>;

       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

       const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;

     public:

       OutEdgeIt() { }

       //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }

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

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

 		const Node& n) : 

 	Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { }

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

 		const Edge& e) : 

 	Edge(e), gw(&_gw) { }

       OutEdgeIt& operator++() { 

 	*(static_cast<Edge*>(this))=

 	  ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

 	return *this; 

       }

     };

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

       Node n=tail(e);

       typename Graph::OutEdgeIt f(*Parent::graph, n);

       ++f;

       first_out_edges->set(n, f);

     }

   };

   ///@}

 } //namespace hugo

 #endif //HUGO_GRAPH_WRAPPER_H