Last change on this file since 1160:d9c32f713cad was 1160:d9c32f713cad, checked in by Alpar Juttner, 15 years ago

We have UndirGraph?, so BidirGraph? has been removed.

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