/* -*- C++ -*-

  * lemon/graph_adaptor.h - Part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #ifndef LEMON_GRAPH_ADAPTOR_H

 #define LEMON_GRAPH_ADAPTOR_H

 ///\ingroup graph_adaptors

 ///\file

 ///\brief Several graph adaptors.

 ///

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

 ///

 ///\author Marton Makai

 #include <lemon/invalid.h>

 #include <lemon/maps.h>

 #include <lemon/bits/erasable_graph_extender.h>

 #include <lemon/bits/clearable_graph_extender.h>

 #include <lemon/bits/extendable_graph_extender.h>

 #include <lemon/bits/iterable_graph_extender.h>

 #include <lemon/bits/alteration_notifier.h>

 #include <lemon/bits/default_map.h>

 #include <lemon/bits/graph_extender.h>

 #include <iostream>

 namespace lemon {

   ///\brief Base type for the Graph Adaptors

   ///\ingroup graph_adaptors

   ///

   ///Base type for the Graph Adaptors

   ///

   ///\warning Graph adaptors are in even

   ///more experimental state than the other

   ///parts of the lib. Use them at you own risk.

   ///

   ///This is the base type for most of LEMON graph adaptors. 

   ///This class implements a trivial graph adaptor i.e. it only wraps the 

   ///functions and types of the graph. The purpose of this class is to 

   ///make easier implementing graph adaptors. E.g. if an adaptor is 

   ///considered which differs from the wrapped graph only in some of its 

   ///functions or types, then it can be derived from GraphAdaptor,

   ///and only the 

   ///differences should be implemented.

   ///

   ///author Marton Makai 

   template<typename _Graph>

   class GraphAdaptorBase {

   public:

     typedef _Graph Graph;

     typedef Graph ParentGraph;

   protected:

     Graph* graph;

     GraphAdaptorBase() : graph(0) { }

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

   public:

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

     typedef typename Graph::Node Node;

     typedef typename Graph::Edge Edge;

     void first(Node& i) const { graph->first(i); }

     void first(Edge& i) const { graph->first(i); }

     void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }

     void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }

     void next(Node& i) const { graph->next(i); }

     void next(Edge& i) const { graph->next(i); }

     void nextIn(Edge& i) const { graph->nextIn(i); }

     void nextOut(Edge& i) const { graph->nextOut(i); }

     Node source(const Edge& e) const { return graph->source(e); }

     Node target(const Edge& e) const { return graph->target(e); }

     typedef NodeNumTagIndicator<Graph> NodeNumTag;

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

     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

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

     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

     Edge findEdge(const Node& source, const Node& target, 

 		  const Edge& prev = INVALID) {

       return graph->findEdge(source, target, prev);

     }

     Node addNode() const { 

       return Node(graph->addNode()); 

     }

     Edge addEdge(const Node& source, const Node& target) const { 

       return Edge(graph->addEdge(source, target)); 

     }

     void erase(const Node& i) const { graph->erase(i); }

     void erase(const Edge& i) const { graph->erase(i); }

     void clear() const { graph->clear(); }

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

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

     Edge oppositeNode(const Edge& e) const { 

       return Edge(graph->opposite(e)); 

     }

     template <typename _Value>

     class NodeMap : public _Graph::template NodeMap<_Value> {

     public:

       typedef typename _Graph::template NodeMap<_Value> Parent;

       explicit NodeMap(const GraphAdaptorBase<_Graph>& gw) 

 	: Parent(*gw.graph) { }

       NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)

 	: Parent(*gw.graph, value) { }

     };

     template <typename _Value>

     class EdgeMap : public _Graph::template EdgeMap<_Value> {

     public:

       typedef typename _Graph::template EdgeMap<_Value> Parent;

       explicit EdgeMap(const GraphAdaptorBase<_Graph>& gw) 

 	: Parent(*gw.graph) { }

       EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)

 	: Parent(*gw.graph, value) { }

     };

   };

   template <typename _Graph>

   class GraphAdaptor :

     public IterableGraphExtender<GraphAdaptorBase<_Graph> > { 

   public:

     typedef _Graph Graph;

     typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;

   protected:

     GraphAdaptor() : Parent() { }

   public:

     explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }

   };

   template <typename _Graph>

   class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

   public:

     typedef _Graph Graph;

     typedef GraphAdaptorBase<_Graph> Parent;

   protected:

     RevGraphAdaptorBase() : Parent() { }

   public:

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }

     void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }

     void nextIn(Edge& i) const { Parent::nextOut(i); }

     void nextOut(Edge& i) const { Parent::nextIn(i); }

     Node source(const Edge& e) const { return Parent::target(e); }

     Node target(const Edge& e) const { return Parent::source(e); }

   };

   ///\brief A graph adaptor which reverses the orientation of the edges.

   ///\ingroup graph_adaptors

   ///

   ///\warning Graph adaptors are in even more experimental 

   ///state than the other

   ///parts of the lib. Use them at you own risk.

   ///

   /// If \c g is defined as

   ///\code

   /// ListGraph g;

   ///\endcode

   /// then

   ///\code

   /// RevGraphAdaptor<ListGraph> gw(g);

   ///\endcode

   ///implements the graph obtained from \c g by 

   /// reversing the orientation of its edges.

   template<typename _Graph>

   class RevGraphAdaptor : 

     public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {

   public:

     typedef _Graph Graph;

     typedef IterableGraphExtender<

       RevGraphAdaptorBase<_Graph> > Parent;

   protected:

     RevGraphAdaptor() { }

   public:

     explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }

   };

   template <typename _Graph, typename NodeFilterMap, 

 	    typename EdgeFilterMap, bool checked = true>

   class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

   public:

     typedef _Graph Graph;

     typedef GraphAdaptorBase<_Graph> Parent;

   protected:

     NodeFilterMap* node_filter_map;

     EdgeFilterMap* edge_filter_map;

     SubGraphAdaptorBase() : Parent(), 

 			    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:

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     void first(Node& i) const { 

       Parent::first(i); 

       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 

     }

     void first(Edge& i) const { 

       Parent::first(i); 

       while (i!=INVALID && (!(*edge_filter_map)[i] 

 	     || !(*node_filter_map)[Parent::source(i)]

 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 

     }

     void firstIn(Edge& i, const Node& n) const { 

       Parent::firstIn(i, n); 

       while (i!=INVALID && (!(*edge_filter_map)[i] 

 	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 

     }

     void firstOut(Edge& i, const Node& n) const { 

       Parent::firstOut(i, n); 

       while (i!=INVALID && (!(*edge_filter_map)[i] 

 	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 

     }

     void next(Node& i) const { 

       Parent::next(i); 

       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 

     }

     void next(Edge& i) const { 

       Parent::next(i); 

       while (i!=INVALID && (!(*edge_filter_map)[i] 

 	     || !(*node_filter_map)[Parent::source(i)]

 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 

     }

     void nextIn(Edge& i) const { 

       Parent::nextIn(i); 

       while (i!=INVALID && (!(*edge_filter_map)[i] 

 	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 

     }

     void nextOut(Edge& i) const { 

       Parent::nextOut(i); 

       while (i!=INVALID && (!(*edge_filter_map)[i] 

 	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 

     }

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

     ///\e

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

     ///\e

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

     ///\e

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

     ///\e

     ///

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

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

     ///\e

     ///

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

     typedef False NodeNumTag;

     typedef False EdgeNumTag;

   };

   template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>

   class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false> 

     : public GraphAdaptorBase<_Graph> {

   public:

     typedef _Graph Graph;

     typedef GraphAdaptorBase<_Graph> Parent;

   protected:

     NodeFilterMap* node_filter_map;

     EdgeFilterMap* edge_filter_map;

     SubGraphAdaptorBase() : Parent(), 

 			    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:

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     void first(Node& i) const { 

       Parent::first(i); 

       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 

     }

     void first(Edge& i) const { 

       Parent::first(i); 

       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 

     }

     void firstIn(Edge& i, const Node& n) const { 

       Parent::firstIn(i, n); 

       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 

     }

     void firstOut(Edge& i, const Node& n) const { 

       Parent::firstOut(i, n); 

       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 

     }

     void next(Node& i) const { 

       Parent::next(i); 

       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 

     }

     void next(Edge& i) const { 

       Parent::next(i); 

       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 

     }

     void nextIn(Edge& i) const { 

       Parent::nextIn(i); 

       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 

     }

     void nextOut(Edge& i) const { 

       Parent::nextOut(i); 

       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 

     }

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

     ///\e

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

     ///\e

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

     ///\e

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

     ///\e

     ///

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

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

     ///\e

     ///

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

     typedef False NodeNumTag;

     typedef False EdgeNumTag;

   };

   /// \brief A graph adaptor for hiding nodes and edges from a graph.

   /// \ingroup graph_adaptors

   /// 

   /// \warning Graph adaptors are in even more experimental state than the

   /// other parts of the lib. Use them at you own risk.

   /// 

   /// SubGraphAdaptor shows the graph with filtered node-set and 

   /// edge-set. If the \c checked parameter is true then it filters the edgeset

   /// to do not get invalid edges without source or target.

   /// Let  \f$  G=(V, A)  \f$  be a directed graph

   /// and suppose that the graph instance \c g of type ListGraph

   /// implements  \f$  G  \f$ .

   /// Let moreover  \f$  b_V  \f$  and  \f$  b_A  \f$  be bool-valued functions resp.

   /// on the node-set and edge-set.

   /// SubGraphAdaptor<...>::NodeIt iterates 

   /// on the node-set  \f$ \{v\in V : b_V(v)=true\} \f$  and 

   /// SubGraphAdaptor<...>::EdgeIt iterates 

   /// on the edge-set  \f$ \{e\in A : b_A(e)=true\} \f$ . Similarly, 

   /// SubGraphAdaptor<...>::OutEdgeIt and

   /// SubGraphAdaptor<...>::InEdgeIt iterates 

   /// only on edges leaving and entering a specific node which have true value.

   /// 

   /// If the \c checked template parameter is false then we have to note that 

   /// the node-iterator cares only the filter on the node-set, and the 

   /// edge-iterator cares only the filter on the edge-set.

   /// This way the edge-map

   /// should filter all edges which's source or target is filtered by the 

   /// node-filter.

   /// \code

   /// typedef ListGraph Graph;

   /// Graph g;

   /// typedef Graph::Node Node;

   /// typedef Graph::Edge Edge;

   /// Node u=g.addNode(); //node of id 0

   /// Node v=g.addNode(); //node of id 1

   /// Node e=g.addEdge(u, v); //edge of id 0

   /// Node f=g.addEdge(v, u); //edge of id 1

   /// Graph::NodeMap<bool> nm(g, true);

   /// nm.set(u, false);

   /// Graph::EdgeMap<bool> em(g, true);

   /// em.set(e, false);

   /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;

   /// SubGW gw(g, nm, em);

   /// for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;

   /// std::cout << ":-)" << std::endl;

   /// for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;

   /// \endcode

   /// The output of the above code is the following.

   /// \code

   /// 1

   /// :-)

   /// 1

   /// \endcode

   /// Note that \c n is of type \c SubGW::NodeIt, but it can be converted to

   /// \c Graph::Node that is why \c g.id(n) can be applied.

   /// 

   /// For other examples see also the documentation of NodeSubGraphAdaptor and 

   /// EdgeSubGraphAdaptor.

   /// 

   /// \author Marton Makai

   template<typename _Graph, typename NodeFilterMap, 

 	   typename EdgeFilterMap, bool checked = true>

   class SubGraphAdaptor : 

     public IterableGraphExtender<

     SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {

   public:

     typedef _Graph Graph;

     typedef IterableGraphExtender<

       SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;

   protected:

     SubGraphAdaptor() { }

   public:

     SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map, 

 		    EdgeFilterMap& _edge_filter_map) { 

       setGraph(_graph);

       setNodeFilterMap(_node_filter_map);

       setEdgeFilterMap(_edge_filter_map);

     }

   };

   ///\brief An adaptor for hiding nodes from a graph.

   ///\ingroup graph_adaptors

   ///

   ///\warning Graph adaptors are in even more experimental state

   ///than the other

   ///parts of the lib. Use them at you own risk.

   ///

   ///An adaptor for hiding nodes from a graph.

   ///This adaptor specializes SubGraphAdaptor in the way that only

   ///the node-set 

   ///can be filtered. In usual case the checked parameter is true, we get the

   ///induced subgraph. But if the checked parameter is false then we can only

   ///filter only isolated nodes.

   ///\author Marton Makai

   template<typename Graph, typename NodeFilterMap, bool checked = true>

   class NodeSubGraphAdaptor : 

     public SubGraphAdaptor<Graph, NodeFilterMap, 

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

   public:

     typedef SubGraphAdaptor<Graph, NodeFilterMap, 

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

   protected:

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

   public:

     NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) : 

       Parent(), const_true_map(true) { 

       Parent::setGraph(_graph);

       Parent::setNodeFilterMap(_node_filter_map);

       Parent::setEdgeFilterMap(const_true_map);

     }

   };

   ///\brief An adaptor for hiding edges from a graph.

   ///

   ///\warning Graph adaptors are in even more experimental state

   ///than the other parts of the lib. Use them at you own risk.

   ///

   ///An adaptor for hiding edges from a graph.

   ///This adaptor specializes SubGraphAdaptor in the way that

   ///only the edge-set 

   ///can be filtered. The usefulness of this adaptor is demonstrated in the 

   ///problem of searching a maximum number of edge-disjoint shortest paths 

   ///between 

   ///two nodes \c s and \c t. Shortest here means being shortest w.r.t. 

   ///non-negative edge-lengths. Note that 

   ///the comprehension of the presented solution 

   ///need's some elementary knowledge from combinatorial optimization. 

   ///

   ///If a single shortest path is to be 

   ///searched between \c s and \c t, then this can be done easily by 

   ///applying the Dijkstra algorithm. What happens, if a maximum number of 

   ///edge-disjoint shortest paths is to be computed. It can be proved that an 

   ///edge can be in a shortest path if and only

   ///if it is tight with respect to 

   ///the potential function computed by Dijkstra.

   ///Moreover, any path containing 

   ///only such edges is a shortest one.

   ///Thus we have to compute a maximum number 

   ///of edge-disjoint paths between \c s and \c t in

   ///the graph which has edge-set 

   ///all the tight edges. The computation will be demonstrated

   ///on the following 

   ///graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim. 

   ///The full source code is available in \ref sub_graph_adaptor_demo.cc. 

   ///If you are interested in more demo programs, you can use 

   ///\ref dim_to_dot.cc to generate .dot files from dimacs files. 

   ///The .dot file of the following figure was generated by  

   ///the demo program \ref dim_to_dot.cc.

   ///

   ///\dot

   ///digraph lemon_dot_example {

   ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];

   ///n0 [ label="0 (s)" ];

   ///n1 [ label="1" ];

   ///n2 [ label="2" ];

   ///n3 [ label="3" ];

   ///n4 [ label="4" ];

   ///n5 [ label="5" ];

   ///n6 [ label="6 (t)" ];

   ///edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];

   ///n5 ->  n6 [ label="9, length:4" ];

   ///n4 ->  n6 [ label="8, length:2" ];

   ///n3 ->  n5 [ label="7, length:1" ];

   ///n2 ->  n5 [ label="6, length:3" ];

   ///n2 ->  n6 [ label="5, length:5" ];

   ///n2 ->  n4 [ label="4, length:2" ];

   ///n1 ->  n4 [ label="3, length:3" ];

   ///n0 ->  n3 [ label="2, length:1" ];

   ///n0 ->  n2 [ label="1, length:2" ];

   ///n0 ->  n1 [ label="0, length:3" ];

   ///}

   ///\enddot

   ///

   ///\code

   ///Graph g;

   ///Node s, t;

   ///LengthMap length(g);

   ///

   ///readDimacs(std::cin, g, length, s, t);

   ///

   ///cout << "edges with lengths (of form id, source--length->target): " << endl;

   ///for(EdgeIt e(g); e!=INVALID; ++e) 

   ///  cout << g.id(e) << ", " << g.id(g.source(e)) << "--" 

   ///       << length[e] << "->" << g.id(g.target(e)) << endl;

   ///

   ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;

   ///\endcode

   ///Next, the potential function is computed with Dijkstra.

   ///\code

   ///typedef Dijkstra<Graph, LengthMap> Dijkstra;

   ///Dijkstra dijkstra(g, length);

   ///dijkstra.run(s);

   ///\endcode

   ///Next, we consrtruct a map which filters the edge-set to the tight edges.

   ///\code

   ///typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> 

   ///  TightEdgeFilter;

   ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);

   ///

   ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;

   ///SubGW gw(g, tight_edge_filter);

   ///\endcode

   ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed 

   ///with a max flow algorithm Preflow.

   ///\code

   ///ConstMap<Edge, int> const_1_map(1);

   ///Graph::EdgeMap<int> flow(g, 0);

   ///

   ///Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 

   ///  preflow(gw, s, t, const_1_map, flow);

   ///preflow.run();

   ///\endcode

   ///Last, the output is:

   ///\code  

   ///cout << "maximum number of edge-disjoint shortest path: " 

   ///     << preflow.flowValue() << endl;

   ///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " 

   ///     << endl;

   ///for(EdgeIt e(g); e!=INVALID; ++e) 

   ///  if (flow[e])

   ///    cout << " " << g.id(g.source(e)) << "--"

   ///         << length[e] << "->" << g.id(g.target(e)) << endl;

   ///\endcode

   ///The program has the following (expected :-)) output:

   ///\code

   ///edges with lengths (of form id, source--length->target):

   /// 9, 5--4->6

   /// 8, 4--2->6

   /// 7, 3--1->5

   /// 6, 2--3->5

   /// 5, 2--5->6

   /// 4, 2--2->4

   /// 3, 1--3->4

   /// 2, 0--1->3

   /// 1, 0--2->2

   /// 0, 0--3->1

   ///s: 0 t: 6

   ///maximum number of edge-disjoint shortest path: 2

   ///edges of the maximum number of edge-disjoint shortest s-t paths:

   /// 9, 5--4->6

   /// 8, 4--2->6

   /// 7, 3--1->5

   /// 4, 2--2->4

   /// 2, 0--1->3

   /// 1, 0--2->2

   ///\endcode

   ///

   ///\author Marton Makai

   template<typename Graph, typename EdgeFilterMap>

   class EdgeSubGraphAdaptor : 

     public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 

 			   EdgeFilterMap, false> {

   public:

     typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 

 			    EdgeFilterMap, false> Parent;

   protected:

     ConstMap<typename Graph::Node, bool> const_true_map;

   public:

     EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) : 

       Parent(), const_true_map(true) { 

       Parent::setGraph(_graph);

       Parent::setNodeFilterMap(const_true_map);

       Parent::setEdgeFilterMap(_edge_filter_map);

     }

   };

   template <typename _Graph>

   class UGraphAdaptorBase : 

     public UGraphExtender<GraphAdaptorBase<_Graph> > {

   public:

     typedef _Graph Graph;

     typedef UGraphExtender<GraphAdaptorBase<_Graph> > Parent;

   protected:

     UGraphAdaptorBase() : Parent() { }

   public:

     typedef typename Parent::UEdge UEdge;

     typedef typename Parent::Edge Edge;

     template <typename T>

     class EdgeMap {

     protected:

       const UGraphAdaptorBase<_Graph>* g;

       template <typename TT> friend class EdgeMap;

       typename _Graph::template EdgeMap<T> forward_map, backward_map; 

     public:

       typedef T Value;

       typedef Edge Key;

       EdgeMap(const UGraphAdaptorBase<_Graph>& _g) : g(&_g), 

 	forward_map(*(g->graph)), backward_map(*(g->graph)) { }

       EdgeMap(const UGraphAdaptorBase<_Graph>& _g, T a) : g(&_g), 

 	forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }

       void set(Edge e, T a) { 

 	if (g->direction(e)) 

 	  forward_map.set(e, a); 

 	else 

 	  backward_map.set(e, a); 

       }

       T operator[](Edge e) const { 

 	if (g->direction(e)) 

 	  return forward_map[e]; 

 	else 

 	  return backward_map[e]; 

       }

     };

     template <typename T>

     class UEdgeMap {

       template <typename TT> friend class UEdgeMap;

       typename _Graph::template EdgeMap<T> map; 

     public:

       typedef T Value;

       typedef UEdge Key;

       UEdgeMap(const UGraphAdaptorBase<_Graph>& g) : 

 	map(*(g.graph)) { }

       UEdgeMap(const UGraphAdaptorBase<_Graph>& g, T a) : 

 	map(*(g.graph), a) { }

       void set(UEdge e, T a) { 

 	map.set(e, a); 

       }

       T operator[](UEdge e) const { 

 	return map[e]; 

       }

     };

   };

   ///\brief An undirected graph is made from a directed graph by an adaptor

   ///\ingroup graph_adaptors

   ///

   /// Undocumented, untested!!!

   /// If somebody knows nice demo application, let's polulate it.

   /// 

   /// \author Marton Makai

   template<typename _Graph>

   class UGraphAdaptor : 

     public IterableUGraphExtender<

     UGraphAdaptorBase<_Graph> > {

   public:

     typedef _Graph Graph;

     typedef IterableUGraphExtender<

       UGraphAdaptorBase<_Graph> > Parent;

   protected:

     UGraphAdaptor() { }

   public:

     UGraphAdaptor(_Graph& _graph) { 

       setGraph(_graph);

     }

   };

   template <typename _Graph, 

 	    typename ForwardFilterMap, typename BackwardFilterMap>

   class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

   public:

     typedef _Graph Graph;

     typedef GraphAdaptorBase<_Graph> Parent;

   protected:

     ForwardFilterMap* forward_filter;

     BackwardFilterMap* backward_filter;

     SubBidirGraphAdaptorBase() : Parent(), 

 				 forward_filter(0), backward_filter(0) { }

     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {

       forward_filter=&_forward_filter;

     }

     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {

       backward_filter=&_backward_filter;

     }

   public:

 //     SubGraphAdaptorBase(Graph& _graph, 

 // 			NodeFilterMap& _node_filter_map, 

 // 			EdgeFilterMap& _edge_filter_map) : 

 //       Parent(&_graph), 

 //       node_filter_map(&node_filter_map), 

 //       edge_filter_map(&edge_filter_map) { }

     typedef typename Parent::Node Node;

     typedef typename _Graph::Edge GraphEdge;

     template <typename T> class EdgeMap;

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

     // _Graph::Edge. It contains an extra bool flag which is true 

     // if and only if the 

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

     class Edge : public _Graph::Edge {

       friend class SubBidirGraphAdaptorBase<

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

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

       }

     };

     void first(Node& i) const { 

       Parent::first(i); 

     }

     void first(Edge& i) const { 

       Parent::first(i); 

       i.backward=false;

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

 	     !(*forward_filter)[i]) Parent::next(i);

       if (*static_cast<GraphEdge*>(&i)==INVALID) {

 	Parent::first(i); 

 	i.backward=true;

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

 	       !(*backward_filter)[i]) Parent::next(i);

       }

     }

     void firstIn(Edge& i, const Node& n) const { 

       Parent::firstIn(i, n); 

       i.backward=false;

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

 	     !(*forward_filter)[i]) Parent::nextIn(i);

       if (*static_cast<GraphEdge*>(&i)==INVALID) {

 	Parent::firstOut(i, n); 

 	i.backward=true;

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

 	       !(*backward_filter)[i]) Parent::nextOut(i);

       }

     }

     void firstOut(Edge& i, const Node& n) const { 

       Parent::firstOut(i, n); 

       i.backward=false;

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

 	     !(*forward_filter)[i]) Parent::nextOut(i);

       if (*static_cast<GraphEdge*>(&i)==INVALID) {

 	Parent::firstIn(i, n); 

 	i.backward=true;

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

 	       !(*backward_filter)[i]) Parent::nextIn(i);

       }

     }

     void next(Node& i) const { 

       Parent::next(i); 

     }

     void next(Edge& i) const { 

       if (!(i.backward)) {

 	Parent::next(i);

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

 	       !(*forward_filter)[i]) Parent::next(i);

 	if (*static_cast<GraphEdge*>(&i)==INVALID) {

 	  Parent::first(i); 

 	  i.backward=true;

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

 		 !(*backward_filter)[i]) Parent::next(i);

 	}

       } else {

 	Parent::next(i);

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

 	       !(*backward_filter)[i]) Parent::next(i);

       }

     }

     void nextIn(Edge& i) const { 

       if (!(i.backward)) {

 	Node n=Parent::target(i);

 	Parent::nextIn(i);

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

 	       !(*forward_filter)[i]) Parent::nextIn(i);

 	if (*static_cast<GraphEdge*>(&i)==INVALID) {

 	  Parent::firstOut(i, n); 

 	  i.backward=true;

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

 		 !(*backward_filter)[i]) Parent::nextOut(i);

 	}

       } else {

 	Parent::nextOut(i);

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

 	       !(*backward_filter)[i]) Parent::nextOut(i);

       }

     }

     void nextOut(Edge& i) const { 

       if (!(i.backward)) {

 	Node n=Parent::source(i);

 	Parent::nextOut(i);

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

 	       !(*forward_filter)[i]) Parent::nextOut(i);

 	if (*static_cast<GraphEdge*>(&i)==INVALID) {

 	  Parent::firstIn(i, n); 

 	  i.backward=true;

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

 		 !(*backward_filter)[i]) Parent::nextIn(i);

 	}

       } else {

 	Parent::nextIn(i);

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

 	       !(*backward_filter)[i]) Parent::nextIn(i);

       }

     }

     Node source(Edge e) const { 

       return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }

     Node target(Edge e) const { 

       return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }

     /// Gives back the opposite edge.

     ///\e

     ///

     Edge opposite(const Edge& e) const { 

       Edge f=e;

       f.backward=!f.backward;

       return f;

     }

     ///\e

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

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

     /// \todo hmm

     int edgeNum() const { 

       int i=0;

       Edge e;

       for (first(e); e!=INVALID; next(e)) ++i;

       return i; 

     }

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

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

     ///\e

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

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

     /// one for the backward edges.

     template <typename T>

     class EdgeMap {

       template <typename TT> friend class EdgeMap;

       typename _Graph::template EdgeMap<T> forward_map, backward_map; 

     public:

       typedef T Value;

       typedef Edge Key;

       EdgeMap(const SubBidirGraphAdaptorBase<_Graph, 

 	      ForwardFilterMap, BackwardFilterMap>& g) : 

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

       EdgeMap(const SubBidirGraphAdaptorBase<_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); 

       }

 //       typename _Graph::template EdgeMap<T>::ConstReference 

 //       operator[](Edge e) const { 

 // 	if (!e.backward) 

 // 	  return forward_map[e]; 

 // 	else 

 // 	  return backward_map[e]; 

 //       }

 //      typename _Graph::template EdgeMap<T>::Reference 

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

       }

     };

   };

   ///\brief An adaptor for composing a subgraph of a 

   /// bidirected graph made from a directed one. 

   ///\ingroup graph_adaptors

   ///

   /// An adaptor for composing a subgraph of a 

   /// bidirected graph made from a directed one. 

   ///

   ///\warning Graph adaptors are in even more experimental state

   ///than the other

   ///parts of the lib. Use them at you own risk.

   ///

   /// Let  \f$  G=(V, A)  \f$  be a directed graph and for each directed edge 

   ///  \f$  e\in A  \f$ , let  \f$  \bar e  \f$  denote the edge obtained by

   /// reversing its orientation. We are given moreover two bool valued 

   /// maps on the edge-set, 

   ///  \f$  forward\_filter  \f$ , and  \f$  backward\_filter  \f$ . 

   /// SubBidirGraphAdaptor implements the graph structure with node-set 

   ///  \f$  V  \f$  and edge-set 

   ///  \f$  \{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}  \f$ . 

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

   /// edges can arise. (Similarly, antiparallel edges also can arise).

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

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

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

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

   ///

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

   /// forward_filter is everywhere false and the backward_filter is 

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

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

   /// But BidirGraphAdaptor is obtained from 

   /// SubBidirGraphAdaptor by considering everywhere true 

   /// valued maps both for forward_filter and backward_filter. 

   ///

   /// The most important application of SubBidirGraphAdaptor 

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

   /// flow and circulation problems. 

   /// As adaptors usually, the SubBidirGraphAdaptor implements the 

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

   /// that is the whole stuff is stored in constant memory. 

   template<typename _Graph, 

 	   typename ForwardFilterMap, typename BackwardFilterMap>

   class SubBidirGraphAdaptor : 

     public IterableGraphExtender<

     SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {

   public:

     typedef _Graph Graph;

     typedef IterableGraphExtender<

       SubBidirGraphAdaptorBase<

       _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;

   protected:

     SubBidirGraphAdaptor() { }

   public:

     SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter, 

 			 BackwardFilterMap& _backward_filter) { 

       setGraph(_graph);

       setForwardFilterMap(_forward_filter);

       setBackwardFilterMap(_backward_filter);

     }

   };

   ///\brief An adaptor for composing bidirected graph from a directed one. 

   ///\ingroup graph_adaptors

   ///

   ///\warning Graph adaptors are in even more experimental state

   ///than the other

   ///parts of the lib. Use them at you own risk.

   ///

   /// An adaptor 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 BidirGraphAdaptor : 

     public SubBidirGraphAdaptor<

     Graph, 

     ConstMap<typename Graph::Edge, bool>, 

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

   public:

     typedef  SubBidirGraphAdaptor<

       Graph, 

       ConstMap<typename Graph::Edge, bool>, 

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

   protected:

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

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

       Parent::setForwardFilterMap(cm);

       Parent::setBackwardFilterMap(cm);

     }

   public:

     BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) { 

       Parent::setGraph(_graph);

       Parent::setForwardFilterMap(cm);

       Parent::setBackwardFilterMap(cm);

     }

     int edgeNum() const { 

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

     }

   };

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

     }

   };

   ///\brief An adaptor for composing the residual

   ///graph for directed flow and circulation problems.

   ///\ingroup graph_adaptors

   ///

   ///An adaptor for composing the residual graph for

   ///directed flow and circulation problems. 

   ///Let  \f$ G=(V, A) \f$  be a directed graph and let  \f$ F \f$  be a 

   ///number type. Let moreover 

   /// \f$ f,c:A\to F \f$ , be functions on the edge-set. 

   ///In the appications of ResGraphAdaptor,  \f$ f \f$  usually stands for a flow 

   ///and  \f$ c \f$  for a capacity function.   

   ///Suppose that a graph instange \c g of type 

   ///\c ListGraph implements  \f$ G \f$  .

   ///\code

   ///  ListGraph g;

   ///\endcode

   ///Then RevGraphAdaptor implements the graph structure with node-set 

   /// \f$ V \f$  and edge-set  \f$ A_{forward}\cup A_{backward} \f$ , where 

   /// \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$  and 

   /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$ , 

   ///i.e. the so called residual graph. 

   ///When we take the union  \f$ A_{forward}\cup A_{backward} \f$ , 

   ///multilicities are counted, i.e. if an edge is in both 

   /// \f$ A_{forward} \f$  and  \f$ A_{backward} \f$ , then in the adaptor it 

   ///appears twice. 

   ///The following code shows how 

   ///such an instance can be constructed.

   ///\code

   ///typedef ListGraph Graph;

   ///Graph::EdgeMap<int> f(g);

   ///Graph::EdgeMap<int> c(g);

   ///ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);

   ///\endcode

   ///\author Marton Makai

   ///

   template<typename Graph, typename Number, 

 	   typename CapacityMap, typename FlowMap>

   class ResGraphAdaptor : 

     public SubBidirGraphAdaptor< 

     Graph, 

     ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  

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

   public:

     typedef SubBidirGraphAdaptor< 

       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;

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

     }

   public:

     ResGraphAdaptor(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;

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

       if (Parent::forward(e))  

 	flow->set(e, (*flow)[e]+a);

       else  

 	flow->set(e, (*flow)[e]-a);

     }

     /// \brief Residual capacity map.

     ///

     /// In generic residual graphs the residual capacity can be obtained 

     /// as a map. 

     class ResCap {

     protected:

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

     public:

       typedef Number Value;

       typedef Edge Key;

       ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>& 

 	     _res_graph) : res_graph(&_res_graph) { }

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

 	if (res_graph->forward(e)) 

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

 	else 

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

       }

     };

     //    KEEP_MAPS(Parent, ResGraphAdaptor);

   };

   template <typename _Graph, typename FirstOutEdgesMap>

   class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

   public:

     typedef _Graph Graph;

     typedef GraphAdaptorBase<_Graph> Parent;

   protected:

     FirstOutEdgesMap* first_out_edges;

     ErasingFirstGraphAdaptorBase() : Parent(), 

 				     first_out_edges(0) { }

     void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {

       first_out_edges=&_first_out_edges;

     }

   public:

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     void firstOut(Edge& i, const Node& n) const { 

       i=(*first_out_edges)[n];

     }

     void erase(const Edge& e) const {

       Node n=source(e);

       Edge f=e;

       Parent::nextOut(f);

       first_out_edges->set(n, f);

     }    

   };

   ///\brief For blocking flows.

   ///\ingroup graph_adaptors

   ///

   ///\warning Graph adaptors are in even more

   ///experimental state than the other

   ///parts of the lib. Use them at you own risk.

   ///

   ///This graph adaptor 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 ErasingFirstGraphAdaptor : 

     public IterableGraphExtender<

     ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {

   public:

     typedef _Graph Graph;

     typedef IterableGraphExtender<

       ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;

     ErasingFirstGraphAdaptor(Graph& _graph, 

 			     FirstOutEdgesMap& _first_out_edges) { 

       setGraph(_graph);

       setFirstOutEdgesMap(_first_out_edges);

     } 

   };

   template <typename _Graph>

   class SplitGraphAdaptorBase 

     : public GraphAdaptorBase<_Graph> {

   public:

     typedef GraphAdaptorBase<_Graph> Parent;

     class Node;

     class Edge;

     template <typename T> class NodeMap;

     template <typename T> class EdgeMap;

     class Node : public Parent::Node {

       friend class SplitGraphAdaptorBase;

       template <typename T> friend class NodeMap;

       typedef typename Parent::Node NodeParent;

     private:

       bool entry;

       Node(typename Parent::Node _node, bool _entry)

 	: Parent::Node(_node), entry(_entry) {}

     public:

       Node() {}

       Node(Invalid) : NodeParent(INVALID), entry(true) {}

       bool operator==(const Node& node) const {

 	return NodeParent::operator==(node) && entry == node.entry;

       }

       bool operator!=(const Node& node) const {

 	return !(*this == node);

       }

       bool operator<(const Node& node) const {

 	return NodeParent::operator<(node) || 

 	  (NodeParent::operator==(node) && entry < node.entry);

       }

     };

     /// \todo May we want VARIANT/union type

     class Edge : public Parent::Edge {

       friend class SplitGraphAdaptorBase;

       template <typename T> friend class EdgeMap;

     private:

       typedef typename Parent::Edge EdgeParent;

       typedef typename Parent::Node NodeParent;

       NodeParent bind;

       Edge(const EdgeParent& edge, const NodeParent& node)

 	: EdgeParent(edge), bind(node) {}

     public:

       Edge() {}

       Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}

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

 	return EdgeParent::operator==(edge) && bind == edge.bind;

       }

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

 	return !(*this == edge);

       }

       bool operator<(const Edge& edge) const {

 	return EdgeParent::operator<(edge) || 

 	  (EdgeParent::operator==(edge) && bind < edge.bind);

       }

     };

     void first(Node& node) const {

       Parent::first(node);

       node.entry = true;

     } 

     void next(Node& node) const {

       if (node.entry) {

 	node.entry = false;

       } else {

 	node.entry = true;

 	Parent::next(node);

       }

     }

     void first(Edge& edge) const {

       Parent::first(edge);

       if ((typename Parent::Edge&)edge == INVALID) {

 	Parent::first(edge.bind);

       } else {

 	edge.bind = INVALID;

       }

     }

     void next(Edge& edge) const {

       if ((typename Parent::Edge&)edge != INVALID) {

 	Parent::next(edge);

 	if ((typename Parent::Edge&)edge == INVALID) {

 	  Parent::first(edge.bind);

 	}

       } else {

 	Parent::next(edge.bind);

       }      

     }

     void firstIn(Edge& edge, const Node& node) const {

       if (node.entry) {

 	Parent::firstIn(edge, node);

 	edge.bind = INVALID;

       } else {

 	(typename Parent::Edge&)edge = INVALID;

 	edge.bind = node;

       }

     }

     void nextIn(Edge& edge) const {

       if ((typename Parent::Edge&)edge != INVALID) {

 	Parent::nextIn(edge);

       } else {

 	edge.bind = INVALID;

       }      

     }

     void firstOut(Edge& edge, const Node& node) const {

       if (!node.entry) {

 	Parent::firstOut(edge, node);

 	edge.bind = INVALID;

       } else {

 	(typename Parent::Edge&)edge = INVALID;

 	edge.bind = node;

       }

     }

     void nextOut(Edge& edge) const {

       if ((typename Parent::Edge&)edge != INVALID) {

 	Parent::nextOut(edge);

       } else {

 	edge.bind = INVALID;

       }

     }

     Node source(const Edge& edge) const {

       if ((typename Parent::Edge&)edge != INVALID) {

 	return Node(Parent::source(edge), false);

       } else {

 	return Node(edge.bind, true);

       }

     }

     Node target(const Edge& edge) const {

       if ((typename Parent::Edge&)edge != INVALID) {

 	return Node(Parent::target(edge), true);

       } else {

 	return Node(edge.bind, false);

       }

     }

     static bool entryNode(const Node& node) {

       return node.entry;

     }

     static bool exitNode(const Node& node) {

       return !node.entry;

     }

     static Node getEntry(const typename Parent::Node& node) {

       return Node(node, true);

     }

     static Node getExit(const typename Parent::Node& node) {

       return Node(node, false);

     }

     static bool originalEdge(const Edge& edge) {

       return (typename Parent::Edge&)edge != INVALID;

     }

     static bool bindingEdge(const Edge& edge) {

       return edge.bind != INVALID;

     }

     static Node getBindedNode(const Edge& edge) {

       return edge.bind;

     }

     int nodeNum() const {

       return Parent::nodeNum() * 2;

     }

     typedef CompileTimeAnd<typename Parent::NodeNumTag, 

     			   typename Parent::EdgeNumTag> EdgeNumTag;

     int edgeNum() const {

       return Parent::edgeNum() + Parent::nodeNum();

     }

     Edge findEdge(const Node& source, const Node& target, 

 		  const Edge& prev = INVALID) const {

       if (exitNode(source) && entryNode(target)) {

 	return Parent::findEdge(source, target, prev);

       } else {

 	if (prev == INVALID && entryNode(source) && exitNode(target) && 

 	    (typename Parent::Node&)source == (typename Parent::Node&)target) {

 	  return Edge(INVALID, source);

 	} else {

 	  return INVALID;

 	}

       }

     }

     template <typename T>

     class NodeMap : public MapBase<Node, T> {

       typedef typename Parent::template NodeMap<T> NodeImpl;

     public:

       NodeMap(const SplitGraphAdaptorBase& _graph) 

 	: entry(_graph), exit(_graph) {}

       NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) 

 	: entry(_graph, t), exit(_graph, t) {}

       void set(const Node& key, const T& val) {

 	if (key.entry) { entry.set(key, val); }

 	else {exit.set(key, val); }

       }

       typename MapTraits<NodeImpl>::ReturnValue 

       operator[](const Node& key) {

 	if (key.entry) { return entry[key]; }

 	else { return exit[key]; }

       }

       typename MapTraits<NodeImpl>::ConstReturnValue

       operator[](const Node& key) const {

 	if (key.entry) { return entry[key]; }

 	else { return exit[key]; }

       }

     private:

       NodeImpl entry, exit;

     };

     template <typename T>

     class EdgeMap : public MapBase<Edge, T> {

       typedef typename Parent::template NodeMap<T> NodeImpl;

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

     public:

       EdgeMap(const SplitGraphAdaptorBase& _graph) 

 	: bind(_graph), orig(_graph) {}

       EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) 

 	: bind(_graph, t), orig(_graph, t) {}

       void set(const Edge& key, const T& val) {

 	if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }

 	else {bind.set(key.bind, val); }

       }

       typename MapTraits<EdgeImpl>::ReturnValue

       operator[](const Edge& key) {

 	if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }

 	else {return bind[key.bind]; }

       }

       typename MapTraits<EdgeImpl>::ConstReturnValue

       operator[](const Edge& key) const {

 	if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }

 	else {return bind[key.bind]; }

       }

     private:

       typename Parent::template NodeMap<T> bind;

       typename Parent::template EdgeMap<T> orig;

     };

     template <typename EntryMap, typename ExitMap>

     class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {

     public:

       typedef MapBase<Node, typename EntryMap::Value> Parent;

       typedef typename Parent::Key Key;

       typedef typename Parent::Value Value;

       CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap) 

 	: entryMap(_entryMap), exitMap(_exitMap) {}

       Value& operator[](const Key& key) {

 	if (key.entry) {

 	  return entryMap[key];

 	} else {

 	  return exitMap[key];

 	}

       }

       Value operator[](const Key& key) const {

 	if (key.entry) {

 	  return entryMap[key];

 	} else {

 	  return exitMap[key];

 	}

       }

       void set(const Key& key, const Value& value) {

 	if (key.entry) {

 	  entryMap.set(key, value);

 	} else {

 	  exitMap.set(key, value);

 	}

       }

     private:

       EntryMap& entryMap;

       ExitMap& exitMap;

     };

     template <typename EdgeMap, typename NodeMap>

     class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {

     public:

       typedef MapBase<Edge, typename EdgeMap::Value> Parent;

       typedef typename Parent::Key Key;

       typedef typename Parent::Value Value;

       CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap) 

 	: edgeMap(_edgeMap), nodeMap(_nodeMap) {}

       void set(const Edge& edge, const Value& val) {

 	if (SplitGraphAdaptorBase::originalEdge(edge)) {

 	  edgeMap.set(edge, val);

 	} else {

 	  nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);

 	}

       }

       Value operator[](const Key& edge) const {

 	if (SplitGraphAdaptorBase::originalEdge(edge)) {

 	  return edgeMap[edge];

 	} else {

 	  return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];

 	}

       }      

       Value& operator[](const Key& edge) {

 	if (SplitGraphAdaptorBase::originalEdge(edge)) {

 	  return edgeMap[edge];

 	} else {

 	  return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];

 	}

       }      

     private:

       EdgeMap& edgeMap;

       NodeMap& nodeMap;

     };

   };

   template <typename _Graph>

   class SplitGraphAdaptor 

     : public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > {

   public:

     typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent;

     SplitGraphAdaptor(_Graph& graph) {

       Parent::setGraph(graph);

     }

   };

 } //namespace lemon

 #endif //LEMON_GRAPH_ADAPTOR_H