COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_wrapper.h @ 932:ade3cdb9b45d

Last change on this file since 932:ade3cdb9b45d was 932:ade3cdb9b45d, checked in by marci, 16 years ago

New EdgeSubGraphWrapper? class specializing SubGraphWrapper? in the way that only the edge-set can be filtered.

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