source: lemon-0.x/lemon/graph_adaptor.h @ 1979:c2992fd74dad

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-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/graph_adaptor_extender.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); }
    
    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 GraphAdaptorExtender<GraphAdaptorBase<_Graph> > { 
  public:
    typedef _Graph Graph;
    typedef GraphAdaptorExtender<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 GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > {
  public:
    typedef _Graph Graph;
    typedef GraphAdaptorExtender<
      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 FindEdgeTag;
    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 FindEdgeTag;
    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 GraphAdaptorExtender<
    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
  public:
    typedef _Graph Graph;
    typedef GraphAdaptorExtender<
      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 UndirectGraphAdaptorBase : 
    public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
  public:
    typedef _Graph Graph;
    typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
  protected:
    UndirectGraphAdaptorBase() : Parent() { }
  public:
    typedef typename Parent::UEdge UEdge;
    typedef typename Parent::Edge Edge;
    
    template <typename T>
    class EdgeMap {
    protected:
      const UndirectGraphAdaptorBase<_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 UndirectGraphAdaptorBase<_Graph>& _g) : g(&_g), 
        forward_map(*(g->graph)), backward_map(*(g->graph)) { }

      EdgeMap(const UndirectGraphAdaptorBase<_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 UndirectGraphAdaptorBase<_Graph>& g) : 
        map(*(g.graph)) { }

      UEdgeMap(const UndirectGraphAdaptorBase<_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 UndirectGraphAdaptor : 
    public UGraphAdaptorExtender<
    UndirectGraphAdaptorBase<_Graph> > {
  public:
    typedef _Graph Graph;
    typedef UGraphAdaptorExtender<
      UndirectGraphAdaptorBase<_Graph> > Parent;
  protected:
    UndirectGraphAdaptor() { }
  public:
    UndirectGraphAdaptor(_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 GraphAdaptorExtender<
    SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
  public:
    typedef _Graph Graph;
    typedef GraphAdaptorExtender<
      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 GraphAdaptorExtender<
    ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
  public:
    typedef _Graph Graph;
    typedef GraphAdaptorExtender<
      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 GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
  public:
    typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;

    SplitGraphAdaptor(_Graph& graph) {
      Parent::setGraph(graph);
    }


  };

} //namespace lemon

#endif //LEMON_GRAPH_ADAPTOR_H