COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_wrapper.h @ 1135:cfccb33ecf7b

Last change on this file since 1135:cfccb33ecf7b was 1135:cfccb33ecf7b, checked in by Balazs Dezso, 15 years ago

Removing graph_defines.h

File size: 41.3 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 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 */
16
17#ifndef LEMON_GRAPH_WRAPPER_H
18#define LEMON_GRAPH_WRAPPER_H
19
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
27
28#include <lemon/invalid.h>
29#include <lemon/maps.h>
30#include <lemon/iterable_graph_extender.h>
31#include <iostream>
32
33namespace lemon {
34
35  // Graph wrappers
36
37  /*! \addtogroup gwrappers
38    The main parts of LEMON are the different graph structures,
39    generic graph algorithms, graph concepts which couple these, and
40    graph wrappers. While the previous ones are more or less clear, the
41    latter notion needs further explanation.
42    Graph wrappers are graph classes which serve for considering graph
43    structures in different ways. A short example makes the notion much
44    clearer.
45    Suppose that we have an instance \c g of a directed graph
46    type say \c ListGraph and an algorithm
47    \code template<typename Graph> int algorithm(const Graph&); \endcode
48    is needed to run on the reversely oriented graph.
49    It may be expensive (in time or in memory usage) to copy
50    \c g with the reverse orientation.
51    Thus, a wrapper class
52    \code template<typename Graph> class RevGraphWrapper; \endcode is used.
53    The code looks as follows
54    \code
55    ListGraph g;
56    RevGraphWrapper<ListGraph> rgw(g);
57    int result=algorithm(rgw);
58    \endcode
59    After running the algorithm, the original graph \c g
60    remains untouched. Thus the graph wrapper used above is to consider the
61    original graph with reverse orientation.
62    This techniques gives rise to an elegant code, and
63    based on stable graph wrappers, complex algorithms can be
64    implemented easily.
65    In flow, circulation and bipartite matching problems, the residual
66    graph is of particular importance. Combining a wrapper implementing
67    this, shortest path algorithms and minimum mean cycle algorithms,
68    a range of weighted and cardinality optimization algorithms can be
69    obtained. For lack of space, for other examples,
70    the interested user is referred to the detailed documentation of graph
71    wrappers.
72    The behavior of graph wrappers can be very different. Some of them keep
73    capabilities of the original graph while in other cases this would be
74    meaningless. This means that the concepts that they are a model of depend
75    on the graph wrapper, and the wrapped graph(s).
76    If an edge of \c rgw is deleted, this is carried out by
77    deleting the corresponding edge of \c g. But for a residual
78    graph, this operation has no sense.
79    Let we stand one more example here to simplify your work.
80    wrapper class
81    \code template<typename Graph> class RevGraphWrapper; \endcode
82    has constructor
83    <tt> RevGraphWrapper(Graph& _g)</tt>.
84    This means that in a situation,
85    when a <tt> const ListGraph& </tt> reference to a graph is given,
86    then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
87    \code
88    int algorithm1(const ListGraph& g) {
89    RevGraphWrapper<const ListGraph> rgw(g);
90    return algorithm2(rgw);
91    }
92    \endcode
93
94    \addtogroup gwrappers
95    @{
96
97    Base type for the Graph Wrappers
98
99    \warning Graph wrappers are in even more experimental state than the other
100    parts of the lib. Use them at you own risk.
101 
102    This is the base type for most of LEMON graph wrappers.
103    This class implements a trivial graph wrapper i.e. it only wraps the
104    functions and types of the graph. The purpose of this class is to
105    make easier implementing graph wrappers. E.g. if a wrapper is
106    considered which differs from the wrapped graph only in some of its
107    functions or types, then it can be derived from GraphWrapper, and only the
108    differences should be implemented.
109 
110    \author Marton Makai
111  */
112  template<typename _Graph>
113  class GraphWrapperBase {
114  public:
115    typedef _Graph Graph;
116    /// \todo Is it needed?
117    typedef Graph BaseGraph;
118    typedef Graph ParentGraph;
119
120  protected:
121    Graph* graph;
122    GraphWrapperBase() : graph(0) { }
123    void setGraph(Graph& _graph) { graph=&_graph; }
124
125  public:
126    GraphWrapperBase(Graph& _graph) : graph(&_graph) { }
127 
128    typedef typename Graph::Node Node;
129    typedef typename Graph::Edge Edge;
130   
131    void first(Node& i) const { graph->first(i); }
132    void first(Edge& i) const { graph->first(i); }
133    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
134    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
135
136    void next(Node& i) const { graph->next(i); }
137    void next(Edge& i) const { graph->next(i); }
138    void nextIn(Edge& i) const { graph->nextIn(i); }
139    void nextOut(Edge& i) const { graph->nextOut(i); }
140
141    Node source(const Edge& e) const { return graph->source(e); }
142    Node target(const Edge& e) const { return graph->target(e); }
143
144    int nodeNum() const { return graph->nodeNum(); }
145    int edgeNum() const { return graph->edgeNum(); }
146 
147    Node addNode() const { return Node(graph->addNode()); }
148    Edge addEdge(const Node& source, const Node& target) const {
149      return Edge(graph->addEdge(source, target)); }
150
151    void erase(const Node& i) const { graph->erase(i); }
152    void erase(const Edge& i) const { graph->erase(i); }
153 
154    void clear() const { graph->clear(); }
155   
156    bool forward(const Edge& e) const { return graph->forward(e); }
157    bool backward(const Edge& e) const { return graph->backward(e); }
158
159    int id(const Node& v) const { return graph->id(v); }
160    int id(const Edge& e) const { return graph->id(e); }
161   
162    Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
163
164    template <typename _Value>
165    class NodeMap : public _Graph::template NodeMap<_Value> {
166    public:
167      typedef typename _Graph::template NodeMap<_Value> Parent;
168      NodeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
169      NodeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
170      : Parent(*gw.graph, value) { }
171    };
172
173    template <typename _Value>
174    class EdgeMap : public _Graph::template EdgeMap<_Value> {
175    public:
176      typedef typename _Graph::template EdgeMap<_Value> Parent;
177      EdgeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
178      EdgeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
179      : Parent(*gw.graph, value) { }
180    };
181
182  };
183
184  template <typename _Graph>
185  class GraphWrapper :
186    public IterableGraphExtender<GraphWrapperBase<_Graph> > {
187  public:
188    typedef _Graph Graph;
189    typedef IterableGraphExtender<GraphWrapperBase<_Graph> > Parent;
190  protected:
191    GraphWrapper() : Parent() { }
192
193  public:
194    GraphWrapper(Graph& _graph) { setGraph(_graph); }
195  };
196
197  template <typename _Graph>
198  class RevGraphWrapperBase : public GraphWrapperBase<_Graph> {
199  public:
200    typedef _Graph Graph;
201    typedef GraphWrapperBase<_Graph> Parent;
202  protected:
203    RevGraphWrapperBase() : Parent() { }
204  public:
205    typedef typename Parent::Node Node;
206    typedef typename Parent::Edge Edge;
207
208    using Parent::first;
209    void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
210    void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
211
212    using Parent::next;
213    void nextIn(Edge& i) const { Parent::nextOut(i); }
214    void nextOut(Edge& i) const { Parent::nextIn(i); }
215
216    Node source(const Edge& e) const { return Parent::target(e); }
217    Node target(const Edge& e) const { return Parent::source(e); }
218  };
219   
220
221  /// A graph wrapper which reverses the orientation of the edges.
222
223  ///\warning Graph wrappers are in even more experimental state than the other
224  ///parts of the lib. Use them at you own risk.
225  ///
226  /// Let \f$G=(V, A)\f$ be a directed graph and
227  /// suppose that a graph instange \c g of type
228  /// \c ListGraph implements \f$G\f$.
229  /// \code
230  /// ListGraph g;
231  /// \endcode
232  /// For each directed edge
233  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
234  /// reversing its orientation.
235  /// Then RevGraphWrapper implements the graph structure with node-set
236  /// \f$V\f$ and edge-set
237  /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
238  /// reversing the orientation of its edges. The following code shows how
239  /// such an instance can be constructed.
240  /// \code
241  /// RevGraphWrapper<ListGraph> gw(g);
242  /// \endcode
243  ///\author Marton Makai
244  template<typename _Graph>
245  class RevGraphWrapper :
246    public IterableGraphExtender<RevGraphWrapperBase<_Graph> > {
247  public:
248    typedef _Graph Graph;
249    typedef IterableGraphExtender<
250      RevGraphWrapperBase<_Graph> > Parent;
251  protected:
252    RevGraphWrapper() { }
253  public:
254    RevGraphWrapper(_Graph& _graph) { setGraph(_graph); }
255  };
256
257 
258  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
259  class SubGraphWrapperBase : public GraphWrapperBase<_Graph> {
260  public:
261    typedef _Graph Graph;
262    typedef GraphWrapperBase<_Graph> Parent;
263  protected:
264    NodeFilterMap* node_filter_map;
265    EdgeFilterMap* edge_filter_map;
266    SubGraphWrapperBase() : Parent(),
267                            node_filter_map(0), edge_filter_map(0) { }
268
269    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
270      node_filter_map=&_node_filter_map;
271    }
272    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
273      edge_filter_map=&_edge_filter_map;
274    }
275
276  public:
277//     SubGraphWrapperBase(Graph& _graph,
278//                      NodeFilterMap& _node_filter_map,
279//                      EdgeFilterMap& _edge_filter_map) :
280//       Parent(&_graph),
281//       node_filter_map(&node_filter_map),
282//       edge_filter_map(&edge_filter_map) { }
283
284    typedef typename Parent::Node Node;
285    typedef typename Parent::Edge Edge;
286
287    void first(Node& i) const {
288      Parent::first(i);
289      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
290    }
291    void first(Edge& i) const {
292      Parent::first(i);
293      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
294    }
295    void firstIn(Edge& i, const Node& n) const {
296      Parent::firstIn(i, n);
297      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
298    }
299    void firstOut(Edge& i, const Node& n) const {
300      Parent::firstOut(i, n);
301      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
302    }
303
304    void next(Node& i) const {
305      Parent::next(i);
306      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
307    }
308    void next(Edge& i) const {
309      Parent::next(i);
310      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
311    }
312    void nextIn(Edge& i) const {
313      Parent::nextIn(i);
314      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
315    }
316    void nextOut(Edge& i) const {
317      Parent::nextOut(i);
318      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
319    }
320
321    /// This function hides \c n in the graph, i.e. the iteration
322    /// jumps over it. This is done by simply setting the value of \c n 
323    /// to be false in the corresponding node-map.
324    void hide(const Node& n) const { node_filter_map->set(n, false); }
325
326    /// This function hides \c e in the graph, i.e. the iteration
327    /// jumps over it. This is done by simply setting the value of \c e 
328    /// to be false in the corresponding edge-map.
329    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
330
331    /// The value of \c n is set to be true in the node-map which stores
332    /// hide information. If \c n was hidden previuosly, then it is shown
333    /// again
334     void unHide(const Node& n) const { node_filter_map->set(n, true); }
335
336    /// The value of \c e is set to be true in the edge-map which stores
337    /// hide information. If \c e was hidden previuosly, then it is shown
338    /// again
339    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
340
341    /// Returns true if \c n is hidden.
342    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
343
344    /// Returns true if \c n is hidden.
345    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
346
347    /// \warning This is a linear time operation and works only if s
348    /// \c Graph::NodeIt is defined.
349    /// \todo assign tags.
350    int nodeNum() const {
351      int i=0;
352      Node n;
353      for (first(n); n!=INVALID; next(n)) ++i;
354      return i;
355    }
356
357    /// \warning This is a linear time operation and works only if
358    /// \c Graph::EdgeIt is defined.
359    /// \todo assign tags.
360    int edgeNum() const {
361      int i=0;
362      Edge e;
363      for (first(e); e!=INVALID; next(e)) ++i;
364      return i;
365    }
366
367
368  };
369
370  /*! \brief A graph wrapper for hiding nodes and edges from a graph.
371 
372  \warning Graph wrappers are in even more experimental state than the other
373  parts of the lib. Use them at you own risk.
374 
375  This wrapper shows a graph with filtered node-set and
376  edge-set.
377  Given a bool-valued map on the node-set and one on
378  the edge-set of the graph, the iterators show only the objects
379  having true value. We have to note that this does not mean that an
380  induced subgraph is obtained, the node-iterator cares only the filter
381  on the node-set, and the edge-iterators care only the filter on the
382  edge-set.
383  \code
384  typedef SmartGraph Graph;
385  Graph g;
386  typedef Graph::Node Node;
387  typedef Graph::Edge Edge;
388  Node u=g.addNode(); //node of id 0
389  Node v=g.addNode(); //node of id 1
390  Node e=g.addEdge(u, v); //edge of id 0
391  Node f=g.addEdge(v, u); //edge of id 1
392  Graph::NodeMap<bool> nm(g, true);
393  nm.set(u, false);
394  Graph::EdgeMap<bool> em(g, true);
395  em.set(e, false);
396  typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
397  SubGW gw(g, nm, em);
398  for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
399  std::cout << ":-)" << std::endl;
400  for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
401  \endcode
402  The output of the above code is the following.
403  \code
404  1
405  :-)
406  1
407  \endcode
408  Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
409  \c Graph::Node that is why \c g.id(n) can be applied.
410
411  For other examples see also the documentation of NodeSubGraphWrapper and
412  EdgeSubGraphWrapper.
413
414  \author Marton Makai
415  */
416  template<typename _Graph, typename NodeFilterMap,
417           typename EdgeFilterMap>
418  class SubGraphWrapper :
419    public IterableGraphExtender<
420    SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
421  public:
422    typedef _Graph Graph;
423    typedef IterableGraphExtender<
424      SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
425  protected:
426    SubGraphWrapper() { }
427  public:
428    SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map,
429                    EdgeFilterMap& _edge_filter_map) {
430      setGraph(_graph);
431      setNodeFilterMap(_node_filter_map);
432      setEdgeFilterMap(_edge_filter_map);
433    }
434  };
435
436
437
438  /*! \brief A wrapper for hiding nodes from a graph.
439
440  \warning Graph wrappers are in even more experimental state than the other
441  parts of the lib. Use them at you own risk.
442 
443  A wrapper for hiding nodes from a graph.
444  This wrapper specializes SubGraphWrapper in the way that only the node-set
445  can be filtered. Note that this does not mean of considering induced
446  subgraph, the edge-iterators consider the original edge-set.
447  \author Marton Makai
448  */
449  template<typename Graph, typename NodeFilterMap>
450  class NodeSubGraphWrapper :
451    public SubGraphWrapper<Graph, NodeFilterMap,
452                           ConstMap<typename Graph::Edge,bool> > {
453  public:
454    typedef SubGraphWrapper<Graph, NodeFilterMap,
455                            ConstMap<typename Graph::Edge,bool> > Parent;
456  protected:
457    ConstMap<typename Graph::Edge, bool> const_true_map;
458  public:
459    NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :
460      Parent(), const_true_map(true) {
461      Parent::setGraph(_graph);
462      Parent::setNodeFilterMap(_node_filter_map);
463      Parent::setEdgeFilterMap(const_true_map);
464    }
465  };
466
467
468  /*! \brief A wrapper for hiding edges from a graph.
469
470  \warning Graph wrappers are in even more experimental state than the other
471  parts of the lib. Use them at you own risk.
472 
473  A wrapper for hiding edges from a graph.
474  This wrapper specializes SubGraphWrapper in the way that only the edge-set
475  can be filtered. The usefulness of this wrapper is demonstrated in the
476  problem of searching a maximum number of edge-disjoint shortest paths
477  between
478  two nodes \c s and \c t. Shortest here means being shortest w.r.t.
479  non-negative edge-lengths. Note that
480  the comprehension of the presented solution
481  need's some knowledge from elementary combinatorial optimization.
482
483  If a single shortest path is to be
484  searched between two nodes \c s and \c t, then this can be done easily by
485  applying the Dijkstra algorithm class. What happens, if a maximum number of
486  edge-disjoint shortest paths is to be computed. It can be proved that an
487  edge can be in a shortest path if and only if it is tight with respect to
488  the potential function computed by Dijkstra. Moreover, any path containing
489  only such edges is a shortest one. Thus we have to compute a maximum number
490  of edge-disjoint paths between \c s and \c t in the graph which has edge-set
491  all the tight edges. The computation will be demonstrated on the following
492  graph, which is read from a dimacs file.
493 
494  \dot
495  digraph lemon_dot_example {
496  node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
497  n0 [ label="0 (s)" ];
498  n1 [ label="1" ];
499  n2 [ label="2" ];
500  n3 [ label="3" ];
501  n4 [ label="4" ];
502  n5 [ label="5" ];
503  n6 [ label="6 (t)" ];
504  edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
505  n5 ->  n6 [ label="9, length:4" ];
506  n4 ->  n6 [ label="8, length:2" ];
507  n3 ->  n5 [ label="7, length:1" ];
508  n2 ->  n5 [ label="6, length:3" ];
509  n2 ->  n6 [ label="5, length:5" ];
510  n2 ->  n4 [ label="4, length:2" ];
511  n1 ->  n4 [ label="3, length:3" ];
512  n0 ->  n3 [ label="2, length:1" ];
513  n0 ->  n2 [ label="1, length:2" ];
514  n0 ->  n1 [ label="0, length:3" ];
515  }
516  \enddot
517
518  \code
519  Graph g;
520  Node s, t;
521  LengthMap length(g);
522
523  readDimacs(std::cin, g, length, s, t);
524
525  cout << "edges with lengths (of form id, source--length->target): " << endl;
526  for(EdgeIt e(g); e!=INVALID; ++e)
527    cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
528         << length[e] << "->" << g.id(g.target(e)) << endl;
529
530  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
531  \endcode
532  Next, the potential function is computed with Dijkstra.
533  \code
534  typedef Dijkstra<Graph, LengthMap> Dijkstra;
535  Dijkstra dijkstra(g, length);
536  dijkstra.run(s);
537  \endcode
538  Next, we consrtruct a map which filters the edge-set to the tight edges.
539  \code
540  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
541    TightEdgeFilter;
542  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
543 
544  typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
545  SubGW gw(g, tight_edge_filter);
546  \endcode
547  Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
548  with a max flow algorithm Preflow.
549  \code
550  ConstMap<Edge, int> const_1_map(1);
551  Graph::EdgeMap<int> flow(g, 0);
552
553  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
554    preflow(gw, s, t, const_1_map, flow);
555  preflow.run();
556  \endcode
557  Last, the output is:
558  \code 
559  cout << "maximum number of edge-disjoint shortest path: "
560       << preflow.flowValue() << endl;
561  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
562       << endl;
563  for(EdgeIt e(g); e!=INVALID; ++e)
564    if (flow[e])
565      cout << " " << g.id(g.source(e)) << "--"
566           << length[e] << "->" << g.id(g.target(e)) << endl;
567  \endcode
568  The program has the following (expected :-)) output:
569  \code
570  edges with lengths (of form id, source--length->target):
571   9, 5--4->6
572   8, 4--2->6
573   7, 3--1->5
574   6, 2--3->5
575   5, 2--5->6
576   4, 2--2->4
577   3, 1--3->4
578   2, 0--1->3
579   1, 0--2->2
580   0, 0--3->1
581  s: 0 t: 6
582  maximum number of edge-disjoint shortest path: 2
583  edges of the maximum number of edge-disjoint shortest s-t paths:
584   9, 5--4->6
585   8, 4--2->6
586   7, 3--1->5
587   4, 2--2->4
588   2, 0--1->3
589   1, 0--2->2
590  \endcode
591
592  \author Marton Makai
593  */
594  template<typename Graph, typename EdgeFilterMap>
595  class EdgeSubGraphWrapper :
596    public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
597                           EdgeFilterMap> {
598  public:
599    typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
600                            EdgeFilterMap> Parent;
601  protected:
602    ConstMap<typename Graph::Node, bool> const_true_map;
603  public:
604    EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
605      Parent(), const_true_map(true) {
606      Parent::setGraph(_graph);
607      Parent::setNodeFilterMap(const_true_map);
608      Parent::setEdgeFilterMap(_edge_filter_map);
609    }
610  };
611
612
613  template<typename Graph>
614  class UndirGraphWrapper : public GraphWrapper<Graph> {
615  public:
616    typedef GraphWrapper<Graph> Parent;
617  protected:
618    UndirGraphWrapper() : GraphWrapper<Graph>() { }
619   
620  public:
621    typedef typename GraphWrapper<Graph>::Node Node;
622    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
623    typedef typename GraphWrapper<Graph>::Edge Edge;
624    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
625
626    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
627
628    class OutEdgeIt {
629      friend class UndirGraphWrapper<Graph>;
630      bool out_or_in; //true iff out
631      typename Graph::OutEdgeIt out;
632      typename Graph::InEdgeIt in;
633    public:
634      OutEdgeIt() { }
635      OutEdgeIt(const Invalid& i) : Edge(i) { }
636      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
637        out_or_in=true; _G.graph->first(out, _n);
638        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
639      }
640      operator Edge() const {
641        if (out_or_in) return Edge(out); else return Edge(in);
642      }
643    };
644
645    typedef OutEdgeIt InEdgeIt;
646
647    using GraphWrapper<Graph>::first;
648    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
649      i=OutEdgeIt(*this, p); return i;
650    }
651
652    using GraphWrapper<Graph>::next;
653
654    OutEdgeIt& next(OutEdgeIt& e) const {
655      if (e.out_or_in) {
656        typename Graph::Node n=this->graph->source(e.out);
657        this->graph->next(e.out);
658        if (!this->graph->valid(e.out)) {
659          e.out_or_in=false; this->graph->first(e.in, n); }
660      } else {
661        this->graph->next(e.in);
662      }
663      return e;
664    }
665
666    Node aNode(const OutEdgeIt& e) const {
667      if (e.out_or_in) return this->graph->source(e); else
668        return this->graph->target(e); }
669    Node bNode(const OutEdgeIt& e) const {
670      if (e.out_or_in) return this->graph->target(e); else
671        return this->graph->source(e); }
672
673    //    KEEP_MAPS(Parent, UndirGraphWrapper);
674
675  };
676 
677//   /// \brief An undirected graph template.
678//   ///
679//   ///\warning Graph wrappers are in even more experimental state than the other
680//   ///parts of the lib. Use them at your own risk.
681//   ///
682//   /// An undirected graph template.
683//   /// This class works as an undirected graph and a directed graph of
684//   /// class \c Graph is used for the physical storage.
685//   /// \ingroup graphs
686  template<typename Graph>
687  class UndirGraph : public UndirGraphWrapper<Graph> {
688    typedef UndirGraphWrapper<Graph> Parent;
689  protected:
690    Graph gr;
691  public:
692    UndirGraph() : UndirGraphWrapper<Graph>() {
693      Parent::setGraph(gr);
694    }
695
696    //    KEEP_MAPS(Parent, UndirGraph);
697  };
698
699 
700  template <typename _Graph,
701            typename ForwardFilterMap, typename BackwardFilterMap>
702  class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {
703  public:
704    typedef _Graph Graph;
705    typedef GraphWrapperBase<_Graph> Parent;
706  protected:
707    ForwardFilterMap* forward_filter;
708    BackwardFilterMap* backward_filter;
709    SubBidirGraphWrapperBase() : Parent(),
710                                 forward_filter(0), backward_filter(0) { }
711
712    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
713      forward_filter=&_forward_filter;
714    }
715    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
716      backward_filter=&_backward_filter;
717    }
718
719  public:
720//     SubGraphWrapperBase(Graph& _graph,
721//                      NodeFilterMap& _node_filter_map,
722//                      EdgeFilterMap& _edge_filter_map) :
723//       Parent(&_graph),
724//       node_filter_map(&node_filter_map),
725//       edge_filter_map(&edge_filter_map) { }
726
727    typedef typename Parent::Node Node;
728    typedef typename _Graph::Edge GraphEdge;
729    template <typename T> class EdgeMap;
730    /// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from
731    /// _Graph::Edge. It contains an extra bool flag which is true
732    /// if and only if the
733    /// edge is the backward version of the original edge.
734    class Edge : public _Graph::Edge {
735      friend class SubBidirGraphWrapperBase<
736        Graph, ForwardFilterMap, BackwardFilterMap>;
737      template<typename T> friend class EdgeMap;
738    protected:
739      bool backward; //true, iff backward
740    public:
741      Edge() { }
742      /// \todo =false is needed, or causes problems?
743      /// If \c _backward is false, then we get an edge corresponding to the
744      /// original one, otherwise its oppositely directed pair is obtained.
745      Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
746        _Graph::Edge(e), backward(_backward) { }
747      Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
748      bool operator==(const Edge& v) const {
749        return (this->backward==v.backward &&
750                static_cast<typename _Graph::Edge>(*this)==
751                static_cast<typename _Graph::Edge>(v));
752      }
753      bool operator!=(const Edge& v) const {
754        return (this->backward!=v.backward ||
755                static_cast<typename _Graph::Edge>(*this)!=
756                static_cast<typename _Graph::Edge>(v));
757      }
758    };
759
760    void first(Node& i) const {
761      Parent::first(i);
762    }
763
764    void first(Edge& i) const {
765      Parent::first(i);
766      i.backward=false;
767      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
768             !(*forward_filter)[i]) Parent::next(i);
769      if (*static_cast<GraphEdge*>(&i)==INVALID) {
770        Parent::first(i);
771        i.backward=true;
772        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
773               !(*backward_filter)[i]) Parent::next(i);
774      }
775    }
776
777    void firstIn(Edge& i, const Node& n) const {
778      Parent::firstIn(i, n);
779      i.backward=false;
780      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
781             !(*forward_filter)[i]) Parent::nextOut(i);
782      if (*static_cast<GraphEdge*>(&i)==INVALID) {
783        Parent::firstOut(i, n);
784        i.backward=true;
785        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
786               !(*backward_filter)[i]) Parent::nextOut(i);
787      }
788    }
789
790    void firstOut(Edge& i, const Node& n) const {
791      Parent::firstOut(i, n);
792      i.backward=false;
793      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
794             !(*forward_filter)[i]) Parent::nextOut(i);
795      if (*static_cast<GraphEdge*>(&i)==INVALID) {
796        Parent::firstIn(i, n);
797        i.backward=true;
798        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
799               !(*backward_filter)[i]) Parent::nextIn(i);
800      }
801    }
802
803    void next(Node& i) const {
804      Parent::next(i);
805    }
806
807    void next(Edge& i) const {
808      if (!(i.backward)) {
809        Parent::next(i);
810        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
811               !(*forward_filter)[i]) Parent::next(i);
812        if (*static_cast<GraphEdge*>(&i)==INVALID) {
813          Parent::first(i);
814          i.backward=true;
815          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
816                 !(*backward_filter)[i]) Parent::next(i);
817        }
818      } else {
819        Parent::next(i);
820        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
821               !(*backward_filter)[i]) Parent::next(i);
822      }
823    }
824
825    void nextIn(Edge& i) const {
826      if (!(i.backward)) {
827        Node n=Parent::target(i);
828        Parent::nextIn(i);
829        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
830               !(*forward_filter)[i]) Parent::nextIn(i);
831        if (*static_cast<GraphEdge*>(&i)==INVALID) {
832          Parent::firstOut(i, n);
833          i.backward=true;
834          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
835                 !(*backward_filter)[i]) Parent::nextOut(i);
836        }
837      } else {
838        Parent::nextOut(i);
839        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
840               !(*backward_filter)[i]) Parent::nextOut(i);
841      }
842    }
843
844    void nextOut(Edge& i) const {
845      if (!(i.backward)) {
846        Node n=Parent::source(i);
847        Parent::nextOut(i);
848        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
849               !(*forward_filter)[i]) Parent::nextOut(i);
850        if (*static_cast<GraphEdge*>(&i)==INVALID) {
851          Parent::firstIn(i, n);
852          i.backward=true;
853          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
854                 !(*backward_filter)[i]) Parent::nextIn(i);
855        }
856      } else {
857        Parent::nextIn(i);
858        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
859               !(*backward_filter)[i]) Parent::nextIn(i);
860      }
861    }
862
863    Node source(Edge e) const {
864      return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
865    Node target(Edge e) const {
866      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
867
868    /// Gives back the opposite edge.
869    Edge opposite(const Edge& e) const {
870      Edge f=e;
871      f.backward=!f.backward;
872      return f;
873    }
874
875    /// \warning This is a linear time operation and works only if
876    /// \c Graph::EdgeIt is defined.
877    /// \todo hmm
878    int edgeNum() const {
879      int i=0;
880      Edge e;
881      for (first(e); e!=INVALID; next(e)) ++i;
882      return i;
883    }
884
885    bool forward(const Edge& e) const { return !e.backward; }
886    bool backward(const Edge& e) const { return e.backward; }
887
888    template <typename T>
889    /// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two
890    /// _Graph::EdgeMap one for the forward edges and
891    /// one for the backward edges.
892    class EdgeMap {
893      template <typename TT> friend class EdgeMap;
894      typename _Graph::template EdgeMap<T> forward_map, backward_map;
895    public:
896      typedef T Value;
897      typedef Edge Key;
898
899      EdgeMap(const SubBidirGraphWrapperBase<_Graph,
900              ForwardFilterMap, BackwardFilterMap>& g) :
901        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
902
903      EdgeMap(const SubBidirGraphWrapperBase<_Graph,
904              ForwardFilterMap, BackwardFilterMap>& g, T a) :
905        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
906     
907      void set(Edge e, T a) {
908        if (!e.backward)
909          forward_map.set(e, a);
910        else
911          backward_map.set(e, a);
912      }
913
914//       typename _Graph::template EdgeMap<T>::ConstReference
915//       operator[](Edge e) const {
916//      if (!e.backward)
917//        return forward_map[e];
918//      else
919//        return backward_map[e];
920//       }
921
922//      typename _Graph::template EdgeMap<T>::Reference
923      T operator[](Edge e) const {
924        if (!e.backward)
925          return forward_map[e];
926        else
927          return backward_map[e];
928      }
929
930      void update() {
931        forward_map.update();
932        backward_map.update();
933      }
934    };
935
936  };
937
938
939  ///\brief A wrapper for composing a subgraph of a
940  /// bidirected graph made from a directed one.
941  ///
942  /// A wrapper for composing a subgraph of a
943  /// bidirected graph made from a directed one.
944  ///
945  ///\warning Graph wrappers are in even more experimental state than the other
946  ///parts of the lib. Use them at you own risk.
947  ///
948  /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
949  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
950  /// reversing its orientation. We are given moreover two bool valued
951  /// maps on the edge-set,
952  /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
953  /// SubBidirGraphWrapper implements the graph structure with node-set
954  /// \f$V\f$ and edge-set
955  /// \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$.
956  /// The purpose of writing + instead of union is because parallel
957  /// edges can arise. (Similarly, antiparallel edges also can arise).
958  /// In other words, a subgraph of the bidirected graph obtained, which
959  /// is given by orienting the edges of the original graph in both directions.
960  /// As the oppositely directed edges are logically different,
961  /// the maps are able to attach different values for them.
962  ///
963  /// An example for such a construction is \c RevGraphWrapper where the
964  /// forward_filter is everywhere false and the backward_filter is
965  /// everywhere true. We note that for sake of efficiency,
966  /// \c RevGraphWrapper is implemented in a different way.
967  /// But BidirGraphWrapper is obtained from
968  /// SubBidirGraphWrapper by considering everywhere true
969  /// valued maps both for forward_filter and backward_filter.
970  /// Finally, one of the most important applications of SubBidirGraphWrapper
971  /// is ResGraphWrapper, which stands for the residual graph in directed
972  /// flow and circulation problems.
973  /// As wrappers usually, the SubBidirGraphWrapper implements the
974  /// above mentioned graph structure without its physical storage,
975  /// that is the whole stuff is stored in constant memory.
976  template<typename _Graph,
977           typename ForwardFilterMap, typename BackwardFilterMap>
978  class SubBidirGraphWrapper :
979    public IterableGraphExtender<
980    SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
981  public:
982    typedef _Graph Graph;
983    typedef IterableGraphExtender<
984      SubBidirGraphWrapperBase<
985      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
986  protected:
987    SubBidirGraphWrapper() { }
988  public:
989    SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,
990                         BackwardFilterMap& _backward_filter) {
991      setGraph(_graph);
992      setForwardFilterMap(_forward_filter);
993      setBackwardFilterMap(_backward_filter);
994    }
995  };
996
997
998
999  ///\brief A wrapper for composing bidirected graph from a directed one.
1000  ///
1001  ///\warning Graph wrappers are in even more experimental state than the other
1002  ///parts of the lib. Use them at you own risk.
1003  ///
1004  /// A wrapper for composing bidirected graph from a directed one.
1005  /// A bidirected graph is composed over the directed one without physical
1006  /// storage. As the oppositely directed edges are logically different ones
1007  /// the maps are able to attach different values for them.
1008  template<typename Graph>
1009  class BidirGraphWrapper :
1010    public SubBidirGraphWrapper<
1011    Graph,
1012    ConstMap<typename Graph::Edge, bool>,
1013    ConstMap<typename Graph::Edge, bool> > {
1014  public:
1015    typedef  SubBidirGraphWrapper<
1016      Graph,
1017      ConstMap<typename Graph::Edge, bool>,
1018      ConstMap<typename Graph::Edge, bool> > Parent;
1019  protected:
1020    ConstMap<typename Graph::Edge, bool> cm;
1021
1022    BidirGraphWrapper() : Parent(), cm(true) {
1023      Parent::setForwardFilterMap(cm);
1024      Parent::setBackwardFilterMap(cm);
1025    }
1026  public:
1027    BidirGraphWrapper(Graph& _graph) : Parent() {
1028      Parent::setGraph(_graph);
1029      Parent::setForwardFilterMap(cm);
1030      Parent::setBackwardFilterMap(cm);
1031    }
1032
1033    int edgeNum() const {
1034      return 2*this->graph->edgeNum();
1035    }
1036    //    KEEP_MAPS(Parent, BidirGraphWrapper);
1037  };
1038
1039
1040  /// \brief A bidirected graph template.
1041  ///
1042  ///\warning Graph wrappers are in even more experimental state than the other
1043  ///parts of the lib. Use them at you own risk.
1044  ///
1045  /// A bidirected graph template.
1046  /// Such a bidirected graph stores each pair of oppositely directed edges
1047  /// ones in the memory, i.e. a directed graph of type
1048  /// \c Graph is used for that.
1049  /// As the oppositely directed edges are logically different ones
1050  /// the maps are able to attach different values for them.
1051  /// \ingroup graphs
1052  template<typename Graph>
1053  class BidirGraph : public BidirGraphWrapper<Graph> {
1054  public:
1055    typedef UndirGraphWrapper<Graph> Parent;
1056  protected:
1057    Graph gr;
1058  public:
1059    BidirGraph() : BidirGraphWrapper<Graph>() {
1060      Parent::setGraph(gr);
1061    }
1062    //    KEEP_MAPS(Parent, BidirGraph);
1063  };
1064
1065
1066
1067  template<typename Graph, typename Number,
1068           typename CapacityMap, typename FlowMap>
1069  class ResForwardFilter {
1070    //    const Graph* graph;
1071    const CapacityMap* capacity;
1072    const FlowMap* flow;
1073  public:
1074    ResForwardFilter(/*const Graph& _graph, */
1075                     const CapacityMap& _capacity, const FlowMap& _flow) :
1076      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1077    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1078    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1079    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1080    bool operator[](const typename Graph::Edge& e) const {
1081      return (Number((*flow)[e]) < Number((*capacity)[e]));
1082    }
1083  };
1084
1085  template<typename Graph, typename Number,
1086           typename CapacityMap, typename FlowMap>
1087  class ResBackwardFilter {
1088    const CapacityMap* capacity;
1089    const FlowMap* flow;
1090  public:
1091    ResBackwardFilter(/*const Graph& _graph,*/
1092                      const CapacityMap& _capacity, const FlowMap& _flow) :
1093      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1094    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1095    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1096    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1097    bool operator[](const typename Graph::Edge& e) const {
1098      return (Number(0) < Number((*flow)[e]));
1099    }
1100  };
1101
1102 
1103  /// A wrapper for composing the residual graph for directed flow and circulation problems.
1104
1105  ///\warning Graph wrappers are in even more experimental state than the other
1106  ///parts of the lib. Use them at you own risk.
1107  ///
1108  /// A wrapper for composing the residual graph for directed flow and circulation problems.
1109  template<typename Graph, typename Number,
1110           typename CapacityMap, typename FlowMap>
1111  class ResGraphWrapper :
1112    public SubBidirGraphWrapper<
1113    Graph,
1114    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1115    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1116  public:
1117    typedef SubBidirGraphWrapper<
1118      Graph,
1119      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1120      ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1121  protected:
1122    const CapacityMap* capacity;
1123    FlowMap* flow;
1124    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1125    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1126    ResGraphWrapper() : Parent(),
1127                        capacity(0), flow(0) { }
1128    void setCapacityMap(const CapacityMap& _capacity) {
1129      capacity=&_capacity;
1130      forward_filter.setCapacity(_capacity);
1131      backward_filter.setCapacity(_capacity);
1132    }
1133    void setFlowMap(FlowMap& _flow) {
1134      flow=&_flow;
1135      forward_filter.setFlow(_flow);
1136      backward_filter.setFlow(_flow);
1137    }
1138  public:
1139    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1140                       FlowMap& _flow) :
1141      Parent(), capacity(&_capacity), flow(&_flow),
1142      forward_filter(/*_graph,*/ _capacity, _flow),
1143      backward_filter(/*_graph,*/ _capacity, _flow) {
1144      Parent::setGraph(_graph);
1145      Parent::setForwardFilterMap(forward_filter);
1146      Parent::setBackwardFilterMap(backward_filter);
1147    }
1148
1149    typedef typename Parent::Edge Edge;
1150
1151    void augment(const Edge& e, Number a) const {
1152      if (Parent::forward(e)) 
1153        flow->set(e, (*flow)[e]+a);
1154      else 
1155        flow->set(e, (*flow)[e]-a);
1156    }
1157
1158    /// \brief Residual capacity map.
1159    ///
1160    /// In generic residual graphs the residual capacity can be obtained
1161    /// as a map.
1162    class ResCap {
1163    protected:
1164      const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1165    public:
1166      typedef Number Value;
1167      typedef Edge Key;
1168      ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
1169             _res_graph) : res_graph(&_res_graph) { }
1170      Number operator[](const Edge& e) const {
1171        if (res_graph->forward(e))
1172          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1173        else
1174          return (*(res_graph->flow))[e];
1175      }
1176    };
1177
1178    //    KEEP_MAPS(Parent, ResGraphWrapper);
1179  };
1180
1181
1182
1183  template <typename _Graph, typename FirstOutEdgesMap>
1184  class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {
1185  public:
1186    typedef _Graph Graph;
1187    typedef GraphWrapperBase<_Graph> Parent;
1188  protected:
1189    FirstOutEdgesMap* first_out_edges;
1190    ErasingFirstGraphWrapperBase() : Parent(),
1191                                     first_out_edges(0) { }
1192
1193    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1194      first_out_edges=&_first_out_edges;
1195    }
1196
1197  public:
1198
1199    typedef typename Parent::Node Node;
1200    typedef typename Parent::Edge Edge;
1201
1202    void firstOut(Edge& i, const Node& n) const {
1203      i=(*first_out_edges)[n];
1204    }
1205
1206    void erase(const Edge& e) const {
1207      Node n=source(e);
1208      Edge f=e;
1209      Parent::nextOut(f);
1210      first_out_edges->set(n, f);
1211    }   
1212  };
1213
1214
1215  /// For blocking flows.
1216
1217  ///\warning Graph wrappers are in even more experimental state than the other
1218  ///parts of the lib. Use them at you own risk.
1219  ///
1220  /// This graph wrapper is used for on-the-fly
1221  /// Dinits blocking flow computations.
1222  /// For each node, an out-edge is stored which is used when the
1223  /// \code
1224  /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1225  /// \endcode
1226  /// is called.
1227  ///
1228  /// \author Marton Makai
1229  template <typename _Graph, typename FirstOutEdgesMap>
1230  class ErasingFirstGraphWrapper :
1231    public IterableGraphExtender<
1232    ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {
1233  public:
1234    typedef _Graph Graph;
1235    typedef IterableGraphExtender<
1236      ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;
1237    ErasingFirstGraphWrapper(Graph& _graph,
1238                             FirstOutEdgesMap& _first_out_edges) {
1239      setGraph(_graph);
1240      setFirstOutEdgesMap(_first_out_edges);
1241    }
1242
1243  };
1244
1245  ///@}
1246
1247} //namespace lemon
1248
1249#endif //LEMON_GRAPH_WRAPPER_H
1250
Note: See TracBrowser for help on using the repository browser.