COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 1738:470aa67893f5

Last change on this file since 1738:470aa67893f5 was 1725:22752dd6c693, checked in by Balazs Dezso, 18 years ago

Using proper return type

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