COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/graph_wrapper.h @ 878:86b42ec55f3e

Last change on this file since 878:86b42ec55f3e was 878:86b42ec55f3e, checked in by Alpar Juttner, 18 years ago

Graph wrapper tests added.

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