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

     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/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 knowledge from elementary combinatorial optimization.

   439   If a single shortest path is to be

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

   441   applying the Dijkstra algorithm class. 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::nextOut(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   /// Finally, one of the most important applications of SubBidirGraphWrapper

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

   928   /// flow and circulation problems.

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

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

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

   932   template<typename _Graph,

   933 	   typename ForwardFilterMap, typename BackwardFilterMap>

   934   class SubBidirGraphWrapper :

   935     public IterableGraphExtender<

   936     SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {

   937   public:

   938     typedef _Graph Graph;

   939     typedef IterableGraphExtender<

   940       SubBidirGraphWrapperBase<

   941       _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;

   942   protected:

   943     SubBidirGraphWrapper() { }

   944   public:

   945     SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,

   946 			 BackwardFilterMap& _backward_filter) {

   947       setGraph(_graph);

   948       setForwardFilterMap(_forward_filter);

   949       setBackwardFilterMap(_backward_filter);

   950     }

   951   };

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

   956   ///

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

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

   959   ///

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

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

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

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

   964   template<typename Graph>

   965   class BidirGraphWrapper :

   966     public SubBidirGraphWrapper<

   967     Graph,

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

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

   970   public:

   971     typedef  SubBidirGraphWrapper<

   972       Graph,

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

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

   975   protected:

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

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

   979       Parent::setForwardFilterMap(cm);

   980       Parent::setBackwardFilterMap(cm);

   981     }

   982   public:

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

   984       Parent::setGraph(_graph);

   985       Parent::setForwardFilterMap(cm);

   986       Parent::setBackwardFilterMap(cm);

   987     }

   989     int edgeNum() const {

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

   991     }

   992     //    KEEP_MAPS(Parent, BidirGraphWrapper);

   993   };

   996   template<typename Graph, typename Number,

   997 	   typename CapacityMap, typename FlowMap>

   998   class ResForwardFilter {

   999     //    const Graph* graph;

  1000     const CapacityMap* capacity;

  1001     const FlowMap* flow;

  1002   public:

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

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

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

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

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

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

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

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

  1011     }

  1012   };

  1014   template<typename Graph, typename Number,

  1015 	   typename CapacityMap, typename FlowMap>

  1016   class ResBackwardFilter {

  1017     const CapacityMap* capacity;

  1018     const FlowMap* flow;

  1019   public:

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

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

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

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

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

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

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

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

  1028     }

  1029   };

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

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

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

  1036   number type. Let moreover

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

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

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

  1040   Suppose that a graph instange \c g of type

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

  1042   \code

  1043   ListGraph g;

  1044   \endcode

  1045   Then RevGraphWrapper implements the graph structure with node-set

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

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

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

  1049   i.e. the so called residual graph.

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

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

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

  1053   appears twice.

  1054   The following code shows how

  1055   such an instance can be constructed.

  1056   \code

  1057   typedef ListGraph Graph;

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

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

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

  1061   \endcode

  1062   \author Marton Makai

  1063   */

  1064   template<typename Graph, typename Number,

  1065 	   typename CapacityMap, typename FlowMap>

  1066   class ResGraphWrapper :

  1067     public SubBidirGraphWrapper<

  1068     Graph,

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

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

  1071   public:

  1072     typedef SubBidirGraphWrapper<

  1073       Graph,

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

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

  1076   protected:

  1077     const CapacityMap* capacity;

  1078     FlowMap* flow;

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

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

  1081     ResGraphWrapper() : Parent(),

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

  1083     void setCapacityMap(const CapacityMap& _capacity) {

  1084       capacity=&_capacity;

  1085       forward_filter.setCapacity(_capacity);

  1086       backward_filter.setCapacity(_capacity);

  1087     }

  1088     void setFlowMap(FlowMap& _flow) {

  1089       flow=&_flow;

  1090       forward_filter.setFlow(_flow);

  1091       backward_filter.setFlow(_flow);

  1092     }

  1093   public:

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

  1095 		       FlowMap& _flow) :

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

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

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

  1099       Parent::setGraph(_graph);

  1100       Parent::setForwardFilterMap(forward_filter);

  1101       Parent::setBackwardFilterMap(backward_filter);

  1102     }

  1104     typedef typename Parent::Edge Edge;

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

  1107       if (Parent::forward(e))

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

  1109       else

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

  1111     }

  1113     /// \brief Residual capacity map.

  1114     ///

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

  1116     /// as a map.

  1117     class ResCap {

  1118     protected:

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

  1120     public:

  1121       typedef Number Value;

  1122       typedef Edge Key;

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

  1124 	     _res_graph) : res_graph(&_res_graph) { }

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

  1126 	if (res_graph->forward(e))

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

  1128 	else

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

  1130       }

  1131     };

  1133     //    KEEP_MAPS(Parent, ResGraphWrapper);

  1134   };

  1138   template <typename _Graph, typename FirstOutEdgesMap>

  1139   class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {

  1140   public:

  1141     typedef _Graph Graph;

  1142     typedef GraphWrapperBase<_Graph> Parent;

  1143   protected:

  1144     FirstOutEdgesMap* first_out_edges;

  1145     ErasingFirstGraphWrapperBase() : Parent(),

  1146 				     first_out_edges(0) { }

  1148     void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {

  1149       first_out_edges=&_first_out_edges;

  1150     }

  1152   public:

  1154     typedef typename Parent::Node Node;

  1155     typedef typename Parent::Edge Edge;

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

  1158       i=(*first_out_edges)[n];

  1159     }

  1161     void erase(const Edge& e) const {

  1162       Node n=source(e);

  1163       Edge f=e;

  1164       Parent::nextOut(f);

  1165       first_out_edges->set(n, f);

  1166     }

  1167   };

  1170   /// For blocking flows.

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

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

  1174   ///

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

  1176   /// Dinits blocking flow computations.

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

  1178   /// \code

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

  1180   /// \endcode

  1181   /// is called.

  1182   ///

  1183   /// \author Marton Makai

  1184   template <typename _Graph, typename FirstOutEdgesMap>

  1185   class ErasingFirstGraphWrapper :

  1186     public IterableGraphExtender<

  1187     ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {

  1188   public:

  1189     typedef _Graph Graph;

  1190     typedef IterableGraphExtender<

  1191       ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;

  1192     ErasingFirstGraphWrapper(Graph& _graph,

  1193 			     FirstOutEdgesMap& _first_out_edges) {

  1194       setGraph(_graph);

  1195       setFirstOutEdgesMap(_first_out_edges);

  1196     }

  1198   };

  1200   ///@}

  1202 } //namespace lemon

  1204 #endif //LEMON_GRAPH_WRAPPER_H

author	marci
	Tue, 22 Mar 2005 16:00:00 +0000
changeset 1242	e48c4fe47aaf
parent 1198	6f1604392dc8
child 1252	4fee8e9d9014
permissions	-rw-r--r--