COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/graph_wrapper.h @ 898:c46cfb2651ec

Last change on this file since 898:c46cfb2651ec was 892:004636791dd7, checked in by marci, 20 years ago

graph_wrappers now pass the tests.

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