COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 2242:16523135943d

Last change on this file since 2242:16523135943d was 2177:416a7030b7e3, checked in by Balazs Dezso, 18 years ago

BiVariant? moved to lemon/bits/variant.h

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