COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_wrapper.h @ 1081:c0ad2673b11f

Last change on this file since 1081:c0ad2673b11f was 1019:ee01de62188d, checked in by marci, 16 years ago

the old-style codes are removed from comment

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