lemon-0.x: src/lemon/graph_adaptor.h@9ba88ddc629c

     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 the dimacs file \ref sub_graph_adaptor_demo.dim.

   450   The full source code is available in \ref sub_graph_adaptor_demo.cc.

   451   If you are interested in more demo programs, you can use

   452   \ref dim_to_dot.cc to generate .dot files from dimacs files.

   453   The .dot file of the following figure of was generated generated by

   454   the demo program \ref dim_to_dot.cc.

   456   \dot

   457   digraph lemon_dot_example {

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

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

   460   n1 [ label="1" ];

   461   n2 [ label="2" ];

   462   n3 [ label="3" ];

   463   n4 [ label="4" ];

   464   n5 [ label="5" ];

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

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

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

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

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

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

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

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

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

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

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

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

   477   }

   478   \enddot

   480   \code

   481   Graph g;

   482   Node s, t;

   483   LengthMap length(g);

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

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

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

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

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

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

   493   \endcode

   494   Next, the potential function is computed with Dijkstra.

   495   \code

   496   typedef Dijkstra<Graph, LengthMap> Dijkstra;

   497   Dijkstra dijkstra(g, length);

   498   dijkstra.run(s);

   499   \endcode

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

   501   \code

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

   503     TightEdgeFilter;

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

   506   typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;

   507   SubGW gw(g, tight_edge_filter);

   508   \endcode

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

   510   with a max flow algorithm Preflow.

   511   \code

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

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

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

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

   517   preflow.run();

   518   \endcode

   519   Last, the output is:

   520   \code

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

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

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

   524        << endl;

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

   526     if (flow[e])

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

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

   529   \endcode

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

   531   \code

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

   533    9, 5--4->6

   534    8, 4--2->6

   535    7, 3--1->5

   536    6, 2--3->5

   537    5, 2--5->6

   538    4, 2--2->4

   539    3, 1--3->4

   540    2, 0--1->3

   541    1, 0--2->2

   542    0, 0--3->1

   543   s: 0 t: 6

   544   maximum number of edge-disjoint shortest path: 2

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

   546    9, 5--4->6

   547    8, 4--2->6

   548    7, 3--1->5

   549    4, 2--2->4

   550    2, 0--1->3

   551    1, 0--2->2

   552   \endcode

   554   \author Marton Makai

   555   */

   556   template<typename Graph, typename EdgeFilterMap>

   557   class EdgeSubGraphAdaptor :

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

   559 			   EdgeFilterMap> {

   560   public:

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

   562 			    EdgeFilterMap> Parent;

   563   protected:

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

   565   public:

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

   567       Parent(), const_true_map(true) {

   568       Parent::setGraph(_graph);

   569       Parent::setNodeFilterMap(const_true_map);

   570       Parent::setEdgeFilterMap(_edge_filter_map);

   571     }

   572   };

   574   template <typename _Graph>

   575   class UndirGraphAdaptorBase :

   576     public UndirGraphExtender<GraphAdaptorBase<_Graph> > {

   577   public:

   578     typedef _Graph Graph;

   579     typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;

   580   protected:

   581     UndirGraphAdaptorBase() : Parent() { }

   582   public:

   583     typedef typename Parent::UndirEdge UndirEdge;

   584     typedef typename Parent::Edge Edge;

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

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

   588     /// The implementation

   589     template <typename T>

   590     class EdgeMap {

   591     protected:

   592       const UndirGraphAdaptorBase<_Graph>* g;

   593       template <typename TT> friend class EdgeMap;

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

   595     public:

   596       typedef T Value;

   597       typedef Edge Key;

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

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

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

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

   605       void set(Edge e, T a) {

   606 	if (g->forward(e))

   607 	  forward_map.set(e, a);

   608 	else

   609 	  backward_map.set(e, a);

   610       }

   612       T operator[](Edge e) const {

   613 	if (g->forward(e))

   614 	  return forward_map[e];

   615 	else

   616 	  return backward_map[e];

   617       }

   618     };

   620     template <typename T>

   621     class UndirEdgeMap {

   622       template <typename TT> friend class UndirEdgeMap;

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

   624     public:

   625       typedef T Value;

   626       typedef UndirEdge Key;

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

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

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

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

   634       void set(UndirEdge e, T a) {

   635 	map.set(e, a);

   636       }

   638       T operator[](UndirEdge e) const {

   639 	return map[e];

   640       }

   641     };

   643   };

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

   646   ///

   647   /// Undocumented, untested!!!

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

   649   ///

   650   /// \author Marton Makai

   651   template<typename _Graph>

   652   class UndirGraphAdaptor :

   653     public IterableUndirGraphExtender<

   654     UndirGraphAdaptorBase<_Graph> > {

   655   public:

   656     typedef _Graph Graph;

   657     typedef IterableUndirGraphExtender<

   658       UndirGraphAdaptorBase<_Graph> > Parent;

   659   protected:

   660     UndirGraphAdaptor() { }

   661   public:

   662     UndirGraphAdaptor(_Graph& _graph) {

   663       setGraph(_graph);

   664     }

   665   };

   668   template <typename _Graph,

   669 	    typename ForwardFilterMap, typename BackwardFilterMap>

   670   class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

   671   public:

   672     typedef _Graph Graph;

   673     typedef GraphAdaptorBase<_Graph> Parent;

   674   protected:

   675     ForwardFilterMap* forward_filter;

   676     BackwardFilterMap* backward_filter;

   677     SubBidirGraphAdaptorBase() : Parent(),

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

   680     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {

   681       forward_filter=&_forward_filter;

   682     }

   683     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {

   684       backward_filter=&_backward_filter;

   685     }

   687   public:

   688 //     SubGraphAdaptorBase(Graph& _graph,

   689 // 			NodeFilterMap& _node_filter_map,

   690 // 			EdgeFilterMap& _edge_filter_map) :

   691 //       Parent(&_graph),

   692 //       node_filter_map(&node_filter_map),

   693 //       edge_filter_map(&edge_filter_map) { }

   695     typedef typename Parent::Node Node;

   696     typedef typename _Graph::Edge GraphEdge;

   697     template <typename T> class EdgeMap;

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

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

   700     /// if and only if the

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

   702     class Edge : public _Graph::Edge {

   703       friend class SubBidirGraphAdaptorBase<

   704 	Graph, ForwardFilterMap, BackwardFilterMap>;

   705       template<typename T> friend class EdgeMap;

   706     protected:

   707       bool backward; //true, iff backward

   708     public:

   709       Edge() { }

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

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

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

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

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

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

   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       bool operator!=(const Edge& v) const {

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

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

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

   725       }

   726     };

   728     void first(Node& i) const {

   729       Parent::first(i);

   730     }

   732     void first(Edge& i) const {

   733       Parent::first(i);

   734       i.backward=false;

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

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

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

   738 	Parent::first(i);

   739 	i.backward=true;

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

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

   742       }

   743     }

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

   746       Parent::firstIn(i, n);

   747       i.backward=false;

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

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

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

   751 	Parent::firstOut(i, n);

   752 	i.backward=true;

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

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

   755       }

   756     }

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

   759       Parent::firstOut(i, n);

   760       i.backward=false;

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

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

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

   764 	Parent::firstIn(i, n);

   765 	i.backward=true;

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

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

   768       }

   769     }

   771     void next(Node& i) const {

   772       Parent::next(i);

   773     }

   775     void next(Edge& i) const {

   776       if (!(i.backward)) {

   777 	Parent::next(i);

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

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

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

   781 	  Parent::first(i);

   782 	  i.backward=true;

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

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

   785 	}

   786       } else {

   787 	Parent::next(i);

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

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

   790       }

   791     }

   793     void nextIn(Edge& i) const {

   794       if (!(i.backward)) {

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

   796 	Parent::nextIn(i);

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

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

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

   800 	  Parent::firstOut(i, n);

   801 	  i.backward=true;

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

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

   804 	}

   805       } else {

   806 	Parent::nextOut(i);

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

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

   809       }

   810     }

   812     void nextOut(Edge& i) const {

   813       if (!(i.backward)) {

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

   815 	Parent::nextOut(i);

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

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

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

   819 	  Parent::firstIn(i, n);

   820 	  i.backward=true;

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

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

   823 	}

   824       } else {

   825 	Parent::nextIn(i);

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

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

   828       }

   829     }

   831     Node source(Edge e) const {

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

   833     Node target(Edge e) const {

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

   836     /// Gives back the opposite edge.

   837     Edge opposite(const Edge& e) const {

   838       Edge f=e;

   839       f.backward=!f.backward;

   840       return f;

   841     }

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

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

   845     /// \todo hmm

   846     int edgeNum() const {

   847       int i=0;

   848       Edge e;

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

   850       return i;

   851     }

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

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

   856     template <typename T>

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

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

   859     /// one for the backward edges.

   860     class EdgeMap {

   861       template <typename TT> friend class EdgeMap;

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

   863     public:

   864       typedef T Value;

   865       typedef Edge Key;

   867       EdgeMap(const SubBidirGraphAdaptorBase<_Graph,

   868 	      ForwardFilterMap, BackwardFilterMap>& g) :

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

   871       EdgeMap(const SubBidirGraphAdaptorBase<_Graph,

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

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

   875       void set(Edge e, T a) {

   876 	if (!e.backward)

   877 	  forward_map.set(e, a);

   878 	else

   879 	  backward_map.set(e, a);

   880       }

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

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

   884 // 	if (!e.backward)

   885 // 	  return forward_map[e];

   886 // 	else

   887 // 	  return backward_map[e];

   888 //       }

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

   891       T operator[](Edge e) const {

   892 	if (!e.backward)

   893 	  return forward_map[e];

   894 	else

   895 	  return backward_map[e];

   896       }

   898       void update() {

   899 	forward_map.update();

   900 	backward_map.update();

   901       }

   902     };

   904   };

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

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

   909   ///

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

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

   912   ///

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

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

   915   ///

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

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

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

   919   /// maps on the edge-set,

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

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

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

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

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

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

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

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

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

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

   930   ///

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

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

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

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

   935   /// But BidirGraphAdaptor is obtained from

   936   /// SubBidirGraphAdaptor by considering everywhere true

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

   938   ///

   939   /// The most important application of SubBidirGraphAdaptor

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

   941   /// flow and circulation problems.

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

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

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

   945   template<typename _Graph,

   946 	   typename ForwardFilterMap, typename BackwardFilterMap>

   947   class SubBidirGraphAdaptor :

   948     public IterableGraphExtender<

   949     SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {

   950   public:

   951     typedef _Graph Graph;

   952     typedef IterableGraphExtender<

   953       SubBidirGraphAdaptorBase<

   954       _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;

   955   protected:

   956     SubBidirGraphAdaptor() { }

   957   public:

   958     SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,

   959 			 BackwardFilterMap& _backward_filter) {

   960       setGraph(_graph);

   961       setForwardFilterMap(_forward_filter);

   962       setBackwardFilterMap(_backward_filter);

   963     }

   964   };

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

   969   ///

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

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

   972   ///

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

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

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

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

   977   template<typename Graph>

   978   class BidirGraphAdaptor :

   979     public SubBidirGraphAdaptor<

   980     Graph,

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

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

   983   public:

   984     typedef  SubBidirGraphAdaptor<

   985       Graph,

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

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

   988   protected:

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

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

   992       Parent::setForwardFilterMap(cm);

   993       Parent::setBackwardFilterMap(cm);

   994     }

   995   public:

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

   997       Parent::setGraph(_graph);

   998       Parent::setForwardFilterMap(cm);

   999       Parent::setBackwardFilterMap(cm);

  1000     }

  1002     int edgeNum() const {

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

  1004     }

  1005     //    KEEP_MAPS(Parent, BidirGraphAdaptor);

  1006   };

  1009   template<typename Graph, typename Number,

  1010 	   typename CapacityMap, typename FlowMap>

  1011   class ResForwardFilter {

  1012     //    const Graph* graph;

  1013     const CapacityMap* capacity;

  1014     const FlowMap* flow;

  1015   public:

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

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

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

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

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

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

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

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

  1024     }

  1025   };

  1027   template<typename Graph, typename Number,

  1028 	   typename CapacityMap, typename FlowMap>

  1029   class ResBackwardFilter {

  1030     const CapacityMap* capacity;

  1031     const FlowMap* flow;

  1032   public:

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

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

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

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

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

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

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

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

  1041     }

  1042   };

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

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

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

  1049   number type. Let moreover

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

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

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

  1053   Suppose that a graph instange \c g of type

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

  1055   \code

  1056   ListGraph g;

  1057   \endcode

  1058   Then RevGraphAdaptor implements the graph structure with node-set

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

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

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

  1062   i.e. the so called residual graph.

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

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

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

  1066   appears twice.

  1067   The following code shows how

  1068   such an instance can be constructed.

  1069   \code

  1070   typedef ListGraph Graph;

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

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

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

  1074   \endcode

  1075   \author Marton Makai

  1076   */

  1077   template<typename Graph, typename Number,

  1078 	   typename CapacityMap, typename FlowMap>

  1079   class ResGraphAdaptor :

  1080     public SubBidirGraphAdaptor<

  1081     Graph,

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

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

  1084   public:

  1085     typedef SubBidirGraphAdaptor<

  1086       Graph,

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

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

  1089   protected:

  1090     const CapacityMap* capacity;

  1091     FlowMap* flow;

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

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

  1094     ResGraphAdaptor() : Parent(),

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

  1096     void setCapacityMap(const CapacityMap& _capacity) {

  1097       capacity=&_capacity;

  1098       forward_filter.setCapacity(_capacity);

  1099       backward_filter.setCapacity(_capacity);

  1100     }

  1101     void setFlowMap(FlowMap& _flow) {

  1102       flow=&_flow;

  1103       forward_filter.setFlow(_flow);

  1104       backward_filter.setFlow(_flow);

  1105     }

  1106   public:

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

  1108 		       FlowMap& _flow) :

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

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

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

  1112       Parent::setGraph(_graph);

  1113       Parent::setForwardFilterMap(forward_filter);

  1114       Parent::setBackwardFilterMap(backward_filter);

  1115     }

  1117     typedef typename Parent::Edge Edge;

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

  1120       if (Parent::forward(e))

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

  1122       else

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

  1124     }

  1126     /// \brief Residual capacity map.

  1127     ///

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

  1129     /// as a map.

  1130     class ResCap {

  1131     protected:

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

  1133     public:

  1134       typedef Number Value;

  1135       typedef Edge Key;

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

  1137 	     _res_graph) : res_graph(&_res_graph) { }

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

  1139 	if (res_graph->forward(e))

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

  1141 	else

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

  1143       }

  1144     };

  1146     //    KEEP_MAPS(Parent, ResGraphAdaptor);

  1147   };

  1151   template <typename _Graph, typename FirstOutEdgesMap>

  1152   class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

  1153   public:

  1154     typedef _Graph Graph;

  1155     typedef GraphAdaptorBase<_Graph> Parent;

  1156   protected:

  1157     FirstOutEdgesMap* first_out_edges;

  1158     ErasingFirstGraphAdaptorBase() : Parent(),

  1159 				     first_out_edges(0) { }

  1161     void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {

  1162       first_out_edges=&_first_out_edges;

  1163     }

  1165   public:

  1167     typedef typename Parent::Node Node;

  1168     typedef typename Parent::Edge Edge;

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

  1171       i=(*first_out_edges)[n];

  1172     }

  1174     void erase(const Edge& e) const {

  1175       Node n=source(e);

  1176       Edge f=e;

  1177       Parent::nextOut(f);

  1178       first_out_edges->set(n, f);

  1179     }

  1180   };

  1183   /// For blocking flows.

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

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

  1187   ///

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

  1189   /// Dinits blocking flow computations.

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

  1191   /// \code

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

  1193   /// \endcode

  1194   /// is called.

  1195   ///

  1196   /// \author Marton Makai

  1197   template <typename _Graph, typename FirstOutEdgesMap>

  1198   class ErasingFirstGraphAdaptor :

  1199     public IterableGraphExtender<

  1200     ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {

  1201   public:

  1202     typedef _Graph Graph;

  1203     typedef IterableGraphExtender<

  1204       ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;

  1205     ErasingFirstGraphAdaptor(Graph& _graph,

  1206 			     FirstOutEdgesMap& _first_out_edges) {

  1207       setGraph(_graph);

  1208       setFirstOutEdgesMap(_first_out_edges);

  1209     }

  1211   };

  1213   ///@}

  1215 } //namespace lemon

  1217 #endif //LEMON_GRAPH_ADAPTOR_H

author	alpar
	Thu, 19 May 2005 11:46:42 +0000
changeset 1428	9ba88ddc629c
parent 1401	9588dcef6793
permissions	-rw-r--r--