COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 1874:396831fa7012

Last change on this file since 1874:396831fa7012 was 1842:8abf74160dc4, checked in by Balazs Dezso, 14 years ago

NewEdgeSetAdaptor? -> ListEdgeSet?
and moved to edge_set.h

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