lemon-0.x: src/lemon/graph_adaptor.h@d2d1f8fa187b

     1 /* -*- C++ -*-

     2  * src/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  */

    17 #ifndef LEMON_GRAPH_ADAPTOR_H

    18 #define LEMON_GRAPH_ADAPTOR_H

    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

    28 #include <lemon/invalid.h>

    29 #include <lemon/maps.h>

    30 #include <lemon/bits/iterable_graph_extender.h>

    31 #include <lemon/bits/undir_graph_extender.h>

    32 #include <iostream>

    34 namespace lemon {

    36   // Graph adaptors

    38   /*!

    39     \addtogroup graph_adaptors

    40     @{

    41    */

    43   /*!

    44     Base type for the Graph Adaptors

    46     \warning Graph adaptors are in even more experimental state than the other

    47     parts of the lib. Use them at you own risk.

    49     This is the base type for most of LEMON graph adaptors.

    50     This class implements a trivial graph adaptor i.e. it only wraps the

    51     functions and types of the graph. The purpose of this class is to

    52     make easier implementing graph adaptors. E.g. if an adaptor is

    53     considered which differs from the wrapped graph only in some of its

    54     functions or types, then it can be derived from GraphAdaptor, and only the

    55     differences should be implemented.

    57     \author Marton Makai

    58   */

    59   template<typename _Graph>

    60   class GraphAdaptorBase {

    61   public:

    62     typedef _Graph Graph;

    63     /// \todo Is it needed?

    64     typedef Graph BaseGraph;

    65     typedef Graph ParentGraph;

    67   protected:

    68     Graph* graph;

    69     GraphAdaptorBase() : graph(0) { }

    70     void setGraph(Graph& _graph) { graph=&_graph; }

    72   public:

    73     GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }

    75     typedef typename Graph::Node Node;

    76     typedef typename Graph::Edge Edge;

    78     void first(Node& i) const { graph->first(i); }

    79     void first(Edge& i) const { graph->first(i); }

    80     void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }

    81     void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }

    83     void next(Node& i) const { graph->next(i); }

    84     void next(Edge& i) const { graph->next(i); }

    85     void nextIn(Edge& i) const { graph->nextIn(i); }

    86     void nextOut(Edge& i) const { graph->nextOut(i); }

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

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

    91     int nodeNum() const { return graph->nodeNum(); }

    92     int edgeNum() const { return graph->edgeNum(); }

    94     Node addNode() const { return Node(graph->addNode()); }

    95     Edge addEdge(const Node& source, const Node& target) const {

    96       return Edge(graph->addEdge(source, target)); }

    98     void erase(const Node& i) const { graph->erase(i); }

    99     void erase(const Edge& i) const { graph->erase(i); }

   101     void clear() const { graph->clear(); }

   103     bool forward(const Edge& e) const { return graph->forward(e); }

   104     bool backward(const Edge& e) const { return graph->backward(e); }

   106     int id(const Node& v) const { return graph->id(v); }

   107     int id(const Edge& e) const { return graph->id(e); }

   109     Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }

   111     template <typename _Value>

   112     class NodeMap : public _Graph::template NodeMap<_Value> {

   113     public:

   114       typedef typename _Graph::template NodeMap<_Value> Parent;

   115       NodeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }

   116       NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)

   117       : Parent(*gw.graph, value) { }

   118     };

   120     template <typename _Value>

   121     class EdgeMap : public _Graph::template EdgeMap<_Value> {

   122     public:

   123       typedef typename _Graph::template EdgeMap<_Value> Parent;

   124       EdgeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }

   125       EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)

   126       : Parent(*gw.graph, value) { }

   127     };

   129   };

   131   template <typename _Graph>

   132   class GraphAdaptor :

   133     public IterableGraphExtender<GraphAdaptorBase<_Graph> > {

   134   public:

   135     typedef _Graph Graph;

   136     typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;

   137   protected:

   138     GraphAdaptor() : Parent() { }

   140   public:

   141     GraphAdaptor(Graph& _graph) { setGraph(_graph); }

   142   };

   144   template <typename _Graph>

   145   class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

   146   public:

   147     typedef _Graph Graph;

   148     typedef GraphAdaptorBase<_Graph> Parent;

   149   protected:

   150     RevGraphAdaptorBase() : Parent() { }

   151   public:

   152     typedef typename Parent::Node Node;

   153     typedef typename Parent::Edge Edge;

   155     //    using Parent::first;

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

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

   159     //    using Parent::next;

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

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

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

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

   165   };

   168   /// A graph adaptor which reverses the orientation of the edges.

   170   ///\warning Graph adaptors are in even more experimental state than the other

   171   ///parts of the lib. Use them at you own risk.

   172   ///

   173   /// Let \f$G=(V, A)\f$ be a directed graph and

   174   /// suppose that a graph instange \c g of type

   175   /// \c ListGraph implements \f$G\f$.

   176   /// \code

   177   /// ListGraph g;

   178   /// \endcode

   179   /// For each directed edge

   180   /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by

   181   /// reversing its orientation.

   182   /// Then RevGraphAdaptor implements the graph structure with node-set

   183   /// \f$V\f$ and edge-set

   184   /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be

   185   /// reversing the orientation of its edges. The following code shows how

   186   /// such an instance can be constructed.

   187   /// \code

   188   /// RevGraphAdaptor<ListGraph> gw(g);

   189   /// \endcode

   190   ///\author Marton Makai

   191   template<typename _Graph>

   192   class RevGraphAdaptor :

   193     public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {

   194   public:

   195     typedef _Graph Graph;

   196     typedef IterableGraphExtender<

   197       RevGraphAdaptorBase<_Graph> > Parent;

   198   protected:

   199     RevGraphAdaptor() { }

   200   public:

   201     RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }

   202   };

   205   template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>

   206   class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

   207   public:

   208     typedef _Graph Graph;

   209     typedef GraphAdaptorBase<_Graph> Parent;

   210   protected:

   211     NodeFilterMap* node_filter_map;

   212     EdgeFilterMap* edge_filter_map;

   213     SubGraphAdaptorBase() : Parent(),

   214 			    node_filter_map(0), edge_filter_map(0) { }

   216     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {

   217       node_filter_map=&_node_filter_map;

   218     }

   219     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {

   220       edge_filter_map=&_edge_filter_map;

   221     }

   223   public:

   224 //     SubGraphAdaptorBase(Graph& _graph,

   225 // 			NodeFilterMap& _node_filter_map,

   226 // 			EdgeFilterMap& _edge_filter_map) :

   227 //       Parent(&_graph),

   228 //       node_filter_map(&node_filter_map),

   229 //       edge_filter_map(&edge_filter_map) { }

   231     typedef typename Parent::Node Node;

   232     typedef typename Parent::Edge Edge;

   234     void first(Node& i) const {

   235       Parent::first(i);

   236       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);

   237     }

   238     void first(Edge& i) const {

   239       Parent::first(i);

   240       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);

   241     }

   242     void firstIn(Edge& i, const Node& n) const {

   243       Parent::firstIn(i, n);

   244       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);

   245     }

   246     void firstOut(Edge& i, const Node& n) const {

   247       Parent::firstOut(i, n);

   248       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);

   249     }

   251     void next(Node& i) const {

   252       Parent::next(i);

   253       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);

   254     }

   255     void next(Edge& i) const {

   256       Parent::next(i);

   257       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);

   258     }

   259     void nextIn(Edge& i) const {

   260       Parent::nextIn(i);

   261       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);

   262     }

   263     void nextOut(Edge& i) const {

   264       Parent::nextOut(i);

   265       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);

   266     }

   268     /// This function hides \c n in the graph, i.e. the iteration

   269     /// jumps over it. This is done by simply setting the value of \c n

   270     /// to be false in the corresponding node-map.

   271     void hide(const Node& n) const { node_filter_map->set(n, false); }

   273     /// This function hides \c e in the graph, i.e. the iteration

   274     /// jumps over it. This is done by simply setting the value of \c e

   275     /// to be false in the corresponding edge-map.

   276     void hide(const Edge& e) const { edge_filter_map->set(e, false); }

   278     /// The value of \c n is set to be true in the node-map which stores

   279     /// hide information. If \c n was hidden previuosly, then it is shown

   280     /// again

   281      void unHide(const Node& n) const { node_filter_map->set(n, true); }

   283     /// The value of \c e is set to be true in the edge-map which stores

   284     /// hide information. If \c e was hidden previuosly, then it is shown

   285     /// again

   286     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }

   288     /// Returns true if \c n is hidden.

   289     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }

   291     /// Returns true if \c n is hidden.

   292     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }

   294     /// \warning This is a linear time operation and works only if s

   295     /// \c Graph::NodeIt is defined.

   296     /// \todo assign tags.

   297     int nodeNum() const {

   298       int i=0;

   299       Node n;

   300       for (first(n); n!=INVALID; next(n)) ++i;

   301       return i;

   302     }

   304     /// \warning This is a linear time operation and works only if

   305     /// \c Graph::EdgeIt is defined.

   306     /// \todo assign tags.

   307     int edgeNum() const {

   308       int i=0;

   309       Edge e;

   310       for (first(e); e!=INVALID; next(e)) ++i;

   311       return i;

   312     }

   315   };

   317   /*! \brief A graph adaptor for hiding nodes and edges from a graph.

   319   \warning Graph adaptors are in even more experimental state than the other

   320   parts of the lib. Use them at you own risk.

   322   SubGraphAdaptor shows the graph with filtered node-set and

   323   edge-set.

   324   Let \f$G=(V, A)\f$ be a directed graph

   325   and suppose that the graph instance \c g of type ListGraph implements

   326   \f$G\f$.

   327   Let moreover \f$b_V\f$ and

   328   \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.

   329   SubGraphAdaptor<...>::NodeIt iterates

   330   on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and

   331   SubGraphAdaptor<...>::EdgeIt iterates

   332   on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,

   333   SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates

   334   only on edges leaving and entering a specific node which have true value.

   336   We have to note that this does not mean that an

   337   induced subgraph is obtained, the node-iterator cares only the filter

   338   on the node-set, and the edge-iterators care only the filter on the

   339   edge-set.

   340   \code

   341   typedef ListGraph Graph;

   342   Graph g;

   343   typedef Graph::Node Node;

   344   typedef Graph::Edge Edge;

   345   Node u=g.addNode(); //node of id 0

   346   Node v=g.addNode(); //node of id 1

   347   Node e=g.addEdge(u, v); //edge of id 0

   348   Node f=g.addEdge(v, u); //edge of id 1

   349   Graph::NodeMap<bool> nm(g, true);

   350   nm.set(u, false);

   351   Graph::EdgeMap<bool> em(g, true);

   352   em.set(e, false);

   353   typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;

   354   SubGW gw(g, nm, em);

   355   for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;

   356   std::cout << ":-)" << std::endl;

   357   for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;

   358   \endcode

   359   The output of the above code is the following.

   360   \code

   361   1

   362   :-)

   363   1

   364   \endcode

   365   Note that \c n is of type \c SubGW::NodeIt, but it can be converted to

   366   \c Graph::Node that is why \c g.id(n) can be applied.

   368   For other examples see also the documentation of NodeSubGraphAdaptor and

   369   EdgeSubGraphAdaptor.

   371   \author Marton Makai

   372   */

   373   template<typename _Graph, typename NodeFilterMap,

   374 	   typename EdgeFilterMap>

   375   class SubGraphAdaptor :

   376     public IterableGraphExtender<

   377     SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {

   378   public:

   379     typedef _Graph Graph;

   380     typedef IterableGraphExtender<

   381       SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;

   382   protected:

   383     SubGraphAdaptor() { }

   384   public:

   385     SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,

   386 		    EdgeFilterMap& _edge_filter_map) {

   387       setGraph(_graph);

   388       setNodeFilterMap(_node_filter_map);

   389       setEdgeFilterMap(_edge_filter_map);

   390     }

   391   };

   395   /*! \brief An adaptor for hiding nodes from a graph.

   397   \warning Graph adaptors are in even more experimental state than the other

   398   parts of the lib. Use them at you own risk.

   400   An adaptor for hiding nodes from a graph.

   401   This adaptor specializes SubGraphAdaptor in the way that only the node-set

   402   can be filtered. Note that this does not mean of considering induced

   403   subgraph, the edge-iterators consider the original edge-set.

   404   \author Marton Makai

   405   */

   406   template<typename Graph, typename NodeFilterMap>

   407   class NodeSubGraphAdaptor :

   408     public SubGraphAdaptor<Graph, NodeFilterMap,

   409 			   ConstMap<typename Graph::Edge,bool> > {

   410   public:

   411     typedef SubGraphAdaptor<Graph, NodeFilterMap,

   412 			    ConstMap<typename Graph::Edge,bool> > Parent;

   413   protected:

   414     ConstMap<typename Graph::Edge, bool> const_true_map;

   415   public:

   416     NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :

   417       Parent(), const_true_map(true) {

   418       Parent::setGraph(_graph);

   419       Parent::setNodeFilterMap(_node_filter_map);

   420       Parent::setEdgeFilterMap(const_true_map);

   421     }

   422   };

   425   /*! \brief An adaptor for hiding edges from a graph.

   427   \warning Graph adaptors are in even more experimental state than the other

   428   parts of the lib. Use them at you own risk.

   430   An adaptor for hiding edges from a graph.

   431   This adaptor specializes SubGraphAdaptor in the way that only the edge-set

   432   can be filtered. The usefulness of this adaptor is demonstrated in the

   433   problem of searching a maximum number of edge-disjoint shortest paths

   434   between

   435   two nodes \c s and \c t. Shortest here means being shortest w.r.t.

   436   non-negative edge-lengths. Note that

   437   the comprehension of the presented solution

   438   need's some elementary knowledge from combinatorial optimization.

   440   If a single shortest path is to be

   441   searched between \c s and \c t, then this can be done easily by

   442   applying the Dijkstra algorithm. What happens, if a maximum number of

   443   edge-disjoint shortest paths is to be computed. It can be proved that an

   444   edge can be in a shortest path if and only if it is tight with respect to

   445   the potential function computed by Dijkstra. Moreover, any path containing

   446   only such edges is a shortest one. Thus we have to compute a maximum number

   447   of edge-disjoint paths between \c s and \c t in the graph which has edge-set

   448   all the tight edges. The computation will be demonstrated on the following

   449   graph, which is read from a dimacs file.

   451   \dot

   452   digraph lemon_dot_example {

   453   node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];

   454   n0 [ label="0 (s)" ];

   455   n1 [ label="1" ];

   456   n2 [ label="2" ];

   457   n3 [ label="3" ];

   458   n4 [ label="4" ];

   459   n5 [ label="5" ];

   460   n6 [ label="6 (t)" ];

   461   edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];

   462   n5 ->  n6 [ label="9, length:4" ];

   463   n4 ->  n6 [ label="8, length:2" ];

   464   n3 ->  n5 [ label="7, length:1" ];

   465   n2 ->  n5 [ label="6, length:3" ];

   466   n2 ->  n6 [ label="5, length:5" ];

   467   n2 ->  n4 [ label="4, length:2" ];

   468   n1 ->  n4 [ label="3, length:3" ];

   469   n0 ->  n3 [ label="2, length:1" ];

   470   n0 ->  n2 [ label="1, length:2" ];

   471   n0 ->  n1 [ label="0, length:3" ];

   472   }

   473   \enddot

   475   \code

   476   Graph g;

   477   Node s, t;

   478   LengthMap length(g);

   480   readDimacs(std::cin, g, length, s, t);

   482   cout << "edges with lengths (of form id, source--length->target): " << endl;

   483   for(EdgeIt e(g); e!=INVALID; ++e)

   484     cout << g.id(e) << ", " << g.id(g.source(e)) << "--"

   485          << length[e] << "->" << g.id(g.target(e)) << endl;

   487   cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;

   488   \endcode

   489   Next, the potential function is computed with Dijkstra.

   490   \code

   491   typedef Dijkstra<Graph, LengthMap> Dijkstra;

   492   Dijkstra dijkstra(g, length);

   493   dijkstra.run(s);

   494   \endcode

   495   Next, we consrtruct a map which filters the edge-set to the tight edges.

   496   \code

   497   typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>

   498     TightEdgeFilter;

   499   TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);

   501   typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;

   502   SubGW gw(g, tight_edge_filter);

   503   \endcode

   504   Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed

   505   with a max flow algorithm Preflow.

   506   \code

   507   ConstMap<Edge, int> const_1_map(1);

   508   Graph::EdgeMap<int> flow(g, 0);

   510   Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >

   511     preflow(gw, s, t, const_1_map, flow);

   512   preflow.run();

   513   \endcode

   514   Last, the output is:

   515   \code

   516   cout << "maximum number of edge-disjoint shortest path: "

   517        << preflow.flowValue() << endl;

   518   cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "

   519        << endl;

   520   for(EdgeIt e(g); e!=INVALID; ++e)

   521     if (flow[e])

   522       cout << " " << g.id(g.source(e)) << "--"

   523 	   << length[e] << "->" << g.id(g.target(e)) << endl;

   524   \endcode

   525   The program has the following (expected :-)) output:

   526   \code

   527   edges with lengths (of form id, source--length->target):

   528    9, 5--4->6

   529    8, 4--2->6

   530    7, 3--1->5

   531    6, 2--3->5

   532    5, 2--5->6

   533    4, 2--2->4

   534    3, 1--3->4

   535    2, 0--1->3

   536    1, 0--2->2

   537    0, 0--3->1

   538   s: 0 t: 6

   539   maximum number of edge-disjoint shortest path: 2

   540   edges of the maximum number of edge-disjoint shortest s-t paths:

   541    9, 5--4->6

   542    8, 4--2->6

   543    7, 3--1->5

   544    4, 2--2->4

   545    2, 0--1->3

   546    1, 0--2->2

   547   \endcode

   549   \author Marton Makai

   550   */

   551   template<typename Graph, typename EdgeFilterMap>

   552   class EdgeSubGraphAdaptor :

   553     public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,

   554 			   EdgeFilterMap> {

   555   public:

   556     typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,

   557 			    EdgeFilterMap> Parent;

   558   protected:

   559     ConstMap<typename Graph::Node, bool> const_true_map;

   560   public:

   561     EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :

   562       Parent(), const_true_map(true) {

   563       Parent::setGraph(_graph);

   564       Parent::setNodeFilterMap(const_true_map);

   565       Parent::setEdgeFilterMap(_edge_filter_map);

   566     }

   567   };

   569   template <typename _Graph>

   570   class UndirGraphAdaptorBase :

   571     public UndirGraphExtender<GraphAdaptorBase<_Graph> > {

   572   public:

   573     typedef _Graph Graph;

   574     typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;

   575   protected:

   576     UndirGraphAdaptorBase() : Parent() { }

   577   public:

   578     typedef typename Parent::UndirEdge UndirEdge;

   579     typedef typename Parent::Edge Edge;

   581     /// \bug Why cant an edge say that it is forward or not???

   582     /// By this, a pointer to the graph have to be stored

   583     /// The implementation

   584     template <typename T>

   585     class EdgeMap {

   586     protected:

   587       const UndirGraphAdaptorBase<_Graph>* g;

   588       template <typename TT> friend class EdgeMap;

   589       typename _Graph::template EdgeMap<T> forward_map, backward_map;

   590     public:

   591       typedef T Value;

   592       typedef Edge Key;

   594       EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),

   595 	forward_map(*(g->graph)), backward_map(*(g->graph)) { }

   597       EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),

   598 	forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }

   600       void set(Edge e, T a) {

   601 	if (g->forward(e))

   602 	  forward_map.set(e, a);

   603 	else

   604 	  backward_map.set(e, a);

   605       }

   607       T operator[](Edge e) const {

   608 	if (g->forward(e))

   609 	  return forward_map[e];

   610 	else

   611 	  return backward_map[e];

   612       }

   613     };

   615     template <typename T>

   616     class UndirEdgeMap {

   617       template <typename TT> friend class UndirEdgeMap;

   618       typename _Graph::template EdgeMap<T> map;

   619     public:

   620       typedef T Value;

   621       typedef UndirEdge Key;

   623       UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :

   624 	map(*(g.graph)) { }

   626       UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :

   627 	map(*(g.graph), a) { }

   629       void set(UndirEdge e, T a) {

   630 	map.set(e, a);

   631       }

   633       T operator[](UndirEdge e) const {

   634 	return map[e];

   635       }

   636     };

   638   };

   640   /// \brief An undirected graph is made from a directed graph by an adaptor

   641   ///

   642   /// Undocumented, untested!!!

   643   /// If somebody knows nice demo application, let's polulate it.

   644   ///

   645   /// \author Marton Makai

   646   template<typename _Graph>

   647   class UndirGraphAdaptor :

   648     public IterableUndirGraphExtender<

   649     UndirGraphAdaptorBase<_Graph> > {

   650   public:

   651     typedef _Graph Graph;

   652     typedef IterableUndirGraphExtender<

   653       UndirGraphAdaptorBase<_Graph> > Parent;

   654   protected:

   655     UndirGraphAdaptor() { }

   656   public:

   657     UndirGraphAdaptor(_Graph& _graph) {

   658       setGraph(_graph);

   659     }

   660   };

   663   template <typename _Graph,

   664 	    typename ForwardFilterMap, typename BackwardFilterMap>

   665   class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

   666   public:

   667     typedef _Graph Graph;

   668     typedef GraphAdaptorBase<_Graph> Parent;

   669   protected:

   670     ForwardFilterMap* forward_filter;

   671     BackwardFilterMap* backward_filter;

   672     SubBidirGraphAdaptorBase() : Parent(),

   673 				 forward_filter(0), backward_filter(0) { }

   675     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {

   676       forward_filter=&_forward_filter;

   677     }

   678     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {

   679       backward_filter=&_backward_filter;

   680     }

   682   public:

   683 //     SubGraphAdaptorBase(Graph& _graph,

   684 // 			NodeFilterMap& _node_filter_map,

   685 // 			EdgeFilterMap& _edge_filter_map) :

   686 //       Parent(&_graph),

   687 //       node_filter_map(&node_filter_map),

   688 //       edge_filter_map(&edge_filter_map) { }

   690     typedef typename Parent::Node Node;

   691     typedef typename _Graph::Edge GraphEdge;

   692     template <typename T> class EdgeMap;

   693     /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from

   694     /// _Graph::Edge. It contains an extra bool flag which is true

   695     /// if and only if the

   696     /// edge is the backward version of the original edge.

   697     class Edge : public _Graph::Edge {

   698       friend class SubBidirGraphAdaptorBase<

   699 	Graph, ForwardFilterMap, BackwardFilterMap>;

   700       template<typename T> friend class EdgeMap;

   701     protected:

   702       bool backward; //true, iff backward

   703     public:

   704       Edge() { }

   705       /// \todo =false is needed, or causes problems?

   706       /// If \c _backward is false, then we get an edge corresponding to the

   707       /// original one, otherwise its oppositely directed pair is obtained.

   708       Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :

   709 	_Graph::Edge(e), backward(_backward) { }

   710       Edge(Invalid i) : _Graph::Edge(i), backward(true) { }

   711       bool operator==(const Edge& v) const {

   712 	return (this->backward==v.backward &&

   713 		static_cast<typename _Graph::Edge>(*this)==

   714 		static_cast<typename _Graph::Edge>(v));

   715       }

   716       bool operator!=(const Edge& v) const {

   717 	return (this->backward!=v.backward ||

   718 		static_cast<typename _Graph::Edge>(*this)!=

   719 		static_cast<typename _Graph::Edge>(v));

   720       }

   721     };

   723     void first(Node& i) const {

   724       Parent::first(i);

   725     }

   727     void first(Edge& i) const {

   728       Parent::first(i);

   729       i.backward=false;

   730       while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   731 	     !(*forward_filter)[i]) Parent::next(i);

   732       if (*static_cast<GraphEdge*>(&i)==INVALID) {

   733 	Parent::first(i);

   734 	i.backward=true;

   735 	while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   736 	       !(*backward_filter)[i]) Parent::next(i);

   737       }

   738     }

   740     void firstIn(Edge& i, const Node& n) const {

   741       Parent::firstIn(i, n);

   742       i.backward=false;

   743       while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   744 	     !(*forward_filter)[i]) Parent::nextIn(i);

   745       if (*static_cast<GraphEdge*>(&i)==INVALID) {

   746 	Parent::firstOut(i, n);

   747 	i.backward=true;

   748 	while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   749 	       !(*backward_filter)[i]) Parent::nextOut(i);

   750       }

   751     }

   753     void firstOut(Edge& i, const Node& n) const {

   754       Parent::firstOut(i, n);

   755       i.backward=false;

   756       while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   757 	     !(*forward_filter)[i]) Parent::nextOut(i);

   758       if (*static_cast<GraphEdge*>(&i)==INVALID) {

   759 	Parent::firstIn(i, n);

   760 	i.backward=true;

   761 	while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   762 	       !(*backward_filter)[i]) Parent::nextIn(i);

   763       }

   764     }

   766     void next(Node& i) const {

   767       Parent::next(i);

   768     }

   770     void next(Edge& i) const {

   771       if (!(i.backward)) {

   772 	Parent::next(i);

   773 	while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   774 	       !(*forward_filter)[i]) Parent::next(i);

   775 	if (*static_cast<GraphEdge*>(&i)==INVALID) {

   776 	  Parent::first(i);

   777 	  i.backward=true;

   778 	  while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   779 		 !(*backward_filter)[i]) Parent::next(i);

   780 	}

   781       } else {

   782 	Parent::next(i);

   783 	while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   784 	       !(*backward_filter)[i]) Parent::next(i);

   785       }

   786     }

   788     void nextIn(Edge& i) const {

   789       if (!(i.backward)) {

   790 	Node n=Parent::target(i);

   791 	Parent::nextIn(i);

   792 	while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   793 	       !(*forward_filter)[i]) Parent::nextIn(i);

   794 	if (*static_cast<GraphEdge*>(&i)==INVALID) {

   795 	  Parent::firstOut(i, n);

   796 	  i.backward=true;

   797 	  while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   798 		 !(*backward_filter)[i]) Parent::nextOut(i);

   799 	}

   800       } else {

   801 	Parent::nextOut(i);

   802 	while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   803 	       !(*backward_filter)[i]) Parent::nextOut(i);

   804       }

   805     }

   807     void nextOut(Edge& i) const {

   808       if (!(i.backward)) {

   809 	Node n=Parent::source(i);

   810 	Parent::nextOut(i);

   811 	while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   812 	       !(*forward_filter)[i]) Parent::nextOut(i);

   813 	if (*static_cast<GraphEdge*>(&i)==INVALID) {

   814 	  Parent::firstIn(i, n);

   815 	  i.backward=true;

   816 	  while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   817 		 !(*backward_filter)[i]) Parent::nextIn(i);

   818 	}

   819       } else {

   820 	Parent::nextIn(i);

   821 	while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   822 	       !(*backward_filter)[i]) Parent::nextIn(i);

   823       }

   824     }

   826     Node source(Edge e) const {

   827       return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }

   828     Node target(Edge e) const {

   829       return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }

   831     /// Gives back the opposite edge.

   832     Edge opposite(const Edge& e) const {

   833       Edge f=e;

   834       f.backward=!f.backward;

   835       return f;

   836     }

   838     /// \warning This is a linear time operation and works only if

   839     /// \c Graph::EdgeIt is defined.

   840     /// \todo hmm

   841     int edgeNum() const {

   842       int i=0;

   843       Edge e;

   844       for (first(e); e!=INVALID; next(e)) ++i;

   845       return i;

   846     }

   848     bool forward(const Edge& e) const { return !e.backward; }

   849     bool backward(const Edge& e) const { return e.backward; }

   851     template <typename T>

   852     /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two

   853     /// _Graph::EdgeMap one for the forward edges and

   854     /// one for the backward edges.

   855     class EdgeMap {

   856       template <typename TT> friend class EdgeMap;

   857       typename _Graph::template EdgeMap<T> forward_map, backward_map;

   858     public:

   859       typedef T Value;

   860       typedef Edge Key;

   862       EdgeMap(const SubBidirGraphAdaptorBase<_Graph,

   863 	      ForwardFilterMap, BackwardFilterMap>& g) :

   864 	forward_map(*(g.graph)), backward_map(*(g.graph)) { }

   866       EdgeMap(const SubBidirGraphAdaptorBase<_Graph,

   867 	      ForwardFilterMap, BackwardFilterMap>& g, T a) :

   868 	forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }

   870       void set(Edge e, T a) {

   871 	if (!e.backward)

   872 	  forward_map.set(e, a);

   873 	else

   874 	  backward_map.set(e, a);

   875       }

   877 //       typename _Graph::template EdgeMap<T>::ConstReference

   878 //       operator[](Edge e) const {

   879 // 	if (!e.backward)

   880 // 	  return forward_map[e];

   881 // 	else

   882 // 	  return backward_map[e];

   883 //       }

   885 //      typename _Graph::template EdgeMap<T>::Reference

   886       T operator[](Edge e) const {

   887 	if (!e.backward)

   888 	  return forward_map[e];

   889 	else

   890 	  return backward_map[e];

   891       }

   893       void update() {

   894 	forward_map.update();

   895 	backward_map.update();

   896       }

   897     };

   899   };

   902   ///\brief An adaptor for composing a subgraph of a

   903   /// bidirected graph made from a directed one.

   904   ///

   905   /// An adaptor for composing a subgraph of a

   906   /// bidirected graph made from a directed one.

   907   ///

   908   ///\warning Graph adaptors are in even more experimental state than the other

   909   ///parts of the lib. Use them at you own risk.

   910   ///

   911   /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge

   912   /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by

   913   /// reversing its orientation. We are given moreover two bool valued

   914   /// maps on the edge-set,

   915   /// \f$forward\_filter\f$, and \f$backward\_filter\f$.

   916   /// SubBidirGraphAdaptor implements the graph structure with node-set

   917   /// \f$V\f$ and edge-set

   918   /// \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$.

   919   /// The purpose of writing + instead of union is because parallel

   920   /// edges can arise. (Similarly, antiparallel edges also can arise).

   921   /// In other words, a subgraph of the bidirected graph obtained, which

   922   /// is given by orienting the edges of the original graph in both directions.

   923   /// As the oppositely directed edges are logically different,

   924   /// the maps are able to attach different values for them.

   925   ///

   926   /// An example for such a construction is \c RevGraphAdaptor where the

   927   /// forward_filter is everywhere false and the backward_filter is

   928   /// everywhere true. We note that for sake of efficiency,

   929   /// \c RevGraphAdaptor is implemented in a different way.

   930   /// But BidirGraphAdaptor is obtained from

   931   /// SubBidirGraphAdaptor by considering everywhere true

   932   /// valued maps both for forward_filter and backward_filter.

   933   ///

   934   /// The most important application of SubBidirGraphAdaptor

   935   /// is ResGraphAdaptor, which stands for the residual graph in directed

   936   /// flow and circulation problems.

   937   /// As adaptors usually, the SubBidirGraphAdaptor implements the

   938   /// above mentioned graph structure without its physical storage,

   939   /// that is the whole stuff is stored in constant memory.

   940   template<typename _Graph,

   941 	   typename ForwardFilterMap, typename BackwardFilterMap>

   942   class SubBidirGraphAdaptor :

   943     public IterableGraphExtender<

   944     SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {

   945   public:

   946     typedef _Graph Graph;

   947     typedef IterableGraphExtender<

   948       SubBidirGraphAdaptorBase<

   949       _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;

   950   protected:

   951     SubBidirGraphAdaptor() { }

   952   public:

   953     SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,

   954 			 BackwardFilterMap& _backward_filter) {

   955       setGraph(_graph);

   956       setForwardFilterMap(_forward_filter);

   957       setBackwardFilterMap(_backward_filter);

   958     }

   959   };

   963   ///\brief An adaptor for composing bidirected graph from a directed one.

   964   ///

   965   ///\warning Graph adaptors are in even more experimental state than the other

   966   ///parts of the lib. Use them at you own risk.

   967   ///

   968   /// An adaptor for composing bidirected graph from a directed one.

   969   /// A bidirected graph is composed over the directed one without physical

   970   /// storage. As the oppositely directed edges are logically different ones

   971   /// the maps are able to attach different values for them.

   972   template<typename Graph>

   973   class BidirGraphAdaptor :

   974     public SubBidirGraphAdaptor<

   975     Graph,

   976     ConstMap<typename Graph::Edge, bool>,

   977     ConstMap<typename Graph::Edge, bool> > {

   978   public:

   979     typedef  SubBidirGraphAdaptor<

   980       Graph,

   981       ConstMap<typename Graph::Edge, bool>,

   982       ConstMap<typename Graph::Edge, bool> > Parent;

   983   protected:

   984     ConstMap<typename Graph::Edge, bool> cm;

   986     BidirGraphAdaptor() : Parent(), cm(true) {

   987       Parent::setForwardFilterMap(cm);

   988       Parent::setBackwardFilterMap(cm);

   989     }

   990   public:

   991     BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {

   992       Parent::setGraph(_graph);

   993       Parent::setForwardFilterMap(cm);

   994       Parent::setBackwardFilterMap(cm);

   995     }

   997     int edgeNum() const {

   998       return 2*this->graph->edgeNum();

   999     }

  1000     //    KEEP_MAPS(Parent, BidirGraphAdaptor);

  1001   };

  1004   template<typename Graph, typename Number,

  1005 	   typename CapacityMap, typename FlowMap>

  1006   class ResForwardFilter {

  1007     //    const Graph* graph;

  1008     const CapacityMap* capacity;

  1009     const FlowMap* flow;

  1010   public:

  1011     ResForwardFilter(/*const Graph& _graph, */

  1012 		     const CapacityMap& _capacity, const FlowMap& _flow) :

  1013       /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }

  1014     ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }

  1015     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }

  1016     void setFlow(const FlowMap& _flow) { flow=&_flow; }

  1017     bool operator[](const typename Graph::Edge& e) const {

  1018       return (Number((*flow)[e]) < Number((*capacity)[e]));

  1019     }

  1020   };

  1022   template<typename Graph, typename Number,

  1023 	   typename CapacityMap, typename FlowMap>

  1024   class ResBackwardFilter {

  1025     const CapacityMap* capacity;

  1026     const FlowMap* flow;

  1027   public:

  1028     ResBackwardFilter(/*const Graph& _graph,*/

  1029 		      const CapacityMap& _capacity, const FlowMap& _flow) :

  1030       /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }

  1031     ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }

  1032     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }

  1033     void setFlow(const FlowMap& _flow) { flow=&_flow; }

  1034     bool operator[](const typename Graph::Edge& e) const {

  1035       return (Number(0) < Number((*flow)[e]));

  1036     }

  1037   };

  1040   /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.

  1042   An adaptor for composing the residual graph for directed flow and circulation problems.

  1043   Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a

  1044   number type. Let moreover

  1045   \f$f,c:A\to F\f$, be functions on the edge-set.

  1046   In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow

  1047   and \f$c\f$ for a capacity function.

  1048   Suppose that a graph instange \c g of type

  1049   \c ListGraph implements \f$G\f$.

  1050   \code

  1051   ListGraph g;

  1052   \endcode

  1053   Then RevGraphAdaptor implements the graph structure with node-set

  1054   \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where

  1055   \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and

  1056   \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,

  1057   i.e. the so called residual graph.

  1058   When we take the union \f$A_{forward}\cup A_{backward}\f$,

  1059   multilicities are counted, i.e. if an edge is in both

  1060   \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it

  1061   appears twice.

  1062   The following code shows how

  1063   such an instance can be constructed.

  1064   \code

  1065   typedef ListGraph Graph;

  1066   Graph::EdgeMap<int> f(g);

  1067   Graph::EdgeMap<int> c(g);

  1068   ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);

  1069   \endcode

  1070   \author Marton Makai

  1071   */

  1072   template<typename Graph, typename Number,

  1073 	   typename CapacityMap, typename FlowMap>

  1074   class ResGraphAdaptor :

  1075     public SubBidirGraphAdaptor<

  1076     Graph,

  1077     ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,

  1078     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {

  1079   public:

  1080     typedef SubBidirGraphAdaptor<

  1081       Graph,

  1082       ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,

  1083       ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;

  1084   protected:

  1085     const CapacityMap* capacity;

  1086     FlowMap* flow;

  1087     ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;

  1088     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;

  1089     ResGraphAdaptor() : Parent(),

  1090  			capacity(0), flow(0) { }

  1091     void setCapacityMap(const CapacityMap& _capacity) {

  1092       capacity=&_capacity;

  1093       forward_filter.setCapacity(_capacity);

  1094       backward_filter.setCapacity(_capacity);

  1095     }

  1096     void setFlowMap(FlowMap& _flow) {

  1097       flow=&_flow;

  1098       forward_filter.setFlow(_flow);

  1099       backward_filter.setFlow(_flow);

  1100     }

  1101   public:

  1102     ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,

  1103 		       FlowMap& _flow) :

  1104       Parent(), capacity(&_capacity), flow(&_flow),

  1105       forward_filter(/*_graph,*/ _capacity, _flow),

  1106       backward_filter(/*_graph,*/ _capacity, _flow) {

  1107       Parent::setGraph(_graph);

  1108       Parent::setForwardFilterMap(forward_filter);

  1109       Parent::setBackwardFilterMap(backward_filter);

  1110     }

  1112     typedef typename Parent::Edge Edge;

  1114     void augment(const Edge& e, Number a) const {

  1115       if (Parent::forward(e))

  1116 	flow->set(e, (*flow)[e]+a);

  1117       else

  1118 	flow->set(e, (*flow)[e]-a);

  1119     }

  1121     /// \brief Residual capacity map.

  1122     ///

  1123     /// In generic residual graphs the residual capacity can be obtained

  1124     /// as a map.

  1125     class ResCap {

  1126     protected:

  1127       const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;

  1128     public:

  1129       typedef Number Value;

  1130       typedef Edge Key;

  1131       ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&

  1132 	     _res_graph) : res_graph(&_res_graph) { }

  1133       Number operator[](const Edge& e) const {

  1134 	if (res_graph->forward(e))

  1135 	  return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];

  1136 	else

  1137 	  return (*(res_graph->flow))[e];

  1138       }

  1139     };

  1141     //    KEEP_MAPS(Parent, ResGraphAdaptor);

  1142   };

  1146   template <typename _Graph, typename FirstOutEdgesMap>

  1147   class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

  1148   public:

  1149     typedef _Graph Graph;

  1150     typedef GraphAdaptorBase<_Graph> Parent;

  1151   protected:

  1152     FirstOutEdgesMap* first_out_edges;

  1153     ErasingFirstGraphAdaptorBase() : Parent(),

  1154 				     first_out_edges(0) { }

  1156     void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {

  1157       first_out_edges=&_first_out_edges;

  1158     }

  1160   public:

  1162     typedef typename Parent::Node Node;

  1163     typedef typename Parent::Edge Edge;

  1165     void firstOut(Edge& i, const Node& n) const {

  1166       i=(*first_out_edges)[n];

  1167     }

  1169     void erase(const Edge& e) const {

  1170       Node n=source(e);

  1171       Edge f=e;

  1172       Parent::nextOut(f);

  1173       first_out_edges->set(n, f);

  1174     }

  1175   };

  1178   /// For blocking flows.

  1180   ///\warning Graph adaptors are in even more experimental state than the other

  1181   ///parts of the lib. Use them at you own risk.

  1182   ///

  1183   /// This graph adaptor is used for on-the-fly

  1184   /// Dinits blocking flow computations.

  1185   /// For each node, an out-edge is stored which is used when the

  1186   /// \code

  1187   /// OutEdgeIt& first(OutEdgeIt&, const Node&)

  1188   /// \endcode

  1189   /// is called.

  1190   ///

  1191   /// \author Marton Makai

  1192   template <typename _Graph, typename FirstOutEdgesMap>

  1193   class ErasingFirstGraphAdaptor :

  1194     public IterableGraphExtender<

  1195     ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {

  1196   public:

  1197     typedef _Graph Graph;

  1198     typedef IterableGraphExtender<

  1199       ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;

  1200     ErasingFirstGraphAdaptor(Graph& _graph,

  1201 			     FirstOutEdgesMap& _first_out_edges) {

  1202       setGraph(_graph);

  1203       setFirstOutEdgesMap(_first_out_edges);

  1204     }

  1206   };

  1208   ///@}

  1210 } //namespace lemon

  1212 #endif //LEMON_GRAPH_ADAPTOR_H

author	deba
	Wed, 11 May 2005 11:50:13 +0000
changeset 1409	d2d1f8fa187b
parent 1383	79b68a337f9f
child 1425	f3717c08e2be
permissions	-rw-r--r--