lemon-0.x: src/lemon/graph_wrapper.h@daaf6b5c28d6

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

     2  * src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library

     3  *

     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     5  * (Egervary Combinatorial Optimization Research Group, 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_WRAPPER_H

    18 #define LEMON_GRAPH_WRAPPER_H

    20 ///\ingroup gwrappers

    21 ///\file

    22 ///\brief Several graph wrappers.

    23 ///

    24 ///This file contains several useful graph wrapper 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 <iostream>

    33 namespace lemon {

    35   // Graph wrappers

    37   /*!

    38     \addtogroup gwrappers

    39     @{

    40    */

    42   /*!

    43     Base type for the Graph Wrappers

    45     \warning Graph wrappers are in even more experimental state than the other

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

    48     This is the base type for most of LEMON graph wrappers.

    49     This class implements a trivial graph wrapper i.e. it only wraps the

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

    51     make easier implementing graph wrappers. E.g. if a wrapper is

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

    53     functions or types, then it can be derived from GraphWrapper, and only the

    54     differences should be implemented.

    56     \author Marton Makai

    57   */

    58   template<typename _Graph>

    59   class GraphWrapperBase {

    60   public:

    61     typedef _Graph Graph;

    62     /// \todo Is it needed?

    63     typedef Graph BaseGraph;

    64     typedef Graph ParentGraph;

    66   protected:

    67     Graph* graph;

    68     GraphWrapperBase() : graph(0) { }

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

    71   public:

    72     GraphWrapperBase(Graph& _graph) : graph(&_graph) { }

    74     typedef typename Graph::Node Node;

    75     typedef typename Graph::Edge Edge;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   110     template <typename _Value>

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

   112     public:

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

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

   115       NodeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)

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

   117     };

   119     template <typename _Value>

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

   121     public:

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

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

   124       EdgeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)

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

   126     };

   128   };

   130   template <typename _Graph>

   131   class GraphWrapper :

   132     public IterableGraphExtender<GraphWrapperBase<_Graph> > {

   133   public:

   134     typedef _Graph Graph;

   135     typedef IterableGraphExtender<GraphWrapperBase<_Graph> > Parent;

   136   protected:

   137     GraphWrapper() : Parent() { }

   139   public:

   140     GraphWrapper(Graph& _graph) { setGraph(_graph); }

   141   };

   143   template <typename _Graph>

   144   class RevGraphWrapperBase : public GraphWrapperBase<_Graph> {

   145   public:

   146     typedef _Graph Graph;

   147     typedef GraphWrapperBase<_Graph> Parent;

   148   protected:

   149     RevGraphWrapperBase() : Parent() { }

   150   public:

   151     typedef typename Parent::Node Node;

   152     typedef typename Parent::Edge Edge;

   154     using Parent::first;

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

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

   158     using Parent::next;

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

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

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

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

   164   };

   167   /// A graph wrapper which reverses the orientation of the edges.

   169   ///\warning Graph wrappers are in even more experimental state than the other

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

   171   ///

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

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

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

   175   /// \code

   176   /// ListGraph g;

   177   /// \endcode

   178   /// For each directed edge

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

   180   /// reversing its orientation.

   181   /// Then RevGraphWrapper implements the graph structure with node-set

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

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

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

   185   /// such an instance can be constructed.

   186   /// \code

   187   /// RevGraphWrapper<ListGraph> gw(g);

   188   /// \endcode

   189   ///\author Marton Makai

   190   template<typename _Graph>

   191   class RevGraphWrapper :

   192     public IterableGraphExtender<RevGraphWrapperBase<_Graph> > {

   193   public:

   194     typedef _Graph Graph;

   195     typedef IterableGraphExtender<

   196       RevGraphWrapperBase<_Graph> > Parent;

   197   protected:

   198     RevGraphWrapper() { }

   199   public:

   200     RevGraphWrapper(_Graph& _graph) { setGraph(_graph); }

   201   };

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

   205   class SubGraphWrapperBase : public GraphWrapperBase<_Graph> {

   206   public:

   207     typedef _Graph Graph;

   208     typedef GraphWrapperBase<_Graph> Parent;

   209   protected:

   210     NodeFilterMap* node_filter_map;

   211     EdgeFilterMap* edge_filter_map;

   212     SubGraphWrapperBase() : Parent(),

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

   215     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {

   216       node_filter_map=&_node_filter_map;

   217     }

   218     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {

   219       edge_filter_map=&_edge_filter_map;

   220     }

   222   public:

   223 //     SubGraphWrapperBase(Graph& _graph,

   224 // 			NodeFilterMap& _node_filter_map,

   225 // 			EdgeFilterMap& _edge_filter_map) :

   226 //       Parent(&_graph),

   227 //       node_filter_map(&node_filter_map),

   228 //       edge_filter_map(&edge_filter_map) { }

   230     typedef typename Parent::Node Node;

   231     typedef typename Parent::Edge Edge;

   233     void first(Node& i) const {

   234       Parent::first(i);

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

   236     }

   237     void first(Edge& i) const {

   238       Parent::first(i);

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

   240     }

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

   242       Parent::firstIn(i, n);

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

   244     }

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

   246       Parent::firstOut(i, n);

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

   248     }

   250     void next(Node& i) const {

   251       Parent::next(i);

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

   253     }

   254     void next(Edge& i) const {

   255       Parent::next(i);

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

   257     }

   258     void nextIn(Edge& i) const {

   259       Parent::nextIn(i);

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

   261     }

   262     void nextOut(Edge& i) const {

   263       Parent::nextOut(i);

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

   265     }

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

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

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

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

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

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

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

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

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

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

   279     /// again

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

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

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

   284     /// again

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

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

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

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

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

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

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

   295     /// \todo assign tags.

   296     int nodeNum() const {

   297       int i=0;

   298       Node n;

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

   300       return i;

   301     }

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

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

   305     /// \todo assign tags.

   306     int edgeNum() const {

   307       int i=0;

   308       Edge e;

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

   310       return i;

   311     }

   314   };

   316   /*! \brief A graph wrapper for hiding nodes and edges from a graph.

   318   \warning Graph wrappers are in even more experimental state than the other

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

   321   SubGraphWrapper shows the graph with filtered node-set and

   322   edge-set.

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

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

   325   \f$G\f$.

   326   Let moreover \f$b_V\f$ and

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

   328   SubGraphWrapper<...>::NodeIt iterates

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

   330   SubGraphWrapper<...>::EdgeIt iterates

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

   332   SubGraphWrapper<...>::OutEdgeIt and SubGraphWrapper<...>::InEdgeIt iterates

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

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

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

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

   338   edge-set.

   339   \code

   340   typedef ListGraph Graph;

   341   Graph g;

   342   typedef Graph::Node Node;

   343   typedef Graph::Edge Edge;

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

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

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

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

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

   349   nm.set(u, false);

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

   351   em.set(e, false);

   352   typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;

   353   SubGW gw(g, nm, em);

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

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

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

   357   \endcode

   358   The output of the above code is the following.

   359   \code

   360   1

   361   :-)

   362   1

   363   \endcode

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

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

   367   For other examples see also the documentation of NodeSubGraphWrapper and

   368   EdgeSubGraphWrapper.

   370   \author Marton Makai

   371   */

   372   template<typename _Graph, typename NodeFilterMap,

   373 	   typename EdgeFilterMap>

   374   class SubGraphWrapper :

   375     public IterableGraphExtender<

   376     SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {

   377   public:

   378     typedef _Graph Graph;

   379     typedef IterableGraphExtender<

   380       SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;

   381   protected:

   382     SubGraphWrapper() { }

   383   public:

   384     SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map,

   385 		    EdgeFilterMap& _edge_filter_map) {

   386       setGraph(_graph);

   387       setNodeFilterMap(_node_filter_map);

   388       setEdgeFilterMap(_edge_filter_map);

   389     }

   390   };

   394   /*! \brief A wrapper for hiding nodes from a graph.

   396   \warning Graph wrappers are in even more experimental state than the other

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

   399   A wrapper for hiding nodes from a graph.

   400   This wrapper specializes SubGraphWrapper in the way that only the node-set

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

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

   403   \author Marton Makai

   404   */

   405   template<typename Graph, typename NodeFilterMap>

   406   class NodeSubGraphWrapper :

   407     public SubGraphWrapper<Graph, NodeFilterMap,

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

   409   public:

   410     typedef SubGraphWrapper<Graph, NodeFilterMap,

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

   412   protected:

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

   414   public:

   415     NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :

   416       Parent(), const_true_map(true) {

   417       Parent::setGraph(_graph);

   418       Parent::setNodeFilterMap(_node_filter_map);

   419       Parent::setEdgeFilterMap(const_true_map);

   420     }

   421   };

   424   /*! \brief A wrapper for hiding edges from a graph.

   426   \warning Graph wrappers are in even more experimental state than the other

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

   429   A wrapper for hiding edges from a graph.

   430   This wrapper specializes SubGraphWrapper in the way that only the edge-set

   431   can be filtered. The usefulness of this wrapper is demonstrated in the

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

   433   between

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

   435   non-negative edge-lengths. Note that

   436   the comprehension of the presented solution

   437   need's some elementary knowledge from combinatorial optimization.

   439   If a single shortest path is to be

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

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

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

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

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

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

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

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

   448   graph, which is read from a dimacs file.

   450   \dot

   451   digraph lemon_dot_example {

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

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

   454   n1 [ label="1" ];

   455   n2 [ label="2" ];

   456   n3 [ label="3" ];

   457   n4 [ label="4" ];

   458   n5 [ label="5" ];

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

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

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

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

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

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

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

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

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

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

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

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

   471   }

   472   \enddot

   474   \code

   475   Graph g;

   476   Node s, t;

   477   LengthMap length(g);

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

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

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

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

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

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

   487   \endcode

   488   Next, the potential function is computed with Dijkstra.

   489   \code

   490   typedef Dijkstra<Graph, LengthMap> Dijkstra;

   491   Dijkstra dijkstra(g, length);

   492   dijkstra.run(s);

   493   \endcode

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

   495   \code

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

   497     TightEdgeFilter;

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

   500   typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;

   501   SubGW gw(g, tight_edge_filter);

   502   \endcode

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

   504   with a max flow algorithm Preflow.

   505   \code

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

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

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

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

   511   preflow.run();

   512   \endcode

   513   Last, the output is:

   514   \code

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

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

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

   518        << endl;

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

   520     if (flow[e])

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

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

   523   \endcode

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

   525   \code

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

   527    9, 5--4->6

   528    8, 4--2->6

   529    7, 3--1->5

   530    6, 2--3->5

   531    5, 2--5->6

   532    4, 2--2->4

   533    3, 1--3->4

   534    2, 0--1->3

   535    1, 0--2->2

   536    0, 0--3->1

   537   s: 0 t: 6

   538   maximum number of edge-disjoint shortest path: 2

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

   540    9, 5--4->6

   541    8, 4--2->6

   542    7, 3--1->5

   543    4, 2--2->4

   544    2, 0--1->3

   545    1, 0--2->2

   546   \endcode

   548   \author Marton Makai

   549   */

   550   template<typename Graph, typename EdgeFilterMap>

   551   class EdgeSubGraphWrapper :

   552     public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,

   553 			   EdgeFilterMap> {

   554   public:

   555     typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,

   556 			    EdgeFilterMap> Parent;

   557   protected:

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

   559   public:

   560     EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) :

   561       Parent(), const_true_map(true) {

   562       Parent::setGraph(_graph);

   563       Parent::setNodeFilterMap(const_true_map);

   564       Parent::setEdgeFilterMap(_edge_filter_map);

   565     }

   566   };

   569   template<typename Graph>

   570   class UndirGraphWrapper : public GraphWrapper<Graph> {

   571   public:

   572     typedef GraphWrapper<Graph> Parent;

   573   protected:

   574     UndirGraphWrapper() : GraphWrapper<Graph>() { }

   576   public:

   577     typedef typename GraphWrapper<Graph>::Node Node;

   578     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;

   579     typedef typename GraphWrapper<Graph>::Edge Edge;

   580     typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;

   582     UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }

   584     class OutEdgeIt {

   585       friend class UndirGraphWrapper<Graph>;

   586       bool out_or_in; //true iff out

   587       typename Graph::OutEdgeIt out;

   588       typename Graph::InEdgeIt in;

   589     public:

   590       OutEdgeIt() { }

   591       OutEdgeIt(const Invalid& i) : Edge(i) { }

   592       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {

   593 	out_or_in=true; _G.graph->first(out, _n);

   594 	if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);	}

   595       }

   596       operator Edge() const {

   597 	if (out_or_in) return Edge(out); else return Edge(in);

   598       }

   599     };

   601     typedef OutEdgeIt InEdgeIt;

   603     using GraphWrapper<Graph>::first;

   604     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {

   605       i=OutEdgeIt(*this, p); return i;

   606     }

   608     using GraphWrapper<Graph>::next;

   610     OutEdgeIt& next(OutEdgeIt& e) const {

   611       if (e.out_or_in) {

   612 	typename Graph::Node n=this->graph->source(e.out);

   613 	this->graph->next(e.out);

   614 	if (!this->graph->valid(e.out)) {

   615 	  e.out_or_in=false; this->graph->first(e.in, n); }

   616       } else {

   617 	this->graph->next(e.in);

   618       }

   619       return e;

   620     }

   622     Node aNode(const OutEdgeIt& e) const {

   623       if (e.out_or_in) return this->graph->source(e); else

   624 	return this->graph->target(e); }

   625     Node bNode(const OutEdgeIt& e) const {

   626       if (e.out_or_in) return this->graph->target(e); else

   627 	return this->graph->source(e); }

   629     //    KEEP_MAPS(Parent, UndirGraphWrapper);

   631   };

   633 //   /// \brief An undirected graph template.

   634 //   ///

   635 //   ///\warning Graph wrappers are in even more experimental state than the other

   636 //   ///parts of the lib. Use them at your own risk.

   637 //   ///

   638 //   /// An undirected graph template.

   639 //   /// This class works as an undirected graph and a directed graph of

   640 //   /// class \c Graph is used for the physical storage.

   641 //   /// \ingroup graphs

   642   template<typename Graph>

   643   class UndirGraph : public UndirGraphWrapper<Graph> {

   644     typedef UndirGraphWrapper<Graph> Parent;

   645   protected:

   646     Graph gr;

   647   public:

   648     UndirGraph() : UndirGraphWrapper<Graph>() {

   649       Parent::setGraph(gr);

   650     }

   652     //    KEEP_MAPS(Parent, UndirGraph);

   653   };

   656   template <typename _Graph,

   657 	    typename ForwardFilterMap, typename BackwardFilterMap>

   658   class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {

   659   public:

   660     typedef _Graph Graph;

   661     typedef GraphWrapperBase<_Graph> Parent;

   662   protected:

   663     ForwardFilterMap* forward_filter;

   664     BackwardFilterMap* backward_filter;

   665     SubBidirGraphWrapperBase() : Parent(),

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

   668     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {

   669       forward_filter=&_forward_filter;

   670     }

   671     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {

   672       backward_filter=&_backward_filter;

   673     }

   675   public:

   676 //     SubGraphWrapperBase(Graph& _graph,

   677 // 			NodeFilterMap& _node_filter_map,

   678 // 			EdgeFilterMap& _edge_filter_map) :

   679 //       Parent(&_graph),

   680 //       node_filter_map(&node_filter_map),

   681 //       edge_filter_map(&edge_filter_map) { }

   683     typedef typename Parent::Node Node;

   684     typedef typename _Graph::Edge GraphEdge;

   685     template <typename T> class EdgeMap;

   686     /// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from

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

   688     /// if and only if the

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

   690     class Edge : public _Graph::Edge {

   691       friend class SubBidirGraphWrapperBase<

   692 	Graph, ForwardFilterMap, BackwardFilterMap>;

   693       template<typename T> friend class EdgeMap;

   694     protected:

   695       bool backward; //true, iff backward

   696     public:

   697       Edge() { }

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

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

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

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

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

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

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

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

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

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

   708       }

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

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

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

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

   713       }

   714     };

   716     void first(Node& i) const {

   717       Parent::first(i);

   718     }

   720     void first(Edge& i) const {

   721       Parent::first(i);

   722       i.backward=false;

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

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

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

   726 	Parent::first(i);

   727 	i.backward=true;

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

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

   730       }

   731     }

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

   734       Parent::firstIn(i, n);

   735       i.backward=false;

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

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

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

   739 	Parent::firstOut(i, n);

   740 	i.backward=true;

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

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

   743       }

   744     }

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

   747       Parent::firstOut(i, n);

   748       i.backward=false;

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

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

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

   752 	Parent::firstIn(i, n);

   753 	i.backward=true;

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

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

   756       }

   757     }

   759     void next(Node& i) const {

   760       Parent::next(i);

   761     }

   763     void next(Edge& i) const {

   764       if (!(i.backward)) {

   765 	Parent::next(i);

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

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

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

   769 	  Parent::first(i);

   770 	  i.backward=true;

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

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

   773 	}

   774       } else {

   775 	Parent::next(i);

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

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

   778       }

   779     }

   781     void nextIn(Edge& i) const {

   782       if (!(i.backward)) {

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

   784 	Parent::nextIn(i);

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

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

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

   788 	  Parent::firstOut(i, n);

   789 	  i.backward=true;

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

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

   792 	}

   793       } else {

   794 	Parent::nextOut(i);

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

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

   797       }

   798     }

   800     void nextOut(Edge& i) const {

   801       if (!(i.backward)) {

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

   803 	Parent::nextOut(i);

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

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

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

   807 	  Parent::firstIn(i, n);

   808 	  i.backward=true;

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

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

   811 	}

   812       } else {

   813 	Parent::nextIn(i);

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

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

   816       }

   817     }

   819     Node source(Edge e) const {

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

   821     Node target(Edge e) const {

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

   824     /// Gives back the opposite edge.

   825     Edge opposite(const Edge& e) const {

   826       Edge f=e;

   827       f.backward=!f.backward;

   828       return f;

   829     }

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

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

   833     /// \todo hmm

   834     int edgeNum() const {

   835       int i=0;

   836       Edge e;

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

   838       return i;

   839     }

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

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

   844     template <typename T>

   845     /// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two

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

   847     /// one for the backward edges.

   848     class EdgeMap {

   849       template <typename TT> friend class EdgeMap;

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

   851     public:

   852       typedef T Value;

   853       typedef Edge Key;

   855       EdgeMap(const SubBidirGraphWrapperBase<_Graph,

   856 	      ForwardFilterMap, BackwardFilterMap>& g) :

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

   859       EdgeMap(const SubBidirGraphWrapperBase<_Graph,

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

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

   863       void set(Edge e, T a) {

   864 	if (!e.backward)

   865 	  forward_map.set(e, a);

   866 	else

   867 	  backward_map.set(e, a);

   868       }

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

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

   872 // 	if (!e.backward)

   873 // 	  return forward_map[e];

   874 // 	else

   875 // 	  return backward_map[e];

   876 //       }

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

   879       T operator[](Edge e) const {

   880 	if (!e.backward)

   881 	  return forward_map[e];

   882 	else

   883 	  return backward_map[e];

   884       }

   886       void update() {

   887 	forward_map.update();

   888 	backward_map.update();

   889       }

   890     };

   892   };

   895   ///\brief A wrapper for composing a subgraph of a

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

   897   ///

   898   /// A wrapper for composing a subgraph of a

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

   900   ///

   901   ///\warning Graph wrappers are in even more experimental state than the other

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

   903   ///

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

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

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

   907   /// maps on the edge-set,

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

   909   /// SubBidirGraphWrapper implements the graph structure with node-set

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

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

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

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

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

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

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

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

   918   ///

   919   /// An example for such a construction is \c RevGraphWrapper where the

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

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

   922   /// \c RevGraphWrapper is implemented in a different way.

   923   /// But BidirGraphWrapper is obtained from

   924   /// SubBidirGraphWrapper by considering everywhere true

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

   926   ///

   927   /// The most important application of SubBidirGraphWrapper

   928   /// is ResGraphWrapper, which stands for the residual graph in directed

   929   /// flow and circulation problems.

   930   /// As wrappers usually, the SubBidirGraphWrapper implements the

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

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

   933   template<typename _Graph,

   934 	   typename ForwardFilterMap, typename BackwardFilterMap>

   935   class SubBidirGraphWrapper :

   936     public IterableGraphExtender<

   937     SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {

   938   public:

   939     typedef _Graph Graph;

   940     typedef IterableGraphExtender<

   941       SubBidirGraphWrapperBase<

   942       _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;

   943   protected:

   944     SubBidirGraphWrapper() { }

   945   public:

   946     SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,

   947 			 BackwardFilterMap& _backward_filter) {

   948       setGraph(_graph);

   949       setForwardFilterMap(_forward_filter);

   950       setBackwardFilterMap(_backward_filter);

   951     }

   952   };

   956   ///\brief A wrapper for composing bidirected graph from a directed one.

   957   ///

   958   ///\warning Graph wrappers are in even more experimental state than the other

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

   960   ///

   961   /// A wrapper for composing bidirected graph from a directed one.

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

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

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

   965   template<typename Graph>

   966   class BidirGraphWrapper :

   967     public SubBidirGraphWrapper<

   968     Graph,

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

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

   971   public:

   972     typedef  SubBidirGraphWrapper<

   973       Graph,

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

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

   976   protected:

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

   979     BidirGraphWrapper() : Parent(), cm(true) {

   980       Parent::setForwardFilterMap(cm);

   981       Parent::setBackwardFilterMap(cm);

   982     }

   983   public:

   984     BidirGraphWrapper(Graph& _graph) : Parent(), cm(true) {

   985       Parent::setGraph(_graph);

   986       Parent::setForwardFilterMap(cm);

   987       Parent::setBackwardFilterMap(cm);

   988     }

   990     int edgeNum() const {

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

   992     }

   993     //    KEEP_MAPS(Parent, BidirGraphWrapper);

   994   };

   997   template<typename Graph, typename Number,

   998 	   typename CapacityMap, typename FlowMap>

   999   class ResForwardFilter {

  1000     //    const Graph* graph;

  1001     const CapacityMap* capacity;

  1002     const FlowMap* flow;

  1003   public:

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

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

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

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

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

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

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

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

  1012     }

  1013   };

  1015   template<typename Graph, typename Number,

  1016 	   typename CapacityMap, typename FlowMap>

  1017   class ResBackwardFilter {

  1018     const CapacityMap* capacity;

  1019     const FlowMap* flow;

  1020   public:

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

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

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

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

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

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

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

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

  1029     }

  1030   };

  1033   /*! \brief A wrapper for composing the residual graph for directed flow and circulation problems.

  1035   A wrapper for composing the residual graph for directed flow and circulation problems.

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

  1037   number type. Let moreover

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

  1039   In the appications of ResGraphWrapper, \f$f\f$ usually stands for a flow

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

  1041   Suppose that a graph instange \c g of type

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

  1043   \code

  1044   ListGraph g;

  1045   \endcode

  1046   Then RevGraphWrapper implements the graph structure with node-set

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

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

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

  1050   i.e. the so called residual graph.

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

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

  1053   \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the wrapper it

  1054   appears twice.

  1055   The following code shows how

  1056   such an instance can be constructed.

  1057   \code

  1058   typedef ListGraph Graph;

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

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

  1061   ResGraphWrapper<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);

  1062   \endcode

  1063   \author Marton Makai

  1064   */

  1065   template<typename Graph, typename Number,

  1066 	   typename CapacityMap, typename FlowMap>

  1067   class ResGraphWrapper :

  1068     public SubBidirGraphWrapper<

  1069     Graph,

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

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

  1072   public:

  1073     typedef SubBidirGraphWrapper<

  1074       Graph,

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

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

  1077   protected:

  1078     const CapacityMap* capacity;

  1079     FlowMap* flow;

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

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

  1082     ResGraphWrapper() : Parent(),

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

  1084     void setCapacityMap(const CapacityMap& _capacity) {

  1085       capacity=&_capacity;

  1086       forward_filter.setCapacity(_capacity);

  1087       backward_filter.setCapacity(_capacity);

  1088     }

  1089     void setFlowMap(FlowMap& _flow) {

  1090       flow=&_flow;

  1091       forward_filter.setFlow(_flow);

  1092       backward_filter.setFlow(_flow);

  1093     }

  1094   public:

  1095     ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,

  1096 		       FlowMap& _flow) :

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

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

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

  1100       Parent::setGraph(_graph);

  1101       Parent::setForwardFilterMap(forward_filter);

  1102       Parent::setBackwardFilterMap(backward_filter);

  1103     }

  1105     typedef typename Parent::Edge Edge;

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

  1108       if (Parent::forward(e))

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

  1110       else

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

  1112     }

  1114     /// \brief Residual capacity map.

  1115     ///

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

  1117     /// as a map.

  1118     class ResCap {

  1119     protected:

  1120       const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;

  1121     public:

  1122       typedef Number Value;

  1123       typedef Edge Key;

  1124       ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&

  1125 	     _res_graph) : res_graph(&_res_graph) { }

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

  1127 	if (res_graph->forward(e))

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

  1129 	else

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

  1131       }

  1132     };

  1134     //    KEEP_MAPS(Parent, ResGraphWrapper);

  1135   };

  1139   template <typename _Graph, typename FirstOutEdgesMap>

  1140   class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {

  1141   public:

  1142     typedef _Graph Graph;

  1143     typedef GraphWrapperBase<_Graph> Parent;

  1144   protected:

  1145     FirstOutEdgesMap* first_out_edges;

  1146     ErasingFirstGraphWrapperBase() : Parent(),

  1147 				     first_out_edges(0) { }

  1149     void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {

  1150       first_out_edges=&_first_out_edges;

  1151     }

  1153   public:

  1155     typedef typename Parent::Node Node;

  1156     typedef typename Parent::Edge Edge;

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

  1159       i=(*first_out_edges)[n];

  1160     }

  1162     void erase(const Edge& e) const {

  1163       Node n=source(e);

  1164       Edge f=e;

  1165       Parent::nextOut(f);

  1166       first_out_edges->set(n, f);

  1167     }

  1168   };

  1171   /// For blocking flows.

  1173   ///\warning Graph wrappers are in even more experimental state than the other

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

  1175   ///

  1176   /// This graph wrapper is used for on-the-fly

  1177   /// Dinits blocking flow computations.

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

  1179   /// \code

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

  1181   /// \endcode

  1182   /// is called.

  1183   ///

  1184   /// \author Marton Makai

  1185   template <typename _Graph, typename FirstOutEdgesMap>

  1186   class ErasingFirstGraphWrapper :

  1187     public IterableGraphExtender<

  1188     ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {

  1189   public:

  1190     typedef _Graph Graph;

  1191     typedef IterableGraphExtender<

  1192       ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;

  1193     ErasingFirstGraphWrapper(Graph& _graph,

  1194 			     FirstOutEdgesMap& _first_out_edges) {

  1195       setGraph(_graph);

  1196       setFirstOutEdgesMap(_first_out_edges);

  1197     }

  1199   };

  1201   ///@}

  1203 } //namespace lemon

  1205 #endif //LEMON_GRAPH_WRAPPER_H

author	athos
	Thu, 07 Apr 2005 10:44:32 +0000
changeset 1316	daaf6b5c28d6
parent 1269	4c63ff4e16fa
child 1359	1581f961cfaa
permissions	-rw-r--r--