COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_wrapper.h @ 1204:c3e29c6ae4e4

Last change on this file since 1204:c3e29c6ae4e4 was 1198:6f1604392dc8, checked in by Alpar Juttner, 19 years ago

Bugfix in BidirGraphWrapper?

File size: 37.8 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  This wrapper shows a graph with filtered node-set and
322  edge-set.
323  Given a bool-valued map on the node-set and one on
324  the edge-set of the graph, the iterators show only the objects
325  having true value. We have to note that this does not mean that an
326  induced subgraph is obtained, the node-iterator cares only the filter
327  on the node-set, and the edge-iterators care only the filter on the
328  edge-set.
329  \code
330  typedef SmartGraph Graph;
331  Graph g;
332  typedef Graph::Node Node;
333  typedef Graph::Edge Edge;
334  Node u=g.addNode(); //node of id 0
335  Node v=g.addNode(); //node of id 1
336  Node e=g.addEdge(u, v); //edge of id 0
337  Node f=g.addEdge(v, u); //edge of id 1
338  Graph::NodeMap<bool> nm(g, true);
339  nm.set(u, false);
340  Graph::EdgeMap<bool> em(g, true);
341  em.set(e, false);
342  typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
343  SubGW gw(g, nm, em);
344  for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
345  std::cout << ":-)" << std::endl;
346  for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
347  \endcode
348  The output of the above code is the following.
349  \code
350  1
351  :-)
352  1
353  \endcode
354  Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
355  \c Graph::Node that is why \c g.id(n) can be applied.
356
357  For other examples see also the documentation of NodeSubGraphWrapper and
358  EdgeSubGraphWrapper.
359
360  \author Marton Makai
361  */
362  template<typename _Graph, typename NodeFilterMap,
363           typename EdgeFilterMap>
364  class SubGraphWrapper :
365    public IterableGraphExtender<
366    SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
367  public:
368    typedef _Graph Graph;
369    typedef IterableGraphExtender<
370      SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
371  protected:
372    SubGraphWrapper() { }
373  public:
374    SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map,
375                    EdgeFilterMap& _edge_filter_map) {
376      setGraph(_graph);
377      setNodeFilterMap(_node_filter_map);
378      setEdgeFilterMap(_edge_filter_map);
379    }
380  };
381
382
383
384  /*! \brief A wrapper for hiding nodes from a graph.
385
386  \warning Graph wrappers are in even more experimental state than the other
387  parts of the lib. Use them at you own risk.
388 
389  A wrapper for hiding nodes from a graph.
390  This wrapper specializes SubGraphWrapper in the way that only the node-set
391  can be filtered. Note that this does not mean of considering induced
392  subgraph, the edge-iterators consider the original edge-set.
393  \author Marton Makai
394  */
395  template<typename Graph, typename NodeFilterMap>
396  class NodeSubGraphWrapper :
397    public SubGraphWrapper<Graph, NodeFilterMap,
398                           ConstMap<typename Graph::Edge,bool> > {
399  public:
400    typedef SubGraphWrapper<Graph, NodeFilterMap,
401                            ConstMap<typename Graph::Edge,bool> > Parent;
402  protected:
403    ConstMap<typename Graph::Edge, bool> const_true_map;
404  public:
405    NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :
406      Parent(), const_true_map(true) {
407      Parent::setGraph(_graph);
408      Parent::setNodeFilterMap(_node_filter_map);
409      Parent::setEdgeFilterMap(const_true_map);
410    }
411  };
412
413
414  /*! \brief A wrapper for hiding edges from a graph.
415
416  \warning Graph wrappers are in even more experimental state than the other
417  parts of the lib. Use them at you own risk.
418 
419  A wrapper for hiding edges from a graph.
420  This wrapper specializes SubGraphWrapper in the way that only the edge-set
421  can be filtered. The usefulness of this wrapper is demonstrated in the
422  problem of searching a maximum number of edge-disjoint shortest paths
423  between
424  two nodes \c s and \c t. Shortest here means being shortest w.r.t.
425  non-negative edge-lengths. Note that
426  the comprehension of the presented solution
427  need's some knowledge from elementary combinatorial optimization.
428
429  If a single shortest path is to be
430  searched between two nodes \c s and \c t, then this can be done easily by
431  applying the Dijkstra algorithm class. What happens, if a maximum number of
432  edge-disjoint shortest paths is to be computed. It can be proved that an
433  edge can be in a shortest path if and only if it is tight with respect to
434  the potential function computed by Dijkstra. Moreover, any path containing
435  only such edges is a shortest one. Thus we have to compute a maximum number
436  of edge-disjoint paths between \c s and \c t in the graph which has edge-set
437  all the tight edges. The computation will be demonstrated on the following
438  graph, which is read from a dimacs file.
439 
440  \dot
441  digraph lemon_dot_example {
442  node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
443  n0 [ label="0 (s)" ];
444  n1 [ label="1" ];
445  n2 [ label="2" ];
446  n3 [ label="3" ];
447  n4 [ label="4" ];
448  n5 [ label="5" ];
449  n6 [ label="6 (t)" ];
450  edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
451  n5 ->  n6 [ label="9, length:4" ];
452  n4 ->  n6 [ label="8, length:2" ];
453  n3 ->  n5 [ label="7, length:1" ];
454  n2 ->  n5 [ label="6, length:3" ];
455  n2 ->  n6 [ label="5, length:5" ];
456  n2 ->  n4 [ label="4, length:2" ];
457  n1 ->  n4 [ label="3, length:3" ];
458  n0 ->  n3 [ label="2, length:1" ];
459  n0 ->  n2 [ label="1, length:2" ];
460  n0 ->  n1 [ label="0, length:3" ];
461  }
462  \enddot
463
464  \code
465  Graph g;
466  Node s, t;
467  LengthMap length(g);
468
469  readDimacs(std::cin, g, length, s, t);
470
471  cout << "edges with lengths (of form id, source--length->target): " << endl;
472  for(EdgeIt e(g); e!=INVALID; ++e)
473    cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
474         << length[e] << "->" << g.id(g.target(e)) << endl;
475
476  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
477  \endcode
478  Next, the potential function is computed with Dijkstra.
479  \code
480  typedef Dijkstra<Graph, LengthMap> Dijkstra;
481  Dijkstra dijkstra(g, length);
482  dijkstra.run(s);
483  \endcode
484  Next, we consrtruct a map which filters the edge-set to the tight edges.
485  \code
486  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
487    TightEdgeFilter;
488  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
489 
490  typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
491  SubGW gw(g, tight_edge_filter);
492  \endcode
493  Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
494  with a max flow algorithm Preflow.
495  \code
496  ConstMap<Edge, int> const_1_map(1);
497  Graph::EdgeMap<int> flow(g, 0);
498
499  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
500    preflow(gw, s, t, const_1_map, flow);
501  preflow.run();
502  \endcode
503  Last, the output is:
504  \code 
505  cout << "maximum number of edge-disjoint shortest path: "
506       << preflow.flowValue() << endl;
507  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
508       << endl;
509  for(EdgeIt e(g); e!=INVALID; ++e)
510    if (flow[e])
511      cout << " " << g.id(g.source(e)) << "--"
512           << length[e] << "->" << g.id(g.target(e)) << endl;
513  \endcode
514  The program has the following (expected :-)) output:
515  \code
516  edges with lengths (of form id, source--length->target):
517   9, 5--4->6
518   8, 4--2->6
519   7, 3--1->5
520   6, 2--3->5
521   5, 2--5->6
522   4, 2--2->4
523   3, 1--3->4
524   2, 0--1->3
525   1, 0--2->2
526   0, 0--3->1
527  s: 0 t: 6
528  maximum number of edge-disjoint shortest path: 2
529  edges of the maximum number of edge-disjoint shortest s-t paths:
530   9, 5--4->6
531   8, 4--2->6
532   7, 3--1->5
533   4, 2--2->4
534   2, 0--1->3
535   1, 0--2->2
536  \endcode
537
538  \author Marton Makai
539  */
540  template<typename Graph, typename EdgeFilterMap>
541  class EdgeSubGraphWrapper :
542    public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
543                           EdgeFilterMap> {
544  public:
545    typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
546                            EdgeFilterMap> Parent;
547  protected:
548    ConstMap<typename Graph::Node, bool> const_true_map;
549  public:
550    EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
551      Parent(), const_true_map(true) {
552      Parent::setGraph(_graph);
553      Parent::setNodeFilterMap(const_true_map);
554      Parent::setEdgeFilterMap(_edge_filter_map);
555    }
556  };
557
558
559  template<typename Graph>
560  class UndirGraphWrapper : public GraphWrapper<Graph> {
561  public:
562    typedef GraphWrapper<Graph> Parent;
563  protected:
564    UndirGraphWrapper() : GraphWrapper<Graph>() { }
565   
566  public:
567    typedef typename GraphWrapper<Graph>::Node Node;
568    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
569    typedef typename GraphWrapper<Graph>::Edge Edge;
570    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
571
572    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
573
574    class OutEdgeIt {
575      friend class UndirGraphWrapper<Graph>;
576      bool out_or_in; //true iff out
577      typename Graph::OutEdgeIt out;
578      typename Graph::InEdgeIt in;
579    public:
580      OutEdgeIt() { }
581      OutEdgeIt(const Invalid& i) : Edge(i) { }
582      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
583        out_or_in=true; _G.graph->first(out, _n);
584        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
585      }
586      operator Edge() const {
587        if (out_or_in) return Edge(out); else return Edge(in);
588      }
589    };
590
591    typedef OutEdgeIt InEdgeIt;
592
593    using GraphWrapper<Graph>::first;
594    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
595      i=OutEdgeIt(*this, p); return i;
596    }
597
598    using GraphWrapper<Graph>::next;
599
600    OutEdgeIt& next(OutEdgeIt& e) const {
601      if (e.out_or_in) {
602        typename Graph::Node n=this->graph->source(e.out);
603        this->graph->next(e.out);
604        if (!this->graph->valid(e.out)) {
605          e.out_or_in=false; this->graph->first(e.in, n); }
606      } else {
607        this->graph->next(e.in);
608      }
609      return e;
610    }
611
612    Node aNode(const OutEdgeIt& e) const {
613      if (e.out_or_in) return this->graph->source(e); else
614        return this->graph->target(e); }
615    Node bNode(const OutEdgeIt& e) const {
616      if (e.out_or_in) return this->graph->target(e); else
617        return this->graph->source(e); }
618
619    //    KEEP_MAPS(Parent, UndirGraphWrapper);
620
621  };
622 
623//   /// \brief An undirected graph template.
624//   ///
625//   ///\warning Graph wrappers are in even more experimental state than the other
626//   ///parts of the lib. Use them at your own risk.
627//   ///
628//   /// An undirected graph template.
629//   /// This class works as an undirected graph and a directed graph of
630//   /// class \c Graph is used for the physical storage.
631//   /// \ingroup graphs
632  template<typename Graph>
633  class UndirGraph : public UndirGraphWrapper<Graph> {
634    typedef UndirGraphWrapper<Graph> Parent;
635  protected:
636    Graph gr;
637  public:
638    UndirGraph() : UndirGraphWrapper<Graph>() {
639      Parent::setGraph(gr);
640    }
641
642    //    KEEP_MAPS(Parent, UndirGraph);
643  };
644
645 
646  template <typename _Graph,
647            typename ForwardFilterMap, typename BackwardFilterMap>
648  class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {
649  public:
650    typedef _Graph Graph;
651    typedef GraphWrapperBase<_Graph> Parent;
652  protected:
653    ForwardFilterMap* forward_filter;
654    BackwardFilterMap* backward_filter;
655    SubBidirGraphWrapperBase() : Parent(),
656                                 forward_filter(0), backward_filter(0) { }
657
658    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
659      forward_filter=&_forward_filter;
660    }
661    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
662      backward_filter=&_backward_filter;
663    }
664
665  public:
666//     SubGraphWrapperBase(Graph& _graph,
667//                      NodeFilterMap& _node_filter_map,
668//                      EdgeFilterMap& _edge_filter_map) :
669//       Parent(&_graph),
670//       node_filter_map(&node_filter_map),
671//       edge_filter_map(&edge_filter_map) { }
672
673    typedef typename Parent::Node Node;
674    typedef typename _Graph::Edge GraphEdge;
675    template <typename T> class EdgeMap;
676    /// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from
677    /// _Graph::Edge. It contains an extra bool flag which is true
678    /// if and only if the
679    /// edge is the backward version of the original edge.
680    class Edge : public _Graph::Edge {
681      friend class SubBidirGraphWrapperBase<
682        Graph, ForwardFilterMap, BackwardFilterMap>;
683      template<typename T> friend class EdgeMap;
684    protected:
685      bool backward; //true, iff backward
686    public:
687      Edge() { }
688      /// \todo =false is needed, or causes problems?
689      /// If \c _backward is false, then we get an edge corresponding to the
690      /// original one, otherwise its oppositely directed pair is obtained.
691      Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
692        _Graph::Edge(e), backward(_backward) { }
693      Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
694      bool operator==(const Edge& v) const {
695        return (this->backward==v.backward &&
696                static_cast<typename _Graph::Edge>(*this)==
697                static_cast<typename _Graph::Edge>(v));
698      }
699      bool operator!=(const Edge& v) const {
700        return (this->backward!=v.backward ||
701                static_cast<typename _Graph::Edge>(*this)!=
702                static_cast<typename _Graph::Edge>(v));
703      }
704    };
705
706    void first(Node& i) const {
707      Parent::first(i);
708    }
709
710    void first(Edge& i) const {
711      Parent::first(i);
712      i.backward=false;
713      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
714             !(*forward_filter)[i]) Parent::next(i);
715      if (*static_cast<GraphEdge*>(&i)==INVALID) {
716        Parent::first(i);
717        i.backward=true;
718        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
719               !(*backward_filter)[i]) Parent::next(i);
720      }
721    }
722
723    void firstIn(Edge& i, const Node& n) const {
724      Parent::firstIn(i, n);
725      i.backward=false;
726      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
727             !(*forward_filter)[i]) Parent::nextOut(i);
728      if (*static_cast<GraphEdge*>(&i)==INVALID) {
729        Parent::firstOut(i, n);
730        i.backward=true;
731        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
732               !(*backward_filter)[i]) Parent::nextOut(i);
733      }
734    }
735
736    void firstOut(Edge& i, const Node& n) const {
737      Parent::firstOut(i, n);
738      i.backward=false;
739      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
740             !(*forward_filter)[i]) Parent::nextOut(i);
741      if (*static_cast<GraphEdge*>(&i)==INVALID) {
742        Parent::firstIn(i, n);
743        i.backward=true;
744        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
745               !(*backward_filter)[i]) Parent::nextIn(i);
746      }
747    }
748
749    void next(Node& i) const {
750      Parent::next(i);
751    }
752
753    void next(Edge& i) const {
754      if (!(i.backward)) {
755        Parent::next(i);
756        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
757               !(*forward_filter)[i]) Parent::next(i);
758        if (*static_cast<GraphEdge*>(&i)==INVALID) {
759          Parent::first(i);
760          i.backward=true;
761          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
762                 !(*backward_filter)[i]) Parent::next(i);
763        }
764      } else {
765        Parent::next(i);
766        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
767               !(*backward_filter)[i]) Parent::next(i);
768      }
769    }
770
771    void nextIn(Edge& i) const {
772      if (!(i.backward)) {
773        Node n=Parent::target(i);
774        Parent::nextIn(i);
775        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
776               !(*forward_filter)[i]) Parent::nextIn(i);
777        if (*static_cast<GraphEdge*>(&i)==INVALID) {
778          Parent::firstOut(i, n);
779          i.backward=true;
780          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
781                 !(*backward_filter)[i]) Parent::nextOut(i);
782        }
783      } else {
784        Parent::nextOut(i);
785        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
786               !(*backward_filter)[i]) Parent::nextOut(i);
787      }
788    }
789
790    void nextOut(Edge& i) const {
791      if (!(i.backward)) {
792        Node n=Parent::source(i);
793        Parent::nextOut(i);
794        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
795               !(*forward_filter)[i]) Parent::nextOut(i);
796        if (*static_cast<GraphEdge*>(&i)==INVALID) {
797          Parent::firstIn(i, n);
798          i.backward=true;
799          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
800                 !(*backward_filter)[i]) Parent::nextIn(i);
801        }
802      } else {
803        Parent::nextIn(i);
804        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
805               !(*backward_filter)[i]) Parent::nextIn(i);
806      }
807    }
808
809    Node source(Edge e) const {
810      return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
811    Node target(Edge e) const {
812      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
813
814    /// Gives back the opposite edge.
815    Edge opposite(const Edge& e) const {
816      Edge f=e;
817      f.backward=!f.backward;
818      return f;
819    }
820
821    /// \warning This is a linear time operation and works only if
822    /// \c Graph::EdgeIt is defined.
823    /// \todo hmm
824    int edgeNum() const {
825      int i=0;
826      Edge e;
827      for (first(e); e!=INVALID; next(e)) ++i;
828      return i;
829    }
830
831    bool forward(const Edge& e) const { return !e.backward; }
832    bool backward(const Edge& e) const { return e.backward; }
833
834    template <typename T>
835    /// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two
836    /// _Graph::EdgeMap one for the forward edges and
837    /// one for the backward edges.
838    class EdgeMap {
839      template <typename TT> friend class EdgeMap;
840      typename _Graph::template EdgeMap<T> forward_map, backward_map;
841    public:
842      typedef T Value;
843      typedef Edge Key;
844
845      EdgeMap(const SubBidirGraphWrapperBase<_Graph,
846              ForwardFilterMap, BackwardFilterMap>& g) :
847        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
848
849      EdgeMap(const SubBidirGraphWrapperBase<_Graph,
850              ForwardFilterMap, BackwardFilterMap>& g, T a) :
851        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
852     
853      void set(Edge e, T a) {
854        if (!e.backward)
855          forward_map.set(e, a);
856        else
857          backward_map.set(e, a);
858      }
859
860//       typename _Graph::template EdgeMap<T>::ConstReference
861//       operator[](Edge e) const {
862//      if (!e.backward)
863//        return forward_map[e];
864//      else
865//        return backward_map[e];
866//       }
867
868//      typename _Graph::template EdgeMap<T>::Reference
869      T operator[](Edge e) const {
870        if (!e.backward)
871          return forward_map[e];
872        else
873          return backward_map[e];
874      }
875
876      void update() {
877        forward_map.update();
878        backward_map.update();
879      }
880    };
881
882  };
883
884
885  ///\brief A wrapper for composing a subgraph of a
886  /// bidirected graph made from a directed one.
887  ///
888  /// A wrapper for composing a subgraph of a
889  /// bidirected graph made from a directed one.
890  ///
891  ///\warning Graph wrappers are in even more experimental state than the other
892  ///parts of the lib. Use them at you own risk.
893  ///
894  /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
895  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
896  /// reversing its orientation. We are given moreover two bool valued
897  /// maps on the edge-set,
898  /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
899  /// SubBidirGraphWrapper implements the graph structure with node-set
900  /// \f$V\f$ and edge-set
901  /// \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$.
902  /// The purpose of writing + instead of union is because parallel
903  /// edges can arise. (Similarly, antiparallel edges also can arise).
904  /// In other words, a subgraph of the bidirected graph obtained, which
905  /// is given by orienting the edges of the original graph in both directions.
906  /// As the oppositely directed edges are logically different,
907  /// the maps are able to attach different values for them.
908  ///
909  /// An example for such a construction is \c RevGraphWrapper where the
910  /// forward_filter is everywhere false and the backward_filter is
911  /// everywhere true. We note that for sake of efficiency,
912  /// \c RevGraphWrapper is implemented in a different way.
913  /// But BidirGraphWrapper is obtained from
914  /// SubBidirGraphWrapper by considering everywhere true
915  /// valued maps both for forward_filter and backward_filter.
916  /// Finally, one of the most important applications of SubBidirGraphWrapper
917  /// is ResGraphWrapper, which stands for the residual graph in directed
918  /// flow and circulation problems.
919  /// As wrappers usually, the SubBidirGraphWrapper implements the
920  /// above mentioned graph structure without its physical storage,
921  /// that is the whole stuff is stored in constant memory.
922  template<typename _Graph,
923           typename ForwardFilterMap, typename BackwardFilterMap>
924  class SubBidirGraphWrapper :
925    public IterableGraphExtender<
926    SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
927  public:
928    typedef _Graph Graph;
929    typedef IterableGraphExtender<
930      SubBidirGraphWrapperBase<
931      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
932  protected:
933    SubBidirGraphWrapper() { }
934  public:
935    SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,
936                         BackwardFilterMap& _backward_filter) {
937      setGraph(_graph);
938      setForwardFilterMap(_forward_filter);
939      setBackwardFilterMap(_backward_filter);
940    }
941  };
942
943
944
945  ///\brief A wrapper for composing bidirected graph from a directed one.
946  ///
947  ///\warning Graph wrappers are in even more experimental state than the other
948  ///parts of the lib. Use them at you own risk.
949  ///
950  /// A wrapper for composing bidirected graph from a directed one.
951  /// A bidirected graph is composed over the directed one without physical
952  /// storage. As the oppositely directed edges are logically different ones
953  /// the maps are able to attach different values for them.
954  template<typename Graph>
955  class BidirGraphWrapper :
956    public SubBidirGraphWrapper<
957    Graph,
958    ConstMap<typename Graph::Edge, bool>,
959    ConstMap<typename Graph::Edge, bool> > {
960  public:
961    typedef  SubBidirGraphWrapper<
962      Graph,
963      ConstMap<typename Graph::Edge, bool>,
964      ConstMap<typename Graph::Edge, bool> > Parent;
965  protected:
966    ConstMap<typename Graph::Edge, bool> cm;
967
968    BidirGraphWrapper() : Parent(), cm(true) {
969      Parent::setForwardFilterMap(cm);
970      Parent::setBackwardFilterMap(cm);
971    }
972  public:
973    BidirGraphWrapper(Graph& _graph) : Parent(), cm(true) {
974      Parent::setGraph(_graph);
975      Parent::setForwardFilterMap(cm);
976      Parent::setBackwardFilterMap(cm);
977    }
978
979    int edgeNum() const {
980      return 2*this->graph->edgeNum();
981    }
982    //    KEEP_MAPS(Parent, BidirGraphWrapper);
983  };
984
985
986  template<typename Graph, typename Number,
987           typename CapacityMap, typename FlowMap>
988  class ResForwardFilter {
989    //    const Graph* graph;
990    const CapacityMap* capacity;
991    const FlowMap* flow;
992  public:
993    ResForwardFilter(/*const Graph& _graph, */
994                     const CapacityMap& _capacity, const FlowMap& _flow) :
995      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
996    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
997    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
998    void setFlow(const FlowMap& _flow) { flow=&_flow; }
999    bool operator[](const typename Graph::Edge& e) const {
1000      return (Number((*flow)[e]) < Number((*capacity)[e]));
1001    }
1002  };
1003
1004  template<typename Graph, typename Number,
1005           typename CapacityMap, typename FlowMap>
1006  class ResBackwardFilter {
1007    const CapacityMap* capacity;
1008    const FlowMap* flow;
1009  public:
1010    ResBackwardFilter(/*const Graph& _graph,*/
1011                      const CapacityMap& _capacity, const FlowMap& _flow) :
1012      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1013    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1014    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1015    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1016    bool operator[](const typename Graph::Edge& e) const {
1017      return (Number(0) < Number((*flow)[e]));
1018    }
1019  };
1020
1021 
1022  /// A wrapper for composing the residual graph for directed flow and circulation problems.
1023
1024  ///\warning Graph wrappers are in even more experimental state than the other
1025  ///parts of the lib. Use them at you own risk.
1026  ///
1027  /// A wrapper for composing the residual graph for directed flow and circulation problems.
1028  template<typename Graph, typename Number,
1029           typename CapacityMap, typename FlowMap>
1030  class ResGraphWrapper :
1031    public SubBidirGraphWrapper<
1032    Graph,
1033    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1034    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1035  public:
1036    typedef SubBidirGraphWrapper<
1037      Graph,
1038      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1039      ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1040  protected:
1041    const CapacityMap* capacity;
1042    FlowMap* flow;
1043    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1044    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1045    ResGraphWrapper() : Parent(),
1046                        capacity(0), flow(0) { }
1047    void setCapacityMap(const CapacityMap& _capacity) {
1048      capacity=&_capacity;
1049      forward_filter.setCapacity(_capacity);
1050      backward_filter.setCapacity(_capacity);
1051    }
1052    void setFlowMap(FlowMap& _flow) {
1053      flow=&_flow;
1054      forward_filter.setFlow(_flow);
1055      backward_filter.setFlow(_flow);
1056    }
1057  public:
1058    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1059                       FlowMap& _flow) :
1060      Parent(), capacity(&_capacity), flow(&_flow),
1061      forward_filter(/*_graph,*/ _capacity, _flow),
1062      backward_filter(/*_graph,*/ _capacity, _flow) {
1063      Parent::setGraph(_graph);
1064      Parent::setForwardFilterMap(forward_filter);
1065      Parent::setBackwardFilterMap(backward_filter);
1066    }
1067
1068    typedef typename Parent::Edge Edge;
1069
1070    void augment(const Edge& e, Number a) const {
1071      if (Parent::forward(e)) 
1072        flow->set(e, (*flow)[e]+a);
1073      else 
1074        flow->set(e, (*flow)[e]-a);
1075    }
1076
1077    /// \brief Residual capacity map.
1078    ///
1079    /// In generic residual graphs the residual capacity can be obtained
1080    /// as a map.
1081    class ResCap {
1082    protected:
1083      const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1084    public:
1085      typedef Number Value;
1086      typedef Edge Key;
1087      ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
1088             _res_graph) : res_graph(&_res_graph) { }
1089      Number operator[](const Edge& e) const {
1090        if (res_graph->forward(e))
1091          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1092        else
1093          return (*(res_graph->flow))[e];
1094      }
1095    };
1096
1097    //    KEEP_MAPS(Parent, ResGraphWrapper);
1098  };
1099
1100
1101
1102  template <typename _Graph, typename FirstOutEdgesMap>
1103  class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {
1104  public:
1105    typedef _Graph Graph;
1106    typedef GraphWrapperBase<_Graph> Parent;
1107  protected:
1108    FirstOutEdgesMap* first_out_edges;
1109    ErasingFirstGraphWrapperBase() : Parent(),
1110                                     first_out_edges(0) { }
1111
1112    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1113      first_out_edges=&_first_out_edges;
1114    }
1115
1116  public:
1117
1118    typedef typename Parent::Node Node;
1119    typedef typename Parent::Edge Edge;
1120
1121    void firstOut(Edge& i, const Node& n) const {
1122      i=(*first_out_edges)[n];
1123    }
1124
1125    void erase(const Edge& e) const {
1126      Node n=source(e);
1127      Edge f=e;
1128      Parent::nextOut(f);
1129      first_out_edges->set(n, f);
1130    }   
1131  };
1132
1133
1134  /// For blocking flows.
1135
1136  ///\warning Graph wrappers are in even more experimental state than the other
1137  ///parts of the lib. Use them at you own risk.
1138  ///
1139  /// This graph wrapper is used for on-the-fly
1140  /// Dinits blocking flow computations.
1141  /// For each node, an out-edge is stored which is used when the
1142  /// \code
1143  /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1144  /// \endcode
1145  /// is called.
1146  ///
1147  /// \author Marton Makai
1148  template <typename _Graph, typename FirstOutEdgesMap>
1149  class ErasingFirstGraphWrapper :
1150    public IterableGraphExtender<
1151    ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {
1152  public:
1153    typedef _Graph Graph;
1154    typedef IterableGraphExtender<
1155      ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;
1156    ErasingFirstGraphWrapper(Graph& _graph,
1157                             FirstOutEdgesMap& _first_out_edges) {
1158      setGraph(_graph);
1159      setFirstOutEdgesMap(_first_out_edges);
1160    }
1161
1162  };
1163
1164  ///@}
1165
1166} //namespace lemon
1167
1168#endif //LEMON_GRAPH_WRAPPER_H
1169
Note: See TracBrowser for help on using the repository browser.