COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_wrapper.h @ 1242:e48c4fe47aaf

Last change on this file since 1242:e48c4fe47aaf was 1242:e48c4fe47aaf, checked in by marci, 19 years ago

small improvment in documentation

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