/* -*- C++ -*-

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

  *

  * Copyright (C) 2005 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 {

   // Graph adaptors

   /*!

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

   };

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

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

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

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

   /// \code

   /// ListGraph g;

   /// \endcode

   /// For each directed edge 

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

   /// reversing its orientation. 

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

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

   /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be 

   /// reversing the orientation of its edges. The following code shows how 

   /// such an instance can be constructed.

   /// \code

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

   /// \endcode

   ///\author Marton Makai

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

     }

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

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

     }

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

     typedef False NodeNumTag;

     typedef False EdgeNumTag;

   };

   /*! \brief A graph adaptor for hiding nodes and 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.

   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.

   \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 UndirGraphAdaptorBase : 

     public UndirGraphExtender<GraphAdaptorBase<_Graph> > {

   public:

     typedef _Graph Graph;

     typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;

   protected:

     UndirGraphAdaptorBase() : Parent() { }

   public:

     typedef typename Parent::UndirEdge UndirEdge;

     typedef typename Parent::Edge Edge;

     template <typename T>

     class EdgeMap {

     protected:

       const UndirGraphAdaptorBase<_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 UndirGraphAdaptorBase<_Graph>& _g) : g(&_g), 

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

       EdgeMap(const UndirGraphAdaptorBase<_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 UndirEdgeMap {

       template <typename TT> friend class UndirEdgeMap;

       typename _Graph::template EdgeMap<T> map; 

     public:

       typedef T Value;

       typedef UndirEdge Key;

       UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) : 

 	map(*(g.graph)) { }

       UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) : 

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

       void set(UndirEdge e, T a) { 

 	map.set(e, a); 

       }

       T operator[](UndirEdge e) const { 

 	return map[e]; 

       }

     };

   };

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

   ///

   /// Undocumented, untested!!!

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

   /// 

   /// \author Marton Makai

   template<typename _Graph>

   class UndirGraphAdaptor : 

     public IterableUndirGraphExtender<

     UndirGraphAdaptorBase<_Graph> > {

   public:

     typedef _Graph Graph;

     typedef IterableUndirGraphExtender<

       UndirGraphAdaptorBase<_Graph> > Parent;

   protected:

     UndirGraphAdaptor() { }

   public:

     UndirGraphAdaptor(_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.

     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.

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

     template <typename T>

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

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

     /// one for the backward edges.

     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. 

   ///

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

   ///

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

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

     }    

   };

   /// For blocking flows.

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

     }

   };

   template <typename _Graph>

   class NewEdgeSetAdaptorBase {

   public:

     typedef _Graph Graph;

     typedef typename Graph::Node Node;

     typedef typename Graph::NodeIt NodeIt;

   protected:

     struct NodeT {

       int first_out, first_in;

       NodeT() : first_out(-1), first_in(-1) {}

     };

     class NodesImpl : protected Graph::template NodeMap<NodeT> {

       typedef typename Graph::template NodeMap<NodeT> Parent;

       typedef NewEdgeSetAdaptorBase<Graph> Adaptor;

       Adaptor& adaptor;

     public:

       NodesImpl(Adaptor& _adaptor, const Graph& _graph) 

 	: Parent(_graph), adaptor(_adaptor) {}

       virtual ~NodesImpl() {}

       virtual void build() {

 	Parent::build();

       }

       virtual void clear() {

 	adaptor._clear();

 	Parent::clear();

       }

       virtual void add(const Node& node) {

 	Parent::add(node);

 	adaptor._add(node);

       }

       virtual void erase(const Node& node) {

 	adaptor._erase(node);

 	Parent::erase(node);

       }

       NodeT& operator[](const Node& node) {

 	return Parent::operator[](node);

       }

       const NodeT& operator[](const Node& node) const {

 	return Parent::operator[](node);

       }

     };

     NodesImpl* nodes;

     struct EdgeT {

       Node source, target;

       int next_out, next_in;

       int prev_out, prev_in;

       EdgeT() : prev_out(-1), prev_in(-1) {}

     };

     std::vector<EdgeT> edges;

     int first_edge;

     int first_free_edge;

     virtual void _clear() = 0;

     virtual void _add(const Node& node) = 0;

     virtual void _erase(const Node& node) = 0;

     const Graph* graph;

     void initalize(const Graph& _graph, NodesImpl& _nodes) {

       graph = &_graph;

       nodes = &_nodes;

     }

   public:

     class Edge {

       friend class NewEdgeSetAdaptorBase<Graph>;

     protected:

       Edge(int _id) : id(_id) {}

       int id;

     public:

       Edge() {}

       Edge(Invalid) : id(-1) {}

       bool operator==(const Edge& edge) const { return id == edge.id; }

       bool operator!=(const Edge& edge) const { return id != edge.id; }

       bool operator<(const Edge& edge) const { return id < edge.id; }

     };

     NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {} 

     virtual ~NewEdgeSetAdaptorBase() {}

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

       int n;

       if (first_free_edge == -1) {

 	n = edges.size();

 	edges.push_back(EdgeT());

       } else {

 	n = first_free_edge;

 	first_free_edge = edges[first_free_edge].next_in;

       }

       edges[n].next_in = (*nodes)[target].first_in;

       (*nodes)[target].first_in = n;

       edges[n].next_out = (*nodes)[source].first_out;

       (*nodes)[source].first_out = n;

       edges[n].source = source;

       edges[n].target = target;

       return Edge(n);

     }

     void erase(const Edge& edge) {

       int n = edge.id;

       if (edges[n].prev_in != -1) {

 	edges[edges[n].prev_in].next_in = edges[n].next_in;

       } else {

 	(*nodes)[edges[n].target].first_in = edges[n].next_in;

       }

       if (edges[n].next_in != -1) {

 	edges[edges[n].next_in].prev_in = edges[n].prev_in;

       }

       if (edges[n].prev_out != -1) {

 	edges[edges[n].prev_out].next_out = edges[n].next_out;

       } else {

 	(*nodes)[edges[n].source].first_out = edges[n].next_out;

       }

       if (edges[n].next_out != -1) {

 	edges[edges[n].next_out].prev_out = edges[n].prev_out;

       }

     }

     void first(Node& node) const {

       graph->first(node);

     }

     void next(Node& node) const {

       graph->next(node);

     }

     void first(Edge& edge) const {

       Node node;

       for (first(node); node != INVALID && (*nodes)[node].first_in == -1; 

 	   next(node));

       edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;

     }

     void next(Edge& edge) const {

       if (edges[edge.id].next_in != -1) {

 	edge.id = edges[edge.id].next_in;

       } else {

 	Node node = edges[edge.id].target;

 	for (next(node); node != INVALID && (*nodes)[node].first_in == -1; 

 	     next(node));

 	edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;

       }      

     }

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

       edge.id = (*nodes)[node].first_out;    

     }

     void nextOut(Edge& edge) const {

       edge.id = edges[edge.id].next_out;        

     }

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

       edge.id = (*nodes)[node].first_in;          

     }

     void nextIn(Edge& edge) const {

       edge.id = edges[edge.id].next_in;    

     }

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

     int id(const Edge& edge) const { return edge.id; }

     Node nodeFromId(int id) const { return graph->fromId(id, Node()); }

     Edge edgeFromId(int id) const { return Edge(id); }

     int maxNodeId() const { return graph->maxId(Node()); };

     int maxEdgeId() const { return edges.size() - 1; }

     Node source(const Edge& edge) const { return edges[edge.id].source;}

     Node target(const Edge& edge) const { return edges[edge.id].target;}

   };

   /// \brief Graph adaptor using a node set of another graph and an

   /// own edge set.

   ///

   /// This structure can be used to establish another graph over a node set

   /// of an existing one. The node iterator will go through the nodes of the

   /// original graph.

   ///

   /// \param _Graph The type of the graph which shares its node set with 

   /// this class. Its interface must conform to the \ref concept::StaticGraph

   /// "StaticGraph" concept.

   ///

   /// In the edge extension and removing it conforms to the 

   /// \ref concept::ExtendableGraph "ExtendableGraph" concept.

   template <typename _Graph>

   class NewEdgeSetAdaptor :

     public ErasableGraphExtender<

     ClearableGraphExtender<

     ExtendableGraphExtender<

     MappableGraphExtender<

     IterableGraphExtender<

     AlterableGraphExtender<

     NewEdgeSetAdaptorBase<_Graph> > > > > > > {

   public:

     typedef ErasableGraphExtender<

       ClearableGraphExtender<

       ExtendableGraphExtender<

       MappableGraphExtender<

       IterableGraphExtender<

       AlterableGraphExtender<

       NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent;

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

   private:

     virtual void _clear() {

       Parent::edges.clear();

       Parent::first_edge = -1;

       Parent::first_free_edge = -1;

       Parent::getNotifier(Edge()).clear();

       Parent::getNotifier(Node()).clear();

     }

     virtual void _add(const Node& node) {

       Parent::getNotifier(Node()).add(node);

     }

     virtual void _erase(const Node& node) {

       Edge edge;

       Parent::firstOut(edge, node);

       while (edge != INVALID) {

 	Parent::erase(edge);

 	Parent::firstOut(edge, node);

       }

       Parent::firstIn(edge, node);

       while (edge != INVALID) {

 	Parent::erase(edge);

 	Parent::firstIn(edge, node);

       }

       Parent::getNotifier(Node()).erase(node);

     }

     typedef typename Parent::NodesImpl NodesImpl;

     NodesImpl nodes;

   public:

     /// \brief Constructor of the adaptor.

     /// 

     /// Constructor of the adaptor.

     NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {

       Parent::initalize(_graph, nodes);

     }

     void clear() {

       Parent::getNotifier(Edge()).clear();      

       Parent::edges.clear();

       Parent::first_edge = -1;

       Parent::first_free_edge = -1;

     }

   };

   /// \brief Graph adaptor using a node set of another graph and an

   /// own undir edge set.

   ///

   /// This structure can be used to establish another undirected graph over 

   /// a node set of an existing one. The node iterator will go through the 

   /// nodes of the original graph.

   ///

   /// \param _Graph The type of the graph which shares its node set with 

   /// this class. Its interface must conform to the \ref concept::StaticGraph

   /// "StaticGraph" concept.

   ///

   /// In the edge extension and removing it conforms to the 

   /// \ref concept::ExtendableGraph "ExtendableGraph" concept.

   template <typename _Graph>

   class NewUndirEdgeSetAdaptor :

     public ErasableUndirGraphExtender<

     ClearableUndirGraphExtender<

     ExtendableUndirGraphExtender<

     MappableUndirGraphExtender<

     IterableUndirGraphExtender<

     AlterableUndirGraphExtender<

     UndirGraphExtender<

     NewEdgeSetAdaptorBase<_Graph> > > > > > > > {

   public:

     typedef ErasableUndirGraphExtender<

       ClearableUndirGraphExtender<

       ExtendableUndirGraphExtender<

       MappableUndirGraphExtender<

       IterableUndirGraphExtender<

       AlterableUndirGraphExtender<

       UndirGraphExtender<

       NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     typedef typename Parent::UndirEdge UndirEdge;

   private:

     virtual void _clear() {

       Parent::edges.clear();

       Parent::first_edge = -1;

       Parent::first_free_edge = -1;

       Parent::getNotifier(Edge()).clear();

       Parent::getNotifier(Node()).clear();

     }

     virtual void _add(const Node& node) {

       Parent::getNotifier(Node()).add(node);

     }

     virtual void _erase(const Node& node) {

       Edge edge;

       Parent::firstOut(edge, node);

       while (edge != INVALID) {

 	Parent::erase(edge);

 	Parent::firstOut(edge, node);

       }

       Parent::firstIn(edge, node);

       while (edge != INVALID) {

 	Parent::erase(edge);

 	Parent::firstIn(edge, node);

       }

       Parent::getNotifier(Node()).erase(node);

     }

     typedef typename Parent::NodesImpl NodesImpl;

     NodesImpl nodes;

   public:

     /// \brief Constructor of the adaptor.

     /// 

     /// Constructor of the adaptor.

     NewUndirEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {

       Parent::initalize(_graph, nodes);

     }

     void clear() {

       Parent::getNotifier(Edge()).clear();      

       Parent::getNotifier(UndirEdge()).clear();      

       Parent::edges.clear();

       Parent::first_edge = -1;

       Parent::first_free_edge = -1;

     }

   };

   ///@}

 } //namespace lemon

 #endif //LEMON_GRAPH_ADAPTOR_H