lemon/graph_adaptor.h
author alpar
Thu, 01 Sep 2005 20:35:30 +0000
changeset 1674 648aa2f33dc8
parent 1631 e15162d8eca1
child 1681 84e43c7ca1e3
permissions -rw-r--r--
Warning added on the usage of InDegMap/OutDegMap
     1 /* -*- C++ -*-
     2  * lemon/graph_adaptor.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #ifndef LEMON_GRAPH_ADAPTOR_H
    18 #define LEMON_GRAPH_ADAPTOR_H
    19 
    20 ///\ingroup graph_adaptors
    21 ///\file
    22 ///\brief Several graph adaptors.
    23 ///
    24 ///This file contains several useful graph adaptor functions.
    25 ///
    26 ///\author Marton Makai
    27 
    28 #include <lemon/invalid.h>
    29 #include <lemon/maps.h>
    30 #include <lemon/bits/erasable_graph_extender.h>
    31 #include <lemon/bits/clearable_graph_extender.h>
    32 #include <lemon/bits/extendable_graph_extender.h>
    33 #include <lemon/bits/iterable_graph_extender.h>
    34 #include <lemon/bits/alteration_notifier.h>
    35 #include <lemon/bits/default_map.h>
    36 #include <lemon/bits/undir_graph_extender.h>
    37 #include <iostream>
    38 
    39 namespace lemon {
    40 
    41   // Graph adaptors
    42 
    43   /*!
    44     \addtogroup graph_adaptors
    45     @{
    46    */
    47 
    48   /*! 
    49     Base type for the Graph Adaptors
    50     
    51     \warning Graph adaptors are in even more experimental state than the other
    52     parts of the lib. Use them at you own risk.
    53     
    54     This is the base type for most of LEMON graph adaptors. 
    55     This class implements a trivial graph adaptor i.e. it only wraps the 
    56     functions and types of the graph. The purpose of this class is to 
    57     make easier implementing graph adaptors. E.g. if an adaptor is 
    58     considered which differs from the wrapped graph only in some of its 
    59     functions or types, then it can be derived from GraphAdaptor, and only the 
    60     differences should be implemented.
    61   
    62     \author Marton Makai 
    63   */
    64   template<typename _Graph>
    65   class GraphAdaptorBase {
    66   public:
    67     typedef _Graph Graph;
    68     /// \todo Is it needed?
    69     typedef Graph BaseGraph;
    70     typedef Graph ParentGraph;
    71 
    72   protected:
    73     Graph* graph;
    74     GraphAdaptorBase() : graph(0) { }
    75     void setGraph(Graph& _graph) { graph=&_graph; }
    76 
    77   public:
    78     GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
    79  
    80     typedef typename Graph::Node Node;
    81     typedef typename Graph::Edge Edge;
    82    
    83     void first(Node& i) const { graph->first(i); }
    84     void first(Edge& i) const { graph->first(i); }
    85     void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
    86     void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
    87 
    88     void next(Node& i) const { graph->next(i); }
    89     void next(Edge& i) const { graph->next(i); }
    90     void nextIn(Edge& i) const { graph->nextIn(i); }
    91     void nextOut(Edge& i) const { graph->nextOut(i); }
    92 
    93     Node source(const Edge& e) const { return graph->source(e); }
    94     Node target(const Edge& e) const { return graph->target(e); }
    95 
    96     int nodeNum() const { return graph->nodeNum(); }
    97     int edgeNum() const { return graph->edgeNum(); }
    98   
    99     Node addNode() const { return Node(graph->addNode()); }
   100     Edge addEdge(const Node& source, const Node& target) const { 
   101       return Edge(graph->addEdge(source, target)); }
   102 
   103     void erase(const Node& i) const { graph->erase(i); }
   104     void erase(const Edge& i) const { graph->erase(i); }
   105   
   106     void clear() const { graph->clear(); }
   107     
   108     int id(const Node& v) const { return graph->id(v); }
   109     int id(const Edge& e) const { return graph->id(e); }
   110     
   111     Edge oppositeNode(const Edge& e) const { 
   112       return Edge(graph->opposite(e)); 
   113     }
   114 
   115     template <typename _Value>
   116     class NodeMap : public _Graph::template NodeMap<_Value> {
   117     public:
   118       typedef typename _Graph::template NodeMap<_Value> Parent;
   119       NodeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
   120       NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
   121       : Parent(*gw.graph, value) { }
   122     };
   123 
   124     template <typename _Value>
   125     class EdgeMap : public _Graph::template EdgeMap<_Value> {
   126     public:
   127       typedef typename _Graph::template EdgeMap<_Value> Parent;
   128       EdgeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
   129       EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
   130       : Parent(*gw.graph, value) { }
   131     };
   132 
   133   };
   134 
   135   template <typename _Graph>
   136   class GraphAdaptor :
   137     public IterableGraphExtender<GraphAdaptorBase<_Graph> > { 
   138   public:
   139     typedef _Graph Graph;
   140     typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
   141   protected:
   142     GraphAdaptor() : Parent() { }
   143 
   144   public:
   145     GraphAdaptor(Graph& _graph) { setGraph(_graph); }
   146   };
   147 
   148   template <typename _Graph>
   149   class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
   150   public:
   151     typedef _Graph Graph;
   152     typedef GraphAdaptorBase<_Graph> Parent;
   153   protected:
   154     RevGraphAdaptorBase() : Parent() { }
   155   public:
   156     typedef typename Parent::Node Node;
   157     typedef typename Parent::Edge Edge;
   158 
   159     //    using Parent::first;
   160     void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
   161     void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
   162 
   163     //    using Parent::next;
   164     void nextIn(Edge& i) const { Parent::nextOut(i); }
   165     void nextOut(Edge& i) const { Parent::nextIn(i); }
   166 
   167     Node source(const Edge& e) const { return Parent::target(e); }
   168     Node target(const Edge& e) const { return Parent::source(e); }
   169   };
   170     
   171 
   172   /// A graph adaptor which reverses the orientation of the edges.
   173 
   174   ///\warning Graph adaptors are in even more experimental state than the other
   175   ///parts of the lib. Use them at you own risk.
   176   ///
   177   /// Let \f$G=(V, A)\f$ be a directed graph and 
   178   /// suppose that a graph instange \c g of type 
   179   /// \c ListGraph implements \f$G\f$.
   180   /// \code
   181   /// ListGraph g;
   182   /// \endcode
   183   /// For each directed edge 
   184   /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by 
   185   /// reversing its orientation. 
   186   /// Then RevGraphAdaptor implements the graph structure with node-set 
   187   /// \f$V\f$ and edge-set 
   188   /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be 
   189   /// reversing the orientation of its edges. The following code shows how 
   190   /// such an instance can be constructed.
   191   /// \code
   192   /// RevGraphAdaptor<ListGraph> gw(g);
   193   /// \endcode
   194   ///\author Marton Makai
   195   template<typename _Graph>
   196   class RevGraphAdaptor : 
   197     public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
   198   public:
   199     typedef _Graph Graph;
   200     typedef IterableGraphExtender<
   201       RevGraphAdaptorBase<_Graph> > Parent;
   202   protected:
   203     RevGraphAdaptor() { }
   204   public:
   205     RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
   206   };
   207 
   208   
   209   template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
   210   class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
   211   public:
   212     typedef _Graph Graph;
   213     typedef GraphAdaptorBase<_Graph> Parent;
   214   protected:
   215     NodeFilterMap* node_filter_map;
   216     EdgeFilterMap* edge_filter_map;
   217     SubGraphAdaptorBase() : Parent(), 
   218 			    node_filter_map(0), edge_filter_map(0) { }
   219 
   220     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
   221       node_filter_map=&_node_filter_map;
   222     }
   223     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
   224       edge_filter_map=&_edge_filter_map;
   225     }
   226 
   227   public:
   228 //     SubGraphAdaptorBase(Graph& _graph, 
   229 // 			NodeFilterMap& _node_filter_map, 
   230 // 			EdgeFilterMap& _edge_filter_map) : 
   231 //       Parent(&_graph), 
   232 //       node_filter_map(&node_filter_map), 
   233 //       edge_filter_map(&edge_filter_map) { }
   234 
   235     typedef typename Parent::Node Node;
   236     typedef typename Parent::Edge Edge;
   237 
   238     void first(Node& i) const { 
   239       Parent::first(i); 
   240       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
   241     }
   242     void first(Edge& i) const { 
   243       Parent::first(i); 
   244       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
   245     }
   246     void firstIn(Edge& i, const Node& n) const { 
   247       Parent::firstIn(i, n); 
   248       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
   249     }
   250     void firstOut(Edge& i, const Node& n) const { 
   251       Parent::firstOut(i, n); 
   252       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
   253     }
   254 
   255     void next(Node& i) const { 
   256       Parent::next(i); 
   257       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
   258     }
   259     void next(Edge& i) const { 
   260       Parent::next(i); 
   261       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
   262     }
   263     void nextIn(Edge& i) const { 
   264       Parent::nextIn(i); 
   265       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
   266     }
   267     void nextOut(Edge& i) const { 
   268       Parent::nextOut(i); 
   269       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
   270     }
   271 
   272     /// This function hides \c n in the graph, i.e. the iteration 
   273     /// jumps over it. This is done by simply setting the value of \c n  
   274     /// to be false in the corresponding node-map.
   275     void hide(const Node& n) const { node_filter_map->set(n, false); }
   276 
   277     /// This function hides \c e in the graph, i.e. the iteration 
   278     /// jumps over it. This is done by simply setting the value of \c e  
   279     /// to be false in the corresponding edge-map.
   280     void hide(const Edge& e) const { edge_filter_map->set(e, false); }
   281 
   282     /// The value of \c n is set to be true in the node-map which stores 
   283     /// hide information. If \c n was hidden previuosly, then it is shown 
   284     /// again
   285      void unHide(const Node& n) const { node_filter_map->set(n, true); }
   286 
   287     /// The value of \c e is set to be true in the edge-map which stores 
   288     /// hide information. If \c e was hidden previuosly, then it is shown 
   289     /// again
   290     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
   291 
   292     /// Returns true if \c n is hidden.
   293     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
   294 
   295     /// Returns true if \c n is hidden.
   296     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
   297 
   298     /// \warning This is a linear time operation and works only if s
   299     /// \c Graph::NodeIt is defined.
   300     /// \todo assign tags.
   301     int nodeNum() const { 
   302       int i=0;
   303       Node n;
   304       for (first(n); n!=INVALID; next(n)) ++i;
   305       return i; 
   306     }
   307 
   308     /// \warning This is a linear time operation and works only if 
   309     /// \c Graph::EdgeIt is defined.
   310     /// \todo assign tags.
   311     int edgeNum() const { 
   312       int i=0;
   313       Edge e;
   314       for (first(e); e!=INVALID; next(e)) ++i;
   315       return i; 
   316     }
   317 
   318 
   319   };
   320 
   321   /*! \brief A graph adaptor for hiding nodes and edges from a graph.
   322     
   323   \warning Graph adaptors are in even more experimental state than the other
   324   parts of the lib. Use them at you own risk.
   325   
   326   SubGraphAdaptor shows the graph with filtered node-set and 
   327   edge-set. 
   328   Let \f$G=(V, A)\f$ be a directed graph 
   329   and suppose that the graph instance \c g of type ListGraph implements 
   330   \f$G\f$. 
   331   Let moreover \f$b_V\f$ and 
   332   \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set. 
   333   SubGraphAdaptor<...>::NodeIt iterates 
   334   on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and 
   335   SubGraphAdaptor<...>::EdgeIt iterates 
   336   on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly, 
   337   SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates 
   338   only on edges leaving and entering a specific node which have true value.
   339 
   340   We have to note that this does not mean that an 
   341   induced subgraph is obtained, the node-iterator cares only the filter 
   342   on the node-set, and the edge-iterators care only the filter on the 
   343   edge-set. 
   344   \code
   345   typedef ListGraph Graph;
   346   Graph g;
   347   typedef Graph::Node Node;
   348   typedef Graph::Edge Edge;
   349   Node u=g.addNode(); //node of id 0
   350   Node v=g.addNode(); //node of id 1
   351   Node e=g.addEdge(u, v); //edge of id 0
   352   Node f=g.addEdge(v, u); //edge of id 1
   353   Graph::NodeMap<bool> nm(g, true);
   354   nm.set(u, false);
   355   Graph::EdgeMap<bool> em(g, true);
   356   em.set(e, false);
   357   typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
   358   SubGW gw(g, nm, em);
   359   for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
   360   std::cout << ":-)" << std::endl;
   361   for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
   362   \endcode
   363   The output of the above code is the following.
   364   \code
   365   1
   366   :-)
   367   1
   368   \endcode
   369   Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
   370   \c Graph::Node that is why \c g.id(n) can be applied.
   371 
   372   For other examples see also the documentation of NodeSubGraphAdaptor and 
   373   EdgeSubGraphAdaptor.
   374 
   375   \author Marton Makai
   376   */
   377   template<typename _Graph, typename NodeFilterMap, 
   378 	   typename EdgeFilterMap>
   379   class SubGraphAdaptor : 
   380     public IterableGraphExtender<
   381     SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
   382   public:
   383     typedef _Graph Graph;
   384     typedef IterableGraphExtender<
   385       SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
   386   protected:
   387     SubGraphAdaptor() { }
   388   public:
   389     SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map, 
   390 		    EdgeFilterMap& _edge_filter_map) { 
   391       setGraph(_graph);
   392       setNodeFilterMap(_node_filter_map);
   393       setEdgeFilterMap(_edge_filter_map);
   394     }
   395   };
   396 
   397 
   398 
   399   /*! \brief An adaptor for hiding nodes from a graph.
   400 
   401   \warning Graph adaptors are in even more experimental state than the other
   402   parts of the lib. Use them at you own risk.
   403   
   404   An adaptor for hiding nodes from a graph.
   405   This adaptor specializes SubGraphAdaptor in the way that only the node-set 
   406   can be filtered. Note that this does not mean of considering induced 
   407   subgraph, the edge-iterators consider the original edge-set.
   408   \author Marton Makai
   409   */
   410   template<typename Graph, typename NodeFilterMap>
   411   class NodeSubGraphAdaptor : 
   412     public SubGraphAdaptor<Graph, NodeFilterMap, 
   413 			   ConstMap<typename Graph::Edge,bool> > {
   414   public:
   415     typedef SubGraphAdaptor<Graph, NodeFilterMap, 
   416 			    ConstMap<typename Graph::Edge,bool> > Parent;
   417   protected:
   418     ConstMap<typename Graph::Edge, bool> const_true_map;
   419   public:
   420     NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) : 
   421       Parent(), const_true_map(true) { 
   422       Parent::setGraph(_graph);
   423       Parent::setNodeFilterMap(_node_filter_map);
   424       Parent::setEdgeFilterMap(const_true_map);
   425     }
   426   };
   427 
   428 
   429   /*! \brief An adaptor for hiding edges from a graph.
   430 
   431   \warning Graph adaptors are in even more experimental state than the other
   432   parts of the lib. Use them at you own risk.
   433   
   434   An adaptor for hiding edges from a graph.
   435   This adaptor specializes SubGraphAdaptor in the way that only the edge-set 
   436   can be filtered. The usefulness of this adaptor is demonstrated in the 
   437   problem of searching a maximum number of edge-disjoint shortest paths 
   438   between 
   439   two nodes \c s and \c t. Shortest here means being shortest w.r.t. 
   440   non-negative edge-lengths. Note that 
   441   the comprehension of the presented solution 
   442   need's some elementary knowledge from combinatorial optimization. 
   443 
   444   If a single shortest path is to be 
   445   searched between \c s and \c t, then this can be done easily by 
   446   applying the Dijkstra algorithm. What happens, if a maximum number of 
   447   edge-disjoint shortest paths is to be computed. It can be proved that an 
   448   edge can be in a shortest path if and only if it is tight with respect to 
   449   the potential function computed by Dijkstra. Moreover, any path containing 
   450   only such edges is a shortest one. Thus we have to compute a maximum number 
   451   of edge-disjoint paths between \c s and \c t in the graph which has edge-set 
   452   all the tight edges. The computation will be demonstrated on the following 
   453   graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim. 
   454   The full source code is available in \ref sub_graph_adaptor_demo.cc. 
   455   If you are interested in more demo programs, you can use 
   456   \ref dim_to_dot.cc to generate .dot files from dimacs files. 
   457   The .dot file of the following figure was generated by  
   458   the demo program \ref dim_to_dot.cc.
   459 
   460   \dot
   461   digraph lemon_dot_example {
   462   node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
   463   n0 [ label="0 (s)" ];
   464   n1 [ label="1" ];
   465   n2 [ label="2" ];
   466   n3 [ label="3" ];
   467   n4 [ label="4" ];
   468   n5 [ label="5" ];
   469   n6 [ label="6 (t)" ];
   470   edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
   471   n5 ->  n6 [ label="9, length:4" ];
   472   n4 ->  n6 [ label="8, length:2" ];
   473   n3 ->  n5 [ label="7, length:1" ];
   474   n2 ->  n5 [ label="6, length:3" ];
   475   n2 ->  n6 [ label="5, length:5" ];
   476   n2 ->  n4 [ label="4, length:2" ];
   477   n1 ->  n4 [ label="3, length:3" ];
   478   n0 ->  n3 [ label="2, length:1" ];
   479   n0 ->  n2 [ label="1, length:2" ];
   480   n0 ->  n1 [ label="0, length:3" ];
   481   }
   482   \enddot
   483 
   484   \code
   485   Graph g;
   486   Node s, t;
   487   LengthMap length(g);
   488 
   489   readDimacs(std::cin, g, length, s, t);
   490 
   491   cout << "edges with lengths (of form id, source--length->target): " << endl;
   492   for(EdgeIt e(g); e!=INVALID; ++e) 
   493     cout << g.id(e) << ", " << g.id(g.source(e)) << "--" 
   494          << length[e] << "->" << g.id(g.target(e)) << endl;
   495 
   496   cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
   497   \endcode
   498   Next, the potential function is computed with Dijkstra.
   499   \code
   500   typedef Dijkstra<Graph, LengthMap> Dijkstra;
   501   Dijkstra dijkstra(g, length);
   502   dijkstra.run(s);
   503   \endcode
   504   Next, we consrtruct a map which filters the edge-set to the tight edges.
   505   \code
   506   typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> 
   507     TightEdgeFilter;
   508   TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
   509   
   510   typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
   511   SubGW gw(g, tight_edge_filter);
   512   \endcode
   513   Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed 
   514   with a max flow algorithm Preflow.
   515   \code
   516   ConstMap<Edge, int> const_1_map(1);
   517   Graph::EdgeMap<int> flow(g, 0);
   518 
   519   Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 
   520     preflow(gw, s, t, const_1_map, flow);
   521   preflow.run();
   522   \endcode
   523   Last, the output is:
   524   \code  
   525   cout << "maximum number of edge-disjoint shortest path: " 
   526        << preflow.flowValue() << endl;
   527   cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " 
   528        << endl;
   529   for(EdgeIt e(g); e!=INVALID; ++e) 
   530     if (flow[e])
   531       cout << " " << g.id(g.source(e)) << "--" 
   532 	   << length[e] << "->" << g.id(g.target(e)) << endl;
   533   \endcode
   534   The program has the following (expected :-)) output:
   535   \code
   536   edges with lengths (of form id, source--length->target):
   537    9, 5--4->6
   538    8, 4--2->6
   539    7, 3--1->5
   540    6, 2--3->5
   541    5, 2--5->6
   542    4, 2--2->4
   543    3, 1--3->4
   544    2, 0--1->3
   545    1, 0--2->2
   546    0, 0--3->1
   547   s: 0 t: 6
   548   maximum number of edge-disjoint shortest path: 2
   549   edges of the maximum number of edge-disjoint shortest s-t paths:
   550    9, 5--4->6
   551    8, 4--2->6
   552    7, 3--1->5
   553    4, 2--2->4
   554    2, 0--1->3
   555    1, 0--2->2
   556   \endcode
   557 
   558   \author Marton Makai
   559   */
   560   template<typename Graph, typename EdgeFilterMap>
   561   class EdgeSubGraphAdaptor : 
   562     public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 
   563 			   EdgeFilterMap> {
   564   public:
   565     typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 
   566 			    EdgeFilterMap> Parent;
   567   protected:
   568     ConstMap<typename Graph::Node, bool> const_true_map;
   569   public:
   570     EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) : 
   571       Parent(), const_true_map(true) { 
   572       Parent::setGraph(_graph);
   573       Parent::setNodeFilterMap(const_true_map);
   574       Parent::setEdgeFilterMap(_edge_filter_map);
   575     }
   576   };
   577 
   578   template <typename _Graph>
   579   class UndirGraphAdaptorBase : 
   580     public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
   581   public:
   582     typedef _Graph Graph;
   583     typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
   584   protected:
   585     UndirGraphAdaptorBase() : Parent() { }
   586   public:
   587     typedef typename Parent::UndirEdge UndirEdge;
   588     typedef typename Parent::Edge Edge;
   589     
   590     /// \bug Why cant an edge say that it is forward or not??? 
   591     /// By this, a pointer to the graph have to be stored
   592     /// The implementation
   593     template <typename T>
   594     class EdgeMap {
   595     protected:
   596       const UndirGraphAdaptorBase<_Graph>* g;
   597       template <typename TT> friend class EdgeMap;
   598       typename _Graph::template EdgeMap<T> forward_map, backward_map; 
   599     public:
   600       typedef T Value;
   601       typedef Edge Key;
   602       
   603       EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g), 
   604 	forward_map(*(g->graph)), backward_map(*(g->graph)) { }
   605 
   606       EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g), 
   607 	forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
   608       
   609       void set(Edge e, T a) { 
   610 	if (g->direction(e)) 
   611 	  forward_map.set(e, a); 
   612 	else 
   613 	  backward_map.set(e, a); 
   614       }
   615 
   616       T operator[](Edge e) const { 
   617 	if (g->direction(e)) 
   618 	  return forward_map[e]; 
   619 	else 
   620 	  return backward_map[e]; 
   621       }
   622     };
   623         
   624     template <typename T>
   625     class UndirEdgeMap {
   626       template <typename TT> friend class UndirEdgeMap;
   627       typename _Graph::template EdgeMap<T> map; 
   628     public:
   629       typedef T Value;
   630       typedef UndirEdge Key;
   631       
   632       UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) : 
   633 	map(*(g.graph)) { }
   634 
   635       UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) : 
   636 	map(*(g.graph), a) { }
   637       
   638       void set(UndirEdge e, T a) { 
   639 	map.set(e, a); 
   640       }
   641 
   642       T operator[](UndirEdge e) const { 
   643 	return map[e]; 
   644       }
   645     };
   646       
   647   };
   648 
   649   /// \brief An undirected graph is made from a directed graph by an adaptor
   650   ///
   651   /// Undocumented, untested!!!
   652   /// If somebody knows nice demo application, let's polulate it.
   653   /// 
   654   /// \author Marton Makai
   655   template<typename _Graph>
   656   class UndirGraphAdaptor : 
   657     public IterableUndirGraphExtender<
   658     UndirGraphAdaptorBase<_Graph> > {
   659   public:
   660     typedef _Graph Graph;
   661     typedef IterableUndirGraphExtender<
   662       UndirGraphAdaptorBase<_Graph> > Parent;
   663   protected:
   664     UndirGraphAdaptor() { }
   665   public:
   666     UndirGraphAdaptor(_Graph& _graph) { 
   667       setGraph(_graph);
   668     }
   669   };
   670 
   671   
   672   template <typename _Graph, 
   673 	    typename ForwardFilterMap, typename BackwardFilterMap>
   674   class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
   675   public:
   676     typedef _Graph Graph;
   677     typedef GraphAdaptorBase<_Graph> Parent;
   678   protected:
   679     ForwardFilterMap* forward_filter;
   680     BackwardFilterMap* backward_filter;
   681     SubBidirGraphAdaptorBase() : Parent(), 
   682 				 forward_filter(0), backward_filter(0) { }
   683 
   684     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
   685       forward_filter=&_forward_filter;
   686     }
   687     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
   688       backward_filter=&_backward_filter;
   689     }
   690 
   691   public:
   692 //     SubGraphAdaptorBase(Graph& _graph, 
   693 // 			NodeFilterMap& _node_filter_map, 
   694 // 			EdgeFilterMap& _edge_filter_map) : 
   695 //       Parent(&_graph), 
   696 //       node_filter_map(&node_filter_map), 
   697 //       edge_filter_map(&edge_filter_map) { }
   698 
   699     typedef typename Parent::Node Node;
   700     typedef typename _Graph::Edge GraphEdge;
   701     template <typename T> class EdgeMap;
   702     /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from 
   703     /// _Graph::Edge. It contains an extra bool flag which is true 
   704     /// if and only if the 
   705     /// edge is the backward version of the original edge.
   706     class Edge : public _Graph::Edge {
   707       friend class SubBidirGraphAdaptorBase<
   708 	Graph, ForwardFilterMap, BackwardFilterMap>;
   709       template<typename T> friend class EdgeMap;
   710     protected:
   711       bool backward; //true, iff backward
   712     public:
   713       Edge() { }
   714       /// \todo =false is needed, or causes problems?
   715       /// If \c _backward is false, then we get an edge corresponding to the 
   716       /// original one, otherwise its oppositely directed pair is obtained.
   717       Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) : 
   718 	_Graph::Edge(e), backward(_backward) { }
   719       Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
   720       bool operator==(const Edge& v) const { 
   721 	return (this->backward==v.backward && 
   722 		static_cast<typename _Graph::Edge>(*this)==
   723 		static_cast<typename _Graph::Edge>(v));
   724       } 
   725       bool operator!=(const Edge& v) const { 
   726 	return (this->backward!=v.backward || 
   727 		static_cast<typename _Graph::Edge>(*this)!=
   728 		static_cast<typename _Graph::Edge>(v));
   729       }
   730     };
   731 
   732     void first(Node& i) const { 
   733       Parent::first(i); 
   734     }
   735 
   736     void first(Edge& i) const { 
   737       Parent::first(i); 
   738       i.backward=false;
   739       while (*static_cast<GraphEdge*>(&i)!=INVALID && 
   740 	     !(*forward_filter)[i]) Parent::next(i);
   741       if (*static_cast<GraphEdge*>(&i)==INVALID) {
   742 	Parent::first(i); 
   743 	i.backward=true;
   744 	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
   745 	       !(*backward_filter)[i]) Parent::next(i);
   746       }
   747     }
   748 
   749     void firstIn(Edge& i, const Node& n) const { 
   750       Parent::firstIn(i, n); 
   751       i.backward=false;
   752       while (*static_cast<GraphEdge*>(&i)!=INVALID && 
   753 	     !(*forward_filter)[i]) Parent::nextIn(i);
   754       if (*static_cast<GraphEdge*>(&i)==INVALID) {
   755 	Parent::firstOut(i, n); 
   756 	i.backward=true;
   757 	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
   758 	       !(*backward_filter)[i]) Parent::nextOut(i);
   759       }
   760     }
   761 
   762     void firstOut(Edge& i, const Node& n) const { 
   763       Parent::firstOut(i, n); 
   764       i.backward=false;
   765       while (*static_cast<GraphEdge*>(&i)!=INVALID && 
   766 	     !(*forward_filter)[i]) Parent::nextOut(i);
   767       if (*static_cast<GraphEdge*>(&i)==INVALID) {
   768 	Parent::firstIn(i, n); 
   769 	i.backward=true;
   770 	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
   771 	       !(*backward_filter)[i]) Parent::nextIn(i);
   772       }
   773     }
   774 
   775     void next(Node& i) const { 
   776       Parent::next(i); 
   777     }
   778 
   779     void next(Edge& i) const { 
   780       if (!(i.backward)) {
   781 	Parent::next(i);
   782 	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
   783 	       !(*forward_filter)[i]) Parent::next(i);
   784 	if (*static_cast<GraphEdge*>(&i)==INVALID) {
   785 	  Parent::first(i); 
   786 	  i.backward=true;
   787 	  while (*static_cast<GraphEdge*>(&i)!=INVALID && 
   788 		 !(*backward_filter)[i]) Parent::next(i);
   789 	}
   790       } else {
   791 	Parent::next(i);
   792 	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
   793 	       !(*backward_filter)[i]) Parent::next(i);
   794       }
   795     }
   796 
   797     void nextIn(Edge& i) const { 
   798       if (!(i.backward)) {
   799 	Node n=Parent::target(i);
   800 	Parent::nextIn(i);
   801 	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
   802 	       !(*forward_filter)[i]) Parent::nextIn(i);
   803 	if (*static_cast<GraphEdge*>(&i)==INVALID) {
   804 	  Parent::firstOut(i, n); 
   805 	  i.backward=true;
   806 	  while (*static_cast<GraphEdge*>(&i)!=INVALID && 
   807 		 !(*backward_filter)[i]) Parent::nextOut(i);
   808 	}
   809       } else {
   810 	Parent::nextOut(i);
   811 	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
   812 	       !(*backward_filter)[i]) Parent::nextOut(i);
   813       }
   814     }
   815 
   816     void nextOut(Edge& i) const { 
   817       if (!(i.backward)) {
   818 	Node n=Parent::source(i);
   819 	Parent::nextOut(i);
   820 	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
   821 	       !(*forward_filter)[i]) Parent::nextOut(i);
   822 	if (*static_cast<GraphEdge*>(&i)==INVALID) {
   823 	  Parent::firstIn(i, n); 
   824 	  i.backward=true;
   825 	  while (*static_cast<GraphEdge*>(&i)!=INVALID && 
   826 		 !(*backward_filter)[i]) Parent::nextIn(i);
   827 	}
   828       } else {
   829 	Parent::nextIn(i);
   830 	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
   831 	       !(*backward_filter)[i]) Parent::nextIn(i);
   832       }
   833     }
   834 
   835     Node source(Edge e) const { 
   836       return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
   837     Node target(Edge e) const { 
   838       return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
   839 
   840     /// Gives back the opposite edge.
   841     Edge opposite(const Edge& e) const { 
   842       Edge f=e;
   843       f.backward=!f.backward;
   844       return f;
   845     }
   846 
   847     /// \warning This is a linear time operation and works only if 
   848     /// \c Graph::EdgeIt is defined.
   849     /// \todo hmm
   850     int edgeNum() const { 
   851       int i=0;
   852       Edge e;
   853       for (first(e); e!=INVALID; next(e)) ++i;
   854       return i; 
   855     }
   856 
   857     bool forward(const Edge& e) const { return !e.backward; }
   858     bool backward(const Edge& e) const { return e.backward; }
   859 
   860     template <typename T>
   861     /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two 
   862     /// _Graph::EdgeMap one for the forward edges and 
   863     /// one for the backward edges.
   864     class EdgeMap {
   865       template <typename TT> friend class EdgeMap;
   866       typename _Graph::template EdgeMap<T> forward_map, backward_map; 
   867     public:
   868       typedef T Value;
   869       typedef Edge Key;
   870 
   871       EdgeMap(const SubBidirGraphAdaptorBase<_Graph, 
   872 	      ForwardFilterMap, BackwardFilterMap>& g) : 
   873 	forward_map(*(g.graph)), backward_map(*(g.graph)) { }
   874 
   875       EdgeMap(const SubBidirGraphAdaptorBase<_Graph, 
   876 	      ForwardFilterMap, BackwardFilterMap>& g, T a) : 
   877 	forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
   878       
   879       void set(Edge e, T a) { 
   880 	if (!e.backward) 
   881 	  forward_map.set(e, a); 
   882 	else 
   883 	  backward_map.set(e, a); 
   884       }
   885 
   886 //       typename _Graph::template EdgeMap<T>::ConstReference 
   887 //       operator[](Edge e) const { 
   888 // 	if (!e.backward) 
   889 // 	  return forward_map[e]; 
   890 // 	else 
   891 // 	  return backward_map[e]; 
   892 //       }
   893 
   894 //      typename _Graph::template EdgeMap<T>::Reference 
   895       T operator[](Edge e) const { 
   896 	if (!e.backward) 
   897 	  return forward_map[e]; 
   898 	else 
   899 	  return backward_map[e]; 
   900       }
   901 
   902       void update() { 
   903 	forward_map.update(); 
   904 	backward_map.update();
   905       }
   906     };
   907 
   908   };
   909 
   910 
   911   ///\brief An adaptor for composing a subgraph of a 
   912   /// bidirected graph made from a directed one. 
   913   ///
   914   /// An adaptor for composing a subgraph of a 
   915   /// bidirected graph made from a directed one. 
   916   ///
   917   ///\warning Graph adaptors are in even more experimental state than the other
   918   ///parts of the lib. Use them at you own risk.
   919   ///
   920   /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge 
   921   /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
   922   /// reversing its orientation. We are given moreover two bool valued 
   923   /// maps on the edge-set, 
   924   /// \f$forward\_filter\f$, and \f$backward\_filter\f$. 
   925   /// SubBidirGraphAdaptor implements the graph structure with node-set 
   926   /// \f$V\f$ and edge-set 
   927   /// \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$. 
   928   /// The purpose of writing + instead of union is because parallel 
   929   /// edges can arise. (Similarly, antiparallel edges also can arise).
   930   /// In other words, a subgraph of the bidirected graph obtained, which 
   931   /// is given by orienting the edges of the original graph in both directions.
   932   /// As the oppositely directed edges are logically different, 
   933   /// the maps are able to attach different values for them. 
   934   ///
   935   /// An example for such a construction is \c RevGraphAdaptor where the 
   936   /// forward_filter is everywhere false and the backward_filter is 
   937   /// everywhere true. We note that for sake of efficiency, 
   938   /// \c RevGraphAdaptor is implemented in a different way. 
   939   /// But BidirGraphAdaptor is obtained from 
   940   /// SubBidirGraphAdaptor by considering everywhere true 
   941   /// valued maps both for forward_filter and backward_filter. 
   942   ///
   943   /// The most important application of SubBidirGraphAdaptor 
   944   /// is ResGraphAdaptor, which stands for the residual graph in directed 
   945   /// flow and circulation problems. 
   946   /// As adaptors usually, the SubBidirGraphAdaptor implements the 
   947   /// above mentioned graph structure without its physical storage, 
   948   /// that is the whole stuff is stored in constant memory. 
   949   template<typename _Graph, 
   950 	   typename ForwardFilterMap, typename BackwardFilterMap>
   951   class SubBidirGraphAdaptor : 
   952     public IterableGraphExtender<
   953     SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
   954   public:
   955     typedef _Graph Graph;
   956     typedef IterableGraphExtender<
   957       SubBidirGraphAdaptorBase<
   958       _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
   959   protected:
   960     SubBidirGraphAdaptor() { }
   961   public:
   962     SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter, 
   963 			 BackwardFilterMap& _backward_filter) { 
   964       setGraph(_graph);
   965       setForwardFilterMap(_forward_filter);
   966       setBackwardFilterMap(_backward_filter);
   967     }
   968   };
   969 
   970 
   971 
   972   ///\brief An adaptor for composing bidirected graph from a directed one. 
   973   ///
   974   ///\warning Graph adaptors are in even more experimental state than the other
   975   ///parts of the lib. Use them at you own risk.
   976   ///
   977   /// An adaptor for composing bidirected graph from a directed one. 
   978   /// A bidirected graph is composed over the directed one without physical 
   979   /// storage. As the oppositely directed edges are logically different ones 
   980   /// the maps are able to attach different values for them.
   981   template<typename Graph>
   982   class BidirGraphAdaptor : 
   983     public SubBidirGraphAdaptor<
   984     Graph, 
   985     ConstMap<typename Graph::Edge, bool>, 
   986     ConstMap<typename Graph::Edge, bool> > {
   987   public:
   988     typedef  SubBidirGraphAdaptor<
   989       Graph, 
   990       ConstMap<typename Graph::Edge, bool>, 
   991       ConstMap<typename Graph::Edge, bool> > Parent; 
   992   protected:
   993     ConstMap<typename Graph::Edge, bool> cm;
   994 
   995     BidirGraphAdaptor() : Parent(), cm(true) { 
   996       Parent::setForwardFilterMap(cm);
   997       Parent::setBackwardFilterMap(cm);
   998     }
   999   public:
  1000     BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) { 
  1001       Parent::setGraph(_graph);
  1002       Parent::setForwardFilterMap(cm);
  1003       Parent::setBackwardFilterMap(cm);
  1004     }
  1005 
  1006     int edgeNum() const { 
  1007       return 2*this->graph->edgeNum();
  1008     }
  1009     //    KEEP_MAPS(Parent, BidirGraphAdaptor);
  1010   };
  1011 
  1012 
  1013   template<typename Graph, typename Number,
  1014 	   typename CapacityMap, typename FlowMap>
  1015   class ResForwardFilter {
  1016     //    const Graph* graph;
  1017     const CapacityMap* capacity;
  1018     const FlowMap* flow;
  1019   public:
  1020     ResForwardFilter(/*const Graph& _graph, */
  1021 		     const CapacityMap& _capacity, const FlowMap& _flow) :
  1022       /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
  1023     ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
  1024     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
  1025     void setFlow(const FlowMap& _flow) { flow=&_flow; }
  1026     bool operator[](const typename Graph::Edge& e) const {
  1027       return (Number((*flow)[e]) < Number((*capacity)[e]));
  1028     }
  1029   };
  1030 
  1031   template<typename Graph, typename Number,
  1032 	   typename CapacityMap, typename FlowMap>
  1033   class ResBackwardFilter {
  1034     const CapacityMap* capacity;
  1035     const FlowMap* flow;
  1036   public:
  1037     ResBackwardFilter(/*const Graph& _graph,*/ 
  1038 		      const CapacityMap& _capacity, const FlowMap& _flow) :
  1039       /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
  1040     ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
  1041     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
  1042     void setFlow(const FlowMap& _flow) { flow=&_flow; }
  1043     bool operator[](const typename Graph::Edge& e) const {
  1044       return (Number(0) < Number((*flow)[e]));
  1045     }
  1046   };
  1047 
  1048   
  1049   /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
  1050 
  1051   An adaptor for composing the residual graph for directed flow and circulation problems. 
  1052   Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a 
  1053   number type. Let moreover 
  1054   \f$f,c:A\to F\f$, be functions on the edge-set. 
  1055   In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow 
  1056   and \f$c\f$ for a capacity function.   
  1057   Suppose that a graph instange \c g of type 
  1058   \c ListGraph implements \f$G\f$.
  1059   \code
  1060   ListGraph g;
  1061   \endcode
  1062   Then RevGraphAdaptor implements the graph structure with node-set 
  1063   \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where 
  1064   \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and 
  1065   \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$, 
  1066   i.e. the so called residual graph. 
  1067   When we take the union \f$A_{forward}\cup A_{backward}\f$, 
  1068   multilicities are counted, i.e. if an edge is in both 
  1069   \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it 
  1070   appears twice. 
  1071   The following code shows how 
  1072   such an instance can be constructed.
  1073   \code
  1074   typedef ListGraph Graph;
  1075   Graph::EdgeMap<int> f(g);
  1076   Graph::EdgeMap<int> c(g);
  1077   ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
  1078   \endcode
  1079   \author Marton Makai
  1080   */
  1081   template<typename Graph, typename Number, 
  1082 	   typename CapacityMap, typename FlowMap>
  1083   class ResGraphAdaptor : 
  1084     public SubBidirGraphAdaptor< 
  1085     Graph, 
  1086     ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
  1087     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
  1088   public:
  1089     typedef SubBidirGraphAdaptor< 
  1090       Graph, 
  1091       ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
  1092       ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
  1093   protected:
  1094     const CapacityMap* capacity;
  1095     FlowMap* flow;
  1096     ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
  1097     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
  1098     ResGraphAdaptor() : Parent(), 
  1099  			capacity(0), flow(0) { }
  1100     void setCapacityMap(const CapacityMap& _capacity) {
  1101       capacity=&_capacity;
  1102       forward_filter.setCapacity(_capacity);
  1103       backward_filter.setCapacity(_capacity);
  1104     }
  1105     void setFlowMap(FlowMap& _flow) {
  1106       flow=&_flow;
  1107       forward_filter.setFlow(_flow);
  1108       backward_filter.setFlow(_flow);
  1109     }
  1110   public:
  1111     ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity, 
  1112 		       FlowMap& _flow) : 
  1113       Parent(), capacity(&_capacity), flow(&_flow), 
  1114       forward_filter(/*_graph,*/ _capacity, _flow), 
  1115       backward_filter(/*_graph,*/ _capacity, _flow) {
  1116       Parent::setGraph(_graph);
  1117       Parent::setForwardFilterMap(forward_filter);
  1118       Parent::setBackwardFilterMap(backward_filter);
  1119     }
  1120 
  1121     typedef typename Parent::Edge Edge;
  1122 
  1123     void augment(const Edge& e, Number a) const {
  1124       if (Parent::forward(e))  
  1125 	flow->set(e, (*flow)[e]+a);
  1126       else  
  1127 	flow->set(e, (*flow)[e]-a);
  1128     }
  1129 
  1130     /// \brief Residual capacity map.
  1131     ///
  1132     /// In generic residual graphs the residual capacity can be obtained 
  1133     /// as a map. 
  1134     class ResCap {
  1135     protected:
  1136       const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
  1137     public:
  1138       typedef Number Value;
  1139       typedef Edge Key;
  1140       ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>& 
  1141 	     _res_graph) : res_graph(&_res_graph) { }
  1142       Number operator[](const Edge& e) const { 
  1143 	if (res_graph->forward(e)) 
  1144 	  return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e]; 
  1145 	else 
  1146 	  return (*(res_graph->flow))[e]; 
  1147       }
  1148     };
  1149 
  1150     //    KEEP_MAPS(Parent, ResGraphAdaptor);
  1151   };
  1152 
  1153 
  1154 
  1155   template <typename _Graph, typename FirstOutEdgesMap>
  1156   class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
  1157   public:
  1158     typedef _Graph Graph;
  1159     typedef GraphAdaptorBase<_Graph> Parent;
  1160   protected:
  1161     FirstOutEdgesMap* first_out_edges;
  1162     ErasingFirstGraphAdaptorBase() : Parent(), 
  1163 				     first_out_edges(0) { }
  1164 
  1165     void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
  1166       first_out_edges=&_first_out_edges;
  1167     }
  1168 
  1169   public:
  1170 
  1171     typedef typename Parent::Node Node;
  1172     typedef typename Parent::Edge Edge;
  1173 
  1174     void firstOut(Edge& i, const Node& n) const { 
  1175       i=(*first_out_edges)[n];
  1176     }
  1177 
  1178     void erase(const Edge& e) const {
  1179       Node n=source(e);
  1180       Edge f=e;
  1181       Parent::nextOut(f);
  1182       first_out_edges->set(n, f);
  1183     }    
  1184   };
  1185 
  1186 
  1187   /// For blocking flows.
  1188 
  1189   ///\warning Graph adaptors are in even more experimental state than the other
  1190   ///parts of the lib. Use them at you own risk.
  1191   ///
  1192   /// This graph adaptor is used for on-the-fly 
  1193   /// Dinits blocking flow computations.
  1194   /// For each node, an out-edge is stored which is used when the 
  1195   /// \code 
  1196   /// OutEdgeIt& first(OutEdgeIt&, const Node&)
  1197   /// \endcode
  1198   /// is called. 
  1199   ///
  1200   /// \author Marton Makai
  1201   template <typename _Graph, typename FirstOutEdgesMap>
  1202   class ErasingFirstGraphAdaptor : 
  1203     public IterableGraphExtender<
  1204     ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
  1205   public:
  1206     typedef _Graph Graph;
  1207     typedef IterableGraphExtender<
  1208       ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
  1209     ErasingFirstGraphAdaptor(Graph& _graph, 
  1210 			     FirstOutEdgesMap& _first_out_edges) { 
  1211       setGraph(_graph);
  1212       setFirstOutEdgesMap(_first_out_edges);
  1213     } 
  1214 
  1215   };
  1216 
  1217   template <typename _Graph>
  1218   class NewEdgeSetAdaptorBase {
  1219   public:
  1220 
  1221     typedef _Graph Graph;
  1222     typedef typename Graph::Node Node;
  1223     typedef typename Graph::NodeIt NodeIt;
  1224 
  1225   protected:
  1226 
  1227     struct NodeT {
  1228       int first_out, first_in;
  1229       NodeT() : first_out(-1), first_in(-1) {}
  1230     };
  1231     
  1232     class NodesImpl : protected Graph::template NodeMap<NodeT> {
  1233 
  1234       typedef typename Graph::template NodeMap<NodeT> Parent;
  1235       typedef NewEdgeSetAdaptorBase<Graph> Adaptor;
  1236 
  1237       Adaptor& adaptor;
  1238 
  1239     public:
  1240 
  1241       NodesImpl(Adaptor& _adaptor, const Graph& _graph) 
  1242 	: Parent(_graph), adaptor(_adaptor) {}
  1243 
  1244       virtual ~NodesImpl() {}
  1245 
  1246       virtual void build() {
  1247 	Parent::build();
  1248       }
  1249 
  1250       virtual void clear() {
  1251 	adaptor._clear();
  1252 	Parent::clear();
  1253       }
  1254       
  1255       virtual void add(const Node& node) {
  1256 	Parent::add(node);
  1257 	adaptor._add(node);
  1258       }
  1259       
  1260       virtual void erase(const Node& node) {
  1261 	adaptor._erase(node);
  1262 	Parent::erase(node);
  1263       }
  1264 
  1265       NodeT& operator[](const Node& node) {
  1266 	return Parent::operator[](node);
  1267       }
  1268 
  1269       const NodeT& operator[](const Node& node) const {
  1270 	return Parent::operator[](node);
  1271       }
  1272       
  1273     };
  1274 
  1275     NodesImpl* nodes;
  1276 
  1277     struct EdgeT {
  1278       Node source, target;
  1279       int next_out, next_in;
  1280       int prev_out, prev_in;
  1281       EdgeT() : prev_out(-1), prev_in(-1) {}
  1282     };
  1283 
  1284     std::vector<EdgeT> edges;
  1285 
  1286     int first_edge;
  1287     int first_free_edge;
  1288 
  1289     virtual void _clear() = 0;
  1290     virtual void _add(const Node& node) = 0;
  1291     virtual void _erase(const Node& node) = 0;
  1292     
  1293     const Graph* graph;
  1294 
  1295     void initalize(const Graph& _graph, NodesImpl& _nodes) {
  1296       graph = &_graph;
  1297       nodes = &_nodes;
  1298     }
  1299     
  1300   public:
  1301 
  1302     class Edge {
  1303       friend class NewEdgeSetAdaptorBase<Graph>;
  1304     protected:
  1305       Edge(int _id) : id(_id) {}
  1306       int id;
  1307     public:
  1308       Edge() {}
  1309       Edge(Invalid) : id(-1) {}
  1310       bool operator==(const Edge& edge) const { return id == edge.id; }
  1311       bool operator!=(const Edge& edge) const { return id != edge.id; }
  1312       bool operator<(const Edge& edge) const { return id < edge.id; }
  1313     };
  1314 
  1315     NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {} 
  1316     virtual ~NewEdgeSetAdaptorBase() {}
  1317 
  1318     Edge addEdge(const Node& source, const Node& target) {
  1319       int n;
  1320       if (first_free_edge == -1) {
  1321 	n = edges.size();
  1322 	edges.push_back(EdgeT());
  1323       } else {
  1324 	n = first_free_edge;
  1325 	first_free_edge = edges[first_free_edge].next_in;
  1326       }
  1327       edges[n].next_in = (*nodes)[target].first_in;
  1328       (*nodes)[target].first_in = n;
  1329       edges[n].next_out = (*nodes)[source].first_out;
  1330       (*nodes)[source].first_out = n;
  1331       edges[n].source = source;
  1332       edges[n].target = target;
  1333       return Edge(n);
  1334     }
  1335 
  1336     void erase(const Edge& edge) {
  1337       int n = edge.id;
  1338       if (edges[n].prev_in != -1) {
  1339 	edges[edges[n].prev_in].next_in = edges[n].next_in;
  1340       } else {
  1341 	(*nodes)[edges[n].target].first_in = edges[n].next_in;
  1342       }
  1343       if (edges[n].next_in != -1) {
  1344 	edges[edges[n].next_in].prev_in = edges[n].prev_in;
  1345       }
  1346 
  1347       if (edges[n].prev_out != -1) {
  1348 	edges[edges[n].prev_out].next_out = edges[n].next_out;
  1349       } else {
  1350 	(*nodes)[edges[n].source].first_out = edges[n].next_out;
  1351       }
  1352       if (edges[n].next_out != -1) {
  1353 	edges[edges[n].next_out].prev_out = edges[n].prev_out;
  1354       }
  1355            
  1356     }
  1357 
  1358     void first(Node& node) const {
  1359       graph->first(node);
  1360     }
  1361 
  1362     void next(Node& node) const {
  1363       graph->next(node);
  1364     }
  1365 
  1366     void first(Edge& edge) const {
  1367       Node node;
  1368       for (first(node); node != INVALID && (*nodes)[node].first_in == -1; 
  1369 	   next(node));
  1370       edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
  1371     }
  1372 
  1373     void next(Edge& edge) const {
  1374       if (edges[edge.id].next_in != -1) {
  1375 	edge.id = edges[edge.id].next_in;
  1376       } else {
  1377 	Node node = edges[edge.id].target;
  1378 	for (next(node); node != INVALID && (*nodes)[node].first_in == -1; 
  1379 	     next(node));
  1380 	edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
  1381       }      
  1382     }
  1383 
  1384     void firstOut(Edge& edge, const Node& node) const {
  1385       edge.id = (*nodes)[node].first_out;    
  1386     }
  1387     
  1388     void nextOut(Edge& edge) const {
  1389       edge.id = edges[edge.id].next_out;        
  1390     }
  1391 
  1392     void firstIn(Edge& edge, const Node& node) const {
  1393       edge.id = (*nodes)[node].first_in;          
  1394     }
  1395 
  1396     void nextIn(Edge& edge) const {
  1397       edge.id = edges[edge.id].next_in;    
  1398     }
  1399 
  1400     int id(const Node& node) const { return graph->id(node); }
  1401     int id(const Edge& edge) const { return edge.id; }
  1402 
  1403     Node fromId(int id, Node) const { return graph->fromId(id, Node()); }
  1404     Edge fromId(int id, Edge) const { return Edge(id); }
  1405 
  1406     int maxId(Node) const { return graph->maxId(Node()); };
  1407     int maxId(Edge) const { return edges.size() - 1; }
  1408 
  1409     Node source(const Edge& edge) const { return edges[edge.id].source;}
  1410     Node target(const Edge& edge) const { return edges[edge.id].target;}
  1411 
  1412   };
  1413 
  1414 
  1415   /// \brief Graph adaptor using a node set of another graph and an
  1416   /// own edge set.
  1417   ///
  1418   /// This structure can be used to establish another graph over a node set
  1419   /// of an existing one. The node iterator will go through the nodes of the
  1420   /// original graph.
  1421   ///
  1422   /// \param _Graph The type of the graph which shares its node set with 
  1423   /// this class. Its interface must conform to the \ref concept::StaticGraph
  1424   /// "StaticGraph" concept.
  1425   ///
  1426   /// In the edge extension and removing it conforms to the 
  1427   /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
  1428   template <typename _Graph>
  1429   class NewEdgeSetAdaptor :
  1430     public ErasableGraphExtender<
  1431     ClearableGraphExtender<
  1432     ExtendableGraphExtender<
  1433     MappableGraphExtender<
  1434     IterableGraphExtender<
  1435     AlterableGraphExtender<
  1436     NewEdgeSetAdaptorBase<_Graph> > > > > > > {
  1437 
  1438   public:
  1439 
  1440     typedef ErasableGraphExtender<
  1441       ClearableGraphExtender<
  1442       ExtendableGraphExtender<
  1443       MappableGraphExtender<
  1444       IterableGraphExtender<
  1445       AlterableGraphExtender<
  1446       NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent;
  1447     
  1448 
  1449     typedef typename Parent::Node Node;
  1450     typedef typename Parent::Edge Edge;
  1451 
  1452   private:
  1453 
  1454     virtual void _clear() {
  1455       Parent::edges.clear();
  1456       Parent::first_edge = -1;
  1457       Parent::first_free_edge = -1;
  1458       Parent::getNotifier(Edge()).clear();
  1459       Parent::getNotifier(Node()).clear();
  1460     }
  1461 
  1462     virtual void _add(const Node& node) {
  1463       Parent::getNotifier(Node()).add(node);
  1464     }
  1465 
  1466     virtual void _erase(const Node& node) {
  1467       Edge edge;
  1468       Parent::firstOut(edge, node);
  1469       while (edge != INVALID) {
  1470 	Parent::erase(edge);
  1471 	Parent::firstOut(edge, node);
  1472       }
  1473 
  1474       Parent::firstIn(edge, node);
  1475       while (edge != INVALID) {
  1476 	Parent::erase(edge);
  1477 	Parent::firstIn(edge, node);
  1478       }
  1479       
  1480       Parent::getNotifier(Node()).erase(node);
  1481     }
  1482 
  1483 
  1484     typedef typename Parent::NodesImpl NodesImpl;
  1485 
  1486     NodesImpl nodes;
  1487     
  1488   public:
  1489 
  1490     /// \brief Constructor of the adaptor.
  1491     /// 
  1492     /// Constructor of the adaptor.
  1493     NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
  1494       Parent::initalize(_graph, nodes);
  1495     }
  1496 
  1497     void clear() {
  1498       Parent::getNotifier(Edge()).clear();      
  1499 
  1500       Parent::edges.clear();
  1501       Parent::first_edge = -1;
  1502       Parent::first_free_edge = -1;
  1503     }
  1504     
  1505   };
  1506 
  1507   /// \brief Graph adaptor using a node set of another graph and an
  1508   /// own undir edge set.
  1509   ///
  1510   /// This structure can be used to establish another undirected graph over 
  1511   /// a node set of an existing one. The node iterator will go through the 
  1512   /// nodes of the original graph.
  1513   ///
  1514   /// \param _Graph The type of the graph which shares its node set with 
  1515   /// this class. Its interface must conform to the \ref concept::StaticGraph
  1516   /// "StaticGraph" concept.
  1517   ///
  1518   /// In the edge extension and removing it conforms to the 
  1519   /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
  1520   template <typename _Graph>
  1521   class NewUndirEdgeSetAdaptor :
  1522     public ErasableUndirGraphExtender<
  1523     ClearableUndirGraphExtender<
  1524     ExtendableUndirGraphExtender<
  1525     MappableUndirGraphExtender<
  1526     IterableUndirGraphExtender<
  1527     AlterableUndirGraphExtender<
  1528     UndirGraphExtender<
  1529     NewEdgeSetAdaptorBase<_Graph> > > > > > > > {
  1530 
  1531   public:
  1532 
  1533     typedef ErasableUndirGraphExtender<
  1534       ClearableUndirGraphExtender<
  1535       ExtendableUndirGraphExtender<
  1536       MappableUndirGraphExtender<
  1537       IterableUndirGraphExtender<
  1538       AlterableUndirGraphExtender<
  1539       UndirGraphExtender<
  1540       NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;
  1541     
  1542 
  1543     typedef typename Parent::Node Node;
  1544     typedef typename Parent::Edge Edge;
  1545     typedef typename Parent::UndirEdge UndirEdge;
  1546 
  1547   private:
  1548 
  1549     virtual void _clear() {
  1550       Parent::edges.clear();
  1551       Parent::first_edge = -1;
  1552       Parent::first_free_edge = -1;
  1553       Parent::getNotifier(Edge()).clear();
  1554       Parent::getNotifier(Node()).clear();
  1555     }
  1556 
  1557     virtual void _add(const Node& node) {
  1558       Parent::getNotifier(Node()).add(node);
  1559     }
  1560 
  1561     virtual void _erase(const Node& node) {
  1562       Edge edge;
  1563       Parent::firstOut(edge, node);
  1564       while (edge != INVALID) {
  1565 	Parent::erase(edge);
  1566 	Parent::firstOut(edge, node);
  1567       }
  1568 
  1569       Parent::firstIn(edge, node);
  1570       while (edge != INVALID) {
  1571 	Parent::erase(edge);
  1572 	Parent::firstIn(edge, node);
  1573       }
  1574       
  1575       Parent::getNotifier(Node()).erase(node);
  1576     }
  1577 
  1578     typedef typename Parent::NodesImpl NodesImpl;
  1579 
  1580     NodesImpl nodes;
  1581     
  1582   public:
  1583 
  1584 
  1585     /// \brief Constructor of the adaptor.
  1586     /// 
  1587     /// Constructor of the adaptor.
  1588     NewUndirEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
  1589       Parent::initalize(_graph, nodes);
  1590     }
  1591 
  1592     void clear() {
  1593       Parent::getNotifier(Edge()).clear();      
  1594       Parent::getNotifier(UndirEdge()).clear();      
  1595 
  1596       Parent::edges.clear();
  1597       Parent::first_edge = -1;
  1598       Parent::first_free_edge = -1;
  1599     }
  1600     
  1601   };
  1602 
  1603   ///@}
  1604 
  1605 } //namespace lemon
  1606 
  1607 #endif //LEMON_GRAPH_ADAPTOR_H
  1608