COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_adaptor.h @ 1425:f3717c08e2be

Last change on this file since 1425:f3717c08e2be was 1425:f3717c08e2be, checked in by marci, 14 years ago

minor modifications

File size: 39.6 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/graph_adaptor.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_ADAPTOR_H
18#define LEMON_GRAPH_ADAPTOR_H
19
20///\ingroup graph_adaptors
21///\file
22///\brief Several graph adaptors.
23///
24///This file contains several useful graph adaptor 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 adaptors
37
38  /*!
39    \addtogroup graph_adaptors
40    @{
41   */
42
43  /*!
44    Base type for the Graph Adaptors
45   
46    \warning Graph adaptors 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 adaptors.
50    This class implements a trivial graph adaptor 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 adaptors. E.g. if an adaptor is
53    considered which differs from the wrapped graph only in some of its
54    functions or types, then it can be derived from GraphAdaptor, and only the
55    differences should be implemented.
56 
57    \author Marton Makai
58  */
59  template<typename _Graph>
60  class GraphAdaptorBase {
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    GraphAdaptorBase() : graph(0) { }
70    void setGraph(Graph& _graph) { graph=&_graph; }
71
72  public:
73    GraphAdaptorBase(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 GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
116      NodeMap(const GraphAdaptorBase<_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 GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
125      EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
126      : Parent(*gw.graph, value) { }
127    };
128
129  };
130
131  template <typename _Graph>
132  class GraphAdaptor :
133    public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
134  public:
135    typedef _Graph Graph;
136    typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
137  protected:
138    GraphAdaptor() : Parent() { }
139
140  public:
141    GraphAdaptor(Graph& _graph) { setGraph(_graph); }
142  };
143
144  template <typename _Graph>
145  class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
146  public:
147    typedef _Graph Graph;
148    typedef GraphAdaptorBase<_Graph> Parent;
149  protected:
150    RevGraphAdaptorBase() : 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 adaptor which reverses the orientation of the edges.
169
170  ///\warning Graph adaptors 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 RevGraphAdaptor 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  /// RevGraphAdaptor<ListGraph> gw(g);
189  /// \endcode
190  ///\author Marton Makai
191  template<typename _Graph>
192  class RevGraphAdaptor :
193    public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
194  public:
195    typedef _Graph Graph;
196    typedef IterableGraphExtender<
197      RevGraphAdaptorBase<_Graph> > Parent;
198  protected:
199    RevGraphAdaptor() { }
200  public:
201    RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
202  };
203
204 
205  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
206  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
207  public:
208    typedef _Graph Graph;
209    typedef GraphAdaptorBase<_Graph> Parent;
210  protected:
211    NodeFilterMap* node_filter_map;
212    EdgeFilterMap* edge_filter_map;
213    SubGraphAdaptorBase() : 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//     SubGraphAdaptorBase(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 adaptor for hiding nodes and edges from a graph.
318   
319  \warning Graph adaptors are in even more experimental state than the other
320  parts of the lib. Use them at you own risk.
321 
322  SubGraphAdaptor 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  SubGraphAdaptor<...>::NodeIt iterates
330  on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
331  SubGraphAdaptor<...>::EdgeIt iterates
332  on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
333  SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::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 SubGraphAdaptor<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 NodeSubGraphAdaptor and
369  EdgeSubGraphAdaptor.
370
371  \author Marton Makai
372  */
373  template<typename _Graph, typename NodeFilterMap,
374           typename EdgeFilterMap>
375  class SubGraphAdaptor :
376    public IterableGraphExtender<
377    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
378  public:
379    typedef _Graph Graph;
380    typedef IterableGraphExtender<
381      SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
382  protected:
383    SubGraphAdaptor() { }
384  public:
385    SubGraphAdaptor(_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 An adaptor for hiding nodes from a graph.
396
397  \warning Graph adaptors are in even more experimental state than the other
398  parts of the lib. Use them at you own risk.
399 
400  An adaptor for hiding nodes from a graph.
401  This adaptor specializes SubGraphAdaptor 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 NodeSubGraphAdaptor :
408    public SubGraphAdaptor<Graph, NodeFilterMap,
409                           ConstMap<typename Graph::Edge,bool> > {
410  public:
411    typedef SubGraphAdaptor<Graph, NodeFilterMap,
412                            ConstMap<typename Graph::Edge,bool> > Parent;
413  protected:
414    ConstMap<typename Graph::Edge, bool> const_true_map;
415  public:
416    NodeSubGraphAdaptor(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 An adaptor for hiding edges from a graph.
426
427  \warning Graph adaptors are in even more experimental state than the other
428  parts of the lib. Use them at you own risk.
429 
430  An adaptor for hiding edges from a graph.
431  This adaptor specializes SubGraphAdaptor in the way that only the edge-set
432  can be filtered. The usefulness of this adaptor 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 the dimacs file \ref sub_graph_adaptor_demo.dim.
450  The full source code is available in \ref sub_graph_adaptor_demo.cc.
451  If you are interested in more demo programs, you can use
452  \ref dim_to_dot.cc to generate .dot files from dimacs files.
453  The .dot file of the following figure of was generated generated by 
454  the demo program \ref dim_to_dot.cc.
455
456  \dot
457  digraph lemon_dot_example {
458  node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
459  n0 [ label="0 (s)" ];
460  n1 [ label="1" ];
461  n2 [ label="2" ];
462  n3 [ label="3" ];
463  n4 [ label="4" ];
464  n5 [ label="5" ];
465  n6 [ label="6 (t)" ];
466  edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
467  n5 ->  n6 [ label="9, length:4" ];
468  n4 ->  n6 [ label="8, length:2" ];
469  n3 ->  n5 [ label="7, length:1" ];
470  n2 ->  n5 [ label="6, length:3" ];
471  n2 ->  n6 [ label="5, length:5" ];
472  n2 ->  n4 [ label="4, length:2" ];
473  n1 ->  n4 [ label="3, length:3" ];
474  n0 ->  n3 [ label="2, length:1" ];
475  n0 ->  n2 [ label="1, length:2" ];
476  n0 ->  n1 [ label="0, length:3" ];
477  }
478  \enddot
479
480  \code
481  Graph g;
482  Node s, t;
483  LengthMap length(g);
484
485  readDimacs(std::cin, g, length, s, t);
486
487  cout << "edges with lengths (of form id, source--length->target): " << endl;
488  for(EdgeIt e(g); e!=INVALID; ++e)
489    cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
490         << length[e] << "->" << g.id(g.target(e)) << endl;
491
492  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
493  \endcode
494  Next, the potential function is computed with Dijkstra.
495  \code
496  typedef Dijkstra<Graph, LengthMap> Dijkstra;
497  Dijkstra dijkstra(g, length);
498  dijkstra.run(s);
499  \endcode
500  Next, we consrtruct a map which filters the edge-set to the tight edges.
501  \code
502  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
503    TightEdgeFilter;
504  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
505 
506  typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
507  SubGW gw(g, tight_edge_filter);
508  \endcode
509  Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
510  with a max flow algorithm Preflow.
511  \code
512  ConstMap<Edge, int> const_1_map(1);
513  Graph::EdgeMap<int> flow(g, 0);
514
515  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
516    preflow(gw, s, t, const_1_map, flow);
517  preflow.run();
518  \endcode
519  Last, the output is:
520  \code 
521  cout << "maximum number of edge-disjoint shortest path: "
522       << preflow.flowValue() << endl;
523  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
524       << endl;
525  for(EdgeIt e(g); e!=INVALID; ++e)
526    if (flow[e])
527      cout << " " << g.id(g.source(e)) << "--"
528           << length[e] << "->" << g.id(g.target(e)) << endl;
529  \endcode
530  The program has the following (expected :-)) output:
531  \code
532  edges with lengths (of form id, source--length->target):
533   9, 5--4->6
534   8, 4--2->6
535   7, 3--1->5
536   6, 2--3->5
537   5, 2--5->6
538   4, 2--2->4
539   3, 1--3->4
540   2, 0--1->3
541   1, 0--2->2
542   0, 0--3->1
543  s: 0 t: 6
544  maximum number of edge-disjoint shortest path: 2
545  edges of the maximum number of edge-disjoint shortest s-t paths:
546   9, 5--4->6
547   8, 4--2->6
548   7, 3--1->5
549   4, 2--2->4
550   2, 0--1->3
551   1, 0--2->2
552  \endcode
553
554  \author Marton Makai
555  */
556  template<typename Graph, typename EdgeFilterMap>
557  class EdgeSubGraphAdaptor :
558    public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
559                           EdgeFilterMap> {
560  public:
561    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
562                            EdgeFilterMap> Parent;
563  protected:
564    ConstMap<typename Graph::Node, bool> const_true_map;
565  public:
566    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
567      Parent(), const_true_map(true) {
568      Parent::setGraph(_graph);
569      Parent::setNodeFilterMap(const_true_map);
570      Parent::setEdgeFilterMap(_edge_filter_map);
571    }
572  };
573
574  template <typename _Graph>
575  class UndirGraphAdaptorBase :
576    public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
577  public:
578    typedef _Graph Graph;
579    typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
580  protected:
581    UndirGraphAdaptorBase() : Parent() { }
582  public:
583    typedef typename Parent::UndirEdge UndirEdge;
584    typedef typename Parent::Edge Edge;
585   
586    /// \bug Why cant an edge say that it is forward or not???
587    /// By this, a pointer to the graph have to be stored
588    /// The implementation
589    template <typename T>
590    class EdgeMap {
591    protected:
592      const UndirGraphAdaptorBase<_Graph>* g;
593      template <typename TT> friend class EdgeMap;
594      typename _Graph::template EdgeMap<T> forward_map, backward_map;
595    public:
596      typedef T Value;
597      typedef Edge Key;
598     
599      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
600        forward_map(*(g->graph)), backward_map(*(g->graph)) { }
601
602      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
603        forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
604     
605      void set(Edge e, T a) {
606        if (g->forward(e))
607          forward_map.set(e, a);
608        else
609          backward_map.set(e, a);
610      }
611
612      T operator[](Edge e) const {
613        if (g->forward(e))
614          return forward_map[e];
615        else
616          return backward_map[e];
617      }
618    };
619       
620    template <typename T>
621    class UndirEdgeMap {
622      template <typename TT> friend class UndirEdgeMap;
623      typename _Graph::template EdgeMap<T> map;
624    public:
625      typedef T Value;
626      typedef UndirEdge Key;
627     
628      UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
629        map(*(g.graph)) { }
630
631      UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
632        map(*(g.graph), a) { }
633     
634      void set(UndirEdge e, T a) {
635        map.set(e, a);
636      }
637
638      T operator[](UndirEdge e) const {
639        return map[e];
640      }
641    };
642     
643  };
644
645  /// \brief An undirected graph is made from a directed graph by an adaptor
646  ///
647  /// Undocumented, untested!!!
648  /// If somebody knows nice demo application, let's polulate it.
649  ///
650  /// \author Marton Makai
651  template<typename _Graph>
652  class UndirGraphAdaptor :
653    public IterableUndirGraphExtender<
654    UndirGraphAdaptorBase<_Graph> > {
655  public:
656    typedef _Graph Graph;
657    typedef IterableUndirGraphExtender<
658      UndirGraphAdaptorBase<_Graph> > Parent;
659  protected:
660    UndirGraphAdaptor() { }
661  public:
662    UndirGraphAdaptor(_Graph& _graph) {
663      setGraph(_graph);
664    }
665  };
666
667 
668  template <typename _Graph,
669            typename ForwardFilterMap, typename BackwardFilterMap>
670  class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
671  public:
672    typedef _Graph Graph;
673    typedef GraphAdaptorBase<_Graph> Parent;
674  protected:
675    ForwardFilterMap* forward_filter;
676    BackwardFilterMap* backward_filter;
677    SubBidirGraphAdaptorBase() : Parent(),
678                                 forward_filter(0), backward_filter(0) { }
679
680    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
681      forward_filter=&_forward_filter;
682    }
683    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
684      backward_filter=&_backward_filter;
685    }
686
687  public:
688//     SubGraphAdaptorBase(Graph& _graph,
689//                      NodeFilterMap& _node_filter_map,
690//                      EdgeFilterMap& _edge_filter_map) :
691//       Parent(&_graph),
692//       node_filter_map(&node_filter_map),
693//       edge_filter_map(&edge_filter_map) { }
694
695    typedef typename Parent::Node Node;
696    typedef typename _Graph::Edge GraphEdge;
697    template <typename T> class EdgeMap;
698    /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
699    /// _Graph::Edge. It contains an extra bool flag which is true
700    /// if and only if the
701    /// edge is the backward version of the original edge.
702    class Edge : public _Graph::Edge {
703      friend class SubBidirGraphAdaptorBase<
704        Graph, ForwardFilterMap, BackwardFilterMap>;
705      template<typename T> friend class EdgeMap;
706    protected:
707      bool backward; //true, iff backward
708    public:
709      Edge() { }
710      /// \todo =false is needed, or causes problems?
711      /// If \c _backward is false, then we get an edge corresponding to the
712      /// original one, otherwise its oppositely directed pair is obtained.
713      Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
714        _Graph::Edge(e), backward(_backward) { }
715      Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
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      bool operator!=(const Edge& v) const {
722        return (this->backward!=v.backward ||
723                static_cast<typename _Graph::Edge>(*this)!=
724                static_cast<typename _Graph::Edge>(v));
725      }
726    };
727
728    void first(Node& i) const {
729      Parent::first(i);
730    }
731
732    void first(Edge& i) const {
733      Parent::first(i);
734      i.backward=false;
735      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
736             !(*forward_filter)[i]) Parent::next(i);
737      if (*static_cast<GraphEdge*>(&i)==INVALID) {
738        Parent::first(i);
739        i.backward=true;
740        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
741               !(*backward_filter)[i]) Parent::next(i);
742      }
743    }
744
745    void firstIn(Edge& i, const Node& n) const {
746      Parent::firstIn(i, n);
747      i.backward=false;
748      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
749             !(*forward_filter)[i]) Parent::nextIn(i);
750      if (*static_cast<GraphEdge*>(&i)==INVALID) {
751        Parent::firstOut(i, n);
752        i.backward=true;
753        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
754               !(*backward_filter)[i]) Parent::nextOut(i);
755      }
756    }
757
758    void firstOut(Edge& i, const Node& n) const {
759      Parent::firstOut(i, n);
760      i.backward=false;
761      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
762             !(*forward_filter)[i]) Parent::nextOut(i);
763      if (*static_cast<GraphEdge*>(&i)==INVALID) {
764        Parent::firstIn(i, n);
765        i.backward=true;
766        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
767               !(*backward_filter)[i]) Parent::nextIn(i);
768      }
769    }
770
771    void next(Node& i) const {
772      Parent::next(i);
773    }
774
775    void next(Edge& i) const {
776      if (!(i.backward)) {
777        Parent::next(i);
778        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
779               !(*forward_filter)[i]) Parent::next(i);
780        if (*static_cast<GraphEdge*>(&i)==INVALID) {
781          Parent::first(i);
782          i.backward=true;
783          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
784                 !(*backward_filter)[i]) Parent::next(i);
785        }
786      } else {
787        Parent::next(i);
788        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
789               !(*backward_filter)[i]) Parent::next(i);
790      }
791    }
792
793    void nextIn(Edge& i) const {
794      if (!(i.backward)) {
795        Node n=Parent::target(i);
796        Parent::nextIn(i);
797        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
798               !(*forward_filter)[i]) Parent::nextIn(i);
799        if (*static_cast<GraphEdge*>(&i)==INVALID) {
800          Parent::firstOut(i, n);
801          i.backward=true;
802          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
803                 !(*backward_filter)[i]) Parent::nextOut(i);
804        }
805      } else {
806        Parent::nextOut(i);
807        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
808               !(*backward_filter)[i]) Parent::nextOut(i);
809      }
810    }
811
812    void nextOut(Edge& i) const {
813      if (!(i.backward)) {
814        Node n=Parent::source(i);
815        Parent::nextOut(i);
816        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
817               !(*forward_filter)[i]) Parent::nextOut(i);
818        if (*static_cast<GraphEdge*>(&i)==INVALID) {
819          Parent::firstIn(i, n);
820          i.backward=true;
821          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
822                 !(*backward_filter)[i]) Parent::nextIn(i);
823        }
824      } else {
825        Parent::nextIn(i);
826        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
827               !(*backward_filter)[i]) Parent::nextIn(i);
828      }
829    }
830
831    Node source(Edge e) const {
832      return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
833    Node target(Edge e) const {
834      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
835
836    /// Gives back the opposite edge.
837    Edge opposite(const Edge& e) const {
838      Edge f=e;
839      f.backward=!f.backward;
840      return f;
841    }
842
843    /// \warning This is a linear time operation and works only if
844    /// \c Graph::EdgeIt is defined.
845    /// \todo hmm
846    int edgeNum() const {
847      int i=0;
848      Edge e;
849      for (first(e); e!=INVALID; next(e)) ++i;
850      return i;
851    }
852
853    bool forward(const Edge& e) const { return !e.backward; }
854    bool backward(const Edge& e) const { return e.backward; }
855
856    template <typename T>
857    /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
858    /// _Graph::EdgeMap one for the forward edges and
859    /// one for the backward edges.
860    class EdgeMap {
861      template <typename TT> friend class EdgeMap;
862      typename _Graph::template EdgeMap<T> forward_map, backward_map;
863    public:
864      typedef T Value;
865      typedef Edge Key;
866
867      EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
868              ForwardFilterMap, BackwardFilterMap>& g) :
869        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
870
871      EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
872              ForwardFilterMap, BackwardFilterMap>& g, T a) :
873        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
874     
875      void set(Edge e, T a) {
876        if (!e.backward)
877          forward_map.set(e, a);
878        else
879          backward_map.set(e, a);
880      }
881
882//       typename _Graph::template EdgeMap<T>::ConstReference
883//       operator[](Edge e) const {
884//      if (!e.backward)
885//        return forward_map[e];
886//      else
887//        return backward_map[e];
888//       }
889
890//      typename _Graph::template EdgeMap<T>::Reference
891      T operator[](Edge e) const {
892        if (!e.backward)
893          return forward_map[e];
894        else
895          return backward_map[e];
896      }
897
898      void update() {
899        forward_map.update();
900        backward_map.update();
901      }
902    };
903
904  };
905
906
907  ///\brief An adaptor for composing a subgraph of a
908  /// bidirected graph made from a directed one.
909  ///
910  /// An adaptor for composing a subgraph of a
911  /// bidirected graph made from a directed one.
912  ///
913  ///\warning Graph adaptors are in even more experimental state than the other
914  ///parts of the lib. Use them at you own risk.
915  ///
916  /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
917  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
918  /// reversing its orientation. We are given moreover two bool valued
919  /// maps on the edge-set,
920  /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
921  /// SubBidirGraphAdaptor implements the graph structure with node-set
922  /// \f$V\f$ and edge-set
923  /// \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$.
924  /// The purpose of writing + instead of union is because parallel
925  /// edges can arise. (Similarly, antiparallel edges also can arise).
926  /// In other words, a subgraph of the bidirected graph obtained, which
927  /// is given by orienting the edges of the original graph in both directions.
928  /// As the oppositely directed edges are logically different,
929  /// the maps are able to attach different values for them.
930  ///
931  /// An example for such a construction is \c RevGraphAdaptor where the
932  /// forward_filter is everywhere false and the backward_filter is
933  /// everywhere true. We note that for sake of efficiency,
934  /// \c RevGraphAdaptor is implemented in a different way.
935  /// But BidirGraphAdaptor is obtained from
936  /// SubBidirGraphAdaptor by considering everywhere true
937  /// valued maps both for forward_filter and backward_filter.
938  ///
939  /// The most important application of SubBidirGraphAdaptor
940  /// is ResGraphAdaptor, which stands for the residual graph in directed
941  /// flow and circulation problems.
942  /// As adaptors usually, the SubBidirGraphAdaptor implements the
943  /// above mentioned graph structure without its physical storage,
944  /// that is the whole stuff is stored in constant memory.
945  template<typename _Graph,
946           typename ForwardFilterMap, typename BackwardFilterMap>
947  class SubBidirGraphAdaptor :
948    public IterableGraphExtender<
949    SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
950  public:
951    typedef _Graph Graph;
952    typedef IterableGraphExtender<
953      SubBidirGraphAdaptorBase<
954      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
955  protected:
956    SubBidirGraphAdaptor() { }
957  public:
958    SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
959                         BackwardFilterMap& _backward_filter) {
960      setGraph(_graph);
961      setForwardFilterMap(_forward_filter);
962      setBackwardFilterMap(_backward_filter);
963    }
964  };
965
966
967
968  ///\brief An adaptor for composing bidirected graph from a directed one.
969  ///
970  ///\warning Graph adaptors are in even more experimental state than the other
971  ///parts of the lib. Use them at you own risk.
972  ///
973  /// An adaptor for composing bidirected graph from a directed one.
974  /// A bidirected graph is composed over the directed one without physical
975  /// storage. As the oppositely directed edges are logically different ones
976  /// the maps are able to attach different values for them.
977  template<typename Graph>
978  class BidirGraphAdaptor :
979    public SubBidirGraphAdaptor<
980    Graph,
981    ConstMap<typename Graph::Edge, bool>,
982    ConstMap<typename Graph::Edge, bool> > {
983  public:
984    typedef  SubBidirGraphAdaptor<
985      Graph,
986      ConstMap<typename Graph::Edge, bool>,
987      ConstMap<typename Graph::Edge, bool> > Parent;
988  protected:
989    ConstMap<typename Graph::Edge, bool> cm;
990
991    BidirGraphAdaptor() : Parent(), cm(true) {
992      Parent::setForwardFilterMap(cm);
993      Parent::setBackwardFilterMap(cm);
994    }
995  public:
996    BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
997      Parent::setGraph(_graph);
998      Parent::setForwardFilterMap(cm);
999      Parent::setBackwardFilterMap(cm);
1000    }
1001
1002    int edgeNum() const {
1003      return 2*this->graph->edgeNum();
1004    }
1005    //    KEEP_MAPS(Parent, BidirGraphAdaptor);
1006  };
1007
1008
1009  template<typename Graph, typename Number,
1010           typename CapacityMap, typename FlowMap>
1011  class ResForwardFilter {
1012    //    const Graph* graph;
1013    const CapacityMap* capacity;
1014    const FlowMap* flow;
1015  public:
1016    ResForwardFilter(/*const Graph& _graph, */
1017                     const CapacityMap& _capacity, const FlowMap& _flow) :
1018      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1019    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1020    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1021    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1022    bool operator[](const typename Graph::Edge& e) const {
1023      return (Number((*flow)[e]) < Number((*capacity)[e]));
1024    }
1025  };
1026
1027  template<typename Graph, typename Number,
1028           typename CapacityMap, typename FlowMap>
1029  class ResBackwardFilter {
1030    const CapacityMap* capacity;
1031    const FlowMap* flow;
1032  public:
1033    ResBackwardFilter(/*const Graph& _graph,*/
1034                      const CapacityMap& _capacity, const FlowMap& _flow) :
1035      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1036    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1037    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1038    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1039    bool operator[](const typename Graph::Edge& e) const {
1040      return (Number(0) < Number((*flow)[e]));
1041    }
1042  };
1043
1044 
1045  /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
1046
1047  An adaptor for composing the residual graph for directed flow and circulation problems.
1048  Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
1049  number type. Let moreover
1050  \f$f,c:A\to F\f$, be functions on the edge-set.
1051  In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
1052  and \f$c\f$ for a capacity function.   
1053  Suppose that a graph instange \c g of type
1054  \c ListGraph implements \f$G\f$.
1055  \code
1056  ListGraph g;
1057  \endcode
1058  Then RevGraphAdaptor implements the graph structure with node-set
1059  \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
1060  \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
1061  \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
1062  i.e. the so called residual graph.
1063  When we take the union \f$A_{forward}\cup A_{backward}\f$,
1064  multilicities are counted, i.e. if an edge is in both
1065  \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
1066  appears twice.
1067  The following code shows how
1068  such an instance can be constructed.
1069  \code
1070  typedef ListGraph Graph;
1071  Graph::EdgeMap<int> f(g);
1072  Graph::EdgeMap<int> c(g);
1073  ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
1074  \endcode
1075  \author Marton Makai
1076  */
1077  template<typename Graph, typename Number,
1078           typename CapacityMap, typename FlowMap>
1079  class ResGraphAdaptor :
1080    public SubBidirGraphAdaptor<
1081    Graph,
1082    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1083    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1084  public:
1085    typedef SubBidirGraphAdaptor<
1086      Graph,
1087      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1088      ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1089  protected:
1090    const CapacityMap* capacity;
1091    FlowMap* flow;
1092    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1093    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1094    ResGraphAdaptor() : Parent(),
1095                        capacity(0), flow(0) { }
1096    void setCapacityMap(const CapacityMap& _capacity) {
1097      capacity=&_capacity;
1098      forward_filter.setCapacity(_capacity);
1099      backward_filter.setCapacity(_capacity);
1100    }
1101    void setFlowMap(FlowMap& _flow) {
1102      flow=&_flow;
1103      forward_filter.setFlow(_flow);
1104      backward_filter.setFlow(_flow);
1105    }
1106  public:
1107    ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
1108                       FlowMap& _flow) :
1109      Parent(), capacity(&_capacity), flow(&_flow),
1110      forward_filter(/*_graph,*/ _capacity, _flow),
1111      backward_filter(/*_graph,*/ _capacity, _flow) {
1112      Parent::setGraph(_graph);
1113      Parent::setForwardFilterMap(forward_filter);
1114      Parent::setBackwardFilterMap(backward_filter);
1115    }
1116
1117    typedef typename Parent::Edge Edge;
1118
1119    void augment(const Edge& e, Number a) const {
1120      if (Parent::forward(e)) 
1121        flow->set(e, (*flow)[e]+a);
1122      else 
1123        flow->set(e, (*flow)[e]-a);
1124    }
1125
1126    /// \brief Residual capacity map.
1127    ///
1128    /// In generic residual graphs the residual capacity can be obtained
1129    /// as a map.
1130    class ResCap {
1131    protected:
1132      const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
1133    public:
1134      typedef Number Value;
1135      typedef Edge Key;
1136      ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
1137             _res_graph) : res_graph(&_res_graph) { }
1138      Number operator[](const Edge& e) const {
1139        if (res_graph->forward(e))
1140          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1141        else
1142          return (*(res_graph->flow))[e];
1143      }
1144    };
1145
1146    //    KEEP_MAPS(Parent, ResGraphAdaptor);
1147  };
1148
1149
1150
1151  template <typename _Graph, typename FirstOutEdgesMap>
1152  class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1153  public:
1154    typedef _Graph Graph;
1155    typedef GraphAdaptorBase<_Graph> Parent;
1156  protected:
1157    FirstOutEdgesMap* first_out_edges;
1158    ErasingFirstGraphAdaptorBase() : Parent(),
1159                                     first_out_edges(0) { }
1160
1161    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1162      first_out_edges=&_first_out_edges;
1163    }
1164
1165  public:
1166
1167    typedef typename Parent::Node Node;
1168    typedef typename Parent::Edge Edge;
1169
1170    void firstOut(Edge& i, const Node& n) const {
1171      i=(*first_out_edges)[n];
1172    }
1173
1174    void erase(const Edge& e) const {
1175      Node n=source(e);
1176      Edge f=e;
1177      Parent::nextOut(f);
1178      first_out_edges->set(n, f);
1179    }   
1180  };
1181
1182
1183  /// For blocking flows.
1184
1185  ///\warning Graph adaptors are in even more experimental state than the other
1186  ///parts of the lib. Use them at you own risk.
1187  ///
1188  /// This graph adaptor is used for on-the-fly
1189  /// Dinits blocking flow computations.
1190  /// For each node, an out-edge is stored which is used when the
1191  /// \code
1192  /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1193  /// \endcode
1194  /// is called.
1195  ///
1196  /// \author Marton Makai
1197  template <typename _Graph, typename FirstOutEdgesMap>
1198  class ErasingFirstGraphAdaptor :
1199    public IterableGraphExtender<
1200    ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
1201  public:
1202    typedef _Graph Graph;
1203    typedef IterableGraphExtender<
1204      ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1205    ErasingFirstGraphAdaptor(Graph& _graph,
1206                             FirstOutEdgesMap& _first_out_edges) {
1207      setGraph(_graph);
1208      setFirstOutEdgesMap(_first_out_edges);
1209    }
1210
1211  };
1212
1213  ///@}
1214
1215} //namespace lemon
1216
1217#endif //LEMON_GRAPH_ADAPTOR_H
1218
Note: See TracBrowser for help on using the repository browser.