diff -r d8475431bbbb -r 8e85e6bbefdf src/lemon/graph_adaptor.h
--- a/src/lemon/graph_adaptor.h	Sat May 21 21:04:57 2005 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,1218 +0,0 @@
-/* -*- C++ -*-
- * src/lemon/graph_adaptor.h - Part of LEMON, a generic C++ optimization library
- *
- * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#ifndef LEMON_GRAPH_ADAPTOR_H
-#define LEMON_GRAPH_ADAPTOR_H
-
-///\ingroup graph_adaptors
-///\file
-///\brief Several graph adaptors.
-///
-///This file contains several useful graph adaptor functions.
-///
-///\author Marton Makai
-
-#include <lemon/invalid.h>
-#include <lemon/maps.h>
-#include <lemon/bits/iterable_graph_extender.h>
-#include <lemon/bits/undir_graph_extender.h>
-#include <iostream>
-
-namespace lemon {
-
-  // Graph adaptors
-
-  /*!
-    \addtogroup graph_adaptors
-    @{
-   */
-
-  /*! 
-    Base type for the Graph Adaptors
-    
-    \warning Graph adaptors are in even more experimental state than the other
-    parts of the lib. Use them at you own risk.
-    
-    This is the base type for most of LEMON graph adaptors. 
-    This class implements a trivial graph adaptor i.e. it only wraps the 
-    functions and types of the graph. The purpose of this class is to 
-    make easier implementing graph adaptors. E.g. if an adaptor is 
-    considered which differs from the wrapped graph only in some of its 
-    functions or types, then it can be derived from GraphAdaptor, and only the 
-    differences should be implemented.
-  
-    \author Marton Makai 
-  */
-  template<typename _Graph>
-  class GraphAdaptorBase {
-  public:
-    typedef _Graph Graph;
-    /// \todo Is it needed?
-    typedef Graph BaseGraph;
-    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); }
-
-    int nodeNum() const { return graph->nodeNum(); }
-    int edgeNum() const { return graph->edgeNum(); }
-  
-    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(); }
-    
-    bool forward(const Edge& e) const { return graph->forward(e); }
-    bool backward(const Edge& e) const { return graph->backward(e); }
-
-    int id(const Node& v) const { return graph->id(v); }
-    int id(const Edge& e) const { return graph->id(e); }
-    
-    Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
-
-    template <typename _Value>
-    class NodeMap : public _Graph::template NodeMap<_Value> {
-    public:
-      typedef typename _Graph::template NodeMap<_Value> Parent;
-      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;
-      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:
-    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;
-
-    //    using Parent::first;
-    void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
-    void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
-
-    //    using Parent::next;
-    void nextIn(Edge& i) const { Parent::nextOut(i); }
-    void nextOut(Edge& i) const { Parent::nextIn(i); }
-
-    Node source(const Edge& e) const { return Parent::target(e); }
-    Node target(const Edge& e) const { return Parent::source(e); }
-  };
-    
-
-  /// A graph adaptor which reverses the orientation of the edges.
-
-  ///\warning Graph adaptors are in even more experimental state than the other
-  ///parts of the lib. Use them at you own risk.
-  ///
-  /// Let \f$G=(V, A)\f$ be a directed graph and 
-  /// suppose that a graph instange \c g of type 
-  /// \c ListGraph implements \f$G\f$.
-  /// \code
-  /// ListGraph g;
-  /// \endcode
-  /// For each directed edge 
-  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by 
-  /// reversing its orientation. 
-  /// Then RevGraphAdaptor implements the graph structure with node-set 
-  /// \f$V\f$ and edge-set 
-  /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be 
-  /// reversing the orientation of its edges. The following code shows how 
-  /// such an instance can be constructed.
-  /// \code
-  /// RevGraphAdaptor<ListGraph> gw(g);
-  /// \endcode
-  ///\author Marton Makai
-  template<typename _Graph>
-  class RevGraphAdaptor : 
-    public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
-  public:
-    typedef _Graph Graph;
-    typedef IterableGraphExtender<
-      RevGraphAdaptorBase<_Graph> > Parent;
-  protected:
-    RevGraphAdaptor() { }
-  public:
-    RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
-  };
-
-  
-  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
-  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:
-//     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 Parent::Edge Edge;
-
-    void first(Node& i) const { 
-      Parent::first(i); 
-      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
-    }
-    void first(Edge& i) const { 
-      Parent::first(i); 
-      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
-    }
-    void firstIn(Edge& i, const Node& n) const { 
-      Parent::firstIn(i, n); 
-      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
-    }
-    void firstOut(Edge& i, const Node& n) const { 
-      Parent::firstOut(i, n); 
-      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
-    }
-
-    void next(Node& i) const { 
-      Parent::next(i); 
-      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
-    }
-    void next(Edge& i) const { 
-      Parent::next(i); 
-      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
-    }
-    void nextIn(Edge& i) const { 
-      Parent::nextIn(i); 
-      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
-    }
-    void nextOut(Edge& i) const { 
-      Parent::nextOut(i); 
-      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
-    }
-
-    /// This function hides \c n in the graph, i.e. the iteration 
-    /// jumps over it. This is done by simply setting the value of \c n  
-    /// to be false in the corresponding node-map.
-    void hide(const Node& n) const { node_filter_map->set(n, false); }
-
-    /// This function hides \c e in the graph, i.e. the iteration 
-    /// jumps over it. This is done by simply setting the value of \c e  
-    /// to be false in the corresponding edge-map.
-    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
-
-    /// The value of \c n is set to be true in the node-map which stores 
-    /// hide information. If \c n was hidden previuosly, then it is shown 
-    /// again
-     void unHide(const Node& n) const { node_filter_map->set(n, true); }
-
-    /// The value of \c e is set to be true in the edge-map which stores 
-    /// hide information. If \c e was hidden previuosly, then it is shown 
-    /// again
-    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
-
-    /// Returns true if \c n is hidden.
-    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
-
-    /// Returns true if \c n is hidden.
-    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
-
-    /// \warning This is a linear time operation and works only if s
-    /// \c Graph::NodeIt is defined.
-    /// \todo assign tags.
-    int nodeNum() const { 
-      int i=0;
-      Node n;
-      for (first(n); n!=INVALID; next(n)) ++i;
-      return i; 
-    }
-
-    /// \warning This is a linear time operation and works only if 
-    /// \c Graph::EdgeIt is defined.
-    /// \todo assign tags.
-    int edgeNum() const { 
-      int i=0;
-      Edge e;
-      for (first(e); e!=INVALID; next(e)) ++i;
-      return i; 
-    }
-
-
-  };
-
-  /*! \brief A graph adaptor for hiding nodes and edges from a graph.
-    
-  \warning Graph adaptors are in even more experimental state than the other
-  parts of the lib. Use them at you own risk.
-  
-  SubGraphAdaptor shows the graph with filtered node-set and 
-  edge-set. 
-  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.
-
-  We have to note that this does not mean that an 
-  induced subgraph is obtained, the node-iterator cares only the filter 
-  on the node-set, and the edge-iterators care only the filter on the 
-  edge-set. 
-  \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>
-  class SubGraphAdaptor : 
-    public IterableGraphExtender<
-    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
-  public:
-    typedef _Graph Graph;
-    typedef IterableGraphExtender<
-      SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
-  protected:
-    SubGraphAdaptor() { }
-  public:
-    SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map, 
-		    EdgeFilterMap& _edge_filter_map) { 
-      setGraph(_graph);
-      setNodeFilterMap(_node_filter_map);
-      setEdgeFilterMap(_edge_filter_map);
-    }
-  };
-
-
-
-  /*! \brief An adaptor for hiding nodes from a graph.
-
-  \warning Graph adaptors are in even more experimental state than the other
-  parts of the lib. Use them at you own risk.
-  
-  An adaptor for hiding nodes from a graph.
-  This adaptor specializes SubGraphAdaptor in the way that only the node-set 
-  can be filtered. Note that this does not mean of considering induced 
-  subgraph, the edge-iterators consider the original edge-set.
-  \author Marton Makai
-  */
-  template<typename Graph, typename NodeFilterMap>
-  class NodeSubGraphAdaptor : 
-    public SubGraphAdaptor<Graph, NodeFilterMap, 
-			   ConstMap<typename Graph::Edge,bool> > {
-  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 \ref 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 of was generated 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> {
-  public:
-    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 
-			    EdgeFilterMap> Parent;
-  protected:
-    ConstMap<typename Graph::Node, bool> const_true_map;
-  public:
-    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) : 
-      Parent(), const_true_map(true) { 
-      Parent::setGraph(_graph);
-      Parent::setNodeFilterMap(const_true_map);
-      Parent::setEdgeFilterMap(_edge_filter_map);
-    }
-  };
-
-  template <typename _Graph>
-  class UndirGraphAdaptorBase : 
-    public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
-  public:
-    typedef _Graph Graph;
-    typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
-  protected:
-    UndirGraphAdaptorBase() : Parent() { }
-  public:
-    typedef typename Parent::UndirEdge UndirEdge;
-    typedef typename Parent::Edge Edge;
-    
-    /// \bug Why cant an edge say that it is forward or not??? 
-    /// By this, a pointer to the graph have to be stored
-    /// The implementation
-    template <typename T>
-    class EdgeMap {
-    protected:
-      const UndirGraphAdaptorBase<_Graph>* g;
-      template <typename TT> friend class EdgeMap;
-      typename _Graph::template EdgeMap<T> forward_map, backward_map; 
-    public:
-      typedef T Value;
-      typedef Edge Key;
-      
-      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g), 
-	forward_map(*(g->graph)), backward_map(*(g->graph)) { }
-
-      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g), 
-	forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
-      
-      void set(Edge e, T a) { 
-	if (g->forward(e)) 
-	  forward_map.set(e, a); 
-	else 
-	  backward_map.set(e, a); 
-      }
-
-      T operator[](Edge e) const { 
-	if (g->forward(e)) 
-	  return forward_map[e]; 
-	else 
-	  return backward_map[e]; 
-      }
-    };
-        
-    template <typename T>
-    class UndirEdgeMap {
-      template <typename TT> friend class UndirEdgeMap;
-      typename _Graph::template EdgeMap<T> map; 
-    public:
-      typedef T Value;
-      typedef UndirEdge Key;
-      
-      UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) : 
-	map(*(g.graph)) { }
-
-      UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) : 
-	map(*(g.graph), a) { }
-      
-      void set(UndirEdge e, T a) { 
-	map.set(e, a); 
-      }
-
-      T operator[](UndirEdge e) const { 
-	return map[e]; 
-      }
-    };
-      
-  };
-
-  /// \brief An undirected graph is made from a directed graph by an adaptor
-  ///
-  /// Undocumented, untested!!!
-  /// If somebody knows nice demo application, let's polulate it.
-  /// 
-  /// \author Marton Makai
-  template<typename _Graph>
-  class UndirGraphAdaptor : 
-    public IterableUndirGraphExtender<
-    UndirGraphAdaptorBase<_Graph> > {
-  public:
-    typedef _Graph Graph;
-    typedef IterableUndirGraphExtender<
-      UndirGraphAdaptorBase<_Graph> > Parent;
-  protected:
-    UndirGraphAdaptor() { }
-  public:
-    UndirGraphAdaptor(_Graph& _graph) { 
-      setGraph(_graph);
-    }
-  };
-
-  
-  template <typename _Graph, 
-	    typename ForwardFilterMap, typename BackwardFilterMap>
-  class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
-  public:
-    typedef _Graph Graph;
-    typedef GraphAdaptorBase<_Graph> Parent;
-  protected:
-    ForwardFilterMap* forward_filter;
-    BackwardFilterMap* backward_filter;
-    SubBidirGraphAdaptorBase() : Parent(), 
-				 forward_filter(0), backward_filter(0) { }
-
-    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
-      forward_filter=&_forward_filter;
-    }
-    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
-      backward_filter=&_backward_filter;
-    }
-
-  public:
-//     SubGraphAdaptorBase(Graph& _graph, 
-// 			NodeFilterMap& _node_filter_map, 
-// 			EdgeFilterMap& _edge_filter_map) : 
-//       Parent(&_graph), 
-//       node_filter_map(&node_filter_map), 
-//       edge_filter_map(&edge_filter_map) { }
-
-    typedef typename Parent::Node Node;
-    typedef typename _Graph::Edge GraphEdge;
-    template <typename T> class EdgeMap;
-    /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from 
-    /// _Graph::Edge. It contains an extra bool flag which is true 
-    /// if and only if the 
-    /// edge is the backward version of the original edge.
-    class Edge : public _Graph::Edge {
-      friend class SubBidirGraphAdaptorBase<
-	Graph, ForwardFilterMap, BackwardFilterMap>;
-      template<typename T> friend class EdgeMap;
-    protected:
-      bool backward; //true, iff backward
-    public:
-      Edge() { }
-      /// \todo =false is needed, or causes problems?
-      /// If \c _backward is false, then we get an edge corresponding to the 
-      /// original one, otherwise its oppositely directed pair is obtained.
-      Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) : 
-	_Graph::Edge(e), backward(_backward) { }
-      Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
-      bool operator==(const Edge& v) const { 
-	return (this->backward==v.backward && 
-		static_cast<typename _Graph::Edge>(*this)==
-		static_cast<typename _Graph::Edge>(v));
-      } 
-      bool operator!=(const Edge& v) const { 
-	return (this->backward!=v.backward || 
-		static_cast<typename _Graph::Edge>(*this)!=
-		static_cast<typename _Graph::Edge>(v));
-      }
-    };
-
-    void first(Node& i) const { 
-      Parent::first(i); 
-    }
-
-    void first(Edge& i) const { 
-      Parent::first(i); 
-      i.backward=false;
-      while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-	     !(*forward_filter)[i]) Parent::next(i);
-      if (*static_cast<GraphEdge*>(&i)==INVALID) {
-	Parent::first(i); 
-	i.backward=true;
-	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-	       !(*backward_filter)[i]) Parent::next(i);
-      }
-    }
-
-    void firstIn(Edge& i, const Node& n) const { 
-      Parent::firstIn(i, n); 
-      i.backward=false;
-      while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-	     !(*forward_filter)[i]) Parent::nextIn(i);
-      if (*static_cast<GraphEdge*>(&i)==INVALID) {
-	Parent::firstOut(i, n); 
-	i.backward=true;
-	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-	       !(*backward_filter)[i]) Parent::nextOut(i);
-      }
-    }
-
-    void firstOut(Edge& i, const Node& n) const { 
-      Parent::firstOut(i, n); 
-      i.backward=false;
-      while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-	     !(*forward_filter)[i]) Parent::nextOut(i);
-      if (*static_cast<GraphEdge*>(&i)==INVALID) {
-	Parent::firstIn(i, n); 
-	i.backward=true;
-	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-	       !(*backward_filter)[i]) Parent::nextIn(i);
-      }
-    }
-
-    void next(Node& i) const { 
-      Parent::next(i); 
-    }
-
-    void next(Edge& i) const { 
-      if (!(i.backward)) {
-	Parent::next(i);
-	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-	       !(*forward_filter)[i]) Parent::next(i);
-	if (*static_cast<GraphEdge*>(&i)==INVALID) {
-	  Parent::first(i); 
-	  i.backward=true;
-	  while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-		 !(*backward_filter)[i]) Parent::next(i);
-	}
-      } else {
-	Parent::next(i);
-	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-	       !(*backward_filter)[i]) Parent::next(i);
-      }
-    }
-
-    void nextIn(Edge& i) const { 
-      if (!(i.backward)) {
-	Node n=Parent::target(i);
-	Parent::nextIn(i);
-	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-	       !(*forward_filter)[i]) Parent::nextIn(i);
-	if (*static_cast<GraphEdge*>(&i)==INVALID) {
-	  Parent::firstOut(i, n); 
-	  i.backward=true;
-	  while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-		 !(*backward_filter)[i]) Parent::nextOut(i);
-	}
-      } else {
-	Parent::nextOut(i);
-	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-	       !(*backward_filter)[i]) Parent::nextOut(i);
-      }
-    }
-
-    void nextOut(Edge& i) const { 
-      if (!(i.backward)) {
-	Node n=Parent::source(i);
-	Parent::nextOut(i);
-	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-	       !(*forward_filter)[i]) Parent::nextOut(i);
-	if (*static_cast<GraphEdge*>(&i)==INVALID) {
-	  Parent::firstIn(i, n); 
-	  i.backward=true;
-	  while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-		 !(*backward_filter)[i]) Parent::nextIn(i);
-	}
-      } else {
-	Parent::nextIn(i);
-	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-	       !(*backward_filter)[i]) Parent::nextIn(i);
-      }
-    }
-
-    Node source(Edge e) const { 
-      return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
-    Node target(Edge e) const { 
-      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
-
-    /// Gives back the opposite edge.
-    Edge opposite(const Edge& e) const { 
-      Edge f=e;
-      f.backward=!f.backward;
-      return f;
-    }
-
-    /// \warning This is a linear time operation and works only if 
-    /// \c Graph::EdgeIt is defined.
-    /// \todo hmm
-    int edgeNum() const { 
-      int i=0;
-      Edge e;
-      for (first(e); e!=INVALID; next(e)) ++i;
-      return i; 
-    }
-
-    bool forward(const Edge& e) const { return !e.backward; }
-    bool backward(const Edge& e) const { return e.backward; }
-
-    template <typename T>
-    /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two 
-    /// _Graph::EdgeMap one for the forward edges and 
-    /// one for the backward edges.
-    class EdgeMap {
-      template <typename TT> friend class EdgeMap;
-      typename _Graph::template EdgeMap<T> forward_map, backward_map; 
-    public:
-      typedef T Value;
-      typedef Edge Key;
-
-      EdgeMap(const SubBidirGraphAdaptorBase<_Graph, 
-	      ForwardFilterMap, BackwardFilterMap>& g) : 
-	forward_map(*(g.graph)), backward_map(*(g.graph)) { }
-
-      EdgeMap(const SubBidirGraphAdaptorBase<_Graph, 
-	      ForwardFilterMap, BackwardFilterMap>& g, T a) : 
-	forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
-      
-      void set(Edge e, T a) { 
-	if (!e.backward) 
-	  forward_map.set(e, a); 
-	else 
-	  backward_map.set(e, a); 
-      }
-
-//       typename _Graph::template EdgeMap<T>::ConstReference 
-//       operator[](Edge e) const { 
-// 	if (!e.backward) 
-// 	  return forward_map[e]; 
-// 	else 
-// 	  return backward_map[e]; 
-//       }
-
-//      typename _Graph::template EdgeMap<T>::Reference 
-      T operator[](Edge e) const { 
-	if (!e.backward) 
-	  return forward_map[e]; 
-	else 
-	  return backward_map[e]; 
-      }
-
-      void update() { 
-	forward_map.update(); 
-	backward_map.update();
-      }
-    };
-
-  };
-
-
-  ///\brief An adaptor for composing a subgraph of a 
-  /// bidirected graph made from a directed one. 
-  ///
-  /// An adaptor for composing a subgraph of a 
-  /// bidirected graph made from a directed one. 
-  ///
-  ///\warning Graph adaptors are in even more experimental state than the other
-  ///parts of the lib. Use them at you own risk.
-  ///
-  /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge 
-  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
-  /// reversing its orientation. We are given moreover two bool valued 
-  /// maps on the edge-set, 
-  /// \f$forward\_filter\f$, and \f$backward\_filter\f$. 
-  /// SubBidirGraphAdaptor implements the graph structure with node-set 
-  /// \f$V\f$ and edge-set 
-  /// \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$. 
-  /// The purpose of writing + instead of union is because parallel 
-  /// edges can arise. (Similarly, antiparallel edges also can arise).
-  /// In other words, a subgraph of the bidirected graph obtained, which 
-  /// is given by orienting the edges of the original graph in both directions.
-  /// As the oppositely directed edges are logically different, 
-  /// the maps are able to attach different values for them. 
-  ///
-  /// An example for such a construction is \c RevGraphAdaptor where the 
-  /// forward_filter is everywhere false and the backward_filter is 
-  /// everywhere true. We note that for sake of efficiency, 
-  /// \c RevGraphAdaptor is implemented in a different way. 
-  /// But BidirGraphAdaptor is obtained from 
-  /// SubBidirGraphAdaptor by considering everywhere true 
-  /// valued maps both for forward_filter and backward_filter. 
-  ///
-  /// The most important application of SubBidirGraphAdaptor 
-  /// is ResGraphAdaptor, which stands for the residual graph in directed 
-  /// flow and circulation problems. 
-  /// As adaptors usually, the SubBidirGraphAdaptor implements the 
-  /// above mentioned graph structure without its physical storage, 
-  /// that is the whole stuff is stored in constant memory. 
-  template<typename _Graph, 
-	   typename ForwardFilterMap, typename BackwardFilterMap>
-  class SubBidirGraphAdaptor : 
-    public IterableGraphExtender<
-    SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
-  public:
-    typedef _Graph Graph;
-    typedef IterableGraphExtender<
-      SubBidirGraphAdaptorBase<
-      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
-  protected:
-    SubBidirGraphAdaptor() { }
-  public:
-    SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter, 
-			 BackwardFilterMap& _backward_filter) { 
-      setGraph(_graph);
-      setForwardFilterMap(_forward_filter);
-      setBackwardFilterMap(_backward_filter);
-    }
-  };
-
-
-
-  ///\brief An adaptor for composing bidirected graph from a directed one. 
-  ///
-  ///\warning Graph adaptors are in even more experimental state than the other
-  ///parts of the lib. Use them at you own risk.
-  ///
-  /// An adaptor for composing bidirected graph from a directed one. 
-  /// A bidirected graph is composed over the directed one without physical 
-  /// storage. As the oppositely directed edges are logically different ones 
-  /// the maps are able to attach different values for them.
-  template<typename Graph>
-  class BidirGraphAdaptor : 
-    public SubBidirGraphAdaptor<
-    Graph, 
-    ConstMap<typename Graph::Edge, bool>, 
-    ConstMap<typename Graph::Edge, bool> > {
-  public:
-    typedef  SubBidirGraphAdaptor<
-      Graph, 
-      ConstMap<typename Graph::Edge, bool>, 
-      ConstMap<typename Graph::Edge, bool> > Parent; 
-  protected:
-    ConstMap<typename Graph::Edge, bool> cm;
-
-    BidirGraphAdaptor() : Parent(), cm(true) { 
-      Parent::setForwardFilterMap(cm);
-      Parent::setBackwardFilterMap(cm);
-    }
-  public:
-    BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) { 
-      Parent::setGraph(_graph);
-      Parent::setForwardFilterMap(cm);
-      Parent::setBackwardFilterMap(cm);
-    }
-
-    int edgeNum() const { 
-      return 2*this->graph->edgeNum();
-    }
-    //    KEEP_MAPS(Parent, BidirGraphAdaptor);
-  };
-
-
-  template<typename Graph, typename Number,
-	   typename CapacityMap, typename FlowMap>
-  class ResForwardFilter {
-    //    const Graph* graph;
-    const CapacityMap* capacity;
-    const FlowMap* flow;
-  public:
-    ResForwardFilter(/*const Graph& _graph, */
-		     const CapacityMap& _capacity, const FlowMap& _flow) :
-      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
-    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
-    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
-    void setFlow(const FlowMap& _flow) { flow=&_flow; }
-    bool operator[](const typename Graph::Edge& e) const {
-      return (Number((*flow)[e]) < Number((*capacity)[e]));
-    }
-  };
-
-  template<typename Graph, typename Number,
-	   typename CapacityMap, typename FlowMap>
-  class ResBackwardFilter {
-    const CapacityMap* capacity;
-    const FlowMap* flow;
-  public:
-    ResBackwardFilter(/*const Graph& _graph,*/ 
-		      const CapacityMap& _capacity, const FlowMap& _flow) :
-      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
-    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
-    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
-    void setFlow(const FlowMap& _flow) { flow=&_flow; }
-    bool operator[](const typename Graph::Edge& e) const {
-      return (Number(0) < Number((*flow)[e]));
-    }
-  };
-
-  
-  /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
-
-  An adaptor for composing the residual graph for directed flow and circulation problems. 
-  Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a 
-  number type. Let moreover 
-  \f$f,c:A\to F\f$, be functions on the edge-set. 
-  In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow 
-  and \f$c\f$ for a capacity function.   
-  Suppose that a graph instange \c g of type 
-  \c ListGraph implements \f$G\f$.
-  \code
-  ListGraph g;
-  \endcode
-  Then RevGraphAdaptor implements the graph structure with node-set 
-  \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where 
-  \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and 
-  \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$, 
-  i.e. the so called residual graph. 
-  When we take the union \f$A_{forward}\cup A_{backward}\f$, 
-  multilicities are counted, i.e. if an edge is in both 
-  \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it 
-  appears twice. 
-  The following code shows how 
-  such an instance can be constructed.
-  \code
-  typedef ListGraph Graph;
-  Graph::EdgeMap<int> f(g);
-  Graph::EdgeMap<int> c(g);
-  ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
-  \endcode
-  \author Marton Makai
-  */
-  template<typename Graph, typename Number, 
-	   typename CapacityMap, typename FlowMap>
-  class ResGraphAdaptor : 
-    public SubBidirGraphAdaptor< 
-    Graph, 
-    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
-    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
-  public:
-    typedef SubBidirGraphAdaptor< 
-      Graph, 
-      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
-      ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
-  protected:
-    const CapacityMap* capacity;
-    FlowMap* flow;
-    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
-    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
-    ResGraphAdaptor() : Parent(), 
- 			capacity(0), flow(0) { }
-    void setCapacityMap(const CapacityMap& _capacity) {
-      capacity=&_capacity;
-      forward_filter.setCapacity(_capacity);
-      backward_filter.setCapacity(_capacity);
-    }
-    void setFlowMap(FlowMap& _flow) {
-      flow=&_flow;
-      forward_filter.setFlow(_flow);
-      backward_filter.setFlow(_flow);
-    }
-  public:
-    ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity, 
-		       FlowMap& _flow) : 
-      Parent(), capacity(&_capacity), flow(&_flow), 
-      forward_filter(/*_graph,*/ _capacity, _flow), 
-      backward_filter(/*_graph,*/ _capacity, _flow) {
-      Parent::setGraph(_graph);
-      Parent::setForwardFilterMap(forward_filter);
-      Parent::setBackwardFilterMap(backward_filter);
-    }
-
-    typedef typename Parent::Edge Edge;
-
-    void augment(const Edge& e, Number a) const {
-      if (Parent::forward(e))  
-	flow->set(e, (*flow)[e]+a);
-      else  
-	flow->set(e, (*flow)[e]-a);
-    }
-
-    /// \brief Residual capacity map.
-    ///
-    /// In generic residual graphs the residual capacity can be obtained 
-    /// as a map. 
-    class ResCap {
-    protected:
-      const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
-    public:
-      typedef Number Value;
-      typedef Edge Key;
-      ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>& 
-	     _res_graph) : res_graph(&_res_graph) { }
-      Number operator[](const Edge& e) const { 
-	if (res_graph->forward(e)) 
-	  return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e]; 
-	else 
-	  return (*(res_graph->flow))[e]; 
-      }
-    };
-
-    //    KEEP_MAPS(Parent, ResGraphAdaptor);
-  };
-
-
-
-  template <typename _Graph, typename FirstOutEdgesMap>
-  class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
-  public:
-    typedef _Graph Graph;
-    typedef GraphAdaptorBase<_Graph> Parent;
-  protected:
-    FirstOutEdgesMap* first_out_edges;
-    ErasingFirstGraphAdaptorBase() : Parent(), 
-				     first_out_edges(0) { }
-
-    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
-      first_out_edges=&_first_out_edges;
-    }
-
-  public:
-
-    typedef typename Parent::Node Node;
-    typedef typename Parent::Edge Edge;
-
-    void firstOut(Edge& i, const Node& n) const { 
-      i=(*first_out_edges)[n];
-    }
-
-    void erase(const Edge& e) const {
-      Node n=source(e);
-      Edge f=e;
-      Parent::nextOut(f);
-      first_out_edges->set(n, f);
-    }    
-  };
-
-
-  /// For blocking flows.
-
-  ///\warning Graph adaptors are in even more experimental state than the other
-  ///parts of the lib. Use them at you own risk.
-  ///
-  /// This graph adaptor is used for on-the-fly 
-  /// Dinits blocking flow computations.
-  /// For each node, an out-edge is stored which is used when the 
-  /// \code 
-  /// OutEdgeIt& first(OutEdgeIt&, const Node&)
-  /// \endcode
-  /// is called. 
-  ///
-  /// \author Marton Makai
-  template <typename _Graph, typename FirstOutEdgesMap>
-  class ErasingFirstGraphAdaptor : 
-    public IterableGraphExtender<
-    ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
-  public:
-    typedef _Graph Graph;
-    typedef IterableGraphExtender<
-      ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
-    ErasingFirstGraphAdaptor(Graph& _graph, 
-			     FirstOutEdgesMap& _first_out_edges) { 
-      setGraph(_graph);
-      setFirstOutEdgesMap(_first_out_edges);
-    } 
-
-  };
-
-  ///@}
-
-} //namespace lemon
-
-#endif //LEMON_GRAPH_ADAPTOR_H
-