COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_wrapper.h @ 924:ccb657556d84

Last change on this file since 924:ccb657556d84 was 923:acbef5dd0e65, checked in by marci, 16 years ago

more docs

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