COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_wrapper.h @ 1364:ee5959aa4410

Last change on this file since 1364:ee5959aa4410 was 1359:1581f961cfaa, checked in by Alpar Juttner, 19 years ago

Correct the english name of EGRES.

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 Research Group on Combinatorial Optimization, 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/bits/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 elementary knowledge from combinatorial optimization.
438
439  If a single shortest path is to be
440  searched between \c s and \c t, then this can be done easily by
441  applying the Dijkstra algorithm. 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::nextIn(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  ///
927  /// The most important application of SubBidirGraphWrapper
928  /// is ResGraphWrapper, which stands for the residual graph in directed
929  /// flow and circulation problems.
930  /// As wrappers usually, the SubBidirGraphWrapper implements the
931  /// above mentioned graph structure without its physical storage,
932  /// that is the whole stuff is stored in constant memory.
933  template<typename _Graph,
934           typename ForwardFilterMap, typename BackwardFilterMap>
935  class SubBidirGraphWrapper :
936    public IterableGraphExtender<
937    SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
938  public:
939    typedef _Graph Graph;
940    typedef IterableGraphExtender<
941      SubBidirGraphWrapperBase<
942      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
943  protected:
944    SubBidirGraphWrapper() { }
945  public:
946    SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,
947                         BackwardFilterMap& _backward_filter) {
948      setGraph(_graph);
949      setForwardFilterMap(_forward_filter);
950      setBackwardFilterMap(_backward_filter);
951    }
952  };
953
954
955
956  ///\brief A wrapper for composing bidirected graph from a directed one.
957  ///
958  ///\warning Graph wrappers are in even more experimental state than the other
959  ///parts of the lib. Use them at you own risk.
960  ///
961  /// A wrapper for composing bidirected graph from a directed one.
962  /// A bidirected graph is composed over the directed one without physical
963  /// storage. As the oppositely directed edges are logically different ones
964  /// the maps are able to attach different values for them.
965  template<typename Graph>
966  class BidirGraphWrapper :
967    public SubBidirGraphWrapper<
968    Graph,
969    ConstMap<typename Graph::Edge, bool>,
970    ConstMap<typename Graph::Edge, bool> > {
971  public:
972    typedef  SubBidirGraphWrapper<
973      Graph,
974      ConstMap<typename Graph::Edge, bool>,
975      ConstMap<typename Graph::Edge, bool> > Parent;
976  protected:
977    ConstMap<typename Graph::Edge, bool> cm;
978
979    BidirGraphWrapper() : Parent(), cm(true) {
980      Parent::setForwardFilterMap(cm);
981      Parent::setBackwardFilterMap(cm);
982    }
983  public:
984    BidirGraphWrapper(Graph& _graph) : Parent(), cm(true) {
985      Parent::setGraph(_graph);
986      Parent::setForwardFilterMap(cm);
987      Parent::setBackwardFilterMap(cm);
988    }
989
990    int edgeNum() const {
991      return 2*this->graph->edgeNum();
992    }
993    //    KEEP_MAPS(Parent, BidirGraphWrapper);
994  };
995
996
997  template<typename Graph, typename Number,
998           typename CapacityMap, typename FlowMap>
999  class ResForwardFilter {
1000    //    const Graph* graph;
1001    const CapacityMap* capacity;
1002    const FlowMap* flow;
1003  public:
1004    ResForwardFilter(/*const Graph& _graph, */
1005                     const CapacityMap& _capacity, const FlowMap& _flow) :
1006      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1007    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1008    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1009    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1010    bool operator[](const typename Graph::Edge& e) const {
1011      return (Number((*flow)[e]) < Number((*capacity)[e]));
1012    }
1013  };
1014
1015  template<typename Graph, typename Number,
1016           typename CapacityMap, typename FlowMap>
1017  class ResBackwardFilter {
1018    const CapacityMap* capacity;
1019    const FlowMap* flow;
1020  public:
1021    ResBackwardFilter(/*const Graph& _graph,*/
1022                      const CapacityMap& _capacity, const FlowMap& _flow) :
1023      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1024    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1025    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1026    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1027    bool operator[](const typename Graph::Edge& e) const {
1028      return (Number(0) < Number((*flow)[e]));
1029    }
1030  };
1031
1032 
1033  /*! \brief A wrapper for composing the residual graph for directed flow and circulation problems.
1034
1035  A wrapper for composing the residual graph for directed flow and circulation problems.
1036  Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
1037  number type. Let moreover
1038  \f$f,c:A\to F\f$, be functions on the edge-set.
1039  In the appications of ResGraphWrapper, \f$f\f$ usually stands for a flow
1040  and \f$c\f$ for a capacity function.   
1041  Suppose that a graph instange \c g of type
1042  \c ListGraph implements \f$G\f$.
1043  \code
1044  ListGraph g;
1045  \endcode
1046  Then RevGraphWrapper implements the graph structure with node-set
1047  \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
1048  \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
1049  \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
1050  i.e. the so called residual graph.
1051  When we take the union \f$A_{forward}\cup A_{backward}\f$,
1052  multilicities are counted, i.e. if an edge is in both
1053  \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the wrapper it
1054  appears twice.
1055  The following code shows how
1056  such an instance can be constructed.
1057  \code
1058  typedef ListGraph Graph;
1059  Graph::EdgeMap<int> f(g);
1060  Graph::EdgeMap<int> c(g);
1061  ResGraphWrapper<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
1062  \endcode
1063  \author Marton Makai
1064  */
1065  template<typename Graph, typename Number,
1066           typename CapacityMap, typename FlowMap>
1067  class ResGraphWrapper :
1068    public SubBidirGraphWrapper<
1069    Graph,
1070    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1071    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1072  public:
1073    typedef SubBidirGraphWrapper<
1074      Graph,
1075      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1076      ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1077  protected:
1078    const CapacityMap* capacity;
1079    FlowMap* flow;
1080    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1081    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1082    ResGraphWrapper() : Parent(),
1083                        capacity(0), flow(0) { }
1084    void setCapacityMap(const CapacityMap& _capacity) {
1085      capacity=&_capacity;
1086      forward_filter.setCapacity(_capacity);
1087      backward_filter.setCapacity(_capacity);
1088    }
1089    void setFlowMap(FlowMap& _flow) {
1090      flow=&_flow;
1091      forward_filter.setFlow(_flow);
1092      backward_filter.setFlow(_flow);
1093    }
1094  public:
1095    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1096                       FlowMap& _flow) :
1097      Parent(), capacity(&_capacity), flow(&_flow),
1098      forward_filter(/*_graph,*/ _capacity, _flow),
1099      backward_filter(/*_graph,*/ _capacity, _flow) {
1100      Parent::setGraph(_graph);
1101      Parent::setForwardFilterMap(forward_filter);
1102      Parent::setBackwardFilterMap(backward_filter);
1103    }
1104
1105    typedef typename Parent::Edge Edge;
1106
1107    void augment(const Edge& e, Number a) const {
1108      if (Parent::forward(e)) 
1109        flow->set(e, (*flow)[e]+a);
1110      else 
1111        flow->set(e, (*flow)[e]-a);
1112    }
1113
1114    /// \brief Residual capacity map.
1115    ///
1116    /// In generic residual graphs the residual capacity can be obtained
1117    /// as a map.
1118    class ResCap {
1119    protected:
1120      const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1121    public:
1122      typedef Number Value;
1123      typedef Edge Key;
1124      ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
1125             _res_graph) : res_graph(&_res_graph) { }
1126      Number operator[](const Edge& e) const {
1127        if (res_graph->forward(e))
1128          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1129        else
1130          return (*(res_graph->flow))[e];
1131      }
1132    };
1133
1134    //    KEEP_MAPS(Parent, ResGraphWrapper);
1135  };
1136
1137
1138
1139  template <typename _Graph, typename FirstOutEdgesMap>
1140  class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {
1141  public:
1142    typedef _Graph Graph;
1143    typedef GraphWrapperBase<_Graph> Parent;
1144  protected:
1145    FirstOutEdgesMap* first_out_edges;
1146    ErasingFirstGraphWrapperBase() : Parent(),
1147                                     first_out_edges(0) { }
1148
1149    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1150      first_out_edges=&_first_out_edges;
1151    }
1152
1153  public:
1154
1155    typedef typename Parent::Node Node;
1156    typedef typename Parent::Edge Edge;
1157
1158    void firstOut(Edge& i, const Node& n) const {
1159      i=(*first_out_edges)[n];
1160    }
1161
1162    void erase(const Edge& e) const {
1163      Node n=source(e);
1164      Edge f=e;
1165      Parent::nextOut(f);
1166      first_out_edges->set(n, f);
1167    }   
1168  };
1169
1170
1171  /// For blocking flows.
1172
1173  ///\warning Graph wrappers are in even more experimental state than the other
1174  ///parts of the lib. Use them at you own risk.
1175  ///
1176  /// This graph wrapper is used for on-the-fly
1177  /// Dinits blocking flow computations.
1178  /// For each node, an out-edge is stored which is used when the
1179  /// \code
1180  /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1181  /// \endcode
1182  /// is called.
1183  ///
1184  /// \author Marton Makai
1185  template <typename _Graph, typename FirstOutEdgesMap>
1186  class ErasingFirstGraphWrapper :
1187    public IterableGraphExtender<
1188    ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {
1189  public:
1190    typedef _Graph Graph;
1191    typedef IterableGraphExtender<
1192      ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;
1193    ErasingFirstGraphWrapper(Graph& _graph,
1194                             FirstOutEdgesMap& _first_out_edges) {
1195      setGraph(_graph);
1196      setFirstOutEdgesMap(_first_out_edges);
1197    }
1198
1199  };
1200
1201  ///@}
1202
1203} //namespace lemon
1204
1205#endif //LEMON_GRAPH_WRAPPER_H
1206
Note: See TracBrowser for help on using the repository browser.