diff -r d8475431bbbb -r 8e85e6bbefdf lemon/graph_adaptor.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/graph_adaptor.h	Mon May 23 04:48:14 2005 +0000
@@ -0,0 +1,1218 @@
+/* -*- C++ -*-
+ * lemon/graph_adaptor.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_GRAPH_ADAPTOR_H
+#define LEMON_GRAPH_ADAPTOR_H
+
+///\ingroup graph_adaptors
+///\file
+///\brief Several graph adaptors.
+///
+///This file contains several useful graph adaptor functions.
+///
+///\author Marton Makai
+
+#include <lemon/invalid.h>
+#include <lemon/maps.h>
+#include <lemon/bits/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
+