source: lemon-0.x/lemon/graph_adaptor.h @ 1949:5db4ff8d69de

/* -*- C++ -*-
 * lemon/graph_adaptor.h - Part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#ifndef LEMON_GRAPH_ADAPTOR_H
#define LEMON_GRAPH_ADAPTOR_H

///\ingroup graph_adaptors
///\file
///\brief Several graph adaptors.
///
///This file contains several useful graph adaptor functions.
///
///\author Marton Makai

#include <lemon/invalid.h>
#include <lemon/maps.h>
#include <lemon/bits/erasable_graph_extender.h>
#include <lemon/bits/clearable_graph_extender.h>
#include <lemon/bits/extendable_graph_extender.h>
#include <lemon/bits/iterable_graph_extender.h>
#include <lemon/bits/alteration_notifier.h>
#include <lemon/bits/default_map.h>
#include <lemon/bits/graph_extender.h>
#include <iostream>

namespace lemon {

  //x\brief Base type for the Graph Adaptors
  //x\ingroup graph_adaptors
  //x    
  //xBase type for the Graph Adaptors
  //x    
  //x\warning Graph adaptors are in even
  //xmore experimental state than the other
  //xparts of the lib. Use them at you own risk.
  //x
  //xThis is the base type for most of LEMON graph adaptors. 
  //xThis class implements a trivial graph adaptor i.e. it only wraps the 
  //xfunctions and types of the graph. The purpose of this class is to 
  //xmake easier implementing graph adaptors. E.g. if an adaptor is 
  //xconsidered which differs from the wrapped graph only in some of its 
  //xfunctions or types, then it can be derived from GraphAdaptor,
  //xand only the 
  //xdifferences should be implemented.
  //x
  //xauthor Marton Makai 
  template<typename _Graph>
  class GraphAdaptorBase {
  public:
    typedef _Graph Graph;
    typedef Graph ParentGraph;

  protected:
    Graph* graph;
    GraphAdaptorBase() : graph(0) { }
    void setGraph(Graph& _graph) { graph=&_graph; }

  public:
    GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
 
    typedef typename Graph::Node Node;
    typedef typename Graph::Edge Edge;
   
    void first(Node& i) const { graph->first(i); }
    void first(Edge& i) const { graph->first(i); }
    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }

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

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

    typedef NodeNumTagIndicator<Graph> NodeNumTag;
    int nodeNum() const { return graph->nodeNum(); }
    
    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
    int edgeNum() const { return graph->edgeNum(); }

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
    Edge findEdge(const Node& source, const Node& target, 
                  const Edge& prev = INVALID) {
      return graph->findEdge(source, target, prev);
    }
  
    Node addNode() const { 
      return Node(graph->addNode()); 
    }

    Edge addEdge(const Node& source, const Node& target) const { 
      return Edge(graph->addEdge(source, target)); 
    }

    void erase(const Node& i) const { graph->erase(i); }
    void erase(const Edge& i) const { graph->erase(i); }
  
    void clear() const { graph->clear(); }
    
    int id(const Node& v) const { return graph->id(v); }
    int id(const Edge& e) const { return graph->id(e); }
    
    Edge oppositeNode(const Edge& e) const { 
      return Edge(graph->opposite(e)); 
    }

    template <typename _Value>
    class NodeMap : public _Graph::template NodeMap<_Value> {
    public:
      typedef typename _Graph::template NodeMap<_Value> Parent;
      explicit NodeMap(const GraphAdaptorBase<_Graph>& gw) 
        : Parent(*gw.graph) { }
      NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
        : Parent(*gw.graph, value) { }
    };

    template <typename _Value>
    class EdgeMap : public _Graph::template EdgeMap<_Value> {
    public:
      typedef typename _Graph::template EdgeMap<_Value> Parent;
      explicit EdgeMap(const GraphAdaptorBase<_Graph>& gw) 
        : Parent(*gw.graph) { }
      EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
        : Parent(*gw.graph, value) { }
    };

  };

  template <typename _Graph>
  class GraphAdaptor :
    public IterableGraphExtender<GraphAdaptorBase<_Graph> > { 
  public:
    typedef _Graph Graph;
    typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
  protected:
    GraphAdaptor() : Parent() { }

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

  template <typename _Graph>
  class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
  public:
    typedef _Graph Graph;
    typedef GraphAdaptorBase<_Graph> Parent;
  protected:
    RevGraphAdaptorBase() : Parent() { }
  public:
    typedef typename Parent::Node Node;
    typedef typename Parent::Edge Edge;

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

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

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

  ///\brief A graph adaptor which reverses the orientation of the edges.
  ///\ingroup graph_adaptors
  ///
  ///\warning Graph adaptors are in even more experimental 
  ///state than the other
  ///parts of the lib. Use them at you own risk.
  ///
  /// If \c g is defined as
  ///\code
  /// ListGraph g;
  ///\endcode
  /// then
  ///\code
  /// RevGraphAdaptor<ListGraph> gw(g);
  ///\endcode
  ///implements the graph obtained from \c g by 
  /// reversing the orientation of its edges.

  template<typename _Graph>
  class RevGraphAdaptor : 
    public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
  public:
    typedef _Graph Graph;
    typedef IterableGraphExtender<
      RevGraphAdaptorBase<_Graph> > Parent;
  protected:
    RevGraphAdaptor() { }
  public:
    explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
  };

  
  template <typename _Graph, typename NodeFilterMap, 
            typename EdgeFilterMap, bool checked = true>
  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
  public:
    typedef _Graph Graph;
    typedef GraphAdaptorBase<_Graph> Parent;
  protected:
    NodeFilterMap* node_filter_map;
    EdgeFilterMap* edge_filter_map;
    SubGraphAdaptorBase() : Parent(), 
                            node_filter_map(0), edge_filter_map(0) { }

    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
      node_filter_map=&_node_filter_map;
    }
    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
      edge_filter_map=&_edge_filter_map;
    }

  public:

    typedef typename Parent::Node Node;
    typedef typename Parent::Edge Edge;

    void first(Node& i) const { 
      Parent::first(i); 
      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
    }

    void first(Edge& i) const { 
      Parent::first(i); 
      while (i!=INVALID && (!(*edge_filter_map)[i] 
             || !(*node_filter_map)[Parent::source(i)]
             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
    }

    void firstIn(Edge& i, const Node& n) const { 
      Parent::firstIn(i, n); 
      while (i!=INVALID && (!(*edge_filter_map)[i] 
             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
    }

    void firstOut(Edge& i, const Node& n) const { 
      Parent::firstOut(i, n); 
      while (i!=INVALID && (!(*edge_filter_map)[i] 
             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
    }

    void next(Node& i) const { 
      Parent::next(i); 
      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
    }

    void next(Edge& i) const { 
      Parent::next(i); 
      while (i!=INVALID && (!(*edge_filter_map)[i] 
             || !(*node_filter_map)[Parent::source(i)]
             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
    }

    void nextIn(Edge& i) const { 
      Parent::nextIn(i); 
      while (i!=INVALID && (!(*edge_filter_map)[i] 
             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
    }

    void nextOut(Edge& i) const { 
      Parent::nextOut(i); 
      while (i!=INVALID && (!(*edge_filter_map)[i] 
             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
    }

    //x\e

    //x This function hides \c n in the graph, i.e. the iteration 
    //x jumps over it. This is done by simply setting the value of \c n  
    //x to be false in the corresponding node-map.
    void hide(const Node& n) const { node_filter_map->set(n, false); }

    //x\e

    //x This function hides \c e in the graph, i.e. the iteration 
    //x jumps over it. This is done by simply setting the value of \c e  
    //x to be false in the corresponding edge-map.
    void hide(const Edge& e) const { edge_filter_map->set(e, false); }

    //x\e

    //x The value of \c n is set to be true in the node-map which stores 
    //x hide information. If \c n was hidden previuosly, then it is shown 
    //x again
     void unHide(const Node& n) const { node_filter_map->set(n, true); }

    //x\e

    //x The value of \c e is set to be true in the edge-map which stores 
    //x hide information. If \c e was hidden previuosly, then it is shown 
    //x again
    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }

    //x Returns true if \c n is hidden.
    
    //x\e
    //x
    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }

    //x Returns true if \c n is hidden.
    
    //x\e
    //x
    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); 
    }

    //x\e

    //x This function hides \c n in the graph, i.e. the iteration 
    //x jumps over it. This is done by simply setting the value of \c n  
    //x to be false in the corresponding node-map.
    void hide(const Node& n) const { node_filter_map->set(n, false); }

    //x\e

    //x This function hides \c e in the graph, i.e. the iteration 
    //x jumps over it. This is done by simply setting the value of \c e  
    //x to be false in the corresponding edge-map.
    void hide(const Edge& e) const { edge_filter_map->set(e, false); }

    //x\e

    //x The value of \c n is set to be true in the node-map which stores 
    //x hide information. If \c n was hidden previuosly, then it is shown 
    //x again
     void unHide(const Node& n) const { node_filter_map->set(n, true); }

    //x\e

    //x The value of \c e is set to be true in the edge-map which stores 
    //x hide information. If \c e was hidden previuosly, then it is shown 
    //x again
    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }

    //x Returns true if \c n is hidden.
    
    //x\e
    //x
    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }

    //x Returns true if \c n is hidden.
    
    //x\e
    //x
    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }

    typedef False NodeNumTag;
    typedef False EdgeNumTag;
  };

  //x\brief A graph adaptor for hiding nodes and edges from a graph.
  //x\ingroup graph_adaptors
  //x
  //x\warning Graph adaptors are in even more experimental
  //xstate than the other
  //xparts of the lib. Use them at you own risk.
  //x
  //xSubGraphAdaptor shows the graph with filtered node-set and 
  //xedge-set. If the \c checked parameter is true then it filters the edgeset
  //xto do not get invalid edges without source or target.
  //xLet \f$G=(V, A)\f$ be a directed graph 
  //xand suppose that the graph instance \c g of type ListGraph implements 
  //x\f$G\f$. 
  //x/Let moreover \f$b_V\f$ and 
  //x\f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set. 
  //xSubGraphAdaptor<...>::NodeIt iterates 
  //xon the node-set \f$\{v\in V : b_V(v)=true\}\f$ and 
  //xSubGraphAdaptor<...>::EdgeIt iterates 
  //xon the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly, 
  //xSubGraphAdaptor<...>::OutEdgeIt and
  //xSubGraphAdaptor<...>::InEdgeIt iterates 
  //xonly on edges leaving and entering a specific node which have true value.
  //x
  //xIf the \c checked template parameter is false then we have to note that 
  //xthe node-iterator cares only the filter on the node-set, and the 
  //xedge-iterator cares only the filter on the edge-set.
  //xThis way the edge-map
  //xshould filter all edges which's source or target is filtered by the 
  //xnode-filter.
  //x\code
  //xtypedef ListGraph Graph;
  //xGraph g;
  //xtypedef Graph::Node Node;
  //xtypedef Graph::Edge Edge;
  //xNode u=g.addNode(); //node of id 0
  //xNode v=g.addNode(); //node of id 1
  //xNode e=g.addEdge(u, v); //edge of id 0
  //xNode f=g.addEdge(v, u); //edge of id 1
  //xGraph::NodeMap<bool> nm(g, true);
  //xnm.set(u, false);
  //xGraph::EdgeMap<bool> em(g, true);
  //xem.set(e, false);
  //xtypedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
  //xSubGW gw(g, nm, em);
  //xfor (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
  //xstd::cout << ":-)" << std::endl;
  //xfor (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
  //x\endcode
  //xThe output of the above code is the following.
  //x\code
  //x1
  //x:-)
  //x1
  //x\endcode
  //xNote that \c n is of type \c SubGW::NodeIt, but it can be converted to
  //x\c Graph::Node that is why \c g.id(n) can be applied.
  //x
  //xFor other examples see also the documentation of NodeSubGraphAdaptor and 
  //xEdgeSubGraphAdaptor.
  //x
  //x\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);
    }
  };



  //x\brief An adaptor for hiding nodes from a graph.
  //x\ingroup graph_adaptors
  //x
  //x\warning Graph adaptors are in even more experimental state
  //xthan the other
  //xparts of the lib. Use them at you own risk.
  //x
  //xAn adaptor for hiding nodes from a graph.
  //xThis adaptor specializes SubGraphAdaptor in the way that only
  //xthe node-set 
  //xcan be filtered. In usual case the checked parameter is true, we get the
  //xinduced subgraph. But if the checked parameter is false then we can only
  //xfilter only isolated nodes.
  //x\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);
    }
  };


  //x\brief An adaptor for hiding edges from a graph.
  //x
  //x\warning Graph adaptors are in even more experimental state
  //xthan the other parts of the lib. Use them at you own risk.
  //x
  //xAn adaptor for hiding edges from a graph.
  //xThis adaptor specializes SubGraphAdaptor in the way that
  //xonly the edge-set 
  //xcan be filtered. The usefulness of this adaptor is demonstrated in the 
  //xproblem of searching a maximum number of edge-disjoint shortest paths 
  //xbetween 
  //xtwo nodes \c s and \c t. Shortest here means being shortest w.r.t. 
  //xnon-negative edge-lengths. Note that 
  //xthe comprehension of the presented solution 
  //xneed's some elementary knowledge from combinatorial optimization. 
  //x
  //xIf a single shortest path is to be 
  //xsearched between \c s and \c t, then this can be done easily by 
  //xapplying the Dijkstra algorithm. What happens, if a maximum number of 
  //xedge-disjoint shortest paths is to be computed. It can be proved that an 
  //xedge can be in a shortest path if and only
  //xif it is tight with respect to 
  //xthe potential function computed by Dijkstra.
  //xMoreover, any path containing 
  //xonly such edges is a shortest one.
  //xThus we have to compute a maximum number 
  //xof edge-disjoint paths between \c s and \c t in
  //xthe graph which has edge-set 
  //xall the tight edges. The computation will be demonstrated
  //xon the following 
  //xgraph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim. 
  //xThe full source code is available in \ref sub_graph_adaptor_demo.cc. 
  //xIf you are interested in more demo programs, you can use 
  //x\ref dim_to_dot.cc to generate .dot files from dimacs files. 
  //xThe .dot file of the following figure was generated by  
  //xthe demo program \ref dim_to_dot.cc.
  //x
  //x\dot
  //xdigraph lemon_dot_example {
  //xnode [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
  //xn0 [ label="0 (s)" ];
  //xn1 [ label="1" ];
  //xn2 [ label="2" ];
  //xn3 [ label="3" ];
  //xn4 [ label="4" ];
  //xn5 [ label="5" ];
  //xn6 [ label="6 (t)" ];
  //xedge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
  //xn5 ->  n6 [ label="9, length:4" ];
  //xn4 ->  n6 [ label="8, length:2" ];
  //xn3 ->  n5 [ label="7, length:1" ];
  //xn2 ->  n5 [ label="6, length:3" ];
  //xn2 ->  n6 [ label="5, length:5" ];
  //xn2 ->  n4 [ label="4, length:2" ];
  //xn1 ->  n4 [ label="3, length:3" ];
  //xn0 ->  n3 [ label="2, length:1" ];
  //xn0 ->  n2 [ label="1, length:2" ];
  //xn0 ->  n1 [ label="0, length:3" ];
  //x}
  //x\enddot
  //x
  //x\code
  //xGraph g;
  //xNode s, t;
  //xLengthMap length(g);
  //x
  //xreadDimacs(std::cin, g, length, s, t);
  //x
  //xcout << "edges with lengths (of form id, source--length->target): " << endl;
  //xfor(EdgeIt e(g); e!=INVALID; ++e) 
  //x  cout << g.id(e) << ", " << g.id(g.source(e)) << "--" 
  //x       << length[e] << "->" << g.id(g.target(e)) << endl;
  //x
  //xcout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
  //x\endcode
  //xNext, the potential function is computed with Dijkstra.
  //x\code
  //xtypedef Dijkstra<Graph, LengthMap> Dijkstra;
  //xDijkstra dijkstra(g, length);
  //xdijkstra.run(s);
  //x\endcode
  //xNext, we consrtruct a map which filters the edge-set to the tight edges.
  //x\code
  //xtypedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> 
  //x  TightEdgeFilter;
  //xTightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
  //x
  //xtypedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
  //xSubGW gw(g, tight_edge_filter);
  //x\endcode
  //xThen, the maximum nimber of edge-disjoint \c s-\c t paths are computed 
  //xwith a max flow algorithm Preflow.
  //x\code
  //xConstMap<Edge, int> const_1_map(1);
  //xGraph::EdgeMap<int> flow(g, 0);
  //x
  //xPreflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 
  //x  preflow(gw, s, t, const_1_map, flow);
  //xpreflow.run();
  //x\endcode
  //xLast, the output is:
  //x\code  
  //xcout << "maximum number of edge-disjoint shortest path: " 
  //x     << preflow.flowValue() << endl;
  //xcout << "edges of the maximum number of edge-disjoint shortest s-t paths: " 
  //x     << endl;
  //xfor(EdgeIt e(g); e!=INVALID; ++e) 
  //x  if (flow[e])
  //x    cout << " " << g.id(g.source(e)) << "--"
  //x         << length[e] << "->" << g.id(g.target(e)) << endl;
  //x\endcode
  //xThe program has the following (expected :-)) output:
  //x\code
  //xedges with lengths (of form id, source--length->target):
  //x 9, 5--4->6
  //x 8, 4--2->6
  //x 7, 3--1->5
  //x 6, 2--3->5
  //x 5, 2--5->6
  //x 4, 2--2->4
  //x 3, 1--3->4
  //x 2, 0--1->3
  //x 1, 0--2->2
  //x 0, 0--3->1
  //xs: 0 t: 6
  //xmaximum number of edge-disjoint shortest path: 2
  //xedges of the maximum number of edge-disjoint shortest s-t paths:
  //x 9, 5--4->6
  //x 8, 4--2->6
  //x 7, 3--1->5
  //x 4, 2--2->4
  //x 2, 0--1->3
  //x 1, 0--2->2
  //x\endcode
  //x
  //x\author Marton Makai
  template<typename Graph, typename EdgeFilterMap>
  class EdgeSubGraphAdaptor : 
    public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 
                           EdgeFilterMap, false> {
  public:
    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 
                            EdgeFilterMap, false> Parent;
  protected:
    ConstMap<typename Graph::Node, bool> const_true_map;
  public:
    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) : 
      Parent(), const_true_map(true) { 
      Parent::setGraph(_graph);
      Parent::setNodeFilterMap(const_true_map);
      Parent::setEdgeFilterMap(_edge_filter_map);
    }
  };

  template <typename _Graph>
  class UGraphAdaptorBase : 
    public UGraphExtender<GraphAdaptorBase<_Graph> > {
  public:
    typedef _Graph Graph;
    typedef UGraphExtender<GraphAdaptorBase<_Graph> > Parent;
  protected:
    UGraphAdaptorBase() : Parent() { }
  public:
    typedef typename Parent::UEdge UEdge;
    typedef typename Parent::Edge Edge;
    
    template <typename T>
    class EdgeMap {
    protected:
      const UGraphAdaptorBase<_Graph>* g;
      template <typename TT> friend class EdgeMap;
      typename _Graph::template EdgeMap<T> forward_map, backward_map; 
    public:
      typedef T Value;
      typedef Edge Key;
      
      EdgeMap(const UGraphAdaptorBase<_Graph>& _g) : g(&_g), 
        forward_map(*(g->graph)), backward_map(*(g->graph)) { }

      EdgeMap(const UGraphAdaptorBase<_Graph>& _g, T a) : g(&_g), 
        forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
      
      void set(Edge e, T a) { 
        if (g->direction(e)) 
          forward_map.set(e, a); 
        else 
          backward_map.set(e, a); 
      }

      T operator[](Edge e) const { 
        if (g->direction(e)) 
          return forward_map[e]; 
        else 
          return backward_map[e]; 
      }
    };
        
    template <typename T>
    class UEdgeMap {
      template <typename TT> friend class UEdgeMap;
      typename _Graph::template EdgeMap<T> map; 
    public:
      typedef T Value;
      typedef UEdge Key;
      
      UEdgeMap(const UGraphAdaptorBase<_Graph>& g) : 
        map(*(g.graph)) { }

      UEdgeMap(const UGraphAdaptorBase<_Graph>& g, T a) : 
        map(*(g.graph), a) { }
      
      void set(UEdge e, T a) { 
        map.set(e, a); 
      }

      T operator[](UEdge e) const { 
        return map[e]; 
      }
    };
      
  };

  //x\brief An undirected graph is made from a directed graph by an adaptor
  //x\ingroup graph_adaptors
  //x
  //x Undocumented, untested!!!
  //x If somebody knows nice demo application, let's polulate it.
  //x 
  //x \author Marton Makai
  template<typename _Graph>
  class UGraphAdaptor : 
    public IterableUGraphExtender<
    UGraphAdaptorBase<_Graph> > {
  public:
    typedef _Graph Graph;
    typedef IterableUGraphExtender<
      UGraphAdaptorBase<_Graph> > Parent;
  protected:
    UGraphAdaptor() { }
  public:
    UGraphAdaptor(_Graph& _graph) { 
      setGraph(_graph);
    }
  };

  
  template <typename _Graph, 
            typename ForwardFilterMap, typename BackwardFilterMap>
  class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
  public:
    typedef _Graph Graph;
    typedef GraphAdaptorBase<_Graph> Parent;
  protected:
    ForwardFilterMap* forward_filter;
    BackwardFilterMap* backward_filter;
    SubBidirGraphAdaptorBase() : Parent(), 
                                 forward_filter(0), backward_filter(0) { }

    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
      forward_filter=&_forward_filter;
    }
    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
      backward_filter=&_backward_filter;
    }

  public:
//     SubGraphAdaptorBase(Graph& _graph, 
//                      NodeFilterMap& _node_filter_map, 
//                      EdgeFilterMap& _edge_filter_map) : 
//       Parent(&_graph), 
//       node_filter_map(&node_filter_map), 
//       edge_filter_map(&edge_filter_map) { }

    typedef typename Parent::Node Node;
    typedef typename _Graph::Edge GraphEdge;
    template <typename T> class EdgeMap;
    // SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from 
    // _Graph::Edge. It contains an extra bool flag which is true 
    // if and only if the 
    // edge is the backward version of the original edge.
    class Edge : public _Graph::Edge {
      friend class SubBidirGraphAdaptorBase<
        Graph, ForwardFilterMap, BackwardFilterMap>;
      template<typename T> friend class EdgeMap;
    protected:
      bool backward; //true, iff backward
    public:
      Edge() { }
      // \todo =false is needed, or causes problems?
      // If \c _backward is false, then we get an edge corresponding to the 
      // original one, otherwise its oppositely directed pair is obtained.
      Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) : 
        _Graph::Edge(e), backward(_backward) { }
      Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
      bool operator==(const Edge& v) const { 
        return (this->backward==v.backward && 
                static_cast<typename _Graph::Edge>(*this)==
                static_cast<typename _Graph::Edge>(v));
      } 
      bool operator!=(const Edge& v) const { 
        return (this->backward!=v.backward || 
                static_cast<typename _Graph::Edge>(*this)!=
                static_cast<typename _Graph::Edge>(v));
      }
    };

    void first(Node& i) const { 
      Parent::first(i); 
    }

    void first(Edge& i) const { 
      Parent::first(i); 
      i.backward=false;
      while (*static_cast<GraphEdge*>(&i)!=INVALID && 
             !(*forward_filter)[i]) Parent::next(i);
      if (*static_cast<GraphEdge*>(&i)==INVALID) {
        Parent::first(i); 
        i.backward=true;
        while (*static_cast<GraphEdge*>(&i)!=INVALID && 
               !(*backward_filter)[i]) Parent::next(i);
      }
    }

    void firstIn(Edge& i, const Node& n) const { 
      Parent::firstIn(i, n); 
      i.backward=false;
      while (*static_cast<GraphEdge*>(&i)!=INVALID && 
             !(*forward_filter)[i]) Parent::nextIn(i);
      if (*static_cast<GraphEdge*>(&i)==INVALID) {
        Parent::firstOut(i, n); 
        i.backward=true;
        while (*static_cast<GraphEdge*>(&i)!=INVALID && 
               !(*backward_filter)[i]) Parent::nextOut(i);
      }
    }

    void firstOut(Edge& i, const Node& n) const { 
      Parent::firstOut(i, n); 
      i.backward=false;
      while (*static_cast<GraphEdge*>(&i)!=INVALID && 
             !(*forward_filter)[i]) Parent::nextOut(i);
      if (*static_cast<GraphEdge*>(&i)==INVALID) {
        Parent::firstIn(i, n); 
        i.backward=true;
        while (*static_cast<GraphEdge*>(&i)!=INVALID && 
               !(*backward_filter)[i]) Parent::nextIn(i);
      }
    }

    void next(Node& i) const { 
      Parent::next(i); 
    }

    void next(Edge& i) const { 
      if (!(i.backward)) {
        Parent::next(i);
        while (*static_cast<GraphEdge*>(&i)!=INVALID && 
               !(*forward_filter)[i]) Parent::next(i);
        if (*static_cast<GraphEdge*>(&i)==INVALID) {
          Parent::first(i); 
          i.backward=true;
          while (*static_cast<GraphEdge*>(&i)!=INVALID && 
                 !(*backward_filter)[i]) Parent::next(i);
        }
      } else {
        Parent::next(i);
        while (*static_cast<GraphEdge*>(&i)!=INVALID && 
               !(*backward_filter)[i]) Parent::next(i);
      }
    }

    void nextIn(Edge& i) const { 
      if (!(i.backward)) {
        Node n=Parent::target(i);
        Parent::nextIn(i);
        while (*static_cast<GraphEdge*>(&i)!=INVALID && 
               !(*forward_filter)[i]) Parent::nextIn(i);
        if (*static_cast<GraphEdge*>(&i)==INVALID) {
          Parent::firstOut(i, n); 
          i.backward=true;
          while (*static_cast<GraphEdge*>(&i)!=INVALID && 
                 !(*backward_filter)[i]) Parent::nextOut(i);
        }
      } else {
        Parent::nextOut(i);
        while (*static_cast<GraphEdge*>(&i)!=INVALID && 
               !(*backward_filter)[i]) Parent::nextOut(i);
      }
    }

    void nextOut(Edge& i) const { 
      if (!(i.backward)) {
        Node n=Parent::source(i);
        Parent::nextOut(i);
        while (*static_cast<GraphEdge*>(&i)!=INVALID && 
               !(*forward_filter)[i]) Parent::nextOut(i);
        if (*static_cast<GraphEdge*>(&i)==INVALID) {
          Parent::firstIn(i, n); 
          i.backward=true;
          while (*static_cast<GraphEdge*>(&i)!=INVALID && 
                 !(*backward_filter)[i]) Parent::nextIn(i);
        }
      } else {
        Parent::nextIn(i);
        while (*static_cast<GraphEdge*>(&i)!=INVALID && 
               !(*backward_filter)[i]) Parent::nextIn(i);
      }
    }

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

    //x Gives back the opposite edge.

    //x\e
    //x
    Edge opposite(const Edge& e) const { 
      Edge f=e;
      f.backward=!f.backward;
      return f;
    }

    //x\e

    //x \warning This is a linear time operation and works only if 
    //x \c Graph::EdgeIt is defined.
    //x \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; }

    //x\e

    //x \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two 
    //x _Graph::EdgeMap one for the forward edges and 
    //x 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();
      }
    };

  };


  //x\brief An adaptor for composing a subgraph of a 
  //x bidirected graph made from a directed one. 
  //x\ingroup graph_adaptors
  //x
  //x An adaptor for composing a subgraph of a 
  //x bidirected graph made from a directed one. 
  //x
  //x\warning Graph adaptors are in even more experimental state
  //xthan the other
  //xparts of the lib. Use them at you own risk.
  //x
  //x Let \f$G=(V, A)\f$ be a directed graph and for each directed edge 
  //x \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
  //x reversing its orientation. We are given moreover two bool valued 
  //x maps on the edge-set, 
  //x \f$forward\_filter\f$, and \f$backward\_filter\f$. 
  //x SubBidirGraphAdaptor implements the graph structure with node-set 
  //x \f$V\f$ and edge-set 
  //x \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$. 
  //x The purpose of writing + instead of union is because parallel 
  //x edges can arise. (Similarly, antiparallel edges also can arise).
  //x In other words, a subgraph of the bidirected graph obtained, which 
  //x is given by orienting the edges of the original graph in both directions.
  //x As the oppositely directed edges are logically different, 
  //x the maps are able to attach different values for them. 
  //x
  //x An example for such a construction is \c RevGraphAdaptor where the 
  //x forward_filter is everywhere false and the backward_filter is 
  //x everywhere true. We note that for sake of efficiency, 
  //x \c RevGraphAdaptor is implemented in a different way. 
  //x But BidirGraphAdaptor is obtained from 
  //x SubBidirGraphAdaptor by considering everywhere true 
  //x valued maps both for forward_filter and backward_filter. 
  //x
  //x The most important application of SubBidirGraphAdaptor 
  //x is ResGraphAdaptor, which stands for the residual graph in directed 
  //x flow and circulation problems. 
  //x As adaptors usually, the SubBidirGraphAdaptor implements the 
  //x above mentioned graph structure without its physical storage, 
  //x 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);
    }
  };



  //x\brief An adaptor for composing bidirected graph from a directed one. 
  //x\ingroup graph_adaptors
  //x
  //x\warning Graph adaptors are in even more experimental state
  //xthan the other
  //xparts of the lib. Use them at you own risk.
  //x
  //x An adaptor for composing bidirected graph from a directed one. 
  //x A bidirected graph is composed over the directed one without physical 
  //x storage. As the oppositely directed edges are logically different ones 
  //x 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]));
    }
  };

  
  //x\brief An adaptor for composing the residual
  //xgraph for directed flow and circulation problems.
  //x\ingroup graph_adaptors
  //x
  //xAn adaptor for composing the residual graph for
  //xdirected flow and circulation problems. 
  //xLet \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a 
  //xnumber type. Let moreover 
  //x\f$f,c:A\to F\f$, be functions on the edge-set. 
  //xIn the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow 
  //xand \f$c\f$ for a capacity function.   
  //xSuppose that a graph instange \c g of type 
  //x\c ListGraph implements \f$G\f$ .
  //x\code
  //x  ListGraph g;
  //x\endcode
  //xThen RevGraphAdaptor implements the graph structure with node-set 
  //x\f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where 
  //x\f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and 
  //x\f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$, 
  //xi.e. the so called residual graph. 
  //xWhen we take the union \f$A_{forward}\cup A_{backward}\f$, 
  //xmultilicities are counted, i.e. if an edge is in both 
  //x\f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it 
  //xappears twice. 
  //xThe following code shows how 
  //xsuch an instance can be constructed.
  //x\code
  //xtypedef ListGraph Graph;
  //xGraph::EdgeMap<int> f(g);
  //xGraph::EdgeMap<int> c(g);
  //xResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
  //x\endcode
  //x\author Marton Makai
  //x
  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);
    }

    //x \brief Residual capacity map.
    //x
    //x In generic residual graphs the residual capacity can be obtained 
    //x 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);
    }    
  };


  //x\brief For blocking flows.
  //x\ingroup graph_adaptors
  //x
  //x\warning Graph adaptors are in even more
  //xexperimental state than the other
  //xparts of the lib. Use them at you own risk.
  //x
  //xThis graph adaptor is used for on-the-fly 
  //xDinits blocking flow computations.
  //xFor each node, an out-edge is stored which is used when the 
  //x\code
  //xOutEdgeIt& first(OutEdgeIt&, const Node&)
  //x\endcode
  //xis called. 
  //x
  //x\author Marton Makai
  //x
  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);
      }
    };

    //x \todo May we want VARIANT/union type
    class Edge : public Parent::Edge {
      friend class SplitGraphAdaptorBase;
      template <typename T> friend class EdgeMap;
    private:
      typedef typename Parent::Edge EdgeParent;
      typedef typename Parent::Node NodeParent;
      NodeParent bind;

      Edge(const EdgeParent& edge, const NodeParent& node)
        : EdgeParent(edge), bind(node) {}
    public:
      Edge() {}
      Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}

      bool operator==(const Edge& edge) const {
        return EdgeParent::operator==(edge) && bind == edge.bind;
      }
      
      bool operator!=(const Edge& edge) const {
        return !(*this == edge);
      }
      
      bool operator<(const Edge& edge) const {
        return EdgeParent::operator<(edge) || 
          (EdgeParent::operator==(edge) && bind < edge.bind);
      }
    };

    void first(Node& node) const {
      Parent::first(node);
      node.entry = true;
    } 

    void next(Node& node) const {
      if (node.entry) {
        node.entry = false;
      } else {
        node.entry = true;
        Parent::next(node);
      }
    }

    void first(Edge& edge) const {
      Parent::first(edge);
      if ((typename Parent::Edge&)edge == INVALID) {
        Parent::first(edge.bind);
      } else {
        edge.bind = INVALID;
      }
    }

    void next(Edge& edge) const {
      if ((typename Parent::Edge&)edge != INVALID) {
        Parent::next(edge);
        if ((typename Parent::Edge&)edge == INVALID) {
          Parent::first(edge.bind);
        }
      } else {
        Parent::next(edge.bind);
      }      
    }

    void firstIn(Edge& edge, const Node& node) const {
      if (node.entry) {
        Parent::firstIn(edge, node);
        edge.bind = INVALID;
      } else {
        (typename Parent::Edge&)edge = INVALID;
        edge.bind = node;
      }
    }

    void nextIn(Edge& edge) const {
      if ((typename Parent::Edge&)edge != INVALID) {
        Parent::nextIn(edge);
      } else {
        edge.bind = INVALID;
      }      
    }

    void firstOut(Edge& edge, const Node& node) const {
      if (!node.entry) {
        Parent::firstOut(edge, node);
        edge.bind = INVALID;
      } else {
        (typename Parent::Edge&)edge = INVALID;
        edge.bind = node;
      }
    }

    void nextOut(Edge& edge) const {
      if ((typename Parent::Edge&)edge != INVALID) {
        Parent::nextOut(edge);
      } else {
        edge.bind = INVALID;
      }
    }

    Node source(const Edge& edge) const {
      if ((typename Parent::Edge&)edge != INVALID) {
        return Node(Parent::source(edge), false);
      } else {
        return Node(edge.bind, true);
      }
    }

    Node target(const Edge& edge) const {
      if ((typename Parent::Edge&)edge != INVALID) {
        return Node(Parent::target(edge), true);
      } else {
        return Node(edge.bind, false);
      }
    }

    static bool entryNode(const Node& node) {
      return node.entry;
    }

    static bool exitNode(const Node& node) {
      return !node.entry;
    }

    static Node getEntry(const typename Parent::Node& node) {
      return Node(node, true);
    }

    static Node getExit(const typename Parent::Node& node) {
      return Node(node, false);
    }

    static bool originalEdge(const Edge& edge) {
      return (typename Parent::Edge&)edge != INVALID;
    }

    static bool bindingEdge(const Edge& edge) {
      return edge.bind != INVALID;
    }

    static Node getBindedNode(const Edge& edge) {
      return edge.bind;
    }

    int nodeNum() const {
      return Parent::nodeNum() * 2;
    }

    typedef CompileTimeAnd<typename Parent::NodeNumTag, 
                           typename Parent::EdgeNumTag> EdgeNumTag;
    
    int edgeNum() const {
      return Parent::edgeNum() + Parent::nodeNum();
    }

    Edge findEdge(const Node& source, const Node& target, 
                  const Edge& prev = INVALID) const {
      if (exitNode(source) && entryNode(target)) {
        return Parent::findEdge(source, target, prev);
      } else {
        if (prev == INVALID && entryNode(source) && exitNode(target) && 
            (typename Parent::Node&)source == (typename Parent::Node&)target) {
          return Edge(INVALID, source);
        } else {
          return INVALID;
        }
      }
    }
    
    template <typename T>
    class NodeMap : public MapBase<Node, T> {
      typedef typename Parent::template NodeMap<T> NodeImpl;
    public:
      NodeMap(const SplitGraphAdaptorBase& _graph) 
        : entry(_graph), exit(_graph) {}
      NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) 
        : entry(_graph, t), exit(_graph, t) {}
      
      void set(const Node& key, const T& val) {
        if (key.entry) { entry.set(key, val); }
        else {exit.set(key, val); }
      }
      
      typename MapTraits<NodeImpl>::ReturnValue 
      operator[](const Node& key) {
        if (key.entry) { return entry[key]; }
        else { return exit[key]; }
      }

      typename MapTraits<NodeImpl>::ConstReturnValue
      operator[](const Node& key) const {
        if (key.entry) { return entry[key]; }
        else { return exit[key]; }
      }

    private:
      NodeImpl entry, exit;
    };

    template <typename T>
    class EdgeMap : public MapBase<Edge, T> {
      typedef typename Parent::template NodeMap<T> NodeImpl;
      typedef typename Parent::template EdgeMap<T> EdgeImpl;
    public:
      EdgeMap(const SplitGraphAdaptorBase& _graph) 
        : bind(_graph), orig(_graph) {}
      EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) 
        : bind(_graph, t), orig(_graph, t) {}
      
      void set(const Edge& key, const T& val) {
        if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
        else {bind.set(key.bind, val); }
      }
      
      typename MapTraits<EdgeImpl>::ReturnValue
      operator[](const Edge& key) {
        if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
        else {return bind[key.bind]; }
      }

      typename MapTraits<EdgeImpl>::ConstReturnValue
      operator[](const Edge& key) const {
        if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
        else {return bind[key.bind]; }
      }

    private:
      typename Parent::template NodeMap<T> bind;
      typename Parent::template EdgeMap<T> orig;
    };

    template <typename EntryMap, typename ExitMap>
    class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
    public:
      typedef MapBase<Node, typename EntryMap::Value> Parent;

      typedef typename Parent::Key Key;
      typedef typename Parent::Value Value;

      CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap) 
        : entryMap(_entryMap), exitMap(_exitMap) {}

      Value& operator[](const Key& key) {
        if (key.entry) {
          return entryMap[key];
        } else {
          return exitMap[key];
        }
      }

      Value operator[](const Key& key) const {
        if (key.entry) {
          return entryMap[key];
        } else {
          return exitMap[key];
        }
      }

      void set(const Key& key, const Value& value) {
        if (key.entry) {
          entryMap.set(key, value);
        } else {
          exitMap.set(key, value);
        }
      }
      
    private:
      
      EntryMap& entryMap;
      ExitMap& exitMap;
      
    };

    template <typename EdgeMap, typename NodeMap>
    class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
    public:
      typedef MapBase<Edge, typename EdgeMap::Value> Parent;

      typedef typename Parent::Key Key;
      typedef typename Parent::Value Value;

      CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap) 
        : edgeMap(_edgeMap), nodeMap(_nodeMap) {}

      void set(const Edge& edge, const Value& val) {
        if (SplitGraphAdaptorBase::originalEdge(edge)) {
          edgeMap.set(edge, val);
        } else {
          nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
        }
      }

      Value operator[](const Key& edge) const {
        if (SplitGraphAdaptorBase::originalEdge(edge)) {
          return edgeMap[edge];
        } else {
          return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
        }
      }      

      Value& operator[](const Key& edge) {
        if (SplitGraphAdaptorBase::originalEdge(edge)) {
          return edgeMap[edge];
        } else {
          return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
        }
      }      
      
    private:
      EdgeMap& edgeMap;
      NodeMap& nodeMap;
    };

  };

  template <typename _Graph>
  class SplitGraphAdaptor 
    : public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > {
  public:
    typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent;

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


  };

} //namespace lemon

#endif //LEMON_GRAPH_ADAPTOR_H