COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 2132:783b1d583be3

Last change on this file since 2132:783b1d583be3 was 2111:ea1fa1bc3f6d, checked in by Balazs Dezso, 18 years ago

Removing concepts for extendable and erasable graphs
Renaming StaticGraph? to Graph

File size: 78.6 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_GRAPH_ADAPTOR_H
20#define LEMON_GRAPH_ADAPTOR_H
21
22///\ingroup graph_adaptors
23///\file
24///\brief Several graph adaptors.
25///
26///This file contains several useful graph adaptor functions.
27///
28///\author Marton Makai and Balazs Dezso
29
30#include <lemon/bits/invalid.h>
31#include <lemon/maps.h>
32
33#include <lemon/bits/base_extender.h>
34#include <lemon/bits/graph_adaptor_extender.h>
35#include <lemon/bits/graph_extender.h>
36
37#include <lemon/tolerance.h>
38
39#include <algorithm>
40
41namespace lemon {
42
43  ///\brief Base type for the Graph Adaptors
44  ///
45  ///Base type for the Graph Adaptors
46  ///
47  ///This is the base type for most of LEMON graph adaptors.
48  ///This class implements a trivial graph adaptor i.e. it only wraps the
49  ///functions and types of the graph. The purpose of this class is to
50  ///make easier implementing graph adaptors. E.g. if an adaptor is
51  ///considered which differs from the wrapped graph only in some of its
52  ///functions or types, then it can be derived from GraphAdaptor,
53  ///and only the
54  ///differences should be implemented.
55  ///
56  ///author Marton Makai
57  template<typename _Graph>
58  class GraphAdaptorBase {
59  public:
60    typedef _Graph Graph;
61    typedef GraphAdaptorBase Adaptor;
62    typedef Graph ParentGraph;
63
64  protected:
65    Graph* graph;
66    GraphAdaptorBase() : graph(0) { }
67    void setGraph(Graph& _graph) { graph=&_graph; }
68
69  public:
70    GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
71
72    typedef typename Graph::Node Node;
73    typedef typename Graph::Edge Edge;
74   
75    void first(Node& i) const { graph->first(i); }
76    void first(Edge& i) const { graph->first(i); }
77    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
78    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
79
80    void next(Node& i) const { graph->next(i); }
81    void next(Edge& i) const { graph->next(i); }
82    void nextIn(Edge& i) const { graph->nextIn(i); }
83    void nextOut(Edge& i) const { graph->nextOut(i); }
84
85    Node source(const Edge& e) const { return graph->source(e); }
86    Node target(const Edge& e) const { return graph->target(e); }
87
88    typedef NodeNumTagIndicator<Graph> NodeNumTag;
89    int nodeNum() const { return graph->nodeNum(); }
90   
91    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
92    int edgeNum() const { return graph->edgeNum(); }
93
94    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
95    Edge findEdge(const Node& source, const Node& target,
96                  const Edge& prev = INVALID) {
97      return graph->findEdge(source, target, prev);
98    }
99 
100    Node addNode() const {
101      return Node(graph->addNode());
102    }
103
104    Edge addEdge(const Node& source, const Node& target) const {
105      return Edge(graph->addEdge(source, target));
106    }
107
108    void erase(const Node& i) const { graph->erase(i); }
109    void erase(const Edge& i) const { graph->erase(i); }
110 
111    void clear() const { graph->clear(); }
112   
113    int id(const Node& v) const { return graph->id(v); }
114    int id(const Edge& e) const { return graph->id(e); }
115
116    Node fromNodeId(int id) const {
117      return graph->fromNodeId(id);
118    }
119
120    Edge fromEdgeId(int id) const {
121      return graph->fromEdgeId(id);
122    }
123
124    int maxNodeId() const {
125      return graph->maxNodeId();
126    }
127
128    int maxEdgeId() const {
129      return graph->maxEdgeId();
130    }
131
132    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
133
134    NodeNotifier& getNotifier(Node) const {
135      return graph->getNotifier(Node());
136    }
137
138    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
139
140    EdgeNotifier& getNotifier(Edge) const {
141      return graph->getNotifier(Edge());
142    }
143   
144    template <typename _Value>
145    class NodeMap : public Graph::template NodeMap<_Value> {
146    public:
147
148      typedef typename Graph::template NodeMap<_Value> Parent;
149
150      explicit NodeMap(const Adaptor& ga)
151        : Parent(*ga.graph) {}
152
153      NodeMap(const Adaptor& ga, const _Value& value)
154        : Parent(*ga.graph, value) { }
155
156      NodeMap& operator=(const NodeMap& cmap) {
157        return operator=<NodeMap>(cmap);
158      }
159
160      template <typename CMap>
161      NodeMap& operator=(const CMap& cmap) {
162        Parent::operator=(cmap);
163        return *this;
164      }
165     
166    };
167
168    template <typename _Value>
169    class EdgeMap : public Graph::template EdgeMap<_Value> {
170    public:
171     
172      typedef typename Graph::template EdgeMap<_Value> Parent;
173     
174      explicit EdgeMap(const Adaptor& ga)
175        : Parent(*ga.graph) {}
176
177      EdgeMap(const Adaptor& ga, const _Value& value)
178        : Parent(*ga.graph, value) {}
179
180      EdgeMap& operator=(const EdgeMap& cmap) {
181        return operator=<EdgeMap>(cmap);
182      }
183
184      template <typename CMap>
185      EdgeMap& operator=(const CMap& cmap) {
186        Parent::operator=(cmap);
187        return *this;
188      }
189
190    };
191
192  };
193
194  ///\ingroup graph_adaptors
195  ///
196  ///\brief Trivial Graph Adaptor
197  ///
198  /// This class is an adaptor which does not change the adapted graph.
199  /// It can be used only to test the graph adaptors.
200  template <typename _Graph>
201  class GraphAdaptor :
202    public GraphAdaptorExtender<GraphAdaptorBase<_Graph> > {
203  public:
204    typedef _Graph Graph;
205    typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
206  protected:
207    GraphAdaptor() : Parent() { }
208
209  public:
210    explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }
211  };
212
213  /// \brief Just gives back a graph adaptor
214  ///
215  /// Just gives back a graph adaptor which
216  /// should be provide original graph
217  template<typename Graph>
218  GraphAdaptor<const Graph>
219  graphAdaptor(const Graph& graph) {
220    return GraphAdaptor<const Graph>(graph);
221  }
222
223
224  template <typename _Graph>
225  class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
226  public:
227    typedef _Graph Graph;
228    typedef GraphAdaptorBase<_Graph> Parent;
229  protected:
230    RevGraphAdaptorBase() : Parent() { }
231  public:
232    typedef typename Parent::Node Node;
233    typedef typename Parent::Edge Edge;
234
235    void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
236    void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
237
238    void nextIn(Edge& i) const { Parent::nextOut(i); }
239    void nextOut(Edge& i) const { Parent::nextIn(i); }
240
241    Node source(const Edge& e) const { return Parent::target(e); }
242    Node target(const Edge& e) const { return Parent::source(e); }
243
244    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
245    Edge findEdge(const Node& source, const Node& target,
246                  const Edge& prev = INVALID) {
247      return Parent::findEdge(target, source, prev);
248    }
249
250  };
251   
252
253  ///\ingroup graph_adaptors
254  ///
255  ///\brief A graph adaptor which reverses the orientation of the edges.
256  ///
257  /// If \c g is defined as
258  ///\code
259  /// ListGraph g;
260  ///\endcode
261  /// then
262  ///\code
263  /// RevGraphAdaptor<ListGraph> ga(g);
264  ///\endcode
265  /// implements the graph obtained from \c g by
266  /// reversing the orientation of its edges.
267  ///
268  /// A good example of using RevGraphAdaptor is to decide that the
269  /// directed graph is wheter strongly connected or not. If from one
270  /// node each node is reachable and from each node is reachable this
271  /// node then and just then the graph is strongly connected. Instead of
272  /// this condition we use a little bit different. From one node each node
273  /// ahould be reachable in the graph and in the reversed graph. Now this
274  /// condition can be checked with the Dfs algorithm class and the
275  /// RevGraphAdaptor algorithm class.
276  ///
277  /// And look at the code:
278  ///
279  ///\code
280  /// bool stronglyConnected(const Graph& graph) {
281  ///   if (NodeIt(graph) == INVALID) return true;
282  ///   Dfs<Graph> dfs(graph);
283  ///   dfs.run(NodeIt(graph));
284  ///   for (NodeIt it(graph); it != INVALID; ++it) {
285  ///     if (!dfs.reached(it)) {
286  ///       return false;
287  ///     }
288  ///   }
289  ///   typedef RevGraphAdaptor<const Graph> RGraph;
290  ///   RGraph rgraph(graph);
291  ///   DfsVisit<RGraph> rdfs(rgraph);
292  ///   rdfs.run(NodeIt(graph));
293  ///   for (NodeIt it(graph); it != INVALID; ++it) {
294  ///     if (!rdfs.reached(it)) {
295  ///       return false;
296  ///     }
297  ///   }
298  ///   return true;
299  /// }
300  ///\endcode
301  template<typename _Graph>
302  class RevGraphAdaptor :
303    public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > {
304  public:
305    typedef _Graph Graph;
306    typedef GraphAdaptorExtender<
307      RevGraphAdaptorBase<_Graph> > Parent;
308  protected:
309    RevGraphAdaptor() { }
310  public:
311    explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
312  };
313
314  /// \brief Just gives back a reverse graph adaptor
315  ///
316  /// Just gives back a reverse graph adaptor
317  template<typename Graph>
318  RevGraphAdaptor<const Graph>
319  revGraphAdaptor(const Graph& graph) {
320    return RevGraphAdaptor<const Graph>(graph);
321  }
322
323  template <typename _Graph, typename NodeFilterMap,
324            typename EdgeFilterMap, bool checked = true>
325  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
326  public:
327    typedef _Graph Graph;
328    typedef SubGraphAdaptorBase Adaptor;
329    typedef GraphAdaptorBase<_Graph> Parent;
330  protected:
331    NodeFilterMap* node_filter_map;
332    EdgeFilterMap* edge_filter_map;
333    SubGraphAdaptorBase() : Parent(),
334                            node_filter_map(0), edge_filter_map(0) { }
335
336    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
337      node_filter_map=&_node_filter_map;
338    }
339    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
340      edge_filter_map=&_edge_filter_map;
341    }
342
343  public:
344
345    typedef typename Parent::Node Node;
346    typedef typename Parent::Edge Edge;
347
348    void first(Node& i) const {
349      Parent::first(i);
350      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
351    }
352
353    void first(Edge& i) const {
354      Parent::first(i);
355      while (i!=INVALID && (!(*edge_filter_map)[i]
356             || !(*node_filter_map)[Parent::source(i)]
357             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
358    }
359
360    void firstIn(Edge& i, const Node& n) const {
361      Parent::firstIn(i, n);
362      while (i!=INVALID && (!(*edge_filter_map)[i]
363             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
364    }
365
366    void firstOut(Edge& i, const Node& n) const {
367      Parent::firstOut(i, n);
368      while (i!=INVALID && (!(*edge_filter_map)[i]
369             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
370    }
371
372    void next(Node& i) const {
373      Parent::next(i);
374      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
375    }
376
377    void next(Edge& i) const {
378      Parent::next(i);
379      while (i!=INVALID && (!(*edge_filter_map)[i]
380             || !(*node_filter_map)[Parent::source(i)]
381             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
382    }
383
384    void nextIn(Edge& i) const {
385      Parent::nextIn(i);
386      while (i!=INVALID && (!(*edge_filter_map)[i]
387             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
388    }
389
390    void nextOut(Edge& i) const {
391      Parent::nextOut(i);
392      while (i!=INVALID && (!(*edge_filter_map)[i]
393             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
394    }
395
396    ///\e
397
398    /// This function hides \c n in the graph, i.e. the iteration
399    /// jumps over it. This is done by simply setting the value of \c n 
400    /// to be false in the corresponding node-map.
401    void hide(const Node& n) const { node_filter_map->set(n, false); }
402
403    ///\e
404
405    /// This function hides \c e in the graph, i.e. the iteration
406    /// jumps over it. This is done by simply setting the value of \c e 
407    /// to be false in the corresponding edge-map.
408    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
409
410    ///\e
411
412    /// The value of \c n is set to be true in the node-map which stores
413    /// hide information. If \c n was hidden previuosly, then it is shown
414    /// again
415     void unHide(const Node& n) const { node_filter_map->set(n, true); }
416
417    ///\e
418
419    /// The value of \c e is set to be true in the edge-map which stores
420    /// hide information. If \c e was hidden previuosly, then it is shown
421    /// again
422    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
423
424    /// Returns true if \c n is hidden.
425   
426    ///\e
427    ///
428    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
429
430    /// Returns true if \c n is hidden.
431   
432    ///\e
433    ///
434    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
435
436    typedef False NodeNumTag;
437    typedef False EdgeNumTag;
438
439    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
440    Edge findEdge(const Node& source, const Node& target,
441                  const Edge& prev = INVALID) {
442      if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
443        return INVALID;
444      }
445      Edge edge = Parent::findEdge(source, target, prev);
446      while (edge != INVALID && !(*edge_filter_map)[edge]) {
447        edge = Parent::findEdge(source, target, edge);
448      }
449      return edge;
450    }
451
452    template <typename _Value>
453    class NodeMap
454      : public SubMapExtender<Adaptor,
455                              typename Parent::template NodeMap<_Value> >
456    {
457    public:
458      typedef Adaptor Graph;
459      typedef SubMapExtender<Adaptor, typename Parent::
460                             template NodeMap<_Value> > Parent;
461   
462      NodeMap(const Graph& graph)
463        : Parent(graph) {}
464      NodeMap(const Graph& graph, const _Value& value)
465        : Parent(graph, value) {}
466   
467      NodeMap& operator=(const NodeMap& cmap) {
468        return operator=<NodeMap>(cmap);
469      }
470   
471      template <typename CMap>
472      NodeMap& operator=(const CMap& cmap) {
473        Parent::operator=(cmap);
474        return *this;
475      }
476    };
477
478    template <typename _Value>
479    class EdgeMap
480      : public SubMapExtender<Adaptor,
481                              typename Parent::template EdgeMap<_Value> >
482    {
483    public:
484      typedef Adaptor Graph;
485      typedef SubMapExtender<Adaptor, typename Parent::
486                             template EdgeMap<_Value> > Parent;
487   
488      EdgeMap(const Graph& graph)
489        : Parent(graph) {}
490      EdgeMap(const Graph& graph, const _Value& value)
491        : Parent(graph, value) {}
492   
493      EdgeMap& operator=(const EdgeMap& cmap) {
494        return operator=<EdgeMap>(cmap);
495      }
496   
497      template <typename CMap>
498      EdgeMap& operator=(const CMap& cmap) {
499        Parent::operator=(cmap);
500        return *this;
501      }
502    };
503
504  };
505
506  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
507  class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
508    : public GraphAdaptorBase<_Graph> {
509  public:
510    typedef _Graph Graph;
511    typedef SubGraphAdaptorBase Adaptor;
512    typedef GraphAdaptorBase<_Graph> Parent;
513  protected:
514    NodeFilterMap* node_filter_map;
515    EdgeFilterMap* edge_filter_map;
516    SubGraphAdaptorBase() : Parent(),
517                            node_filter_map(0), edge_filter_map(0) { }
518
519    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
520      node_filter_map=&_node_filter_map;
521    }
522    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
523      edge_filter_map=&_edge_filter_map;
524    }
525
526  public:
527
528    typedef typename Parent::Node Node;
529    typedef typename Parent::Edge Edge;
530
531    void first(Node& i) const {
532      Parent::first(i);
533      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
534    }
535
536    void first(Edge& i) const {
537      Parent::first(i);
538      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
539    }
540
541    void firstIn(Edge& i, const Node& n) const {
542      Parent::firstIn(i, n);
543      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
544    }
545
546    void firstOut(Edge& i, const Node& n) const {
547      Parent::firstOut(i, n);
548      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
549    }
550
551    void next(Node& i) const {
552      Parent::next(i);
553      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
554    }
555    void next(Edge& i) const {
556      Parent::next(i);
557      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
558    }
559    void nextIn(Edge& i) const {
560      Parent::nextIn(i);
561      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
562    }
563
564    void nextOut(Edge& i) const {
565      Parent::nextOut(i);
566      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
567    }
568
569    ///\e
570
571    /// This function hides \c n in the graph, i.e. the iteration
572    /// jumps over it. This is done by simply setting the value of \c n 
573    /// to be false in the corresponding node-map.
574    void hide(const Node& n) const { node_filter_map->set(n, false); }
575
576    ///\e
577
578    /// This function hides \c e in the graph, i.e. the iteration
579    /// jumps over it. This is done by simply setting the value of \c e 
580    /// to be false in the corresponding edge-map.
581    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
582
583    ///\e
584
585    /// The value of \c n is set to be true in the node-map which stores
586    /// hide information. If \c n was hidden previuosly, then it is shown
587    /// again
588     void unHide(const Node& n) const { node_filter_map->set(n, true); }
589
590    ///\e
591
592    /// The value of \c e is set to be true in the edge-map which stores
593    /// hide information. If \c e was hidden previuosly, then it is shown
594    /// again
595    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
596
597    /// Returns true if \c n is hidden.
598   
599    ///\e
600    ///
601    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
602
603    /// Returns true if \c n is hidden.
604   
605    ///\e
606    ///
607    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
608
609    typedef False NodeNumTag;
610    typedef False EdgeNumTag;
611
612    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
613    Edge findEdge(const Node& source, const Node& target,
614                  const Edge& prev = INVALID) {
615      if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
616        return INVALID;
617      }
618      Edge edge = Parent::findEdge(source, target, prev);
619      while (edge != INVALID && !(*edge_filter_map)[edge]) {
620        edge = Parent::findEdge(source, target, edge);
621      }
622      return edge;
623    }
624
625    template <typename _Value>
626    class NodeMap
627      : public SubMapExtender<Adaptor,
628                              typename Parent::template NodeMap<_Value> >
629    {
630    public:
631      typedef Adaptor Graph;
632      typedef SubMapExtender<Adaptor, typename Parent::
633                             template NodeMap<_Value> > Parent;
634   
635      NodeMap(const Graph& graph)
636        : Parent(graph) {}
637      NodeMap(const Graph& graph, const _Value& value)
638        : Parent(graph, value) {}
639   
640      NodeMap& operator=(const NodeMap& cmap) {
641        return operator=<NodeMap>(cmap);
642      }
643   
644      template <typename CMap>
645      NodeMap& operator=(const CMap& cmap) {
646        Parent::operator=(cmap);
647        return *this;
648      }
649    };
650
651    template <typename _Value>
652    class EdgeMap
653      : public SubMapExtender<Adaptor,
654                              typename Parent::template EdgeMap<_Value> >
655    {
656    public:
657      typedef Adaptor Graph;
658      typedef SubMapExtender<Adaptor, typename Parent::
659                             template EdgeMap<_Value> > Parent;
660   
661      EdgeMap(const Graph& graph)
662        : Parent(graph) {}
663      EdgeMap(const Graph& graph, const _Value& value)
664        : Parent(graph, value) {}
665   
666      EdgeMap& operator=(const EdgeMap& cmap) {
667        return operator=<EdgeMap>(cmap);
668      }
669   
670      template <typename CMap>
671      EdgeMap& operator=(const CMap& cmap) {
672        Parent::operator=(cmap);
673        return *this;
674      }
675    };
676
677  };
678
679  /// \ingroup graph_adaptors
680  ///
681  /// \brief A graph adaptor for hiding nodes and edges from a graph.
682  ///
683  /// SubGraphAdaptor shows the graph with filtered node-set and
684  /// edge-set. If the \c checked parameter is true then it filters the edgeset
685  /// to do not get invalid edges without source or target.
686  /// Let \f$ G=(V, A) \f$ be a directed graph
687  /// and suppose that the graph instance \c g of type ListGraph
688  /// implements \f$ G \f$.
689  /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
690  /// on the node-set and edge-set.
691  /// SubGraphAdaptor<...>::NodeIt iterates
692  /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
693  /// SubGraphAdaptor<...>::EdgeIt iterates
694  /// on the edge-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly,
695  /// SubGraphAdaptor<...>::OutEdgeIt and
696  /// SubGraphAdaptor<...>::InEdgeIt iterates
697  /// only on edges leaving and entering a specific node which have true value.
698  ///
699  /// If the \c checked template parameter is false then we have to note that
700  /// the node-iterator cares only the filter on the node-set, and the
701  /// edge-iterator cares only the filter on the edge-set.
702  /// This way the edge-map
703  /// should filter all edges which's source or target is filtered by the
704  /// node-filter.
705  ///\code
706  /// typedef ListGraph Graph;
707  /// Graph g;
708  /// typedef Graph::Node Node;
709  /// typedef Graph::Edge Edge;
710  /// Node u=g.addNode(); //node of id 0
711  /// Node v=g.addNode(); //node of id 1
712  /// Node e=g.addEdge(u, v); //edge of id 0
713  /// Node f=g.addEdge(v, u); //edge of id 1
714  /// Graph::NodeMap<bool> nm(g, true);
715  /// nm.set(u, false);
716  /// Graph::EdgeMap<bool> em(g, true);
717  /// em.set(e, false);
718  /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGA;
719  /// SubGA ga(g, nm, em);
720  /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
721  /// std::cout << ":-)" << std::endl;
722  /// for (SubGA::EdgeIt e(ga); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
723  ///\endcode
724  /// The output of the above code is the following.
725  ///\code
726  /// 1
727  /// :-)
728  /// 1
729  ///\endcode
730  /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
731  /// \c Graph::Node that is why \c g.id(n) can be applied.
732  ///
733  /// For other examples see also the documentation of NodeSubGraphAdaptor and
734  /// EdgeSubGraphAdaptor.
735  ///
736  /// \author Marton Makai
737
738  template<typename _Graph, typename NodeFilterMap,
739           typename EdgeFilterMap, bool checked = true>
740  class SubGraphAdaptor :
741    public GraphAdaptorExtender<
742    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
743  public:
744    typedef _Graph Graph;
745    typedef GraphAdaptorExtender< SubGraphAdaptorBase<_Graph, NodeFilterMap,
746                                                      EdgeFilterMap, checked> >
747    Parent;
748
749  protected:
750    SubGraphAdaptor() { }
751  public:
752
753    SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
754                    EdgeFilterMap& _edge_filter_map) {
755      setGraph(_graph);
756      setNodeFilterMap(_node_filter_map);
757      setEdgeFilterMap(_edge_filter_map);
758    }
759
760  };
761
762  /// \brief Just gives back a sub graph adaptor
763  ///
764  /// Just gives back a sub graph adaptor
765  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
766  SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
767  subGraphAdaptor(const Graph& graph,
768                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
769    return SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
770      (graph, nfm, efm);
771  }
772
773  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
774  SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
775  subGraphAdaptor(const Graph& graph,
776                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
777    return SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
778      (graph, nfm, efm);
779  }
780
781  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
782  SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
783  subGraphAdaptor(const Graph& graph,
784                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
785    return SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
786      (graph, nfm, efm);
787  }
788
789  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
790  SubGraphAdaptor<const Graph, const NodeFilterMap, const EdgeFilterMap>
791  subGraphAdaptor(const Graph& graph,
792                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
793    return SubGraphAdaptor<const Graph, const NodeFilterMap,
794      const EdgeFilterMap>(graph, nfm, efm);
795  }
796
797
798
799  ///\ingroup graph_adaptors
800  ///
801  ///\brief An adaptor for hiding nodes from a graph.
802  ///
803  ///An adaptor for hiding nodes from a graph.
804  ///This adaptor specializes SubGraphAdaptor in the way that only
805  ///the node-set
806  ///can be filtered. In usual case the checked parameter is true, we get the
807  ///induced subgraph. But if the checked parameter is false then we can only
808  ///filter only isolated nodes.
809  ///\author Marton Makai
810  template<typename Graph, typename NodeFilterMap, bool checked = true>
811  class NodeSubGraphAdaptor :
812    public SubGraphAdaptor<Graph, NodeFilterMap,
813                           ConstMap<typename Graph::Edge,bool>, checked> {
814  public:
815
816    typedef SubGraphAdaptor<Graph, NodeFilterMap,
817                            ConstMap<typename Graph::Edge,bool>, checked >
818    Parent;
819
820  protected:
821    ConstMap<typename Graph::Edge, bool> const_true_map;
822
823    NodeSubGraphAdaptor() : const_true_map(true) {
824      Parent::setEdgeFilterMap(const_true_map);
825    }
826
827  public:
828
829    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
830      Parent(), const_true_map(true) {
831      Parent::setGraph(_graph);
832      Parent::setNodeFilterMap(_node_filter_map);
833      Parent::setEdgeFilterMap(const_true_map);
834    }
835
836  };
837
838
839  /// \brief Just gives back a node sub graph adaptor
840  ///
841  /// Just gives back a node sub graph adaptor
842  template<typename Graph, typename NodeFilterMap>
843  NodeSubGraphAdaptor<const Graph, NodeFilterMap>
844  nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
845    return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
846  }
847
848  template<typename Graph, typename NodeFilterMap>
849  NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
850  nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
851    return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
852  }
853
854  ///\ingroup graph_adaptors
855  ///
856  ///\brief An adaptor for hiding edges from a graph.
857  ///
858  ///An adaptor for hiding edges from a graph.
859  ///This adaptor specializes SubGraphAdaptor in the way that
860  ///only the edge-set
861  ///can be filtered. The usefulness of this adaptor is demonstrated in the
862  ///problem of searching a maximum number of edge-disjoint shortest paths
863  ///between
864  ///two nodes \c s and \c t. Shortest here means being shortest w.r.t.
865  ///non-negative edge-lengths. Note that
866  ///the comprehension of the presented solution
867  ///need's some elementary knowledge from combinatorial optimization.
868  ///
869  ///If a single shortest path is to be
870  ///searched between \c s and \c t, then this can be done easily by
871  ///applying the Dijkstra algorithm. What happens, if a maximum number of
872  ///edge-disjoint shortest paths is to be computed. It can be proved that an
873  ///edge can be in a shortest path if and only
874  ///if it is tight with respect to
875  ///the potential function computed by Dijkstra.
876  ///Moreover, any path containing
877  ///only such edges is a shortest one.
878  ///Thus we have to compute a maximum number
879  ///of edge-disjoint paths between \c s and \c t in
880  ///the graph which has edge-set
881  ///all the tight edges. The computation will be demonstrated
882  ///on the following
883  ///graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
884  ///The full source code is available in \ref sub_graph_adaptor_demo.cc.
885  ///If you are interested in more demo programs, you can use
886  ///\ref dim_to_dot.cc to generate .dot files from dimacs files.
887  ///The .dot file of the following figure was generated by 
888  ///the demo program \ref dim_to_dot.cc.
889  ///
890  ///\dot
891  ///digraph lemon_dot_example {
892  ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
893  ///n0 [ label="0 (s)" ];
894  ///n1 [ label="1" ];
895  ///n2 [ label="2" ];
896  ///n3 [ label="3" ];
897  ///n4 [ label="4" ];
898  ///n5 [ label="5" ];
899  ///n6 [ label="6 (t)" ];
900  ///edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
901  ///n5 ->  n6 [ label="9, length:4" ];
902  ///n4 ->  n6 [ label="8, length:2" ];
903  ///n3 ->  n5 [ label="7, length:1" ];
904  ///n2 ->  n5 [ label="6, length:3" ];
905  ///n2 ->  n6 [ label="5, length:5" ];
906  ///n2 ->  n4 [ label="4, length:2" ];
907  ///n1 ->  n4 [ label="3, length:3" ];
908  ///n0 ->  n3 [ label="2, length:1" ];
909  ///n0 ->  n2 [ label="1, length:2" ];
910  ///n0 ->  n1 [ label="0, length:3" ];
911  ///}
912  ///\enddot
913  ///
914  ///\code
915  ///Graph g;
916  ///Node s, t;
917  ///LengthMap length(g);
918  ///
919  ///readDimacs(std::cin, g, length, s, t);
920  ///
921  ///cout << "edges with lengths (of form id, source--length->target): " << endl;
922  ///for(EdgeIt e(g); e!=INVALID; ++e)
923  ///  cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
924  ///       << length[e] << "->" << g.id(g.target(e)) << endl;
925  ///
926  ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
927  ///\endcode
928  ///Next, the potential function is computed with Dijkstra.
929  ///\code
930  ///typedef Dijkstra<Graph, LengthMap> Dijkstra;
931  ///Dijkstra dijkstra(g, length);
932  ///dijkstra.run(s);
933  ///\endcode
934  ///Next, we consrtruct a map which filters the edge-set to the tight edges.
935  ///\code
936  ///typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
937  ///  TightEdgeFilter;
938  ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
939  ///
940  ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGA;
941  ///SubGA ga(g, tight_edge_filter);
942  ///\endcode
943  ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
944  ///with a max flow algorithm Preflow.
945  ///\code
946  ///ConstMap<Edge, int> const_1_map(1);
947  ///Graph::EdgeMap<int> flow(g, 0);
948  ///
949  ///Preflow<SubGA, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
950  ///  preflow(ga, s, t, const_1_map, flow);
951  ///preflow.run();
952  ///\endcode
953  ///Last, the output is:
954  ///\code 
955  ///cout << "maximum number of edge-disjoint shortest path: "
956  ///     << preflow.flowValue() << endl;
957  ///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
958  ///     << endl;
959  ///for(EdgeIt e(g); e!=INVALID; ++e)
960  ///  if (flow[e])
961  ///    cout << " " << g.id(g.source(e)) << "--"
962  ///         << length[e] << "->" << g.id(g.target(e)) << endl;
963  ///\endcode
964  ///The program has the following (expected :-)) output:
965  ///\code
966  ///edges with lengths (of form id, source--length->target):
967  /// 9, 5--4->6
968  /// 8, 4--2->6
969  /// 7, 3--1->5
970  /// 6, 2--3->5
971  /// 5, 2--5->6
972  /// 4, 2--2->4
973  /// 3, 1--3->4
974  /// 2, 0--1->3
975  /// 1, 0--2->2
976  /// 0, 0--3->1
977  ///s: 0 t: 6
978  ///maximum number of edge-disjoint shortest path: 2
979  ///edges of the maximum number of edge-disjoint shortest s-t paths:
980  /// 9, 5--4->6
981  /// 8, 4--2->6
982  /// 7, 3--1->5
983  /// 4, 2--2->4
984  /// 2, 0--1->3
985  /// 1, 0--2->2
986  ///\endcode
987  ///
988  ///\author Marton Makai
989  template<typename Graph, typename EdgeFilterMap>
990  class EdgeSubGraphAdaptor :
991    public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
992                           EdgeFilterMap, false> {
993  public:
994    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
995                            EdgeFilterMap, false> Parent;
996  protected:
997    ConstMap<typename Graph::Node, bool> const_true_map;
998
999    EdgeSubGraphAdaptor() : const_true_map(true) {
1000      Parent::setNodeFilterMap(const_true_map);
1001    }
1002
1003  public:
1004
1005    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
1006      Parent(), const_true_map(true) {
1007      Parent::setGraph(_graph);
1008      Parent::setNodeFilterMap(const_true_map);
1009      Parent::setEdgeFilterMap(_edge_filter_map);
1010    }
1011
1012  };
1013
1014  /// \brief Just gives back an edge sub graph adaptor
1015  ///
1016  /// Just gives back an edge sub graph adaptor
1017  template<typename Graph, typename EdgeFilterMap>
1018  EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
1019  edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
1020    return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
1021  }
1022
1023  template<typename Graph, typename EdgeFilterMap>
1024  EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
1025  edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
1026    return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
1027  }
1028
1029  template <typename _Graph>
1030  class UndirGraphAdaptorBase :
1031    public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
1032  public:
1033    typedef _Graph Graph;
1034    typedef UndirGraphAdaptorBase Adaptor;
1035    typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
1036
1037  protected:
1038
1039    UndirGraphAdaptorBase() : Parent() {}
1040
1041  public:
1042
1043    typedef typename Parent::UEdge UEdge;
1044    typedef typename Parent::Edge Edge;
1045
1046  private:
1047   
1048    template <typename _Value>
1049    class EdgeMapBase {
1050    private:
1051     
1052      typedef typename _Graph::template EdgeMap<_Value> MapImpl;
1053     
1054    public:
1055
1056      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1057
1058      typedef _Value Value;
1059      typedef Edge Key;
1060     
1061      EdgeMapBase(const Adaptor& adaptor) :
1062        forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}
1063
1064      EdgeMapBase(const Adaptor& adaptor, const Value& v)
1065        : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}
1066     
1067      void set(const Edge& e, const Value& a) {
1068        if (Parent::direction(e)) {
1069          forward_map.set(e, a);
1070        } else {
1071          backward_map.set(e, a);
1072        }
1073      }
1074
1075      typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
1076        if (Parent::direction(e)) {
1077          return forward_map[e];
1078        } else {
1079          return backward_map[e];
1080        }
1081      }
1082
1083      typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {
1084        if (Parent::direction(e)) {
1085          return forward_map[e];
1086        } else {
1087          return backward_map[e];
1088        }
1089      }
1090
1091    protected:
1092
1093      MapImpl forward_map, backward_map;
1094
1095    };
1096
1097  public:
1098
1099    template <typename _Value>
1100    class EdgeMap
1101      : public SubMapExtender<Adaptor, EdgeMapBase<_Value> >
1102    {
1103    public:
1104      typedef Adaptor Graph;
1105      typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
1106   
1107      EdgeMap(const Graph& graph)
1108        : Parent(graph) {}
1109      EdgeMap(const Graph& graph, const _Value& value)
1110        : Parent(graph, value) {}
1111   
1112      EdgeMap& operator=(const EdgeMap& cmap) {
1113        return operator=<EdgeMap>(cmap);
1114      }
1115   
1116      template <typename CMap>
1117      EdgeMap& operator=(const CMap& cmap) {
1118        Parent::operator=(cmap);
1119        return *this;
1120      }
1121    };
1122       
1123    template <typename _Value>
1124    class UEdgeMap : public Graph::template EdgeMap<_Value> {
1125    public:
1126     
1127      typedef typename Graph::template EdgeMap<_Value> Parent;
1128     
1129      explicit UEdgeMap(const Adaptor& ga)
1130        : Parent(*ga.graph) {}
1131
1132      UEdgeMap(const Adaptor& ga, const _Value& value)
1133        : Parent(*ga.graph, value) {}
1134
1135      UEdgeMap& operator=(const UEdgeMap& cmap) {
1136        return operator=<UEdgeMap>(cmap);
1137      }
1138
1139      template <typename CMap>
1140      UEdgeMap& operator=(const CMap& cmap) {
1141        Parent::operator=(cmap);
1142        return *this;
1143      }
1144
1145    };
1146     
1147  };
1148
1149  template <typename _Graph, typename Enable = void>
1150  class AlterableUndirGraphAdaptor
1151    : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
1152  public:
1153    typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
1154   
1155  protected:
1156
1157    AlterableUndirGraphAdaptor() : Parent() {}
1158
1159  public:
1160
1161    typedef typename Parent::EdgeNotifier UEdgeNotifier;
1162    typedef InvalidType EdgeNotifier;
1163
1164  };
1165
1166  template <typename _Graph>
1167  class AlterableUndirGraphAdaptor<
1168    _Graph,
1169    typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type >
1170    : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
1171  public:
1172
1173    typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
1174    typedef _Graph Graph;
1175    typedef typename _Graph::Edge GraphEdge;
1176   
1177  protected:
1178
1179    AlterableUndirGraphAdaptor()
1180      : Parent(), edge_notifier(*this), edge_notifier_proxy(*this) {}
1181
1182    void setGraph(_Graph& graph) {
1183      Parent::setGraph(graph);
1184      edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
1185    }
1186
1187  public:
1188
1189    ~AlterableUndirGraphAdaptor() {
1190      edge_notifier.clear();
1191    }
1192
1193    typedef typename Parent::UEdge UEdge;
1194    typedef typename Parent::Edge Edge;
1195
1196    typedef typename Parent::EdgeNotifier UEdgeNotifier;
1197
1198    using Parent::getNotifier;
1199
1200    typedef AlterationNotifier<AlterableUndirGraphAdaptor,
1201                               Edge> EdgeNotifier;
1202    EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
1203
1204  protected:
1205
1206    class NotifierProxy : public Graph::EdgeNotifier::ObserverBase {
1207    public:
1208
1209      typedef typename Graph::EdgeNotifier::ObserverBase Parent;
1210      typedef AlterableUndirGraphAdaptor AdaptorBase;
1211     
1212      NotifierProxy(const AdaptorBase& _adaptor)
1213        : Parent(), adaptor(&_adaptor) {
1214      }
1215
1216      virtual ~NotifierProxy() {
1217        if (Parent::attached()) {
1218          Parent::detach();
1219        }
1220      }
1221
1222      void setNotifier(typename Graph::EdgeNotifier& notifier) {
1223        Parent::attach(notifier);
1224      }
1225
1226     
1227    protected:
1228
1229      virtual void add(const GraphEdge& ge) {
1230        std::vector<Edge> edges;
1231        edges.push_back(AdaptorBase::Parent::direct(ge, true));
1232        edges.push_back(AdaptorBase::Parent::direct(ge, false));
1233        adaptor->getNotifier(Edge()).add(edges);
1234      }
1235      virtual void add(const std::vector<GraphEdge>& ge) {
1236        std::vector<Edge> edges;
1237        for (int i = 0; i < (int)ge.size(); ++i) {
1238          edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
1239          edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
1240        }
1241        adaptor->getNotifier(Edge()).add(edges);
1242      }
1243      virtual void erase(const GraphEdge& ge) {
1244        std::vector<Edge> edges;
1245        edges.push_back(AdaptorBase::Parent::direct(ge, true));
1246        edges.push_back(AdaptorBase::Parent::direct(ge, false));
1247        adaptor->getNotifier(Edge()).erase(edges);
1248      }
1249      virtual void erase(const std::vector<GraphEdge>& ge) {
1250        std::vector<Edge> edges;
1251        for (int i = 0; i < (int)ge.size(); ++i) {
1252          edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
1253          edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
1254        }
1255        adaptor->getNotifier(Edge()).erase(edges);
1256      }
1257      virtual void build() {
1258        adaptor->getNotifier(Edge()).build();
1259      }
1260      virtual void clear() {
1261        adaptor->getNotifier(Edge()).clear();
1262      }
1263
1264      const AdaptorBase* adaptor;
1265    };
1266
1267
1268    mutable EdgeNotifier edge_notifier;
1269    NotifierProxy edge_notifier_proxy;
1270
1271  };
1272
1273
1274  ///\ingroup graph_adaptors
1275  ///
1276  /// \brief An undirected graph is made from a directed graph by an adaptor
1277  ///
1278  /// Undocumented, untested!!!
1279  /// If somebody knows nice demo application, let's polulate it.
1280  ///
1281  /// \author Marton Makai
1282  template<typename _Graph>
1283  class UndirGraphAdaptor : public AlterableUndirGraphAdaptor<_Graph> {
1284  public:
1285    typedef _Graph Graph;
1286    typedef AlterableUndirGraphAdaptor<_Graph> Parent;
1287  protected:
1288    UndirGraphAdaptor() { }
1289  public:
1290    UndirGraphAdaptor(_Graph& _graph) {
1291      setGraph(_graph);
1292    }
1293
1294    template <typename _ForwardMap, typename _BackwardMap>
1295    class CombinedEdgeMap {
1296    public:
1297     
1298      typedef _ForwardMap ForwardMap;
1299      typedef _BackwardMap BackwardMap;
1300
1301      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
1302
1303      typedef typename ForwardMap::Value Value;
1304      typedef typename Parent::Edge Key;
1305     
1306      CombinedEdgeMap() : forward_map(0), backward_map(0) {}
1307
1308      CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map)
1309        : forward_map(&_forward_map), backward_map(&_backward_map) {}
1310     
1311      void set(const Key& e, const Value& a) {
1312        if (Parent::direction(e)) {
1313          forward_map->set(e, a);
1314        } else {
1315          backward_map->set(e, a);
1316        }
1317      }
1318
1319      typename MapTraits<ForwardMap>::ConstReturnValue
1320      operator[](const Key& e) const {
1321        if (Parent::direction(e)) {
1322          return (*forward_map)[e];
1323        } else {
1324          return (*backward_map)[e];
1325        }
1326      }
1327
1328      typename MapTraits<ForwardMap>::ReturnValue
1329      operator[](const Key& e) {
1330        if (Parent::direction(e)) {
1331          return (*forward_map)[e];
1332        } else {
1333          return (*backward_map)[e];
1334        }
1335      }
1336
1337      void setForwardMap(ForwardMap& _forward_map) {
1338        forward_map = &_forward_map;
1339      }
1340
1341      void setBackwardMap(BackwardMap& _backward_map) {
1342        backward_map = &_backward_map;
1343      }
1344
1345    protected:
1346
1347      ForwardMap* forward_map;
1348      BackwardMap* backward_map;
1349
1350    };
1351
1352  };
1353
1354  /// \brief Just gives back an undir graph adaptor
1355  ///
1356  /// Just gives back an undir graph adaptor
1357  template<typename Graph>
1358  UndirGraphAdaptor<const Graph>
1359  undirGraphAdaptor(const Graph& graph) {
1360    return UndirGraphAdaptor<const Graph>(graph);
1361  }
1362
1363  template<typename Graph, typename Number, 
1364           typename CapacityMap, typename FlowMap,
1365           typename Tolerance = Tolerance<Number> >
1366  class ResForwardFilter {
1367    const CapacityMap* capacity;
1368    const FlowMap* flow;
1369    Tolerance tolerance;
1370  public:
1371    typedef typename Graph::Edge Key;
1372    typedef bool Value;
1373
1374    ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
1375                     const Tolerance& _tolerance = Tolerance())
1376      : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
1377
1378    ResForwardFilter(const Tolerance& _tolerance)
1379      : capacity(0), flow(0), tolerance(_tolerance)  { }
1380
1381    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1382    void setFlow(const FlowMap& _flow) { flow = &_flow; }
1383
1384    bool operator[](const typename Graph::Edge& e) const {
1385      return tolerance.less((*flow)[e], (*capacity)[e]);
1386    }
1387  };
1388
1389  template<typename Graph, typename Number,
1390           typename CapacityMap, typename FlowMap,
1391           typename Tolerance = Tolerance<Number> >
1392  class ResBackwardFilter {
1393    const CapacityMap* capacity;
1394    const FlowMap* flow;
1395    Tolerance tolerance;
1396  public:
1397    typedef typename Graph::Edge Key;
1398    typedef bool Value;
1399
1400    ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
1401                      const Tolerance& _tolerance = Tolerance())
1402      : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
1403    ResBackwardFilter(const Tolerance& _tolerance = Tolerance())
1404      : capacity(0), flow(0), tolerance(_tolerance) { }
1405    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1406    void setFlow(const FlowMap& _flow) { flow = &_flow; }
1407    bool operator[](const typename Graph::Edge& e) const {
1408      return tolerance.less(0, Number((*flow)[e]));
1409    }
1410  };
1411
1412 
1413  ///\ingroup graph_adaptors
1414  ///
1415  ///\brief An adaptor for composing the residual
1416  ///graph for directed flow and circulation problems.
1417  ///
1418  ///An adaptor for composing the residual graph for directed flow and
1419  ///circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph
1420  ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
1421  ///be functions on the edge-set.
1422  ///
1423  ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands
1424  ///for a flow and \f$ c \f$ for a capacity function.  Suppose that a
1425  ///graph instange \c g of type \c ListGraph implements \f$ G \f$.
1426  ///
1427  ///\code
1428  ///  ListGraph g;
1429  ///\endcode
1430  ///
1431  ///Then RevGraphAdaptor implements the graph structure with node-set
1432  /// \f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$,
1433  ///where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
1434  /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so called
1435  ///residual graph.  When we take the union
1436  /// \f$ A_{forward}\cup A_{backward} \f$, multilicities are counted, i.e.
1437  ///if an edge is in both \f$ A_{forward} \f$ and \f$ A_{backward} \f$,
1438  ///then in the adaptor it appears twice. The following code shows how
1439  ///such an instance can be constructed.
1440  ///
1441  ///\code
1442  ///  typedef ListGraph Graph;
1443  ///  Graph::EdgeMap<int> f(g);
1444  ///  Graph::EdgeMap<int> c(g);
1445  ///  ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g);
1446  ///\endcode
1447  ///\author Marton Makai
1448  ///
1449  template<typename Graph, typename Number,
1450           typename CapacityMap, typename FlowMap,
1451           typename Tolerance = Tolerance<Number> >
1452  class ResGraphAdaptor :
1453    public EdgeSubGraphAdaptor<
1454    UndirGraphAdaptor<const Graph>,
1455    typename UndirGraphAdaptor<const Graph>::template CombinedEdgeMap<
1456    ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>, 
1457    ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> > > {
1458  public:
1459
1460    typedef UndirGraphAdaptor<const Graph> UGraph;
1461
1462    typedef ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>
1463    ForwardFilter;
1464
1465    typedef ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap>
1466    BackwardFilter;
1467
1468    typedef typename UGraph::
1469    template CombinedEdgeMap<ForwardFilter, BackwardFilter>
1470    EdgeFilter;
1471
1472    typedef EdgeSubGraphAdaptor<UGraph, EdgeFilter> Parent;
1473
1474  protected:
1475
1476    const CapacityMap* capacity;
1477    FlowMap* flow;
1478
1479    UGraph ugraph;
1480    ForwardFilter forward_filter;
1481    BackwardFilter backward_filter;
1482    EdgeFilter edge_filter;
1483
1484    void setCapacityMap(const CapacityMap& _capacity) {
1485      capacity=&_capacity;
1486      forward_filter.setCapacity(_capacity);
1487      backward_filter.setCapacity(_capacity);
1488    }
1489
1490    void setFlowMap(FlowMap& _flow) {
1491      flow=&_flow;
1492      forward_filter.setFlow(_flow);
1493      backward_filter.setFlow(_flow);
1494    }
1495
1496  public:
1497
1498    /// \brief Constructor of the residual graph.
1499    ///
1500    /// Constructor of the residual graph. The parameters are the graph type,
1501    /// the flow map, the capacity map and a tolerance object.
1502    ResGraphAdaptor(const Graph& _graph, const CapacityMap& _capacity,
1503                    FlowMap& _flow, const Tolerance& _tolerance = Tolerance())
1504      : Parent(), capacity(&_capacity), flow(&_flow), ugraph(_graph),
1505        forward_filter(_capacity, _flow, _tolerance),
1506        backward_filter(_capacity, _flow, _tolerance),
1507        edge_filter(forward_filter, backward_filter)
1508    {
1509      Parent::setGraph(ugraph);
1510      Parent::setEdgeFilterMap(edge_filter);
1511    }
1512
1513    typedef typename Parent::Edge Edge;
1514
1515    /// \brief Gives back the residual capacity of the edge.
1516    ///
1517    /// Gives back the residual capacity of the edge.
1518    Number rescap(const Edge& edge) const {
1519      if (UGraph::direction(edge)) {
1520        return (*capacity)[edge]-(*flow)[edge];
1521      } else {
1522        return (*flow)[edge];
1523      }
1524    }
1525
1526    /// \brief Augment on the given edge in the residual graph.
1527    ///
1528    /// Augment on the given edge in the residual graph. It increase
1529    /// or decrease the flow on the original edge depend on the direction
1530    /// of the residual edge.
1531    void augment(const Edge& e, Number a) const {
1532      if (UGraph::direction(e)) {
1533        flow->set(e, (*flow)[e] + a);
1534      } else { 
1535        flow->set(e, (*flow)[e] - a);
1536      }
1537    }
1538
1539    /// \brief Returns the direction of the edge.
1540    ///
1541    /// Returns true when the edge is same oriented as the original edge.
1542    static bool forward(const Edge& e) {
1543      return UGraph::direction(e);
1544    }
1545
1546    /// \brief Returns the direction of the edge.
1547    ///
1548    /// Returns true when the edge is opposite oriented as the original edge.
1549    static bool backward(const Edge& e) {
1550      return !UGraph::direction(e);
1551    }
1552
1553    /// \brief Gives back the forward oriented residual edge.
1554    ///
1555    /// Gives back the forward oriented residual edge.
1556    static Edge forward(const typename Graph::Edge& e) {
1557      return UGraph::direct(e, true);
1558    }
1559
1560    /// \brief Gives back the backward oriented residual edge.
1561    ///
1562    /// Gives back the backward oriented residual edge.
1563    static Edge backward(const typename Graph::Edge& e) {
1564      return UGraph::direct(e, false);
1565    }
1566
1567    /// \brief Residual capacity map.
1568    ///
1569    /// In generic residual graphs the residual capacity can be obtained
1570    /// as a map.
1571    class ResCap {
1572    protected:
1573      const ResGraphAdaptor* res_graph;
1574    public:
1575      typedef Number Value;
1576      typedef Edge Key;
1577      ResCap(const ResGraphAdaptor& _res_graph)
1578        : res_graph(&_res_graph) {}
1579     
1580      Number operator[](const Edge& e) const {
1581        return res_graph->rescap(e);
1582      }
1583     
1584    };
1585
1586  };
1587
1588
1589
1590  template <typename _Graph, typename FirstOutEdgesMap>
1591  class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1592  public:
1593    typedef _Graph Graph;
1594    typedef GraphAdaptorBase<_Graph> Parent;
1595  protected:
1596    FirstOutEdgesMap* first_out_edges;
1597    ErasingFirstGraphAdaptorBase() : Parent(),
1598                                     first_out_edges(0) { }
1599
1600    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1601      first_out_edges=&_first_out_edges;
1602    }
1603
1604  public:
1605
1606    typedef typename Parent::Node Node;
1607    typedef typename Parent::Edge Edge;
1608
1609    void firstOut(Edge& i, const Node& n) const {
1610      i=(*first_out_edges)[n];
1611    }
1612
1613    void erase(const Edge& e) const {
1614      Node n=source(e);
1615      Edge f=e;
1616      Parent::nextOut(f);
1617      first_out_edges->set(n, f);
1618    }   
1619  };
1620
1621
1622  ///\ingroup graph_adaptors
1623  ///
1624  ///\brief For blocking flows.
1625  ///
1626  ///This graph adaptor is used for on-the-fly
1627  ///Dinits blocking flow computations.
1628  ///For each node, an out-edge is stored which is used when the
1629  ///\code
1630  ///OutEdgeIt& first(OutEdgeIt&, const Node&)
1631  ///\endcode
1632  ///is called.
1633  ///
1634  ///\author Marton Makai
1635  ///
1636  template <typename _Graph, typename FirstOutEdgesMap>
1637  class ErasingFirstGraphAdaptor :
1638    public GraphAdaptorExtender<
1639    ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
1640  public:
1641    typedef _Graph Graph;
1642    typedef GraphAdaptorExtender<
1643      ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1644    ErasingFirstGraphAdaptor(Graph& _graph,
1645                             FirstOutEdgesMap& _first_out_edges) {
1646      setGraph(_graph);
1647      setFirstOutEdgesMap(_first_out_edges);
1648    }
1649
1650  };
1651
1652  /// \brief Base class for split graph adaptor
1653  ///
1654  /// Base class of split graph adaptor. In most case you do not need to
1655  /// use it directly but the documented member functions of this class can
1656  /// be used with the SplitGraphAdaptor class.
1657  /// \sa SplitGraphAdaptor
1658  template <typename _Graph>
1659  class SplitGraphAdaptorBase
1660    : public GraphAdaptorBase<const _Graph> {
1661  public:
1662
1663    typedef _Graph Graph;
1664
1665    typedef GraphAdaptorBase<const _Graph> Parent;
1666
1667    typedef typename Graph::Node GraphNode;
1668    typedef typename Graph::Edge GraphEdge;
1669
1670    class Node;
1671    class Edge;
1672
1673    template <typename T> class NodeMap;
1674    template <typename T> class EdgeMap;
1675   
1676
1677    class Node : public GraphNode {
1678      friend class SplitGraphAdaptorBase;
1679      template <typename T> friend class NodeMap;
1680    private:
1681
1682      bool in_node;
1683      Node(GraphNode _node, bool _in_node)
1684        : GraphNode(_node), in_node(_in_node) {}
1685     
1686    public:
1687
1688      Node() {}
1689      Node(Invalid) : GraphNode(INVALID), in_node(true) {}
1690
1691      bool operator==(const Node& node) const {
1692        return GraphNode::operator==(node) && in_node == node.in_node;
1693      }
1694     
1695      bool operator!=(const Node& node) const {
1696        return !(*this == node);
1697      }
1698     
1699      bool operator<(const Node& node) const {
1700        return GraphNode::operator<(node) ||
1701          (GraphNode::operator==(node) && in_node < node.in_node);
1702      }
1703    };
1704
1705    class Edge {
1706      friend class SplitGraphAdaptorBase;
1707      template <typename T> friend class EdgeMap;
1708    private:
1709      typedef BiVariant<GraphEdge, GraphNode> EdgeImpl;
1710
1711      explicit Edge(const GraphEdge& edge) : item(edge) {}
1712      explicit Edge(const GraphNode& node) : item(node) {}
1713     
1714      EdgeImpl item;
1715
1716    public:
1717      Edge() {}
1718      Edge(Invalid) : item(GraphEdge(INVALID)) {}
1719
1720      bool operator==(const Edge& edge) const {
1721        if (item.firstState()) {
1722          if (edge.item.firstState()) {
1723            return item.first() == edge.item.first();
1724          }
1725        } else {
1726          if (edge.item.secondState()) {
1727            return item.second() == edge.item.second();
1728          }
1729        }
1730        return false;
1731      }
1732     
1733      bool operator!=(const Edge& edge) const {
1734        return !(*this == edge);
1735      }
1736     
1737      bool operator<(const Edge& edge) const {
1738        if (item.firstState()) {
1739          if (edge.item.firstState()) {
1740            return item.first() < edge.item.first();
1741          }
1742          return false;
1743        } else {
1744          if (edge.item.secondState()) {
1745            return item.second() < edge.item.second();
1746          }
1747          return true;
1748        }
1749      }
1750
1751      operator GraphEdge() const { return item.first(); }
1752      operator GraphNode() const { return item.second(); }
1753
1754    };
1755
1756    void first(Node& node) const {
1757      Parent::first(node);
1758      node.in_node = true;
1759    }
1760
1761    void next(Node& node) const {
1762      if (node.in_node) {
1763        node.in_node = false;
1764      } else {
1765        node.in_node = true;
1766        Parent::next(node);
1767      }
1768    }
1769
1770    void first(Edge& edge) const {
1771      edge.item.setSecond();
1772      Parent::first(edge.item.second());
1773      if (edge.item.second() == INVALID) {
1774        edge.item.setFirst();
1775        Parent::first(edge.item.first());
1776      }
1777    }
1778
1779    void next(Edge& edge) const {
1780      if (edge.item.secondState()) {
1781        Parent::next(edge.item.second());
1782        if (edge.item.second() == INVALID) {
1783          edge.item.setFirst();
1784          Parent::first(edge.item.first());
1785        }
1786      } else {
1787        Parent::next(edge.item.first());
1788      }     
1789    }
1790
1791    void firstOut(Edge& edge, const Node& node) const {
1792      if (node.in_node) {
1793        edge.item.setSecond(node);
1794      } else {
1795        edge.item.setFirst();
1796        Parent::firstOut(edge.item.first(), node);
1797      }
1798    }
1799
1800    void nextOut(Edge& edge) const {
1801      if (!edge.item.firstState()) {
1802        edge.item.setFirst(INVALID);
1803      } else {
1804        Parent::nextOut(edge.item.first());
1805      }     
1806    }
1807
1808    void firstIn(Edge& edge, const Node& node) const {
1809      if (!node.in_node) {
1810        edge.item.setSecond(node);       
1811      } else {
1812        edge.item.setFirst();
1813        Parent::firstIn(edge.item.first(), node);
1814      }
1815    }
1816
1817    void nextIn(Edge& edge) const {
1818      if (!edge.item.firstState()) {
1819        edge.item.setFirst(INVALID);
1820      } else {
1821        Parent::nextIn(edge.item.first());
1822      }
1823    }
1824
1825    Node source(const Edge& edge) const {
1826      if (edge.item.firstState()) {
1827        return Node(Parent::source(edge.item.first()), false);
1828      } else {
1829        return Node(edge.item.second(), true);
1830      }
1831    }
1832
1833    Node target(const Edge& edge) const {
1834      if (edge.item.firstState()) {
1835        return Node(Parent::target(edge.item.first()), true);
1836      } else {
1837        return Node(edge.item.second(), false);
1838      }
1839    }
1840
1841    int id(const Node& node) const {
1842      return (Parent::id(node) << 1) | (node.in_node ? 0 : 1);
1843    }
1844    Node nodeFromId(int id) const {
1845      return Node(Parent::nodeFromId(id >> 1), (id & 1) == 0);
1846    }
1847    int maxNodeId() const {
1848      return 2 * Parent::maxNodeId() + 1;
1849    }
1850
1851    int id(const Edge& edge) const {
1852      if (edge.item.firstState()) {
1853        return Parent::id(edge.item.first()) << 1;
1854      } else {
1855        return (Parent::id(edge.item.second()) << 1) | 1;
1856      }
1857    }
1858    Edge edgeFromId(int id) const {
1859      if ((id & 1) == 0) {
1860        return Edge(Parent::edgeFromId(id >> 1));
1861      } else {
1862        return Edge(Parent::nodeFromId(id >> 1));
1863      }
1864    }
1865    int maxEdgeId() const {
1866      return std::max(Parent::maxNodeId() << 1,
1867                      (Parent::maxEdgeId() << 1) | 1);
1868    }
1869
1870    /// \brief Returns true when the node is in-node.
1871    ///
1872    /// Returns true when the node is in-node.
1873    static bool inNode(const Node& node) {
1874      return node.in_node;
1875    }
1876
1877    /// \brief Returns true when the node is out-node.
1878    ///
1879    /// Returns true when the node is out-node.
1880    static bool outNode(const Node& node) {
1881      return !node.in_node;
1882    }
1883
1884    /// \brief Returns true when the edge is edge in the original graph.
1885    ///
1886    /// Returns true when the edge is edge in the original graph.
1887    static bool origEdge(const Edge& edge) {
1888      return edge.item.firstState();
1889    }
1890
1891    /// \brief Returns true when the edge binds an in-node and an out-node.
1892    ///
1893    /// Returns true when the edge binds an in-node and an out-node.
1894    static bool bindEdge(const Edge& edge) {
1895      return edge.item.secondState();
1896    }
1897
1898    /// \brief Gives back the in-node created from the \c node.
1899    ///
1900    /// Gives back the in-node created from the \c node.
1901    static Node inNode(const GraphNode& node) {
1902      return Node(node, true);
1903    }
1904
1905    /// \brief Gives back the out-node created from the \c node.
1906    ///
1907    /// Gives back the out-node created from the \c node.
1908    static Node outNode(const GraphNode& node) {
1909      return Node(node, false);
1910    }
1911
1912    /// \brief Gives back the edge binds the two part of the node.
1913    ///
1914    /// Gives back the edge binds the two part of the node.
1915    static Edge edge(const GraphNode& node) {
1916      return Edge(node);
1917    }
1918
1919    /// \brief Gives back the edge of the original edge.
1920    ///
1921    /// Gives back the edge of the original edge.
1922    static Edge edge(const GraphEdge& edge) {
1923      return Edge(edge);
1924    }
1925
1926    typedef True NodeNumTag;
1927
1928    int nodeNum() const {
1929      return  2 * countNodes(*Parent::graph);
1930    }
1931
1932    typedef True EdgeNumTag;
1933   
1934    int edgeNum() const {
1935      return countEdges(*Parent::graph) + countNodes(*Parent::graph);
1936    }
1937
1938    typedef True FindEdgeTag;
1939
1940    Edge findEdge(const Node& source, const Node& target,
1941                  const Edge& prev = INVALID) const {
1942      if (inNode(source)) {
1943        if (outNode(target)) {
1944          if ((GraphNode&)source == (GraphNode&)target && prev == INVALID) {
1945            return Edge(source);
1946          }
1947        }
1948      } else {
1949        if (inNode(target)) {
1950          return Edge(findEdge(*Parent::graph, source, target, prev));
1951        }
1952      }
1953      return INVALID;
1954    }
1955   
1956    template <typename T>
1957    class NodeMap : public MapBase<Node, T> {
1958      typedef typename Parent::template NodeMap<T> NodeImpl;
1959    public:
1960      NodeMap(const SplitGraphAdaptorBase& _graph)
1961        : inNodeMap(_graph), outNodeMap(_graph) {}
1962      NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1963        : inNodeMap(_graph, t), outNodeMap(_graph, t) {}
1964     
1965      void set(const Node& key, const T& val) {
1966        if (SplitGraphAdaptorBase::inNode(key)) { inNodeMap.set(key, val); }
1967        else {outNodeMap.set(key, val); }
1968      }
1969     
1970      typename MapTraits<NodeImpl>::ReturnValue
1971      operator[](const Node& key) {
1972        if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
1973        else { return outNodeMap[key]; }
1974      }
1975
1976      typename MapTraits<NodeImpl>::ConstReturnValue
1977      operator[](const Node& key) const {
1978        if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
1979        else { return outNodeMap[key]; }
1980      }
1981
1982    private:
1983      NodeImpl inNodeMap, outNodeMap;
1984    };
1985
1986    template <typename T>
1987    class EdgeMap : public MapBase<Edge, T> {
1988      typedef typename Parent::template EdgeMap<T> EdgeMapImpl;
1989      typedef typename Parent::template NodeMap<T> NodeMapImpl;
1990    public:
1991
1992      EdgeMap(const SplitGraphAdaptorBase& _graph)
1993        : edge_map(_graph), node_map(_graph) {}
1994      EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1995        : edge_map(_graph, t), node_map(_graph, t) {}
1996     
1997      void set(const Edge& key, const T& val) {
1998        if (SplitGraphAdaptorBase::origEdge(key)) {
1999          edge_map.set(key.item.first(), val);
2000        } else {
2001          node_map.set(key.item.second(), val);
2002        }
2003      }
2004     
2005      typename MapTraits<EdgeMapImpl>::ReturnValue
2006      operator[](const Edge& key) {
2007        if (SplitGraphAdaptorBase::origEdge(key)) {
2008          return edge_map[key.item.first()];
2009        } else {
2010          return node_map[key.item.second()];
2011        }
2012      }
2013
2014      typename MapTraits<EdgeMapImpl>::ConstReturnValue
2015      operator[](const Edge& key) const {
2016        if (SplitGraphAdaptorBase::origEdge(key)) {
2017          return edge_map[key.item.first()];
2018        } else {
2019          return node_map[key.item.second()];
2020        }
2021      }
2022
2023    private:
2024      typename Parent::template EdgeMap<T> edge_map;
2025      typename Parent::template NodeMap<T> node_map;
2026    };
2027
2028
2029  };
2030
2031  template <typename _Graph, typename NodeEnable = void,
2032            typename EdgeEnable = void>
2033  class AlterableSplitGraphAdaptor
2034    : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2035  public:
2036
2037    typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2038    typedef _Graph Graph;
2039
2040    typedef typename Graph::Node GraphNode;
2041    typedef typename Graph::Node GraphEdge;
2042
2043  protected:
2044
2045    AlterableSplitGraphAdaptor() : Parent() {}
2046
2047  public:
2048   
2049    typedef InvalidType NodeNotifier;
2050    typedef InvalidType EdgeNotifier;
2051
2052  };
2053
2054  template <typename _Graph, typename EdgeEnable>
2055  class AlterableSplitGraphAdaptor<
2056    _Graph,
2057    typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
2058    EdgeEnable>
2059      : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2060  public:
2061
2062    typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2063    typedef _Graph Graph;
2064
2065    typedef typename Graph::Node GraphNode;
2066    typedef typename Graph::Edge GraphEdge;
2067
2068    typedef typename Parent::Node Node;
2069    typedef typename Parent::Edge Edge;
2070 
2071  protected:
2072
2073    AlterableSplitGraphAdaptor()
2074      : Parent(), node_notifier(*this), node_notifier_proxy(*this) {}
2075
2076    void setGraph(_Graph& graph) {
2077      Parent::setGraph(graph);
2078      node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
2079    }
2080
2081  public:
2082
2083    ~AlterableSplitGraphAdaptor() {
2084      node_notifier.clear();
2085    }
2086
2087    typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
2088    typedef InvalidType EdgeNotifier;
2089
2090    NodeNotifier& getNotifier(Node) const { return node_notifier; }
2091
2092  protected:
2093
2094    class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
2095    public:
2096
2097      typedef typename Graph::NodeNotifier::ObserverBase Parent;
2098      typedef AlterableSplitGraphAdaptor AdaptorBase;
2099     
2100      NodeNotifierProxy(const AdaptorBase& _adaptor)
2101        : Parent(), adaptor(&_adaptor) {
2102      }
2103
2104      virtual ~NodeNotifierProxy() {
2105        if (Parent::attached()) {
2106          Parent::detach();
2107        }
2108      }
2109
2110      void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
2111        Parent::attach(graph_notifier);
2112      }
2113
2114     
2115    protected:
2116
2117      virtual void add(const GraphNode& gn) {
2118        std::vector<Node> nodes;
2119        nodes.push_back(AdaptorBase::Parent::inNode(gn));
2120        nodes.push_back(AdaptorBase::Parent::outNode(gn));
2121        adaptor->getNotifier(Node()).add(nodes);
2122      }
2123
2124      virtual void add(const std::vector<GraphNode>& gn) {
2125        std::vector<Node> nodes;
2126        for (int i = 0; i < (int)gn.size(); ++i) {
2127          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2128          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2129        }
2130        adaptor->getNotifier(Node()).add(nodes);
2131      }
2132
2133      virtual void erase(const GraphNode& gn) {
2134        std::vector<Node> nodes;
2135        nodes.push_back(AdaptorBase::Parent::inNode(gn));
2136        nodes.push_back(AdaptorBase::Parent::outNode(gn));
2137        adaptor->getNotifier(Node()).erase(nodes);
2138      }
2139
2140      virtual void erase(const std::vector<GraphNode>& gn) {
2141        std::vector<Node> nodes;
2142        for (int i = 0; i < (int)gn.size(); ++i) {
2143          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2144          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2145        }
2146        adaptor->getNotifier(Node()).erase(nodes);
2147      }
2148      virtual void build() {
2149        adaptor->getNotifier(Node()).build();
2150      }
2151      virtual void clear() {
2152        adaptor->getNotifier(Node()).clear();
2153      }
2154
2155      const AdaptorBase* adaptor;
2156    };
2157
2158
2159    mutable NodeNotifier node_notifier;
2160
2161    NodeNotifierProxy node_notifier_proxy;
2162
2163  };
2164
2165  template <typename _Graph>
2166  class AlterableSplitGraphAdaptor<
2167    _Graph,
2168    typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
2169    typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type>
2170      : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2171  public:
2172
2173    typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2174    typedef _Graph Graph;
2175
2176    typedef typename Graph::Node GraphNode;
2177    typedef typename Graph::Edge GraphEdge;
2178
2179    typedef typename Parent::Node Node;
2180    typedef typename Parent::Edge Edge;
2181 
2182  protected:
2183   
2184    AlterableSplitGraphAdaptor()
2185      : Parent(), node_notifier(*this), edge_notifier(*this),
2186        node_notifier_proxy(*this), edge_notifier_proxy(*this) {}
2187   
2188    void setGraph(_Graph& graph) {
2189      Parent::setGraph(graph);
2190      node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
2191      edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
2192    }
2193
2194  public:
2195
2196    ~AlterableSplitGraphAdaptor() {
2197      node_notifier.clear();
2198      edge_notifier.clear();
2199    }
2200
2201    typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
2202    typedef AlterationNotifier<AlterableSplitGraphAdaptor, Edge> EdgeNotifier;
2203
2204    NodeNotifier& getNotifier(Node) const { return node_notifier; }
2205    EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
2206
2207  protected:
2208
2209    class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
2210    public:
2211     
2212      typedef typename Graph::NodeNotifier::ObserverBase Parent;
2213      typedef AlterableSplitGraphAdaptor AdaptorBase;
2214     
2215      NodeNotifierProxy(const AdaptorBase& _adaptor)
2216        : Parent(), adaptor(&_adaptor) {
2217      }
2218
2219      virtual ~NodeNotifierProxy() {
2220        if (Parent::attached()) {
2221          Parent::detach();
2222        }
2223      }
2224
2225      void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
2226        Parent::attach(graph_notifier);
2227      }
2228
2229     
2230    protected:
2231
2232      virtual void add(const GraphNode& gn) {
2233        std::vector<Node> nodes;
2234        nodes.push_back(AdaptorBase::Parent::inNode(gn));
2235        nodes.push_back(AdaptorBase::Parent::outNode(gn));
2236        adaptor->getNotifier(Node()).add(nodes);
2237        adaptor->getNotifier(Edge()).add(AdaptorBase::Parent::edge(gn));
2238      }
2239      virtual void add(const std::vector<GraphNode>& gn) {
2240        std::vector<Node> nodes;
2241        std::vector<Edge> edges;
2242        for (int i = 0; i < (int)gn.size(); ++i) {
2243          edges.push_back(AdaptorBase::Parent::edge(gn[i]));
2244          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2245          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2246        }
2247        adaptor->getNotifier(Node()).add(nodes);
2248        adaptor->getNotifier(Edge()).add(edges);
2249      }
2250      virtual void erase(const GraphNode& gn) {
2251        adaptor->getNotifier(Edge()).erase(AdaptorBase::Parent::edge(gn));
2252        std::vector<Node> nodes;
2253        nodes.push_back(AdaptorBase::Parent::inNode(gn));
2254        nodes.push_back(AdaptorBase::Parent::outNode(gn));
2255        adaptor->getNotifier(Node()).erase(nodes);
2256      }
2257      virtual void erase(const std::vector<GraphNode>& gn) {
2258        std::vector<Node> nodes;
2259        std::vector<Edge> edges;
2260        for (int i = 0; i < (int)gn.size(); ++i) {
2261          edges.push_back(AdaptorBase::Parent::edge(gn[i]));
2262          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2263          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2264        }
2265        adaptor->getNotifier(Edge()).erase(edges);
2266        adaptor->getNotifier(Node()).erase(nodes);
2267      }
2268      virtual void build() {
2269        std::vector<Edge> edges;
2270        const typename Parent::Notifier* notifier = Parent::getNotifier();
2271        GraphNode it;
2272        for (notifier->first(it); it != INVALID; notifier->next(it)) {
2273          edges.push_back(AdaptorBase::Parent::edge(it));
2274        }
2275        adaptor->getNotifier(Node()).build();
2276        adaptor->getNotifier(Edge()).add(edges);       
2277      }
2278      virtual void clear() {
2279        std::vector<Edge> edges;
2280        const typename Parent::Notifier* notifier = Parent::getNotifier();
2281        GraphNode it;
2282        for (notifier->first(it); it != INVALID; notifier->next(it)) {
2283          edges.push_back(AdaptorBase::Parent::edge(it));
2284        }
2285        adaptor->getNotifier(Edge()).erase(edges);       
2286        adaptor->getNotifier(Node()).clear();
2287      }
2288
2289      const AdaptorBase* adaptor;
2290    };
2291
2292    class EdgeNotifierProxy : public Graph::EdgeNotifier::ObserverBase {
2293    public:
2294
2295      typedef typename Graph::EdgeNotifier::ObserverBase Parent;
2296      typedef AlterableSplitGraphAdaptor AdaptorBase;
2297     
2298      EdgeNotifierProxy(const AdaptorBase& _adaptor)
2299        : Parent(), adaptor(&_adaptor) {
2300      }
2301
2302      virtual ~EdgeNotifierProxy() {
2303        if (Parent::attached()) {
2304          Parent::detach();
2305        }
2306      }
2307
2308      void setNotifier(typename Graph::EdgeNotifier& graph_notifier) {
2309        Parent::attach(graph_notifier);
2310      }
2311
2312     
2313    protected:
2314
2315      virtual void add(const GraphEdge& ge) {
2316        adaptor->getNotifier(Edge()).add(AdaptorBase::edge(ge));
2317      }
2318      virtual void add(const std::vector<GraphEdge>& ge) {
2319        std::vector<Edge> edges;
2320        for (int i = 0; i < (int)ge.size(); ++i) {
2321          edges.push_back(AdaptorBase::edge(ge[i]));
2322        }
2323        adaptor->getNotifier(Edge()).add(edges);
2324      }
2325      virtual void erase(const GraphEdge& ge) {
2326        adaptor->getNotifier(Edge()).erase(AdaptorBase::edge(ge));
2327      }
2328      virtual void erase(const std::vector<GraphEdge>& ge) {
2329        std::vector<Edge> edges;
2330        for (int i = 0; i < (int)ge.size(); ++i) {
2331          edges.push_back(AdaptorBase::edge(ge[i]));
2332        }
2333        adaptor->getNotifier(Edge()).erase(edges);
2334      }
2335      virtual void build() {
2336        std::vector<Edge> edges;
2337        const typename Parent::Notifier* notifier = Parent::getNotifier();
2338        GraphEdge it;
2339        for (notifier->first(it); it != INVALID; notifier->next(it)) {
2340          edges.push_back(AdaptorBase::Parent::edge(it));
2341        }
2342        adaptor->getNotifier(Edge()).add(edges);
2343      }
2344      virtual void clear() {
2345        std::vector<Edge> edges;
2346        const typename Parent::Notifier* notifier = Parent::getNotifier();
2347        GraphEdge it;
2348        for (notifier->first(it); it != INVALID; notifier->next(it)) {
2349          edges.push_back(AdaptorBase::Parent::edge(it));
2350        }
2351        adaptor->getNotifier(Edge()).erase(edges);
2352      }
2353
2354      const AdaptorBase* adaptor;
2355    };
2356
2357
2358    mutable NodeNotifier node_notifier;
2359    mutable EdgeNotifier edge_notifier;
2360
2361    NodeNotifierProxy node_notifier_proxy;
2362    EdgeNotifierProxy edge_notifier_proxy;
2363
2364  };
2365
2366  /// \ingroup graph_adaptors
2367  ///
2368  /// \brief Split graph adaptor class
2369  ///
2370  /// This is an graph adaptor which splits all node into an in-node
2371  /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
2372  /// node in the graph with two node, \f$ u_{in} \f$ node and
2373  /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ edge in the
2374  /// original graph the new target of the edge will be \f$ u_{in} \f$ and
2375  /// similarly the source of the original \f$ (u, v) \f$ edge will be
2376  /// \f$ u_{out} \f$.  The adaptor will add for each node in the
2377  /// original graph an additional edge which will connect
2378  /// \f$ (u_{in}, u_{out}) \f$.
2379  ///
2380  /// The aim of this class is to run algorithm with node costs if the
2381  /// algorithm can use directly just edge costs. In this case we should use
2382  /// a \c SplitGraphAdaptor and set the node cost of the graph to the
2383  /// bind edge in the adapted graph.
2384  ///
2385  /// By example a maximum flow algoritm can compute how many edge
2386  /// disjoint paths are in the graph. But we would like to know how
2387  /// many node disjoint paths are in the graph. First we have to
2388  /// adapt the graph with the \c SplitGraphAdaptor. Then run the flow
2389  /// algorithm on the adapted graph. The bottleneck of the flow will
2390  /// be the bind edges which bounds the flow with the count of the
2391  /// node disjoint paths.
2392  ///
2393  ///\code
2394  ///
2395  /// typedef SplitGraphAdaptor<SmartGraph> SGraph;
2396  ///
2397  /// SGraph sgraph(graph);
2398  ///
2399  /// typedef ConstMap<SGraph::Edge, int> SCapacity;
2400  /// SCapacity scapacity(1);
2401  ///
2402  /// SGraph::EdgeMap<int> sflow(sgraph);
2403  ///
2404  /// Preflow<SGraph, int, SCapacity>
2405  ///   spreflow(sgraph, SGraph::outNode(source),SGraph::inNode(target), 
2406  ///            scapacity, sflow);
2407  ///                                           
2408  /// spreflow.run();
2409  ///
2410  ///\endcode
2411  ///
2412  /// The result of the mamixum flow on the original graph
2413  /// shows the next figure:
2414  ///
2415  /// \image html edge_disjoint.png
2416  /// \image latex edge_disjoint.eps "Edge disjoint paths" width=\textwidth
2417  ///
2418  /// And the maximum flow on the adapted graph:
2419  ///
2420  /// \image html node_disjoint.png
2421  /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
2422  ///
2423  /// The second solution contains just 3 disjoint paths while the first 4.
2424  /// The full code can be found in the \ref disjoint_paths_demo.cc demo file.
2425  ///
2426  /// This graph adaptor is fully conform to the
2427  /// \ref concept::Graph "Graph" concept and
2428  /// contains some additional member functions and types. The
2429  /// documentation of some member functions may be found just in the
2430  /// SplitGraphAdaptorBase class.
2431  ///
2432  /// \sa SplitGraphAdaptorBase
2433  template <typename _Graph>
2434  class SplitGraphAdaptor : public AlterableSplitGraphAdaptor<_Graph> {
2435  public:
2436    typedef AlterableSplitGraphAdaptor<_Graph> Parent;
2437
2438    typedef typename Parent::Node Node;
2439    typedef typename Parent::Edge Edge;
2440
2441    /// \brief Constructor of the adaptor.
2442    ///
2443    /// Constructor of the adaptor.
2444    SplitGraphAdaptor(_Graph& graph) {
2445      Parent::setGraph(graph);
2446    }
2447
2448    /// \brief NodeMap combined from two original NodeMap
2449    ///
2450    /// This class adapt two of the original graph NodeMap to
2451    /// get a node map on the adapted graph.
2452    template <typename InNodeMap, typename OutNodeMap>
2453    class CombinedNodeMap {
2454    public:
2455
2456      typedef Node Key;
2457      typedef typename InNodeMap::Value Value;
2458
2459      /// \brief Constructor
2460      ///
2461      /// Constructor.
2462      CombinedNodeMap(InNodeMap& _inNodeMap, OutNodeMap& _outNodeMap)
2463        : inNodeMap(_inNodeMap), outNodeMap(_outNodeMap) {}
2464
2465      /// \brief The subscript operator.
2466      ///
2467      /// The subscript operator.
2468      Value& operator[](const Key& key) {
2469        if (Parent::inNode(key)) {
2470          return inNodeMap[key];
2471        } else {
2472          return outNodeMap[key];
2473        }
2474      }
2475
2476      /// \brief The const subscript operator.
2477      ///
2478      /// The const subscript operator.
2479      Value operator[](const Key& key) const {
2480        if (Parent::inNode(key)) {
2481          return inNodeMap[key];
2482        } else {
2483          return outNodeMap[key];
2484        }
2485      }
2486
2487      /// \brief The setter function of the map.
2488      ///
2489      /// The setter function of the map.
2490      void set(const Key& key, const Value& value) {
2491        if (Parent::inNode(key)) {
2492          inNodeMap.set(key, value);
2493        } else {
2494          outNodeMap.set(key, value);
2495        }
2496      }
2497     
2498    private:
2499     
2500      InNodeMap& inNodeMap;
2501      OutNodeMap& outNodeMap;
2502     
2503    };
2504
2505
2506    /// \brief Just gives back a combined node map.
2507    ///
2508    /// Just gives back a combined node map.
2509    template <typename InNodeMap, typename OutNodeMap>
2510    static CombinedNodeMap<InNodeMap, OutNodeMap>
2511    combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
2512      return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
2513    }
2514
2515    template <typename InNodeMap, typename OutNodeMap>
2516    static CombinedNodeMap<const InNodeMap, OutNodeMap>
2517    combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
2518      return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
2519    }
2520
2521    template <typename InNodeMap, typename OutNodeMap>
2522    static CombinedNodeMap<InNodeMap, const OutNodeMap>
2523    combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
2524      return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
2525    }
2526
2527    template <typename InNodeMap, typename OutNodeMap>
2528    static CombinedNodeMap<const InNodeMap, const OutNodeMap>
2529    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
2530      return CombinedNodeMap<const InNodeMap,
2531        const OutNodeMap>(in_map, out_map);
2532    }
2533
2534    /// \brief EdgeMap combined from an original EdgeMap and NodeMap
2535    ///
2536    /// This class adapt an original graph EdgeMap and NodeMap to
2537    /// get an edge map on the adapted graph.
2538    template <typename GraphEdgeMap, typename GraphNodeMap>
2539    class CombinedEdgeMap
2540      : public MapBase<Edge, typename GraphEdgeMap::Value> {
2541    public:
2542      typedef MapBase<Edge, typename GraphEdgeMap::Value> Parent;
2543
2544      typedef typename Parent::Key Key;
2545      typedef typename Parent::Value Value;
2546
2547      /// \brief Constructor
2548      ///
2549      /// Constructor.
2550      CombinedEdgeMap(GraphEdgeMap& _edge_map, GraphNodeMap& _node_map)
2551        : edge_map(_edge_map), node_map(_node_map) {}
2552
2553      /// \brief The subscript operator.
2554      ///
2555      /// The subscript operator.
2556      void set(const Edge& edge, const Value& val) {
2557        if (Parent::origEdge(edge)) {
2558          edge_map.set(edge, val);
2559        } else {
2560          node_map.set(edge, val);
2561        }
2562      }
2563
2564      /// \brief The const subscript operator.
2565      ///
2566      /// The const subscript operator.
2567      Value operator[](const Key& edge) const {
2568        if (Parent::origEdge(edge)) {
2569          return edge_map[edge];
2570        } else {
2571          return node_map[edge];
2572        }
2573      }     
2574
2575      /// \brief The const subscript operator.
2576      ///
2577      /// The const subscript operator.
2578      Value& operator[](const Key& edge) {
2579        if (Parent::origEdge(edge)) {
2580          return edge_map[edge];
2581        } else {
2582          return node_map[edge];
2583        }
2584      }     
2585     
2586    private:
2587      GraphEdgeMap& edge_map;
2588      GraphNodeMap& node_map;
2589    };
2590                   
2591    /// \brief Just gives back a combined edge map.
2592    ///
2593    /// Just gives back a combined edge map.
2594    template <typename GraphEdgeMap, typename GraphNodeMap>
2595    static CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>
2596    combinedEdgeMap(GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
2597      return CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>(edge_map, node_map);
2598    }
2599
2600    template <typename GraphEdgeMap, typename GraphNodeMap>
2601    static CombinedEdgeMap<const GraphEdgeMap, GraphNodeMap>
2602    combinedEdgeMap(const GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
2603      return CombinedEdgeMap<const GraphEdgeMap,
2604        GraphNodeMap>(edge_map, node_map);
2605    }
2606
2607    template <typename GraphEdgeMap, typename GraphNodeMap>
2608    static CombinedEdgeMap<GraphEdgeMap, const GraphNodeMap>
2609    combinedEdgeMap(GraphEdgeMap& edge_map, const GraphNodeMap& node_map) {
2610      return CombinedEdgeMap<GraphEdgeMap,
2611        const GraphNodeMap>(edge_map, node_map);
2612    }
2613
2614    template <typename GraphEdgeMap, typename GraphNodeMap>
2615    static CombinedEdgeMap<const GraphEdgeMap, const GraphNodeMap>
2616    combinedEdgeMap(const GraphEdgeMap& edge_map,
2617                    const GraphNodeMap& node_map) {
2618      return CombinedEdgeMap<const GraphEdgeMap,
2619        const GraphNodeMap>(edge_map, node_map);
2620    }
2621
2622  };
2623
2624  /// \brief Just gives back a split graph adaptor
2625  ///
2626  /// Just gives back a split graph adaptor
2627  template<typename Graph>
2628  SplitGraphAdaptor<Graph>
2629  splitGraphAdaptor(const Graph& graph) {
2630    return SplitGraphAdaptor<Graph>(graph);
2631  }
2632
2633
2634} //namespace lemon
2635
2636#endif //LEMON_GRAPH_ADAPTOR_H
2637
Note: See TracBrowser for help on using the repository browser.