COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 1838:b61682f0ee96

Last change on this file since 1838:b61682f0ee96 was 1791:62e7d237e1fb, checked in by Balazs Dezso, 14 years ago

Modification on the base graph concept
The extended interface does not changed

File size: 61.8 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  template <typename _Graph>
1677  class NewEdgeSetAdaptorBase {
1678  public:
1679
1680    typedef _Graph Graph;
1681    typedef typename Graph::Node Node;
1682    typedef typename Graph::NodeIt NodeIt;
1683
1684  protected:
1685
1686    struct NodeT {
1687      int first_out, first_in;
1688      NodeT() : first_out(-1), first_in(-1) {}
1689    };
1690   
1691    class NodesImpl : protected Graph::template NodeMap<NodeT> {
1692
1693      typedef typename Graph::template NodeMap<NodeT> Parent;
1694      typedef NewEdgeSetAdaptorBase<Graph> Adaptor;
1695
1696      Adaptor& adaptor;
1697
1698    public:
1699
1700      NodesImpl(Adaptor& _adaptor, const Graph& _graph)
1701        : Parent(_graph), adaptor(_adaptor) {}
1702
1703      virtual ~NodesImpl() {}
1704
1705      virtual void build() {
1706        Parent::build();
1707      }
1708
1709      virtual void clear() {
1710        adaptor._clear();
1711        Parent::clear();
1712      }
1713     
1714      virtual void add(const Node& node) {
1715        Parent::add(node);
1716        adaptor._add(node);
1717      }
1718     
1719      virtual void erase(const Node& node) {
1720        adaptor._erase(node);
1721        Parent::erase(node);
1722      }
1723
1724      NodeT& operator[](const Node& node) {
1725        return Parent::operator[](node);
1726      }
1727
1728      const NodeT& operator[](const Node& node) const {
1729        return Parent::operator[](node);
1730      }
1731     
1732    };
1733
1734    NodesImpl* nodes;
1735
1736    struct EdgeT {
1737      Node source, target;
1738      int next_out, next_in;
1739      int prev_out, prev_in;
1740      EdgeT() : prev_out(-1), prev_in(-1) {}
1741    };
1742
1743    std::vector<EdgeT> edges;
1744
1745    int first_edge;
1746    int first_free_edge;
1747
1748    virtual void _clear() = 0;
1749    virtual void _add(const Node& node) = 0;
1750    virtual void _erase(const Node& node) = 0;
1751   
1752    const Graph* graph;
1753
1754    void initalize(const Graph& _graph, NodesImpl& _nodes) {
1755      graph = &_graph;
1756      nodes = &_nodes;
1757    }
1758   
1759  public:
1760
1761    class Edge {
1762      friend class NewEdgeSetAdaptorBase<Graph>;
1763    protected:
1764      Edge(int _id) : id(_id) {}
1765      int id;
1766    public:
1767      Edge() {}
1768      Edge(Invalid) : id(-1) {}
1769      bool operator==(const Edge& edge) const { return id == edge.id; }
1770      bool operator!=(const Edge& edge) const { return id != edge.id; }
1771      bool operator<(const Edge& edge) const { return id < edge.id; }
1772    };
1773
1774    NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {}
1775    virtual ~NewEdgeSetAdaptorBase() {}
1776
1777    Edge addEdge(const Node& source, const Node& target) {
1778      int n;
1779      if (first_free_edge == -1) {
1780        n = edges.size();
1781        edges.push_back(EdgeT());
1782      } else {
1783        n = first_free_edge;
1784        first_free_edge = edges[first_free_edge].next_in;
1785      }
1786      edges[n].next_in = (*nodes)[target].first_in;
1787      (*nodes)[target].first_in = n;
1788      edges[n].next_out = (*nodes)[source].first_out;
1789      (*nodes)[source].first_out = n;
1790      edges[n].source = source;
1791      edges[n].target = target;
1792      return Edge(n);
1793    }
1794
1795    void erase(const Edge& edge) {
1796      int n = edge.id;
1797      if (edges[n].prev_in != -1) {
1798        edges[edges[n].prev_in].next_in = edges[n].next_in;
1799      } else {
1800        (*nodes)[edges[n].target].first_in = edges[n].next_in;
1801      }
1802      if (edges[n].next_in != -1) {
1803        edges[edges[n].next_in].prev_in = edges[n].prev_in;
1804      }
1805
1806      if (edges[n].prev_out != -1) {
1807        edges[edges[n].prev_out].next_out = edges[n].next_out;
1808      } else {
1809        (*nodes)[edges[n].source].first_out = edges[n].next_out;
1810      }
1811      if (edges[n].next_out != -1) {
1812        edges[edges[n].next_out].prev_out = edges[n].prev_out;
1813      }
1814           
1815    }
1816
1817    void first(Node& node) const {
1818      graph->first(node);
1819    }
1820
1821    void next(Node& node) const {
1822      graph->next(node);
1823    }
1824
1825    void first(Edge& edge) const {
1826      Node node;
1827      for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
1828           next(node));
1829      edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1830    }
1831
1832    void next(Edge& edge) const {
1833      if (edges[edge.id].next_in != -1) {
1834        edge.id = edges[edge.id].next_in;
1835      } else {
1836        Node node = edges[edge.id].target;
1837        for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
1838             next(node));
1839        edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1840      }     
1841    }
1842
1843    void firstOut(Edge& edge, const Node& node) const {
1844      edge.id = (*nodes)[node].first_out;   
1845    }
1846   
1847    void nextOut(Edge& edge) const {
1848      edge.id = edges[edge.id].next_out;       
1849    }
1850
1851    void firstIn(Edge& edge, const Node& node) const {
1852      edge.id = (*nodes)[node].first_in;         
1853    }
1854
1855    void nextIn(Edge& edge) const {
1856      edge.id = edges[edge.id].next_in;   
1857    }
1858
1859    int id(const Node& node) const { return graph->id(node); }
1860    int id(const Edge& edge) const { return edge.id; }
1861
1862    Node nodeFromId(int id) const { return graph->fromId(id, Node()); }
1863    Edge edgeFromId(int id) const { return Edge(id); }
1864
1865    int maxNodeId() const { return graph->maxId(Node()); };
1866    int maxEdgeId() const { return edges.size() - 1; }
1867
1868    Node source(const Edge& edge) const { return edges[edge.id].source;}
1869    Node target(const Edge& edge) const { return edges[edge.id].target;}
1870
1871  };
1872
1873
1874  /// \brief Graph adaptor using a node set of another graph and an
1875  /// own edge set.
1876  ///
1877  /// This structure can be used to establish another graph over a node set
1878  /// of an existing one. The node iterator will go through the nodes of the
1879  /// original graph.
1880  ///
1881  /// \param _Graph The type of the graph which shares its node set with
1882  /// this class. Its interface must conform to the \ref concept::StaticGraph
1883  /// "StaticGraph" concept.
1884  ///
1885  /// In the edge extension and removing it conforms to the
1886  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1887  template <typename _Graph>
1888  class NewEdgeSetAdaptor :
1889    public ErasableGraphExtender<
1890    ClearableGraphExtender<
1891    ExtendableGraphExtender<
1892    MappableGraphExtender<
1893    IterableGraphExtender<
1894    AlterableGraphExtender<
1895    NewEdgeSetAdaptorBase<_Graph> > > > > > > {
1896
1897  public:
1898
1899    typedef ErasableGraphExtender<
1900      ClearableGraphExtender<
1901      ExtendableGraphExtender<
1902      MappableGraphExtender<
1903      IterableGraphExtender<
1904      AlterableGraphExtender<
1905      NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent;
1906   
1907
1908    typedef typename Parent::Node Node;
1909    typedef typename Parent::Edge Edge;
1910
1911  private:
1912
1913    virtual void _clear() {
1914      Parent::edges.clear();
1915      Parent::first_edge = -1;
1916      Parent::first_free_edge = -1;
1917      Parent::getNotifier(Edge()).clear();
1918      Parent::getNotifier(Node()).clear();
1919    }
1920
1921    virtual void _add(const Node& node) {
1922      Parent::getNotifier(Node()).add(node);
1923    }
1924
1925    virtual void _erase(const Node& node) {
1926      Edge edge;
1927      Parent::firstOut(edge, node);
1928      while (edge != INVALID) {
1929        Parent::erase(edge);
1930        Parent::firstOut(edge, node);
1931      }
1932
1933      Parent::firstIn(edge, node);
1934      while (edge != INVALID) {
1935        Parent::erase(edge);
1936        Parent::firstIn(edge, node);
1937      }
1938     
1939      Parent::getNotifier(Node()).erase(node);
1940    }
1941
1942
1943    typedef typename Parent::NodesImpl NodesImpl;
1944
1945    NodesImpl nodes;
1946   
1947  public:
1948
1949    /// \brief Constructor of the adaptor.
1950    ///
1951    /// Constructor of the adaptor.
1952    NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
1953      Parent::initalize(_graph, nodes);
1954    }
1955
1956    void clear() {
1957      Parent::getNotifier(Edge()).clear();     
1958
1959      Parent::edges.clear();
1960      Parent::first_edge = -1;
1961      Parent::first_free_edge = -1;
1962    }
1963   
1964  };
1965
1966  /// \brief Graph adaptor using a node set of another graph and an
1967  /// own undir edge set.
1968  ///
1969  /// This structure can be used to establish another undirected graph over
1970  /// a node set of an existing one. The node iterator will go through the
1971  /// nodes of the original graph.
1972  ///
1973  /// \param _Graph The type of the graph which shares its node set with
1974  /// this class. Its interface must conform to the \ref concept::StaticGraph
1975  /// "StaticGraph" concept.
1976  ///
1977  /// In the edge extension and removing it conforms to the
1978  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1979  template <typename _Graph>
1980  class NewUndirEdgeSetAdaptor :
1981    public ErasableUndirGraphExtender<
1982    ClearableUndirGraphExtender<
1983    ExtendableUndirGraphExtender<
1984    MappableUndirGraphExtender<
1985    IterableUndirGraphExtender<
1986    AlterableUndirGraphExtender<
1987    UndirGraphExtender<
1988    NewEdgeSetAdaptorBase<_Graph> > > > > > > > {
1989
1990  public:
1991
1992    typedef ErasableUndirGraphExtender<
1993      ClearableUndirGraphExtender<
1994      ExtendableUndirGraphExtender<
1995      MappableUndirGraphExtender<
1996      IterableUndirGraphExtender<
1997      AlterableUndirGraphExtender<
1998      UndirGraphExtender<
1999      NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;
2000   
2001
2002    typedef typename Parent::Node Node;
2003    typedef typename Parent::Edge Edge;
2004    typedef typename Parent::UndirEdge UndirEdge;
2005
2006  private:
2007
2008    virtual void _clear() {
2009      Parent::edges.clear();
2010      Parent::first_edge = -1;
2011      Parent::first_free_edge = -1;
2012      Parent::getNotifier(Edge()).clear();
2013      Parent::getNotifier(Node()).clear();
2014    }
2015
2016    virtual void _add(const Node& node) {
2017      Parent::getNotifier(Node()).add(node);
2018    }
2019
2020    virtual void _erase(const Node& node) {
2021      Edge edge;
2022      Parent::firstOut(edge, node);
2023      while (edge != INVALID) {
2024        Parent::erase(edge);
2025        Parent::firstOut(edge, node);
2026      }
2027
2028      Parent::firstIn(edge, node);
2029      while (edge != INVALID) {
2030        Parent::erase(edge);
2031        Parent::firstIn(edge, node);
2032      }
2033     
2034      Parent::getNotifier(Node()).erase(node);
2035    }
2036
2037    typedef typename Parent::NodesImpl NodesImpl;
2038
2039    NodesImpl nodes;
2040   
2041  public:
2042
2043
2044    /// \brief Constructor of the adaptor.
2045    ///
2046    /// Constructor of the adaptor.
2047    NewUndirEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
2048      Parent::initalize(_graph, nodes);
2049    }
2050
2051    void clear() {
2052      Parent::getNotifier(Edge()).clear();     
2053      Parent::getNotifier(UndirEdge()).clear();     
2054
2055      Parent::edges.clear();
2056      Parent::first_edge = -1;
2057      Parent::first_free_edge = -1;
2058    }
2059   
2060  };
2061
2062  ///@}
2063
2064} //namespace lemon
2065
2066#endif //LEMON_GRAPH_ADAPTOR_H
2067
Note: See TracBrowser for help on using the repository browser.