COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_wrapper.h @ 930:e89f3bd26fd4

Last change on this file since 930:e89f3bd26fd4 was 930:e89f3bd26fd4, checked in by marci, 20 years ago

documentation os SubGraphWrapper? with code example.

File size: 48.0 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  /*! \brief 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  Consider now a mathematically more invloved problem, where the application
372  of SubGraphWrapper is reasonable sure enough. If a shortest path is to be
373  searched between two nodes \c s and \c t, then this can be done easily by
374  applying the Dijkstra algorithm class. What happens, if a maximum number of
375  edge-disjoint shortest paths is to be computed. It can be proved that an
376  edge can be in a shortest path if and only if it is tight with respect to
377  the potential function computed by Dijkstra. Moreover, any path containing
378  only such edges is a shortest one. Thus we have to compute a maximum number
379  of edge-disjoint path between \c s and \c t in the graph which has edge-set
380  all the tight edges. The computation will be demonstrated on the following
381  graph, which is read from a dimacs file.
382 
383  \dot
384  digraph lemon_dot_example {
385  node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
386  n0 [ label="0 (s)" ];
387  n1 [ label="1" ];
388  n2 [ label="2" ];
389  n3 [ label="3" ];
390  n4 [ label="4" ];
391  n5 [ label="5" ];
392  n6 [ label="6 (t)" ];
393  edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
394  n5 ->  n6 [ label="9, length:4" ];
395  n4 ->  n6 [ label="8, length:2" ];
396  n3 ->  n5 [ label="7, length:1" ];
397  n2 ->  n5 [ label="6, length:3" ];
398  n2 ->  n6 [ label="5, length:5" ];
399  n2 ->  n4 [ label="4, length:2" ];
400  n1 ->  n4 [ label="3, length:3" ];
401  n0 ->  n3 [ label="2, length:1" ];
402  n0 ->  n2 [ label="1, length:2" ];
403  n0 ->  n1 [ label="0, length:3" ];
404  }
405  \enddot
406
407  \code
408  Graph g;
409  Node s, t;
410  LengthMap length(g);
411
412  readDimacs(std::cin, g, length, s, t);
413
414  cout << "edges with lengths (of form id, tail--length->head): " << endl;
415  for(EdgeIt e(g); e!=INVALID; ++e)
416    cout << g.id(e) << ", " << g.id(g.tail(e)) << "--"
417         << length[e] << "->" << g.id(g.head(e)) << endl;
418
419  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
420  \endcode
421  Next, the potential function is computed with Dijkstra.
422  \code
423  typedef Dijkstra<Graph, LengthMap> Dijkstra;
424  Dijkstra dijkstra(g, length);
425  dijkstra.run(s);
426  \endcode
427  Next, we consrtruct a map which filters the edge-set to the tight edges.
428  \code
429  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
430    TightEdgeFilter;
431  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
432 
433  ConstMap<Node, bool> const_true_map(true);
434  typedef SubGraphWrapper<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW;
435  SubGW gw(g, const_true_map, tight_edge_filter);
436  \endcode
437  Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
438  with a max flow algorithm Preflow.
439  \code
440  ConstMap<Edge, int> const_1_map(1);
441  Graph::EdgeMap<int> flow(g, 0);
442
443  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
444    preflow(gw, s, t, const_1_map, flow);
445  preflow.run();
446  \endcode
447  Last, the output is:
448  \code 
449  cout << "maximum number of edge-disjoint shortest path: "
450       << preflow.flowValue() << endl;
451  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
452       << endl;
453  for(EdgeIt e(g); e!=INVALID; ++e)
454    if (flow[e])
455      cout << " " << g.id(g.tail(e)) << "--"
456           << length[e] << "->" << g.id(g.head(e)) << endl;
457  \endcode
458  The program has the following (expected :-)) output:
459  \code
460  edges with lengths (of form id, tail--length->head):
461   9, 5--4->6
462   8, 4--2->6
463   7, 3--1->5
464   6, 2--3->5
465   5, 2--5->6
466   4, 2--2->4
467   3, 1--3->4
468   2, 0--1->3
469   1, 0--2->2
470   0, 0--3->1
471  s: 0 t: 6
472  maximum number of edge-disjoint shortest path: 2
473  edges of the maximum number of edge-disjoint shortest s-t paths:
474   9, 5--4->6
475   8, 4--2->6
476   7, 3--1->5
477   4, 2--2->4
478   2, 0--1->3
479   1, 0--2->2
480  \endcode
481  \author Marton Makai
482  */
483  template<typename Graph, typename NodeFilterMap,
484           typename EdgeFilterMap>
485  class SubGraphWrapper : public GraphWrapper<Graph> {
486  public:
487    typedef GraphWrapper<Graph> Parent;
488  protected:
489    NodeFilterMap* node_filter_map;
490    EdgeFilterMap* edge_filter_map;
491
492    SubGraphWrapper() : GraphWrapper<Graph>(),
493                        node_filter_map(0), edge_filter_map(0) { }
494    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
495      node_filter_map=&_node_filter_map;
496    }
497    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
498      edge_filter_map=&_edge_filter_map;
499    }
500   
501  public:
502    SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
503                    EdgeFilterMap& _edge_filter_map) :
504      GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
505      edge_filter_map(&_edge_filter_map) { } 
506
507    typedef typename GraphWrapper<Graph>::Node Node;
508    class NodeIt : public Node {
509      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
510      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
511    public:
512      NodeIt() { }
513      NodeIt(Invalid i) : Node(i) { }
514      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
515        Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) {
516        while (*static_cast<Node*>(this)!=INVALID &&
517               !(*(gw->node_filter_map))[*this])
518          *(static_cast<Node*>(this))=
519            ++(typename Graph::NodeIt(*(gw->graph), *this));
520      }
521      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
522             const Node& n) :
523        Node(n), gw(&_gw) { }
524      NodeIt& operator++() {
525        *(static_cast<Node*>(this))=
526          ++(typename Graph::NodeIt(*(gw->graph), *this));
527        while (*static_cast<Node*>(this)!=INVALID &&
528               !(*(gw->node_filter_map))[*this])
529          *(static_cast<Node*>(this))=
530            ++(typename Graph::NodeIt(*(gw->graph), *this));
531        return *this;
532      }
533    };
534    typedef typename GraphWrapper<Graph>::Edge Edge;
535    class OutEdgeIt : public Edge {
536      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
537      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
538    public:
539      OutEdgeIt() { }
540      OutEdgeIt(Invalid i) : Edge(i) { }
541      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
542        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) {
543        while (*static_cast<Edge*>(this)!=INVALID &&
544               !(*(gw->edge_filter_map))[*this])
545          *(static_cast<Edge*>(this))=
546            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
547      }
548      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
549             const Edge& e) :
550        Edge(e), gw(&_gw) { }
551      OutEdgeIt& operator++() {
552        *(static_cast<Edge*>(this))=
553          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
554        while (*static_cast<Edge*>(this)!=INVALID &&
555               !(*(gw->edge_filter_map))[*this])
556          *(static_cast<Edge*>(this))=
557            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
558        return *this;
559      }
560    };
561    class InEdgeIt : public Edge {
562      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
563      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
564    public:
565      InEdgeIt() { }
566      //      InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
567      InEdgeIt(Invalid i) : Edge(i) { }
568      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
569        Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) {
570        while (*static_cast<Edge*>(this)!=INVALID &&
571               !(*(gw->edge_filter_map))[*this])
572          *(static_cast<Edge*>(this))=
573            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
574      }
575      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
576             const Edge& e) :
577        Edge(e), gw(&_gw) { }
578      InEdgeIt& operator++() {
579        *(static_cast<Edge*>(this))=
580          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
581        while (*static_cast<Edge*>(this)!=INVALID &&
582               !(*(gw->edge_filter_map))[*this])
583          *(static_cast<Edge*>(this))=
584            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
585        return *this;
586      }
587    };
588    class EdgeIt : public Edge {
589      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
590      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
591    public:
592      EdgeIt() { }
593      EdgeIt(Invalid i) : Edge(i) { }
594      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
595        Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) {
596        while (*static_cast<Edge*>(this)!=INVALID &&
597               !(*(gw->edge_filter_map))[*this])
598          *(static_cast<Edge*>(this))=
599            ++(typename Graph::EdgeIt(*(gw->graph), *this));
600      }
601      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
602             const Edge& e) :
603        Edge(e), gw(&_gw) { }
604      EdgeIt& operator++() {
605        *(static_cast<Edge*>(this))=
606          ++(typename Graph::EdgeIt(*(gw->graph), *this));
607        while (*static_cast<Edge*>(this)!=INVALID &&
608               !(*(gw->edge_filter_map))[*this])
609          *(static_cast<Edge*>(this))=
610            ++(typename Graph::EdgeIt(*(gw->graph), *this));
611        return *this;
612      }
613    };
614
615    NodeIt& first(NodeIt& i) const {
616      i=NodeIt(*this); return i;
617    }
618    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
619      i=OutEdgeIt(*this, p); return i;
620    }
621    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
622      i=InEdgeIt(*this, p); return i;
623    }
624    EdgeIt& first(EdgeIt& i) const {
625      i=EdgeIt(*this); return i;
626    }
627   
628    /// This function hides \c n in the graph, i.e. the iteration
629    /// jumps over it. This is done by simply setting the value of \c n 
630    /// to be false in the corresponding node-map.
631    void hide(const Node& n) const { node_filter_map->set(n, false); }
632
633    /// This function hides \c e in the graph, i.e. the iteration
634    /// jumps over it. This is done by simply setting the value of \c e 
635    /// to be false in the corresponding edge-map.
636    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
637
638    /// The value of \c n is set to be true in the node-map which stores
639    /// hide information. If \c n was hidden previuosly, then it is shown
640    /// again
641     void unHide(const Node& n) const { node_filter_map->set(n, true); }
642
643    /// The value of \c e is set to be true in the edge-map which stores
644    /// hide information. If \c e was hidden previuosly, then it is shown
645    /// again
646    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
647
648    /// Returns true if \c n is hidden.
649    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
650
651    /// Returns true if \c n is hidden.
652    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
653
654    /// \warning This is a linear time operation and works only if
655    /// \c Graph::NodeIt is defined.
656    int nodeNum() const {
657      int i=0;
658      for (NodeIt n(*this); n!=INVALID; ++n) ++i;
659      return i;
660    }
661
662    /// \warning This is a linear time operation and works only if
663    /// \c Graph::EdgeIt is defined.
664    int edgeNum() const {
665      int i=0;
666      for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
667      return i;
668    }
669
670    //    KEEP_MAPS(Parent, SubGraphWrapper);
671  };
672
673
674
675  template<typename Graph>
676  class UndirGraphWrapper : public GraphWrapper<Graph> {
677  public:
678    typedef GraphWrapper<Graph> Parent;
679  protected:
680    UndirGraphWrapper() : GraphWrapper<Graph>() { }
681   
682  public:
683    typedef typename GraphWrapper<Graph>::Node Node;
684    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
685    typedef typename GraphWrapper<Graph>::Edge Edge;
686    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
687
688    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
689
690    class OutEdgeIt {
691      friend class UndirGraphWrapper<Graph>;
692      bool out_or_in; //true iff out
693      typename Graph::OutEdgeIt out;
694      typename Graph::InEdgeIt in;
695    public:
696      OutEdgeIt() { }
697      OutEdgeIt(const Invalid& i) : Edge(i) { }
698      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
699        out_or_in=true; _G.graph->first(out, _n);
700        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
701      }
702      operator Edge() const {
703        if (out_or_in) return Edge(out); else return Edge(in);
704      }
705    };
706
707    typedef OutEdgeIt InEdgeIt;
708
709    using GraphWrapper<Graph>::first;
710    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
711      i=OutEdgeIt(*this, p); return i;
712    }
713
714    using GraphWrapper<Graph>::next;
715
716    OutEdgeIt& next(OutEdgeIt& e) const {
717      if (e.out_or_in) {
718        typename Graph::Node n=this->graph->tail(e.out);
719        this->graph->next(e.out);
720        if (!this->graph->valid(e.out)) {
721          e.out_or_in=false; this->graph->first(e.in, n); }
722      } else {
723        this->graph->next(e.in);
724      }
725      return e;
726    }
727
728    Node aNode(const OutEdgeIt& e) const {
729      if (e.out_or_in) return this->graph->tail(e); else
730        return this->graph->head(e); }
731    Node bNode(const OutEdgeIt& e) const {
732      if (e.out_or_in) return this->graph->head(e); else
733        return this->graph->tail(e); }
734
735    //    KEEP_MAPS(Parent, UndirGraphWrapper);
736
737  };
738 
739//   /// \brief An undirected graph template.
740//   ///
741//   ///\warning Graph wrappers are in even more experimental state than the other
742//   ///parts of the lib. Use them at your own risk.
743//   ///
744//   /// An undirected graph template.
745//   /// This class works as an undirected graph and a directed graph of
746//   /// class \c Graph is used for the physical storage.
747//   /// \ingroup graphs
748  template<typename Graph>
749  class UndirGraph : public UndirGraphWrapper<Graph> {
750    typedef UndirGraphWrapper<Graph> Parent;
751  protected:
752    Graph gr;
753  public:
754    UndirGraph() : UndirGraphWrapper<Graph>() {
755      Parent::setGraph(gr);
756    }
757
758    //    KEEP_MAPS(Parent, UndirGraph);
759  };
760
761
762
763  ///\brief A wrapper for composing a subgraph of a
764  /// bidirected graph made from a directed one.
765  ///
766  /// A wrapper for composing a subgraph of a
767  /// bidirected graph made from a directed one.
768  ///
769  ///\warning Graph wrappers are in even more experimental state than the other
770  ///parts of the lib. Use them at you own risk.
771  ///
772  /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
773  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
774  /// reversing its orientation. We are given moreover two bool valued
775  /// maps on the edge-set,
776  /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
777  /// SubBidirGraphWrapper implements the graph structure with node-set
778  /// \f$V\f$ and edge-set
779  /// \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$.
780  /// The purpose of writing + instead of union is because parallel
781  /// edges can arise. (Similarly, antiparallel edges also can arise).
782  /// In other words, a subgraph of the bidirected graph obtained, which
783  /// is given by orienting the edges of the original graph in both directions.
784  /// As the oppositely directed edges are logically different,
785  /// the maps are able to attach different values for them.
786  ///
787  /// An example for such a construction is \c RevGraphWrapper where the
788  /// forward_filter is everywhere false and the backward_filter is
789  /// everywhere true. We note that for sake of efficiency,
790  /// \c RevGraphWrapper is implemented in a different way.
791  /// But BidirGraphWrapper is obtained from
792  /// SubBidirGraphWrapper by considering everywhere true
793  /// valued maps both for forward_filter and backward_filter.
794  /// Finally, one of the most important applications of SubBidirGraphWrapper
795  /// is ResGraphWrapper, which stands for the residual graph in directed
796  /// flow and circulation problems.
797  /// As wrappers usually, the SubBidirGraphWrapper implements the
798  /// above mentioned graph structure without its physical storage,
799  /// that is the whole stuff is stored in constant memory.
800  template<typename Graph,
801           typename ForwardFilterMap, typename BackwardFilterMap>
802  class SubBidirGraphWrapper : public GraphWrapper<Graph> {
803  public:
804    typedef GraphWrapper<Graph> Parent;
805  protected:
806    ForwardFilterMap* forward_filter;
807    BackwardFilterMap* backward_filter;
808
809    SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
810    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
811      forward_filter=&_forward_filter;
812    }
813    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
814      backward_filter=&_backward_filter;
815    }
816
817  public:
818
819    SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter,
820                         BackwardFilterMap& _backward_filter) :
821      GraphWrapper<Graph>(_graph),
822      forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
823    SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph,
824                         ForwardFilterMap, BackwardFilterMap>& gw) :
825      Parent(gw),
826      forward_filter(gw.forward_filter),
827      backward_filter(gw.backward_filter) { }
828
829    class Edge;
830    class OutEdgeIt;
831    friend class Edge;
832    friend class OutEdgeIt;
833
834    template<typename T> class EdgeMap;
835
836    typedef typename GraphWrapper<Graph>::Node Node;
837
838    typedef typename Graph::Edge GraphEdge;
839    /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from
840    /// Graph::Edge. It contains an extra bool flag which is true
841    /// if and only if the
842    /// edge is the backward version of the original edge.
843    class Edge : public Graph::Edge {
844      friend class SubBidirGraphWrapper<Graph,
845                                        ForwardFilterMap, BackwardFilterMap>;
846      template<typename T> friend class EdgeMap;
847    protected:
848      bool backward; //true, iff backward
849    public:
850      Edge() { }
851      /// \todo =false is needed, or causes problems?
852      /// If \c _backward is false, then we get an edge corresponding to the
853      /// original one, otherwise its oppositely directed pair is obtained.
854      Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
855        Graph::Edge(e), backward(_backward) { }
856      Edge(Invalid i) : Graph::Edge(i), backward(true) { }
857      bool operator==(const Edge& v) const {
858        return (this->backward==v.backward &&
859                static_cast<typename Graph::Edge>(*this)==
860                static_cast<typename Graph::Edge>(v));
861      }
862      bool operator!=(const Edge& v) const {
863        return (this->backward!=v.backward ||
864                static_cast<typename Graph::Edge>(*this)!=
865                static_cast<typename Graph::Edge>(v));
866      }
867    };
868
869    class OutEdgeIt : public Edge {
870      friend class SubBidirGraphWrapper<Graph,
871                                        ForwardFilterMap, BackwardFilterMap>;
872    protected:
873      const SubBidirGraphWrapper<Graph,
874                                 ForwardFilterMap, BackwardFilterMap>* gw;
875    public:
876      OutEdgeIt() { }
877      OutEdgeIt(Invalid i) : Edge(i) { }
878      OutEdgeIt(const SubBidirGraphWrapper<Graph,
879                ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
880        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
881        while (*static_cast<GraphEdge*>(this)!=INVALID &&
882               !(*(gw->forward_filter))[*this])
883          *(static_cast<GraphEdge*>(this))=
884            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
885        if (*static_cast<GraphEdge*>(this)==INVALID) {
886          *static_cast<Edge*>(this)=
887            Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
888          while (*static_cast<GraphEdge*>(this)!=INVALID &&
889                 !(*(gw->backward_filter))[*this])
890            *(static_cast<GraphEdge*>(this))=
891              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
892        }
893      }
894      OutEdgeIt(const SubBidirGraphWrapper<Graph,
895                ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
896        Edge(e), gw(&_gw) { }
897      OutEdgeIt& operator++() {
898        if (!this->backward) {
899          Node n=gw->tail(*this);
900          *(static_cast<GraphEdge*>(this))=
901            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
902          while (*static_cast<GraphEdge*>(this)!=INVALID &&
903                 !(*(gw->forward_filter))[*this])
904            *(static_cast<GraphEdge*>(this))=
905              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
906          if (*static_cast<GraphEdge*>(this)==INVALID) {
907            *static_cast<Edge*>(this)=
908              Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
909            while (*static_cast<GraphEdge*>(this)!=INVALID &&
910                   !(*(gw->backward_filter))[*this])
911              *(static_cast<GraphEdge*>(this))=
912                ++(typename Graph::InEdgeIt(*(gw->graph), *this));
913          }
914        } else {
915          *(static_cast<GraphEdge*>(this))=
916            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
917          while (*static_cast<GraphEdge*>(this)!=INVALID &&
918                 !(*(gw->backward_filter))[*this])
919            *(static_cast<GraphEdge*>(this))=
920              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
921        }
922        return *this;
923      }
924    };
925
926    class InEdgeIt : public Edge {
927      friend class SubBidirGraphWrapper<Graph,
928                                        ForwardFilterMap, BackwardFilterMap>;
929    protected:
930      const SubBidirGraphWrapper<Graph,
931                                 ForwardFilterMap, BackwardFilterMap>* gw;
932    public:
933      InEdgeIt() { }
934      InEdgeIt(Invalid i) : Edge(i) { }
935      InEdgeIt(const SubBidirGraphWrapper<Graph,
936               ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
937        Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
938        while (*static_cast<GraphEdge*>(this)!=INVALID &&
939               !(*(gw->forward_filter))[*this])
940          *(static_cast<GraphEdge*>(this))=
941            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
942        if (*static_cast<GraphEdge*>(this)==INVALID) {
943          *static_cast<Edge*>(this)=
944            Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
945          while (*static_cast<GraphEdge*>(this)!=INVALID &&
946                 !(*(gw->backward_filter))[*this])
947            *(static_cast<GraphEdge*>(this))=
948              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
949        }
950      }
951      InEdgeIt(const SubBidirGraphWrapper<Graph,
952               ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
953        Edge(e), gw(&_gw) { }
954      InEdgeIt& operator++() {
955        if (!this->backward) {
956          Node n=gw->tail(*this);
957          *(static_cast<GraphEdge*>(this))=
958            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
959          while (*static_cast<GraphEdge*>(this)!=INVALID &&
960                 !(*(gw->forward_filter))[*this])
961            *(static_cast<GraphEdge*>(this))=
962              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
963          if (*static_cast<GraphEdge*>(this)==INVALID) {
964            *static_cast<Edge*>(this)=
965              Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
966            while (*static_cast<GraphEdge*>(this)!=INVALID &&
967                   !(*(gw->backward_filter))[*this])
968              *(static_cast<GraphEdge*>(this))=
969                ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
970          }
971        } else {
972          *(static_cast<GraphEdge*>(this))=
973            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
974          while (*static_cast<GraphEdge*>(this)!=INVALID &&
975                 !(*(gw->backward_filter))[*this])
976            *(static_cast<GraphEdge*>(this))=
977              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
978        }
979        return *this;
980      }
981    };
982
983    class EdgeIt : public Edge {
984      friend class SubBidirGraphWrapper<Graph,
985                                        ForwardFilterMap, BackwardFilterMap>;
986    protected:
987      const SubBidirGraphWrapper<Graph,
988                                 ForwardFilterMap, BackwardFilterMap>* gw;
989    public:
990      EdgeIt() { }
991      EdgeIt(Invalid i) : Edge(i) { }
992      EdgeIt(const SubBidirGraphWrapper<Graph,
993             ForwardFilterMap, BackwardFilterMap>& _gw) :
994        Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) {
995        while (*static_cast<GraphEdge*>(this)!=INVALID &&
996               !(*(gw->forward_filter))[*this])
997          *(static_cast<GraphEdge*>(this))=
998            ++(typename Graph::EdgeIt(*(gw->graph), *this));
999        if (*static_cast<GraphEdge*>(this)==INVALID) {
1000          *static_cast<Edge*>(this)=
1001            Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
1002          while (*static_cast<GraphEdge*>(this)!=INVALID &&
1003                 !(*(gw->backward_filter))[*this])
1004            *(static_cast<GraphEdge*>(this))=
1005              ++(typename Graph::EdgeIt(*(gw->graph), *this));
1006        }
1007      }
1008      EdgeIt(const SubBidirGraphWrapper<Graph,
1009             ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
1010        Edge(e), gw(&_gw) { }
1011      EdgeIt& operator++() {
1012        if (!this->backward) {
1013          *(static_cast<GraphEdge*>(this))=
1014            ++(typename Graph::EdgeIt(*(gw->graph), *this));
1015          while (*static_cast<GraphEdge*>(this)!=INVALID &&
1016                 !(*(gw->forward_filter))[*this])
1017            *(static_cast<GraphEdge*>(this))=
1018              ++(typename Graph::EdgeIt(*(gw->graph), *this));
1019          if (*static_cast<GraphEdge*>(this)==INVALID) {
1020            *static_cast<Edge*>(this)=
1021              Edge(typename Graph::EdgeIt(*(gw->graph)), true);
1022            while (*static_cast<GraphEdge*>(this)!=INVALID &&
1023                   !(*(gw->backward_filter))[*this])
1024              *(static_cast<GraphEdge*>(this))=
1025                ++(typename Graph::EdgeIt(*(gw->graph), *this));
1026          }
1027        } else {
1028          *(static_cast<GraphEdge*>(this))=
1029            ++(typename Graph::EdgeIt(*(gw->graph), *this));
1030          while (*static_cast<GraphEdge*>(this)!=INVALID &&
1031                 !(*(gw->backward_filter))[*this])
1032            *(static_cast<GraphEdge*>(this))=
1033              ++(typename Graph::EdgeIt(*(gw->graph), *this));
1034        }
1035        return *this;
1036      }
1037    };
1038
1039    using GraphWrapper<Graph>::first;
1040    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1041      i=OutEdgeIt(*this, p); return i;
1042    }
1043    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1044      i=InEdgeIt(*this, p); return i;
1045    }
1046    EdgeIt& first(EdgeIt& i) const {
1047      i=EdgeIt(*this); return i;
1048    }
1049 
1050
1051    Node tail(Edge e) const {
1052      return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1053    Node head(Edge e) const {
1054      return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1055
1056    /// Gives back the opposite edge.
1057    Edge opposite(const Edge& e) const {
1058      Edge f=e;
1059      f.backward=!f.backward;
1060      return f;
1061    }
1062
1063    /// \warning This is a linear time operation and works only if
1064    /// \c Graph::EdgeIt is defined.
1065    int edgeNum() const {
1066      int i=0;
1067      for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
1068      return i;
1069    }
1070
1071    bool forward(const Edge& e) const { return !e.backward; }
1072    bool backward(const Edge& e) const { return e.backward; }
1073
1074
1075    template <typename T>
1076    /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two
1077    /// Graph::EdgeMap one for the forward edges and
1078    /// one for the backward edges.
1079    class EdgeMap {
1080      template <typename TT> friend class EdgeMap;
1081      typename Graph::template EdgeMap<T> forward_map, backward_map;
1082    public:
1083      typedef T ValueType;
1084      typedef Edge KeyType;
1085
1086      EdgeMap(const SubBidirGraphWrapper<Graph,
1087              ForwardFilterMap, BackwardFilterMap>& g) :
1088        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
1089
1090      EdgeMap(const SubBidirGraphWrapper<Graph,
1091              ForwardFilterMap, BackwardFilterMap>& g, T a) :
1092        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
1093
1094      template <typename TT>
1095      EdgeMap(const EdgeMap<TT>& copy)
1096        : forward_map(copy.forward_map), backward_map(copy.backward_map) {}
1097
1098      template <typename TT>
1099      EdgeMap& operator=(const EdgeMap<TT>& copy) {
1100        forward_map = copy.forward_map;
1101        backward_map = copy.backward_map;
1102        return *this;
1103      }
1104     
1105      void set(Edge e, T a) {
1106        if (!e.backward)
1107          forward_map.set(e, a);
1108        else
1109          backward_map.set(e, a);
1110      }
1111
1112      typename Graph::template EdgeMap<T>::ConstReferenceType
1113      operator[](Edge e) const {
1114        if (!e.backward)
1115          return forward_map[e];
1116        else
1117          return backward_map[e];
1118      }
1119
1120      typename Graph::template EdgeMap<T>::ReferenceType
1121      operator[](Edge e) {
1122        if (!e.backward)
1123          return forward_map[e];
1124        else
1125          return backward_map[e];
1126      }
1127
1128      void update() {
1129        forward_map.update();
1130        backward_map.update();
1131      }
1132    };
1133
1134
1135    //    KEEP_NODE_MAP(Parent, SubBidirGraphWrapper);
1136
1137  };
1138
1139
1140  ///\brief A wrapper for composing bidirected graph from a directed one.
1141  ///
1142  ///\warning Graph wrappers are in even more experimental state than the other
1143  ///parts of the lib. Use them at you own risk.
1144  ///
1145  /// A wrapper for composing bidirected graph from a directed one.
1146  /// A bidirected graph is composed over the directed one without physical
1147  /// storage. As the oppositely directed edges are logically different ones
1148  /// the maps are able to attach different values for them.
1149  template<typename Graph>
1150  class BidirGraphWrapper :
1151    public SubBidirGraphWrapper<
1152    Graph,
1153    ConstMap<typename Graph::Edge, bool>,
1154    ConstMap<typename Graph::Edge, bool> > {
1155  public:
1156    typedef  SubBidirGraphWrapper<
1157      Graph,
1158      ConstMap<typename Graph::Edge, bool>,
1159      ConstMap<typename Graph::Edge, bool> > Parent;
1160  protected:
1161    ConstMap<typename Graph::Edge, bool> cm;
1162
1163    BidirGraphWrapper() : Parent(), cm(true) {
1164      Parent::setForwardFilterMap(cm);
1165      Parent::setBackwardFilterMap(cm);
1166    }
1167  public:
1168    BidirGraphWrapper(Graph& _graph) : Parent() {
1169      Parent::setGraph(_graph);
1170      Parent::setForwardFilterMap(cm);
1171      Parent::setBackwardFilterMap(cm);
1172    }
1173
1174    int edgeNum() const {
1175      return 2*this->graph->edgeNum();
1176    }
1177    //    KEEP_MAPS(Parent, BidirGraphWrapper);
1178  };
1179
1180
1181  /// \brief A bidirected graph template.
1182  ///
1183  ///\warning Graph wrappers are in even more experimental state than the other
1184  ///parts of the lib. Use them at you own risk.
1185  ///
1186  /// A bidirected graph template.
1187  /// Such a bidirected graph stores each pair of oppositely directed edges
1188  /// ones in the memory, i.e. a directed graph of type
1189  /// \c Graph is used for that.
1190  /// As the oppositely directed edges are logically different ones
1191  /// the maps are able to attach different values for them.
1192  /// \ingroup graphs
1193  template<typename Graph>
1194  class BidirGraph : public BidirGraphWrapper<Graph> {
1195  public:
1196    typedef UndirGraphWrapper<Graph> Parent;
1197  protected:
1198    Graph gr;
1199  public:
1200    BidirGraph() : BidirGraphWrapper<Graph>() {
1201      Parent::setGraph(gr);
1202    }
1203    //    KEEP_MAPS(Parent, BidirGraph);
1204  };
1205
1206
1207
1208  template<typename Graph, typename Number,
1209           typename CapacityMap, typename FlowMap>
1210  class ResForwardFilter {
1211    //    const Graph* graph;
1212    const CapacityMap* capacity;
1213    const FlowMap* flow;
1214  public:
1215    ResForwardFilter(/*const Graph& _graph, */
1216                     const CapacityMap& _capacity, const FlowMap& _flow) :
1217      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1218    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1219    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1220    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1221    bool operator[](const typename Graph::Edge& e) const {
1222      return (Number((*flow)[e]) < Number((*capacity)[e]));
1223    }
1224  };
1225
1226  template<typename Graph, typename Number,
1227           typename CapacityMap, typename FlowMap>
1228  class ResBackwardFilter {
1229    const CapacityMap* capacity;
1230    const FlowMap* flow;
1231  public:
1232    ResBackwardFilter(/*const Graph& _graph,*/
1233                      const CapacityMap& _capacity, const FlowMap& _flow) :
1234      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1235    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1236    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1237    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1238    bool operator[](const typename Graph::Edge& e) const {
1239      return (Number(0) < Number((*flow)[e]));
1240    }
1241  };
1242
1243 
1244  /// A wrapper for composing the residual graph for directed flow and circulation problems.
1245
1246  ///\warning Graph wrappers are in even more experimental state than the other
1247  ///parts of the lib. Use them at you own risk.
1248  ///
1249  /// A wrapper for composing the residual graph for directed flow and circulation problems.
1250  template<typename Graph, typename Number,
1251           typename CapacityMap, typename FlowMap>
1252  class ResGraphWrapper :
1253    public SubBidirGraphWrapper<
1254    Graph,
1255    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1256    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1257  public:
1258    typedef SubBidirGraphWrapper<
1259      Graph,
1260      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1261      ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1262  protected:
1263    const CapacityMap* capacity;
1264    FlowMap* flow;
1265    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1266    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1267    ResGraphWrapper() : Parent(),
1268                        capacity(0), flow(0) { }
1269    void setCapacityMap(const CapacityMap& _capacity) {
1270      capacity=&_capacity;
1271      forward_filter.setCapacity(_capacity);
1272      backward_filter.setCapacity(_capacity);
1273    }
1274    void setFlowMap(FlowMap& _flow) {
1275      flow=&_flow;
1276      forward_filter.setFlow(_flow);
1277      backward_filter.setFlow(_flow);
1278    }
1279  public:
1280    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1281                       FlowMap& _flow) :
1282      Parent(), capacity(&_capacity), flow(&_flow),
1283      forward_filter(/*_graph,*/ _capacity, _flow),
1284      backward_filter(/*_graph,*/ _capacity, _flow) {
1285      Parent::setGraph(_graph);
1286      Parent::setForwardFilterMap(forward_filter);
1287      Parent::setBackwardFilterMap(backward_filter);
1288    }
1289
1290    typedef typename Parent::Edge Edge;
1291
1292    void augment(const Edge& e, Number a) const {
1293      if (Parent::forward(e)) 
1294        flow->set(e, (*flow)[e]+a);
1295      else 
1296        flow->set(e, (*flow)[e]-a);
1297    }
1298
1299    /// \brief Residual capacity map.
1300    ///
1301    /// In generic residual graphs the residual capacity can be obtained
1302    /// as a map.
1303    class ResCap {
1304    protected:
1305      const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1306    public:
1307      typedef Number ValueType;
1308      typedef Edge KeyType;
1309      ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
1310             _res_graph) : res_graph(&_res_graph) { }
1311      Number operator[](const Edge& e) const {
1312        if (res_graph->forward(e))
1313          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1314        else
1315          return (*(res_graph->flow))[e];
1316      }
1317    };
1318
1319    //    KEEP_MAPS(Parent, ResGraphWrapper);
1320  };
1321
1322
1323  /// For blocking flows.
1324
1325  ///\warning Graph wrappers are in even more experimental state than the other
1326  ///parts of the lib. Use them at you own risk.
1327  ///
1328  /// This graph wrapper is used for on-the-fly
1329  /// Dinits blocking flow computations.
1330  /// For each node, an out-edge is stored which is used when the
1331  /// \code
1332  /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1333  /// \endcode
1334  /// is called.
1335  ///
1336  /// \author Marton Makai
1337  template<typename Graph, typename FirstOutEdgesMap>
1338  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1339  public:
1340    typedef GraphWrapper<Graph> Parent;
1341  protected:
1342    FirstOutEdgesMap* first_out_edges;
1343  public:
1344    ErasingFirstGraphWrapper(Graph& _graph,
1345                             FirstOutEdgesMap& _first_out_edges) :
1346      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
1347
1348    typedef typename GraphWrapper<Graph>::Node Node;
1349    typedef typename GraphWrapper<Graph>::Edge Edge;
1350    class OutEdgeIt : public Edge {
1351      friend class GraphWrapper<Graph>;
1352      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1353      const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;
1354    public:
1355      OutEdgeIt() { }
1356      OutEdgeIt(Invalid i) : Edge(i) { }
1357      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1358                const Node& n) :
1359        Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { }
1360      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1361                const Edge& e) :
1362        Edge(e), gw(&_gw) { }
1363      OutEdgeIt& operator++() {
1364        *(static_cast<Edge*>(this))=
1365          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1366        return *this;
1367      }
1368    };
1369
1370    using GraphWrapper<Graph>::first;
1371    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1372      i=OutEdgeIt(*this, p); return i;
1373    }
1374    void erase(const Edge& e) const {
1375      Node n=tail(e);
1376      typename Graph::OutEdgeIt f(*Parent::graph, n);
1377      ++f;
1378      first_out_edges->set(n, f);
1379    }
1380
1381    //    KEEP_MAPS(Parent, ErasingFirstGraphWrapper);
1382  };
1383
1384  ///@}
1385
1386} //namespace lemon
1387
1388#endif //LEMON_GRAPH_WRAPPER_H
1389
Note: See TracBrowser for help on using the repository browser.