COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_wrapper.h @ 921:818510fa3d99

Last change on this file since 921:818510fa3d99 was 921:818510fa3d99, checked in by Alpar Juttner, 16 years ago

hugo -> lemon

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