COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_wrapper.h @ 986:e997802b855c

Last change on this file since 986:e997802b855c was 986:e997802b855c, checked in by Alpar Juttner, 16 years ago

Naming changes:

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