COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/graph_wrapper.h @ 906:17f31d280385

Last change on this file since 906:17f31d280385 was 906:17f31d280385, checked in by Alpar Juttner, 18 years ago

Copyright header added.

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