COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_wrapper.h @ 949:b16a10926781

Last change on this file since 949:b16a10926781 was 933:1b7c88fbb950, checked in by marci, 16 years ago

NodeSubGraphWrapper?, test, and ducumentation modifications.

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