COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 1681:84e43c7ca1e3

Last change on this file since 1681:84e43c7ca1e3 was 1681:84e43c7ca1e3, checked in by Balazs Dezso, 14 years ago

SubGraphAdaptors? with edge checking functionality.

Improved grid_graph_demo

File size: 53.2 KB
Line 
1/* -*- C++ -*-
2 * 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/erasable_graph_extender.h>
31#include <lemon/bits/clearable_graph_extender.h>
32#include <lemon/bits/extendable_graph_extender.h>
33#include <lemon/bits/iterable_graph_extender.h>
34#include <lemon/bits/alteration_notifier.h>
35#include <lemon/bits/default_map.h>
36#include <lemon/bits/undir_graph_extender.h>
37#include <iostream>
38
39namespace lemon {
40
41  // Graph adaptors
42
43  /*!
44    \addtogroup graph_adaptors
45    @{
46   */
47
48  /*!
49    Base type for the Graph Adaptors
50   
51    \warning Graph adaptors are in even more experimental state than the other
52    parts of the lib. Use them at you own risk.
53   
54    This is the base type for most of LEMON graph adaptors.
55    This class implements a trivial graph adaptor i.e. it only wraps the
56    functions and types of the graph. The purpose of this class is to
57    make easier implementing graph adaptors. E.g. if an adaptor is
58    considered which differs from the wrapped graph only in some of its
59    functions or types, then it can be derived from GraphAdaptor, and only the
60    differences should be implemented.
61 
62    \author Marton Makai
63  */
64  template<typename _Graph>
65  class GraphAdaptorBase {
66  public:
67    typedef _Graph Graph;
68    /// \todo Is it needed?
69    typedef Graph BaseGraph;
70    typedef Graph ParentGraph;
71
72  protected:
73    Graph* graph;
74    GraphAdaptorBase() : graph(0) { }
75    void setGraph(Graph& _graph) { graph=&_graph; }
76
77  public:
78    GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
79 
80    typedef typename Graph::Node Node;
81    typedef typename Graph::Edge Edge;
82   
83    void first(Node& i) const { graph->first(i); }
84    void first(Edge& i) const { graph->first(i); }
85    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
86    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
87
88    void next(Node& i) const { graph->next(i); }
89    void next(Edge& i) const { graph->next(i); }
90    void nextIn(Edge& i) const { graph->nextIn(i); }
91    void nextOut(Edge& i) const { graph->nextOut(i); }
92
93    Node source(const Edge& e) const { return graph->source(e); }
94    Node target(const Edge& e) const { return graph->target(e); }
95
96    int nodeNum() const { return graph->nodeNum(); }
97    int edgeNum() const { return graph->edgeNum(); }
98 
99    Node addNode() const { return Node(graph->addNode()); }
100    Edge addEdge(const Node& source, const Node& target) const {
101      return Edge(graph->addEdge(source, target)); }
102
103    void erase(const Node& i) const { graph->erase(i); }
104    void erase(const Edge& i) const { graph->erase(i); }
105 
106    void clear() const { graph->clear(); }
107   
108    int id(const Node& v) const { return graph->id(v); }
109    int id(const Edge& e) const { return graph->id(e); }
110   
111    Edge oppositeNode(const Edge& e) const {
112      return Edge(graph->opposite(e));
113    }
114
115    template <typename _Value>
116    class NodeMap : public _Graph::template NodeMap<_Value> {
117    public:
118      typedef typename _Graph::template NodeMap<_Value> Parent;
119      NodeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
120      NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
121      : Parent(*gw.graph, value) { }
122    };
123
124    template <typename _Value>
125    class EdgeMap : public _Graph::template EdgeMap<_Value> {
126    public:
127      typedef typename _Graph::template EdgeMap<_Value> Parent;
128      EdgeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
129      EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
130      : Parent(*gw.graph, value) { }
131    };
132
133  };
134
135  template <typename _Graph>
136  class GraphAdaptor :
137    public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
138  public:
139    typedef _Graph Graph;
140    typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
141  protected:
142    GraphAdaptor() : Parent() { }
143
144  public:
145    GraphAdaptor(Graph& _graph) { setGraph(_graph); }
146  };
147
148  template <typename _Graph>
149  class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
150  public:
151    typedef _Graph Graph;
152    typedef GraphAdaptorBase<_Graph> Parent;
153  protected:
154    RevGraphAdaptorBase() : Parent() { }
155  public:
156    typedef typename Parent::Node Node;
157    typedef typename Parent::Edge Edge;
158
159    //    using Parent::first;
160    void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
161    void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
162
163    //    using Parent::next;
164    void nextIn(Edge& i) const { Parent::nextOut(i); }
165    void nextOut(Edge& i) const { Parent::nextIn(i); }
166
167    Node source(const Edge& e) const { return Parent::target(e); }
168    Node target(const Edge& e) const { return Parent::source(e); }
169  };
170   
171
172  /// A graph adaptor which reverses the orientation of the edges.
173
174  ///\warning Graph adaptors are in even more experimental state than the other
175  ///parts of the lib. Use them at you own risk.
176  ///
177  /// Let \f$G=(V, A)\f$ be a directed graph and
178  /// suppose that a graph instange \c g of type
179  /// \c ListGraph implements \f$G\f$.
180  /// \code
181  /// ListGraph g;
182  /// \endcode
183  /// For each directed edge
184  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
185  /// reversing its orientation.
186  /// Then RevGraphAdaptor implements the graph structure with node-set
187  /// \f$V\f$ and edge-set
188  /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
189  /// reversing the orientation of its edges. The following code shows how
190  /// such an instance can be constructed.
191  /// \code
192  /// RevGraphAdaptor<ListGraph> gw(g);
193  /// \endcode
194  ///\author Marton Makai
195  template<typename _Graph>
196  class RevGraphAdaptor :
197    public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
198  public:
199    typedef _Graph Graph;
200    typedef IterableGraphExtender<
201      RevGraphAdaptorBase<_Graph> > Parent;
202  protected:
203    RevGraphAdaptor() { }
204  public:
205    RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
206  };
207
208 
209  template <typename _Graph, typename NodeFilterMap,
210            typename EdgeFilterMap, bool checked = true>
211  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
212  public:
213    typedef _Graph Graph;
214    typedef GraphAdaptorBase<_Graph> Parent;
215  protected:
216    NodeFilterMap* node_filter_map;
217    EdgeFilterMap* edge_filter_map;
218    SubGraphAdaptorBase() : Parent(),
219                            node_filter_map(0), edge_filter_map(0) { }
220
221    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
222      node_filter_map=&_node_filter_map;
223    }
224    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
225      edge_filter_map=&_edge_filter_map;
226    }
227
228  public:
229
230    typedef typename Parent::Node Node;
231    typedef typename Parent::Edge Edge;
232
233    void first(Node& i) const {
234      Parent::first(i);
235      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
236    }
237
238    void first(Edge& i) const {
239      Parent::first(i);
240      while (i!=INVALID && (!(*edge_filter_map)[i]
241             || !(*node_filter_map)[Parent::source(i)]
242             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
243    }
244
245    void firstIn(Edge& i, const Node& n) const {
246      Parent::firstIn(i, n);
247      while (i!=INVALID && (!(*edge_filter_map)[i]
248             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
249    }
250
251    void firstOut(Edge& i, const Node& n) const {
252      Parent::firstOut(i, n);
253      while (i!=INVALID && (!(*edge_filter_map)[i]
254             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
255    }
256
257    void next(Node& i) const {
258      Parent::next(i);
259      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
260    }
261
262    void next(Edge& i) const {
263      Parent::next(i);
264      while (i!=INVALID && (!(*edge_filter_map)[i]
265             || !(*node_filter_map)[Parent::source(i)]
266             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
267    }
268
269    void nextIn(Edge& i) const {
270      Parent::nextIn(i);
271      while (i!=INVALID && (!(*edge_filter_map)[i]
272             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
273    }
274
275    void nextOut(Edge& i) const {
276      Parent::nextOut(i);
277      while (i!=INVALID && (!(*edge_filter_map)[i]
278             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
279    }
280
281    /// This function hides \c n in the graph, i.e. the iteration
282    /// jumps over it. This is done by simply setting the value of \c n 
283    /// to be false in the corresponding node-map.
284    void hide(const Node& n) const { node_filter_map->set(n, false); }
285
286    /// This function hides \c e in the graph, i.e. the iteration
287    /// jumps over it. This is done by simply setting the value of \c e 
288    /// to be false in the corresponding edge-map.
289    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
290
291    /// The value of \c n is set to be true in the node-map which stores
292    /// hide information. If \c n was hidden previuosly, then it is shown
293    /// again
294     void unHide(const Node& n) const { node_filter_map->set(n, true); }
295
296    /// The value of \c e is set to be true in the edge-map which stores
297    /// hide information. If \c e was hidden previuosly, then it is shown
298    /// again
299    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
300
301    /// Returns true if \c n is hidden.
302    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
303
304    /// Returns true if \c n is hidden.
305    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
306
307    /// \warning This is a linear time operation and works only if s
308    /// \c Graph::NodeIt is defined.
309    /// \todo assign tags.
310    int nodeNum() const {
311      int i=0;
312      Node n;
313      for (first(n); n!=INVALID; next(n)) ++i;
314      return i;
315    }
316
317    /// \warning This is a linear time operation and works only if
318    /// \c Graph::EdgeIt is defined.
319    /// \todo assign tags.
320    int edgeNum() const {
321      int i=0;
322      Edge e;
323      for (first(e); e!=INVALID; next(e)) ++i;
324      return i;
325    }
326  };
327
328  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
329  class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
330    : public GraphAdaptorBase<_Graph> {
331  public:
332    typedef _Graph Graph;
333    typedef GraphAdaptorBase<_Graph> Parent;
334  protected:
335    NodeFilterMap* node_filter_map;
336    EdgeFilterMap* edge_filter_map;
337    SubGraphAdaptorBase() : Parent(),
338                            node_filter_map(0), edge_filter_map(0) { }
339
340    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
341      node_filter_map=&_node_filter_map;
342    }
343    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
344      edge_filter_map=&_edge_filter_map;
345    }
346
347  public:
348
349    typedef typename Parent::Node Node;
350    typedef typename Parent::Edge Edge;
351
352    void first(Node& i) const {
353      Parent::first(i);
354      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
355    }
356
357    void first(Edge& i) const {
358      Parent::first(i);
359      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
360    }
361
362    void firstIn(Edge& i, const Node& n) const {
363      Parent::firstIn(i, n);
364      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
365    }
366
367    void firstOut(Edge& i, const Node& n) const {
368      Parent::firstOut(i, n);
369      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
370    }
371
372    void next(Node& i) const {
373      Parent::next(i);
374      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
375    }
376    void next(Edge& i) const {
377      Parent::next(i);
378      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
379    }
380    void nextIn(Edge& i) const {
381      Parent::nextIn(i);
382      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
383    }
384
385    void nextOut(Edge& i) const {
386      Parent::nextOut(i);
387      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
388    }
389
390    /// This function hides \c n in the graph, i.e. the iteration
391    /// jumps over it. This is done by simply setting the value of \c n 
392    /// to be false in the corresponding node-map.
393    void hide(const Node& n) const { node_filter_map->set(n, false); }
394
395    /// This function hides \c e in the graph, i.e. the iteration
396    /// jumps over it. This is done by simply setting the value of \c e 
397    /// to be false in the corresponding edge-map.
398    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
399
400    /// The value of \c n is set to be true in the node-map which stores
401    /// hide information. If \c n was hidden previuosly, then it is shown
402    /// again
403     void unHide(const Node& n) const { node_filter_map->set(n, true); }
404
405    /// The value of \c e is set to be true in the edge-map which stores
406    /// hide information. If \c e was hidden previuosly, then it is shown
407    /// again
408    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
409
410    /// Returns true if \c n is hidden.
411    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
412
413    /// Returns true if \c n is hidden.
414    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
415
416    /// \warning This is a linear time operation and works only if s
417    /// \c Graph::NodeIt is defined.
418    /// \todo assign tags.
419    int nodeNum() const {
420      int i=0;
421      Node n;
422      for (first(n); n!=INVALID; next(n)) ++i;
423      return i;
424    }
425
426    /// \warning This is a linear time operation and works only if
427    /// \c Graph::EdgeIt is defined.
428    /// \todo assign tags.
429    int edgeNum() const {
430      int i=0;
431      Edge e;
432      for (first(e); e!=INVALID; next(e)) ++i;
433      return i;
434    }
435  };
436
437  /*! \brief A graph adaptor for hiding nodes and edges from a graph.
438   
439  \warning Graph adaptors are in even more experimental state than the other
440  parts of the lib. Use them at you own risk.
441 
442  SubGraphAdaptor shows the graph with filtered node-set and
443  edge-set.
444  Let \f$G=(V, A)\f$ be a directed graph
445  and suppose that the graph instance \c g of type ListGraph implements
446  \f$G\f$.
447  Let moreover \f$b_V\f$ and
448  \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
449  SubGraphAdaptor<...>::NodeIt iterates
450  on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
451  SubGraphAdaptor<...>::EdgeIt iterates
452  on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
453  SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
454  only on edges leaving and entering a specific node which have true value.
455
456  We have to note that this does not mean that an
457  induced subgraph is obtained, the node-iterator cares only the filter
458  on the node-set, and the edge-iterators care only the filter on the
459  edge-set.
460  \code
461  typedef ListGraph Graph;
462  Graph g;
463  typedef Graph::Node Node;
464  typedef Graph::Edge Edge;
465  Node u=g.addNode(); //node of id 0
466  Node v=g.addNode(); //node of id 1
467  Node e=g.addEdge(u, v); //edge of id 0
468  Node f=g.addEdge(v, u); //edge of id 1
469  Graph::NodeMap<bool> nm(g, true);
470  nm.set(u, false);
471  Graph::EdgeMap<bool> em(g, true);
472  em.set(e, false);
473  typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
474  SubGW gw(g, nm, em);
475  for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
476  std::cout << ":-)" << std::endl;
477  for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
478  \endcode
479  The output of the above code is the following.
480  \code
481  1
482  :-)
483  1
484  \endcode
485  Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
486  \c Graph::Node that is why \c g.id(n) can be applied.
487
488  For other examples see also the documentation of NodeSubGraphAdaptor and
489  EdgeSubGraphAdaptor.
490
491  \author Marton Makai
492  */
493  template<typename _Graph, typename NodeFilterMap,
494           typename EdgeFilterMap, bool checked = true>
495  class SubGraphAdaptor :
496    public IterableGraphExtender<
497    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
498  public:
499    typedef _Graph Graph;
500    typedef IterableGraphExtender<
501      SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
502  protected:
503    SubGraphAdaptor() { }
504  public:
505    SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
506                    EdgeFilterMap& _edge_filter_map) {
507      setGraph(_graph);
508      setNodeFilterMap(_node_filter_map);
509      setEdgeFilterMap(_edge_filter_map);
510    }
511  };
512
513
514
515  /*! \brief An adaptor for hiding nodes from a graph.
516
517  \warning Graph adaptors are in even more experimental state than the other
518  parts of the lib. Use them at you own risk.
519 
520  An adaptor for hiding nodes from a graph.
521  This adaptor specializes SubGraphAdaptor in the way that only the node-set
522  can be filtered. Note that this does not mean of considering induced
523  subgraph, the edge-iterators consider the original edge-set.
524  \author Marton Makai
525  */
526  template<typename Graph, typename NodeFilterMap, bool checked = true>
527  class NodeSubGraphAdaptor :
528    public SubGraphAdaptor<Graph, NodeFilterMap,
529                           ConstMap<typename Graph::Edge,bool>, checked> {
530  public:
531    typedef SubGraphAdaptor<Graph, NodeFilterMap,
532                            ConstMap<typename Graph::Edge,bool> > Parent;
533  protected:
534    ConstMap<typename Graph::Edge, bool> const_true_map;
535  public:
536    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
537      Parent(), const_true_map(true) {
538      Parent::setGraph(_graph);
539      Parent::setNodeFilterMap(_node_filter_map);
540      Parent::setEdgeFilterMap(const_true_map);
541    }
542  };
543
544
545  /*! \brief An adaptor for hiding edges from a graph.
546
547  \warning Graph adaptors are in even more experimental state than the other
548  parts of the lib. Use them at you own risk.
549 
550  An adaptor for hiding edges from a graph.
551  This adaptor specializes SubGraphAdaptor in the way that only the edge-set
552  can be filtered. The usefulness of this adaptor is demonstrated in the
553  problem of searching a maximum number of edge-disjoint shortest paths
554  between
555  two nodes \c s and \c t. Shortest here means being shortest w.r.t.
556  non-negative edge-lengths. Note that
557  the comprehension of the presented solution
558  need's some elementary knowledge from combinatorial optimization.
559
560  If a single shortest path is to be
561  searched between \c s and \c t, then this can be done easily by
562  applying the Dijkstra algorithm. What happens, if a maximum number of
563  edge-disjoint shortest paths is to be computed. It can be proved that an
564  edge can be in a shortest path if and only if it is tight with respect to
565  the potential function computed by Dijkstra. Moreover, any path containing
566  only such edges is a shortest one. Thus we have to compute a maximum number
567  of edge-disjoint paths between \c s and \c t in the graph which has edge-set
568  all the tight edges. The computation will be demonstrated on the following
569  graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
570  The full source code is available in \ref sub_graph_adaptor_demo.cc.
571  If you are interested in more demo programs, you can use
572  \ref dim_to_dot.cc to generate .dot files from dimacs files.
573  The .dot file of the following figure was generated by 
574  the demo program \ref dim_to_dot.cc.
575
576  \dot
577  digraph lemon_dot_example {
578  node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
579  n0 [ label="0 (s)" ];
580  n1 [ label="1" ];
581  n2 [ label="2" ];
582  n3 [ label="3" ];
583  n4 [ label="4" ];
584  n5 [ label="5" ];
585  n6 [ label="6 (t)" ];
586  edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
587  n5 ->  n6 [ label="9, length:4" ];
588  n4 ->  n6 [ label="8, length:2" ];
589  n3 ->  n5 [ label="7, length:1" ];
590  n2 ->  n5 [ label="6, length:3" ];
591  n2 ->  n6 [ label="5, length:5" ];
592  n2 ->  n4 [ label="4, length:2" ];
593  n1 ->  n4 [ label="3, length:3" ];
594  n0 ->  n3 [ label="2, length:1" ];
595  n0 ->  n2 [ label="1, length:2" ];
596  n0 ->  n1 [ label="0, length:3" ];
597  }
598  \enddot
599
600  \code
601  Graph g;
602  Node s, t;
603  LengthMap length(g);
604
605  readDimacs(std::cin, g, length, s, t);
606
607  cout << "edges with lengths (of form id, source--length->target): " << endl;
608  for(EdgeIt e(g); e!=INVALID; ++e)
609    cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
610         << length[e] << "->" << g.id(g.target(e)) << endl;
611
612  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
613  \endcode
614  Next, the potential function is computed with Dijkstra.
615  \code
616  typedef Dijkstra<Graph, LengthMap> Dijkstra;
617  Dijkstra dijkstra(g, length);
618  dijkstra.run(s);
619  \endcode
620  Next, we consrtruct a map which filters the edge-set to the tight edges.
621  \code
622  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
623    TightEdgeFilter;
624  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
625 
626  typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
627  SubGW gw(g, tight_edge_filter);
628  \endcode
629  Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
630  with a max flow algorithm Preflow.
631  \code
632  ConstMap<Edge, int> const_1_map(1);
633  Graph::EdgeMap<int> flow(g, 0);
634
635  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
636    preflow(gw, s, t, const_1_map, flow);
637  preflow.run();
638  \endcode
639  Last, the output is:
640  \code 
641  cout << "maximum number of edge-disjoint shortest path: "
642       << preflow.flowValue() << endl;
643  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
644       << endl;
645  for(EdgeIt e(g); e!=INVALID; ++e)
646    if (flow[e])
647      cout << " " << g.id(g.source(e)) << "--"
648           << length[e] << "->" << g.id(g.target(e)) << endl;
649  \endcode
650  The program has the following (expected :-)) output:
651  \code
652  edges with lengths (of form id, source--length->target):
653   9, 5--4->6
654   8, 4--2->6
655   7, 3--1->5
656   6, 2--3->5
657   5, 2--5->6
658   4, 2--2->4
659   3, 1--3->4
660   2, 0--1->3
661   1, 0--2->2
662   0, 0--3->1
663  s: 0 t: 6
664  maximum number of edge-disjoint shortest path: 2
665  edges of the maximum number of edge-disjoint shortest s-t paths:
666   9, 5--4->6
667   8, 4--2->6
668   7, 3--1->5
669   4, 2--2->4
670   2, 0--1->3
671   1, 0--2->2
672  \endcode
673
674  \author Marton Makai
675  */
676  template<typename Graph, typename EdgeFilterMap>
677  class EdgeSubGraphAdaptor :
678    public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
679                           EdgeFilterMap, false> {
680  public:
681    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
682                            EdgeFilterMap> Parent;
683  protected:
684    ConstMap<typename Graph::Node, bool> const_true_map;
685  public:
686    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
687      Parent(), const_true_map(true) {
688      Parent::setGraph(_graph);
689      Parent::setNodeFilterMap(const_true_map);
690      Parent::setEdgeFilterMap(_edge_filter_map);
691    }
692  };
693
694  template <typename _Graph>
695  class UndirGraphAdaptorBase :
696    public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
697  public:
698    typedef _Graph Graph;
699    typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
700  protected:
701    UndirGraphAdaptorBase() : Parent() { }
702  public:
703    typedef typename Parent::UndirEdge UndirEdge;
704    typedef typename Parent::Edge Edge;
705   
706    /// \bug Why cant an edge say that it is forward or not???
707    /// By this, a pointer to the graph have to be stored
708    /// The implementation
709    template <typename T>
710    class EdgeMap {
711    protected:
712      const UndirGraphAdaptorBase<_Graph>* g;
713      template <typename TT> friend class EdgeMap;
714      typename _Graph::template EdgeMap<T> forward_map, backward_map;
715    public:
716      typedef T Value;
717      typedef Edge Key;
718     
719      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
720        forward_map(*(g->graph)), backward_map(*(g->graph)) { }
721
722      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
723        forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
724     
725      void set(Edge e, T a) {
726        if (g->direction(e))
727          forward_map.set(e, a);
728        else
729          backward_map.set(e, a);
730      }
731
732      T operator[](Edge e) const {
733        if (g->direction(e))
734          return forward_map[e];
735        else
736          return backward_map[e];
737      }
738    };
739       
740    template <typename T>
741    class UndirEdgeMap {
742      template <typename TT> friend class UndirEdgeMap;
743      typename _Graph::template EdgeMap<T> map;
744    public:
745      typedef T Value;
746      typedef UndirEdge Key;
747     
748      UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
749        map(*(g.graph)) { }
750
751      UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
752        map(*(g.graph), a) { }
753     
754      void set(UndirEdge e, T a) {
755        map.set(e, a);
756      }
757
758      T operator[](UndirEdge e) const {
759        return map[e];
760      }
761    };
762     
763  };
764
765  /// \brief An undirected graph is made from a directed graph by an adaptor
766  ///
767  /// Undocumented, untested!!!
768  /// If somebody knows nice demo application, let's polulate it.
769  ///
770  /// \author Marton Makai
771  template<typename _Graph>
772  class UndirGraphAdaptor :
773    public IterableUndirGraphExtender<
774    UndirGraphAdaptorBase<_Graph> > {
775  public:
776    typedef _Graph Graph;
777    typedef IterableUndirGraphExtender<
778      UndirGraphAdaptorBase<_Graph> > Parent;
779  protected:
780    UndirGraphAdaptor() { }
781  public:
782    UndirGraphAdaptor(_Graph& _graph) {
783      setGraph(_graph);
784    }
785  };
786
787 
788  template <typename _Graph,
789            typename ForwardFilterMap, typename BackwardFilterMap>
790  class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
791  public:
792    typedef _Graph Graph;
793    typedef GraphAdaptorBase<_Graph> Parent;
794  protected:
795    ForwardFilterMap* forward_filter;
796    BackwardFilterMap* backward_filter;
797    SubBidirGraphAdaptorBase() : Parent(),
798                                 forward_filter(0), backward_filter(0) { }
799
800    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
801      forward_filter=&_forward_filter;
802    }
803    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
804      backward_filter=&_backward_filter;
805    }
806
807  public:
808//     SubGraphAdaptorBase(Graph& _graph,
809//                      NodeFilterMap& _node_filter_map,
810//                      EdgeFilterMap& _edge_filter_map) :
811//       Parent(&_graph),
812//       node_filter_map(&node_filter_map),
813//       edge_filter_map(&edge_filter_map) { }
814
815    typedef typename Parent::Node Node;
816    typedef typename _Graph::Edge GraphEdge;
817    template <typename T> class EdgeMap;
818    /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
819    /// _Graph::Edge. It contains an extra bool flag which is true
820    /// if and only if the
821    /// edge is the backward version of the original edge.
822    class Edge : public _Graph::Edge {
823      friend class SubBidirGraphAdaptorBase<
824        Graph, ForwardFilterMap, BackwardFilterMap>;
825      template<typename T> friend class EdgeMap;
826    protected:
827      bool backward; //true, iff backward
828    public:
829      Edge() { }
830      /// \todo =false is needed, or causes problems?
831      /// If \c _backward is false, then we get an edge corresponding to the
832      /// original one, otherwise its oppositely directed pair is obtained.
833      Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
834        _Graph::Edge(e), backward(_backward) { }
835      Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
836      bool operator==(const Edge& v) const {
837        return (this->backward==v.backward &&
838                static_cast<typename _Graph::Edge>(*this)==
839                static_cast<typename _Graph::Edge>(v));
840      }
841      bool operator!=(const Edge& v) const {
842        return (this->backward!=v.backward ||
843                static_cast<typename _Graph::Edge>(*this)!=
844                static_cast<typename _Graph::Edge>(v));
845      }
846    };
847
848    void first(Node& i) const {
849      Parent::first(i);
850    }
851
852    void first(Edge& i) const {
853      Parent::first(i);
854      i.backward=false;
855      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
856             !(*forward_filter)[i]) Parent::next(i);
857      if (*static_cast<GraphEdge*>(&i)==INVALID) {
858        Parent::first(i);
859        i.backward=true;
860        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
861               !(*backward_filter)[i]) Parent::next(i);
862      }
863    }
864
865    void firstIn(Edge& i, const Node& n) const {
866      Parent::firstIn(i, n);
867      i.backward=false;
868      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
869             !(*forward_filter)[i]) Parent::nextIn(i);
870      if (*static_cast<GraphEdge*>(&i)==INVALID) {
871        Parent::firstOut(i, n);
872        i.backward=true;
873        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
874               !(*backward_filter)[i]) Parent::nextOut(i);
875      }
876    }
877
878    void firstOut(Edge& i, const Node& n) const {
879      Parent::firstOut(i, n);
880      i.backward=false;
881      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
882             !(*forward_filter)[i]) Parent::nextOut(i);
883      if (*static_cast<GraphEdge*>(&i)==INVALID) {
884        Parent::firstIn(i, n);
885        i.backward=true;
886        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
887               !(*backward_filter)[i]) Parent::nextIn(i);
888      }
889    }
890
891    void next(Node& i) const {
892      Parent::next(i);
893    }
894
895    void next(Edge& i) const {
896      if (!(i.backward)) {
897        Parent::next(i);
898        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
899               !(*forward_filter)[i]) Parent::next(i);
900        if (*static_cast<GraphEdge*>(&i)==INVALID) {
901          Parent::first(i);
902          i.backward=true;
903          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
904                 !(*backward_filter)[i]) Parent::next(i);
905        }
906      } else {
907        Parent::next(i);
908        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
909               !(*backward_filter)[i]) Parent::next(i);
910      }
911    }
912
913    void nextIn(Edge& i) const {
914      if (!(i.backward)) {
915        Node n=Parent::target(i);
916        Parent::nextIn(i);
917        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
918               !(*forward_filter)[i]) Parent::nextIn(i);
919        if (*static_cast<GraphEdge*>(&i)==INVALID) {
920          Parent::firstOut(i, n);
921          i.backward=true;
922          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
923                 !(*backward_filter)[i]) Parent::nextOut(i);
924        }
925      } else {
926        Parent::nextOut(i);
927        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
928               !(*backward_filter)[i]) Parent::nextOut(i);
929      }
930    }
931
932    void nextOut(Edge& i) const {
933      if (!(i.backward)) {
934        Node n=Parent::source(i);
935        Parent::nextOut(i);
936        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
937               !(*forward_filter)[i]) Parent::nextOut(i);
938        if (*static_cast<GraphEdge*>(&i)==INVALID) {
939          Parent::firstIn(i, n);
940          i.backward=true;
941          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
942                 !(*backward_filter)[i]) Parent::nextIn(i);
943        }
944      } else {
945        Parent::nextIn(i);
946        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
947               !(*backward_filter)[i]) Parent::nextIn(i);
948      }
949    }
950
951    Node source(Edge e) const {
952      return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
953    Node target(Edge e) const {
954      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
955
956    /// Gives back the opposite edge.
957    Edge opposite(const Edge& e) const {
958      Edge f=e;
959      f.backward=!f.backward;
960      return f;
961    }
962
963    /// \warning This is a linear time operation and works only if
964    /// \c Graph::EdgeIt is defined.
965    /// \todo hmm
966    int edgeNum() const {
967      int i=0;
968      Edge e;
969      for (first(e); e!=INVALID; next(e)) ++i;
970      return i;
971    }
972
973    bool forward(const Edge& e) const { return !e.backward; }
974    bool backward(const Edge& e) const { return e.backward; }
975
976    template <typename T>
977    /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
978    /// _Graph::EdgeMap one for the forward edges and
979    /// one for the backward edges.
980    class EdgeMap {
981      template <typename TT> friend class EdgeMap;
982      typename _Graph::template EdgeMap<T> forward_map, backward_map;
983    public:
984      typedef T Value;
985      typedef Edge Key;
986
987      EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
988              ForwardFilterMap, BackwardFilterMap>& g) :
989        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
990
991      EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
992              ForwardFilterMap, BackwardFilterMap>& g, T a) :
993        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
994     
995      void set(Edge e, T a) {
996        if (!e.backward)
997          forward_map.set(e, a);
998        else
999          backward_map.set(e, a);
1000      }
1001
1002//       typename _Graph::template EdgeMap<T>::ConstReference
1003//       operator[](Edge e) const {
1004//      if (!e.backward)
1005//        return forward_map[e];
1006//      else
1007//        return backward_map[e];
1008//       }
1009
1010//      typename _Graph::template EdgeMap<T>::Reference
1011      T operator[](Edge e) const {
1012        if (!e.backward)
1013          return forward_map[e];
1014        else
1015          return backward_map[e];
1016      }
1017
1018      void update() {
1019        forward_map.update();
1020        backward_map.update();
1021      }
1022    };
1023
1024  };
1025
1026
1027  ///\brief An adaptor for composing a subgraph of a
1028  /// bidirected graph made from a directed one.
1029  ///
1030  /// An adaptor for composing a subgraph of a
1031  /// bidirected graph made from a directed one.
1032  ///
1033  ///\warning Graph adaptors are in even more experimental state than the other
1034  ///parts of the lib. Use them at you own risk.
1035  ///
1036  /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
1037  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
1038  /// reversing its orientation. We are given moreover two bool valued
1039  /// maps on the edge-set,
1040  /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
1041  /// SubBidirGraphAdaptor implements the graph structure with node-set
1042  /// \f$V\f$ and edge-set
1043  /// \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$.
1044  /// The purpose of writing + instead of union is because parallel
1045  /// edges can arise. (Similarly, antiparallel edges also can arise).
1046  /// In other words, a subgraph of the bidirected graph obtained, which
1047  /// is given by orienting the edges of the original graph in both directions.
1048  /// As the oppositely directed edges are logically different,
1049  /// the maps are able to attach different values for them.
1050  ///
1051  /// An example for such a construction is \c RevGraphAdaptor where the
1052  /// forward_filter is everywhere false and the backward_filter is
1053  /// everywhere true. We note that for sake of efficiency,
1054  /// \c RevGraphAdaptor is implemented in a different way.
1055  /// But BidirGraphAdaptor is obtained from
1056  /// SubBidirGraphAdaptor by considering everywhere true
1057  /// valued maps both for forward_filter and backward_filter.
1058  ///
1059  /// The most important application of SubBidirGraphAdaptor
1060  /// is ResGraphAdaptor, which stands for the residual graph in directed
1061  /// flow and circulation problems.
1062  /// As adaptors usually, the SubBidirGraphAdaptor implements the
1063  /// above mentioned graph structure without its physical storage,
1064  /// that is the whole stuff is stored in constant memory.
1065  template<typename _Graph,
1066           typename ForwardFilterMap, typename BackwardFilterMap>
1067  class SubBidirGraphAdaptor :
1068    public IterableGraphExtender<
1069    SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
1070  public:
1071    typedef _Graph Graph;
1072    typedef IterableGraphExtender<
1073      SubBidirGraphAdaptorBase<
1074      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
1075  protected:
1076    SubBidirGraphAdaptor() { }
1077  public:
1078    SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
1079                         BackwardFilterMap& _backward_filter) {
1080      setGraph(_graph);
1081      setForwardFilterMap(_forward_filter);
1082      setBackwardFilterMap(_backward_filter);
1083    }
1084  };
1085
1086
1087
1088  ///\brief An adaptor for composing bidirected graph from a directed one.
1089  ///
1090  ///\warning Graph adaptors are in even more experimental state than the other
1091  ///parts of the lib. Use them at you own risk.
1092  ///
1093  /// An adaptor for composing bidirected graph from a directed one.
1094  /// A bidirected graph is composed over the directed one without physical
1095  /// storage. As the oppositely directed edges are logically different ones
1096  /// the maps are able to attach different values for them.
1097  template<typename Graph>
1098  class BidirGraphAdaptor :
1099    public SubBidirGraphAdaptor<
1100    Graph,
1101    ConstMap<typename Graph::Edge, bool>,
1102    ConstMap<typename Graph::Edge, bool> > {
1103  public:
1104    typedef  SubBidirGraphAdaptor<
1105      Graph,
1106      ConstMap<typename Graph::Edge, bool>,
1107      ConstMap<typename Graph::Edge, bool> > Parent;
1108  protected:
1109    ConstMap<typename Graph::Edge, bool> cm;
1110
1111    BidirGraphAdaptor() : Parent(), cm(true) {
1112      Parent::setForwardFilterMap(cm);
1113      Parent::setBackwardFilterMap(cm);
1114    }
1115  public:
1116    BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
1117      Parent::setGraph(_graph);
1118      Parent::setForwardFilterMap(cm);
1119      Parent::setBackwardFilterMap(cm);
1120    }
1121
1122    int edgeNum() const {
1123      return 2*this->graph->edgeNum();
1124    }
1125    //    KEEP_MAPS(Parent, BidirGraphAdaptor);
1126  };
1127
1128
1129  template<typename Graph, typename Number,
1130           typename CapacityMap, typename FlowMap>
1131  class ResForwardFilter {
1132    //    const Graph* graph;
1133    const CapacityMap* capacity;
1134    const FlowMap* flow;
1135  public:
1136    ResForwardFilter(/*const Graph& _graph, */
1137                     const CapacityMap& _capacity, const FlowMap& _flow) :
1138      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1139    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1140    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1141    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1142    bool operator[](const typename Graph::Edge& e) const {
1143      return (Number((*flow)[e]) < Number((*capacity)[e]));
1144    }
1145  };
1146
1147  template<typename Graph, typename Number,
1148           typename CapacityMap, typename FlowMap>
1149  class ResBackwardFilter {
1150    const CapacityMap* capacity;
1151    const FlowMap* flow;
1152  public:
1153    ResBackwardFilter(/*const Graph& _graph,*/
1154                      const CapacityMap& _capacity, const FlowMap& _flow) :
1155      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1156    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1157    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1158    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1159    bool operator[](const typename Graph::Edge& e) const {
1160      return (Number(0) < Number((*flow)[e]));
1161    }
1162  };
1163
1164 
1165  /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
1166
1167  An adaptor for composing the residual graph for directed flow and circulation problems.
1168  Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
1169  number type. Let moreover
1170  \f$f,c:A\to F\f$, be functions on the edge-set.
1171  In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
1172  and \f$c\f$ for a capacity function.   
1173  Suppose that a graph instange \c g of type
1174  \c ListGraph implements \f$G\f$.
1175  \code
1176  ListGraph g;
1177  \endcode
1178  Then RevGraphAdaptor implements the graph structure with node-set
1179  \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
1180  \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
1181  \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
1182  i.e. the so called residual graph.
1183  When we take the union \f$A_{forward}\cup A_{backward}\f$,
1184  multilicities are counted, i.e. if an edge is in both
1185  \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
1186  appears twice.
1187  The following code shows how
1188  such an instance can be constructed.
1189  \code
1190  typedef ListGraph Graph;
1191  Graph::EdgeMap<int> f(g);
1192  Graph::EdgeMap<int> c(g);
1193  ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
1194  \endcode
1195  \author Marton Makai
1196  */
1197  template<typename Graph, typename Number,
1198           typename CapacityMap, typename FlowMap>
1199  class ResGraphAdaptor :
1200    public SubBidirGraphAdaptor<
1201    Graph,
1202    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1203    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1204  public:
1205    typedef SubBidirGraphAdaptor<
1206      Graph,
1207      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1208      ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1209  protected:
1210    const CapacityMap* capacity;
1211    FlowMap* flow;
1212    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1213    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1214    ResGraphAdaptor() : Parent(),
1215                        capacity(0), flow(0) { }
1216    void setCapacityMap(const CapacityMap& _capacity) {
1217      capacity=&_capacity;
1218      forward_filter.setCapacity(_capacity);
1219      backward_filter.setCapacity(_capacity);
1220    }
1221    void setFlowMap(FlowMap& _flow) {
1222      flow=&_flow;
1223      forward_filter.setFlow(_flow);
1224      backward_filter.setFlow(_flow);
1225    }
1226  public:
1227    ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
1228                       FlowMap& _flow) :
1229      Parent(), capacity(&_capacity), flow(&_flow),
1230      forward_filter(/*_graph,*/ _capacity, _flow),
1231      backward_filter(/*_graph,*/ _capacity, _flow) {
1232      Parent::setGraph(_graph);
1233      Parent::setForwardFilterMap(forward_filter);
1234      Parent::setBackwardFilterMap(backward_filter);
1235    }
1236
1237    typedef typename Parent::Edge Edge;
1238
1239    void augment(const Edge& e, Number a) const {
1240      if (Parent::forward(e)) 
1241        flow->set(e, (*flow)[e]+a);
1242      else 
1243        flow->set(e, (*flow)[e]-a);
1244    }
1245
1246    /// \brief Residual capacity map.
1247    ///
1248    /// In generic residual graphs the residual capacity can be obtained
1249    /// as a map.
1250    class ResCap {
1251    protected:
1252      const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
1253    public:
1254      typedef Number Value;
1255      typedef Edge Key;
1256      ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
1257             _res_graph) : res_graph(&_res_graph) { }
1258      Number operator[](const Edge& e) const {
1259        if (res_graph->forward(e))
1260          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1261        else
1262          return (*(res_graph->flow))[e];
1263      }
1264    };
1265
1266    //    KEEP_MAPS(Parent, ResGraphAdaptor);
1267  };
1268
1269
1270
1271  template <typename _Graph, typename FirstOutEdgesMap>
1272  class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1273  public:
1274    typedef _Graph Graph;
1275    typedef GraphAdaptorBase<_Graph> Parent;
1276  protected:
1277    FirstOutEdgesMap* first_out_edges;
1278    ErasingFirstGraphAdaptorBase() : Parent(),
1279                                     first_out_edges(0) { }
1280
1281    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1282      first_out_edges=&_first_out_edges;
1283    }
1284
1285  public:
1286
1287    typedef typename Parent::Node Node;
1288    typedef typename Parent::Edge Edge;
1289
1290    void firstOut(Edge& i, const Node& n) const {
1291      i=(*first_out_edges)[n];
1292    }
1293
1294    void erase(const Edge& e) const {
1295      Node n=source(e);
1296      Edge f=e;
1297      Parent::nextOut(f);
1298      first_out_edges->set(n, f);
1299    }   
1300  };
1301
1302
1303  /// For blocking flows.
1304
1305  ///\warning Graph adaptors are in even more experimental state than the other
1306  ///parts of the lib. Use them at you own risk.
1307  ///
1308  /// This graph adaptor is used for on-the-fly
1309  /// Dinits blocking flow computations.
1310  /// For each node, an out-edge is stored which is used when the
1311  /// \code
1312  /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1313  /// \endcode
1314  /// is called.
1315  ///
1316  /// \author Marton Makai
1317  template <typename _Graph, typename FirstOutEdgesMap>
1318  class ErasingFirstGraphAdaptor :
1319    public IterableGraphExtender<
1320    ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
1321  public:
1322    typedef _Graph Graph;
1323    typedef IterableGraphExtender<
1324      ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1325    ErasingFirstGraphAdaptor(Graph& _graph,
1326                             FirstOutEdgesMap& _first_out_edges) {
1327      setGraph(_graph);
1328      setFirstOutEdgesMap(_first_out_edges);
1329    }
1330
1331  };
1332
1333  template <typename _Graph>
1334  class NewEdgeSetAdaptorBase {
1335  public:
1336
1337    typedef _Graph Graph;
1338    typedef typename Graph::Node Node;
1339    typedef typename Graph::NodeIt NodeIt;
1340
1341  protected:
1342
1343    struct NodeT {
1344      int first_out, first_in;
1345      NodeT() : first_out(-1), first_in(-1) {}
1346    };
1347   
1348    class NodesImpl : protected Graph::template NodeMap<NodeT> {
1349
1350      typedef typename Graph::template NodeMap<NodeT> Parent;
1351      typedef NewEdgeSetAdaptorBase<Graph> Adaptor;
1352
1353      Adaptor& adaptor;
1354
1355    public:
1356
1357      NodesImpl(Adaptor& _adaptor, const Graph& _graph)
1358        : Parent(_graph), adaptor(_adaptor) {}
1359
1360      virtual ~NodesImpl() {}
1361
1362      virtual void build() {
1363        Parent::build();
1364      }
1365
1366      virtual void clear() {
1367        adaptor._clear();
1368        Parent::clear();
1369      }
1370     
1371      virtual void add(const Node& node) {
1372        Parent::add(node);
1373        adaptor._add(node);
1374      }
1375     
1376      virtual void erase(const Node& node) {
1377        adaptor._erase(node);
1378        Parent::erase(node);
1379      }
1380
1381      NodeT& operator[](const Node& node) {
1382        return Parent::operator[](node);
1383      }
1384
1385      const NodeT& operator[](const Node& node) const {
1386        return Parent::operator[](node);
1387      }
1388     
1389    };
1390
1391    NodesImpl* nodes;
1392
1393    struct EdgeT {
1394      Node source, target;
1395      int next_out, next_in;
1396      int prev_out, prev_in;
1397      EdgeT() : prev_out(-1), prev_in(-1) {}
1398    };
1399
1400    std::vector<EdgeT> edges;
1401
1402    int first_edge;
1403    int first_free_edge;
1404
1405    virtual void _clear() = 0;
1406    virtual void _add(const Node& node) = 0;
1407    virtual void _erase(const Node& node) = 0;
1408   
1409    const Graph* graph;
1410
1411    void initalize(const Graph& _graph, NodesImpl& _nodes) {
1412      graph = &_graph;
1413      nodes = &_nodes;
1414    }
1415   
1416  public:
1417
1418    class Edge {
1419      friend class NewEdgeSetAdaptorBase<Graph>;
1420    protected:
1421      Edge(int _id) : id(_id) {}
1422      int id;
1423    public:
1424      Edge() {}
1425      Edge(Invalid) : id(-1) {}
1426      bool operator==(const Edge& edge) const { return id == edge.id; }
1427      bool operator!=(const Edge& edge) const { return id != edge.id; }
1428      bool operator<(const Edge& edge) const { return id < edge.id; }
1429    };
1430
1431    NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {}
1432    virtual ~NewEdgeSetAdaptorBase() {}
1433
1434    Edge addEdge(const Node& source, const Node& target) {
1435      int n;
1436      if (first_free_edge == -1) {
1437        n = edges.size();
1438        edges.push_back(EdgeT());
1439      } else {
1440        n = first_free_edge;
1441        first_free_edge = edges[first_free_edge].next_in;
1442      }
1443      edges[n].next_in = (*nodes)[target].first_in;
1444      (*nodes)[target].first_in = n;
1445      edges[n].next_out = (*nodes)[source].first_out;
1446      (*nodes)[source].first_out = n;
1447      edges[n].source = source;
1448      edges[n].target = target;
1449      return Edge(n);
1450    }
1451
1452    void erase(const Edge& edge) {
1453      int n = edge.id;
1454      if (edges[n].prev_in != -1) {
1455        edges[edges[n].prev_in].next_in = edges[n].next_in;
1456      } else {
1457        (*nodes)[edges[n].target].first_in = edges[n].next_in;
1458      }
1459      if (edges[n].next_in != -1) {
1460        edges[edges[n].next_in].prev_in = edges[n].prev_in;
1461      }
1462
1463      if (edges[n].prev_out != -1) {
1464        edges[edges[n].prev_out].next_out = edges[n].next_out;
1465      } else {
1466        (*nodes)[edges[n].source].first_out = edges[n].next_out;
1467      }
1468      if (edges[n].next_out != -1) {
1469        edges[edges[n].next_out].prev_out = edges[n].prev_out;
1470      }
1471           
1472    }
1473
1474    void first(Node& node) const {
1475      graph->first(node);
1476    }
1477
1478    void next(Node& node) const {
1479      graph->next(node);
1480    }
1481
1482    void first(Edge& edge) const {
1483      Node node;
1484      for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
1485           next(node));
1486      edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1487    }
1488
1489    void next(Edge& edge) const {
1490      if (edges[edge.id].next_in != -1) {
1491        edge.id = edges[edge.id].next_in;
1492      } else {
1493        Node node = edges[edge.id].target;
1494        for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
1495             next(node));
1496        edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1497      }     
1498    }
1499
1500    void firstOut(Edge& edge, const Node& node) const {
1501      edge.id = (*nodes)[node].first_out;   
1502    }
1503   
1504    void nextOut(Edge& edge) const {
1505      edge.id = edges[edge.id].next_out;       
1506    }
1507
1508    void firstIn(Edge& edge, const Node& node) const {
1509      edge.id = (*nodes)[node].first_in;         
1510    }
1511
1512    void nextIn(Edge& edge) const {
1513      edge.id = edges[edge.id].next_in;   
1514    }
1515
1516    int id(const Node& node) const { return graph->id(node); }
1517    int id(const Edge& edge) const { return edge.id; }
1518
1519    Node fromId(int id, Node) const { return graph->fromId(id, Node()); }
1520    Edge fromId(int id, Edge) const { return Edge(id); }
1521
1522    int maxId(Node) const { return graph->maxId(Node()); };
1523    int maxId(Edge) const { return edges.size() - 1; }
1524
1525    Node source(const Edge& edge) const { return edges[edge.id].source;}
1526    Node target(const Edge& edge) const { return edges[edge.id].target;}
1527
1528  };
1529
1530
1531  /// \brief Graph adaptor using a node set of another graph and an
1532  /// own edge set.
1533  ///
1534  /// This structure can be used to establish another graph over a node set
1535  /// of an existing one. The node iterator will go through the nodes of the
1536  /// original graph.
1537  ///
1538  /// \param _Graph The type of the graph which shares its node set with
1539  /// this class. Its interface must conform to the \ref concept::StaticGraph
1540  /// "StaticGraph" concept.
1541  ///
1542  /// In the edge extension and removing it conforms to the
1543  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1544  template <typename _Graph>
1545  class NewEdgeSetAdaptor :
1546    public ErasableGraphExtender<
1547    ClearableGraphExtender<
1548    ExtendableGraphExtender<
1549    MappableGraphExtender<
1550    IterableGraphExtender<
1551    AlterableGraphExtender<
1552    NewEdgeSetAdaptorBase<_Graph> > > > > > > {
1553
1554  public:
1555
1556    typedef ErasableGraphExtender<
1557      ClearableGraphExtender<
1558      ExtendableGraphExtender<
1559      MappableGraphExtender<
1560      IterableGraphExtender<
1561      AlterableGraphExtender<
1562      NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent;
1563   
1564
1565    typedef typename Parent::Node Node;
1566    typedef typename Parent::Edge Edge;
1567
1568  private:
1569
1570    virtual void _clear() {
1571      Parent::edges.clear();
1572      Parent::first_edge = -1;
1573      Parent::first_free_edge = -1;
1574      Parent::getNotifier(Edge()).clear();
1575      Parent::getNotifier(Node()).clear();
1576    }
1577
1578    virtual void _add(const Node& node) {
1579      Parent::getNotifier(Node()).add(node);
1580    }
1581
1582    virtual void _erase(const Node& node) {
1583      Edge edge;
1584      Parent::firstOut(edge, node);
1585      while (edge != INVALID) {
1586        Parent::erase(edge);
1587        Parent::firstOut(edge, node);
1588      }
1589
1590      Parent::firstIn(edge, node);
1591      while (edge != INVALID) {
1592        Parent::erase(edge);
1593        Parent::firstIn(edge, node);
1594      }
1595     
1596      Parent::getNotifier(Node()).erase(node);
1597    }
1598
1599
1600    typedef typename Parent::NodesImpl NodesImpl;
1601
1602    NodesImpl nodes;
1603   
1604  public:
1605
1606    /// \brief Constructor of the adaptor.
1607    ///
1608    /// Constructor of the adaptor.
1609    NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
1610      Parent::initalize(_graph, nodes);
1611    }
1612
1613    void clear() {
1614      Parent::getNotifier(Edge()).clear();     
1615
1616      Parent::edges.clear();
1617      Parent::first_edge = -1;
1618      Parent::first_free_edge = -1;
1619    }
1620   
1621  };
1622
1623  /// \brief Graph adaptor using a node set of another graph and an
1624  /// own undir edge set.
1625  ///
1626  /// This structure can be used to establish another undirected graph over
1627  /// a node set of an existing one. The node iterator will go through the
1628  /// nodes of the original graph.
1629  ///
1630  /// \param _Graph The type of the graph which shares its node set with
1631  /// this class. Its interface must conform to the \ref concept::StaticGraph
1632  /// "StaticGraph" concept.
1633  ///
1634  /// In the edge extension and removing it conforms to the
1635  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1636  template <typename _Graph>
1637  class NewUndirEdgeSetAdaptor :
1638    public ErasableUndirGraphExtender<
1639    ClearableUndirGraphExtender<
1640    ExtendableUndirGraphExtender<
1641    MappableUndirGraphExtender<
1642    IterableUndirGraphExtender<
1643    AlterableUndirGraphExtender<
1644    UndirGraphExtender<
1645    NewEdgeSetAdaptorBase<_Graph> > > > > > > > {
1646
1647  public:
1648
1649    typedef ErasableUndirGraphExtender<
1650      ClearableUndirGraphExtender<
1651      ExtendableUndirGraphExtender<
1652      MappableUndirGraphExtender<
1653      IterableUndirGraphExtender<
1654      AlterableUndirGraphExtender<
1655      UndirGraphExtender<
1656      NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;
1657   
1658
1659    typedef typename Parent::Node Node;
1660    typedef typename Parent::Edge Edge;
1661    typedef typename Parent::UndirEdge UndirEdge;
1662
1663  private:
1664
1665    virtual void _clear() {
1666      Parent::edges.clear();
1667      Parent::first_edge = -1;
1668      Parent::first_free_edge = -1;
1669      Parent::getNotifier(Edge()).clear();
1670      Parent::getNotifier(Node()).clear();
1671    }
1672
1673    virtual void _add(const Node& node) {
1674      Parent::getNotifier(Node()).add(node);
1675    }
1676
1677    virtual void _erase(const Node& node) {
1678      Edge edge;
1679      Parent::firstOut(edge, node);
1680      while (edge != INVALID) {
1681        Parent::erase(edge);
1682        Parent::firstOut(edge, node);
1683      }
1684
1685      Parent::firstIn(edge, node);
1686      while (edge != INVALID) {
1687        Parent::erase(edge);
1688        Parent::firstIn(edge, node);
1689      }
1690     
1691      Parent::getNotifier(Node()).erase(node);
1692    }
1693
1694    typedef typename Parent::NodesImpl NodesImpl;
1695
1696    NodesImpl nodes;
1697   
1698  public:
1699
1700
1701    /// \brief Constructor of the adaptor.
1702    ///
1703    /// Constructor of the adaptor.
1704    NewUndirEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
1705      Parent::initalize(_graph, nodes);
1706    }
1707
1708    void clear() {
1709      Parent::getNotifier(Edge()).clear();     
1710      Parent::getNotifier(UndirEdge()).clear();     
1711
1712      Parent::edges.clear();
1713      Parent::first_edge = -1;
1714      Parent::first_free_edge = -1;
1715    }
1716   
1717  };
1718
1719  ///@}
1720
1721} //namespace lemon
1722
1723#endif //LEMON_GRAPH_ADAPTOR_H
1724
Note: See TracBrowser for help on using the repository browser.