COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_wrapper.h @ 1389:58b298e50c20

Last change on this file since 1389:58b298e50c20 was 1383:79b68a337f9f, checked in by marci, 19 years ago

A new implementation of UndirGraphWrapper?, accordig to the undirected concepts

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