COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 2513:26983135fd6d

Last change on this file since 2513:26983135fd6d was 2422:77ed2b97abbd, checked in by Balazs Dezso, 17 years ago

Doc fix

File size: 80.4 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
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& u, const Node& v,
97                  const Edge& prev = INVALID) {
98      return graph->findEdge(u, v, prev);
99    }
100 
101    Node addNode() const {
102      return Node(graph->addNode());
103    }
104
105    Edge addEdge(const Node& u, const Node& v) const {
106      return Edge(graph->addEdge(u, v));
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 ix) const {
118      return graph->fromNodeId(ix);
119    }
120
121    Edge fromEdgeId(int ix) const {
122      return graph->fromEdgeId(ix);
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& notifier(Node) const {
136      return graph->notifier(Node());
137    }
138
139    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
140
141    EdgeNotifier& notifier(Edge) const {
142      return graph->notifier(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& u, const Node& v,
247                  const Edge& prev = INVALID) {
248      return Parent::findEdge(v, u, 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& g)
464        : Parent(g) {}
465      NodeMap(const Graph& g, const _Value& v)
466        : Parent(g, v) {}
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& g)
490        : Parent(g) {}
491      EdgeMap(const Graph& g, const _Value& v)
492        : Parent(g, v) {}
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& g)
637        : Parent(g) {}
638      NodeMap(const Graph& g, const _Value& v)
639        : Parent(g, v) {}
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& g)
663        : Parent(g) {}
664      EdgeMap(const Graph& g, const _Value& v)
665        : Parent(g, v) {}
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
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& g)
1109        : Parent(g) {}
1110      EdgeMap(const Graph& g, const _Value& v)
1111        : Parent(g, v) {}
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& g) {
1184      Parent::setGraph(g);
1185      edge_notifier_proxy.setNotifier(g.notifier(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::notifier;
1200
1201    typedef AlterationNotifier<AlterableUndirGraphAdaptor,
1202                               Edge> EdgeNotifier;
1203    EdgeNotifier& notifier(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& nf) {
1224        Parent::attach(nf);
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->notifier(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->notifier(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->notifier(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->notifier(Edge()).erase(edges);
1257      }
1258      virtual void build() {
1259        adaptor->notifier(Edge()).build();
1260      }
1261      virtual void clear() {
1262        adaptor->notifier(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  /// This adaptor makes an undirected graph from a directed
1280  /// graph. All edge of the underlying will be showed in the adaptor
1281  /// as an undirected edge. Let's see an informal example about using
1282  /// this adaptor:
1283  ///
1284  /// There is a network of the streets of a town. Of course there are
1285  /// some one-way street in the town hence the network is a directed
1286  /// one. There is a crazy driver who go oppositely in the one-way
1287  /// street without moral sense. Of course he can pass this streets
1288  /// slower than the regular way, in fact his speed is half of the
1289  /// normal speed. How long should he drive to get from a source
1290  /// point to the target? Let see the example code which calculate it:
1291  ///
1292  ///\code
1293  /// typedef UndirGraphAdaptor<Graph> UGraph;
1294  /// UGraph ugraph(graph);
1295  ///
1296  /// typedef SimpleMap<LengthMap> FLengthMap;
1297  /// FLengthMap flength(length);
1298  ///
1299  /// typedef ScaleMap<LengthMap> RLengthMap;
1300  /// RLengthMap rlength(length, 2.0);
1301  ///
1302  /// typedef UGraph::CombinedEdgeMap<FLengthMap, RLengthMap > ULengthMap;
1303  /// ULengthMap ulength(flength, rlength);
1304  ///
1305  /// Dijkstra<UGraph, ULengthMap> dijkstra(ugraph, ulength);
1306  /// std::cout << "Driving time : " << dijkstra.run(src, trg) << std::endl;
1307  ///\endcode
1308  ///
1309  /// The combined edge map makes the length map for the undirected
1310  /// graph. It is created from a forward and reverse map. The forward
1311  /// map is created from the original length map with a SimpleMap
1312  /// adaptor which just makes a read-write map from the reference map
1313  /// i.e. it forgets that it can be return reference to values. The
1314  /// reverse map is just the scaled original map with the ScaleMap
1315  /// adaptor. The combination solves that passing the reverse way
1316  /// takes double time than the original. To get the driving time we
1317  /// run the dijkstra algorithm on the undirected graph.
1318  ///
1319  /// \author Marton Makai and Balazs Dezso
1320  template<typename _Graph>
1321  class UndirGraphAdaptor : public AlterableUndirGraphAdaptor<_Graph> {
1322  public:
1323    typedef _Graph Graph;
1324    typedef AlterableUndirGraphAdaptor<_Graph> Parent;
1325  protected:
1326    UndirGraphAdaptor() { }
1327  public:
1328
1329    /// \brief Constructor
1330    ///
1331    /// Constructor
1332    UndirGraphAdaptor(_Graph& _graph) {
1333      setGraph(_graph);
1334    }
1335
1336    /// \brief EdgeMap combined from two original EdgeMap
1337    ///
1338    /// This class adapts two original graph EdgeMap to
1339    /// get an edge map on the adaptor.
1340    template <typename _ForwardMap, typename _BackwardMap>
1341    class CombinedEdgeMap {
1342    public:
1343     
1344      typedef _ForwardMap ForwardMap;
1345      typedef _BackwardMap BackwardMap;
1346
1347      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
1348
1349      typedef typename ForwardMap::Value Value;
1350      typedef typename Parent::Edge Key;
1351
1352      /// \brief Constructor     
1353      ///
1354      /// Constructor     
1355      CombinedEdgeMap() : forward_map(0), backward_map(0) {}
1356
1357      /// \brief Constructor     
1358      ///
1359      /// Constructor     
1360      CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map)
1361        : forward_map(&_forward_map), backward_map(&_backward_map) {}
1362     
1363
1364      /// \brief Sets the value associated with a key.
1365      ///
1366      /// Sets the value associated with a key.
1367      void set(const Key& e, const Value& a) {
1368        if (Parent::direction(e)) {
1369          forward_map->set(e, a);
1370        } else {
1371          backward_map->set(e, a);
1372        }
1373      }
1374
1375      /// \brief Returns the value associated with a key.
1376      ///
1377      /// Returns the value associated with a key.
1378      typename MapTraits<ForwardMap>::ConstReturnValue
1379      operator[](const Key& e) const {
1380        if (Parent::direction(e)) {
1381          return (*forward_map)[e];
1382        } else {
1383          return (*backward_map)[e];
1384        }
1385      }
1386
1387      /// \brief Returns the value associated with a key.
1388      ///
1389      /// Returns the value associated with a key.
1390      typename MapTraits<ForwardMap>::ReturnValue
1391      operator[](const Key& e) {
1392        if (Parent::direction(e)) {
1393          return (*forward_map)[e];
1394        } else {
1395          return (*backward_map)[e];
1396        }
1397      }
1398
1399      /// \brief Sets the forward map
1400      ///
1401      /// Sets the forward map
1402      void setForwardMap(ForwardMap& _forward_map) {
1403        forward_map = &_forward_map;
1404      }
1405
1406      /// \brief Sets the backward map
1407      ///
1408      /// Sets the backward map
1409      void setBackwardMap(BackwardMap& _backward_map) {
1410        backward_map = &_backward_map;
1411      }
1412
1413    protected:
1414
1415      ForwardMap* forward_map;
1416      BackwardMap* backward_map;
1417
1418    };
1419
1420  };
1421
1422  /// \brief Just gives back an undir graph adaptor
1423  ///
1424  /// Just gives back an undir graph adaptor
1425  template<typename Graph>
1426  UndirGraphAdaptor<const Graph>
1427  undirGraphAdaptor(const Graph& graph) {
1428    return UndirGraphAdaptor<const Graph>(graph);
1429  }
1430
1431  template<typename Graph, typename Number, 
1432           typename CapacityMap, typename FlowMap,
1433           typename Tol = Tolerance<Number> >
1434  class ResForwardFilter {
1435    const CapacityMap* capacity;
1436    const FlowMap* flow;
1437    Tol tolerance;
1438  public:
1439    typedef typename Graph::Edge Key;
1440    typedef bool Value;
1441
1442    ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
1443                     const Tol& _tolerance = Tol())
1444      : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
1445
1446    ResForwardFilter(const Tol& _tolerance)
1447      : capacity(0), flow(0), tolerance(_tolerance)  { }
1448
1449    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1450    void setFlow(const FlowMap& _flow) { flow = &_flow; }
1451
1452    bool operator[](const typename Graph::Edge& e) const {
1453      return tolerance.positive((*capacity)[e] - (*flow)[e]);
1454    }
1455  };
1456
1457  template<typename Graph, typename Number,
1458           typename CapacityMap, typename FlowMap,
1459           typename Tol = Tolerance<Number> >
1460  class ResBackwardFilter {
1461    const CapacityMap* capacity;
1462    const FlowMap* flow;
1463    Tol tolerance;
1464  public:
1465    typedef typename Graph::Edge Key;
1466    typedef bool Value;
1467
1468    ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
1469                      const Tol& _tolerance = Tol())
1470      : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
1471    ResBackwardFilter(const Tol& _tolerance = Tol())
1472      : capacity(0), flow(0), tolerance(_tolerance) { }
1473    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1474    void setFlow(const FlowMap& _flow) { flow = &_flow; }
1475    bool operator[](const typename Graph::Edge& e) const {
1476      return tolerance.positive((*flow)[e]);
1477    }
1478  };
1479
1480 
1481  ///\ingroup graph_adaptors
1482  ///
1483  ///\brief An adaptor for composing the residual
1484  ///graph for directed flow and circulation problems.
1485  ///
1486  ///An adaptor for composing the residual graph for directed flow and
1487  ///circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph
1488  ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
1489  ///be functions on the edge-set.
1490  ///
1491  ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands
1492  ///for a flow and \f$ c \f$ for a capacity function.  Suppose that a
1493  ///graph instange \c g of type \c ListGraph implements \f$ G \f$.
1494  ///
1495  ///\code
1496  ///  ListGraph g;
1497  ///\endcode
1498  ///
1499  ///Then ResGraphAdaptor implements the graph structure with node-set
1500  /// \f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$,
1501  ///where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
1502  /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so called
1503  ///residual graph.  When we take the union
1504  /// \f$ A_{forward}\cup A_{backward} \f$, multilicities are counted, i.e.
1505  ///if an edge is in both \f$ A_{forward} \f$ and \f$ A_{backward} \f$,
1506  ///then in the adaptor it appears twice. The following code shows how
1507  ///such an instance can be constructed.
1508  ///
1509  ///\code
1510  ///  typedef ListGraph Graph;
1511  ///  Graph::EdgeMap<int> f(g);
1512  ///  Graph::EdgeMap<int> c(g);
1513  ///  ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g);
1514  ///\endcode
1515  ///\author Marton Makai
1516  ///
1517  template<typename Graph, typename Number,
1518           typename CapacityMap, typename FlowMap,
1519           typename Tol = Tolerance<Number> >
1520  class ResGraphAdaptor :
1521    public EdgeSubGraphAdaptor<
1522    UndirGraphAdaptor<const Graph>,
1523    typename UndirGraphAdaptor<const Graph>::template CombinedEdgeMap<
1524    ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>, 
1525    ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> > > {
1526  public:
1527
1528    typedef UndirGraphAdaptor<const Graph> UGraph;
1529
1530    typedef ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>
1531    ForwardFilter;
1532
1533    typedef ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap>
1534    BackwardFilter;
1535
1536    typedef typename UGraph::
1537    template CombinedEdgeMap<ForwardFilter, BackwardFilter>
1538    EdgeFilter;
1539
1540    typedef EdgeSubGraphAdaptor<UGraph, EdgeFilter> Parent;
1541
1542  protected:
1543
1544    const CapacityMap* capacity;
1545    FlowMap* flow;
1546
1547    UGraph ugraph;
1548    ForwardFilter forward_filter;
1549    BackwardFilter backward_filter;
1550    EdgeFilter edge_filter;
1551
1552    void setCapacityMap(const CapacityMap& _capacity) {
1553      capacity=&_capacity;
1554      forward_filter.setCapacity(_capacity);
1555      backward_filter.setCapacity(_capacity);
1556    }
1557
1558    void setFlowMap(FlowMap& _flow) {
1559      flow=&_flow;
1560      forward_filter.setFlow(_flow);
1561      backward_filter.setFlow(_flow);
1562    }
1563
1564  public:
1565
1566    /// \brief Constructor of the residual graph.
1567    ///
1568    /// Constructor of the residual graph. The parameters are the graph type,
1569    /// the flow map, the capacity map and a tolerance object.
1570    ResGraphAdaptor(const Graph& _graph, const CapacityMap& _capacity,
1571                    FlowMap& _flow, const Tol& _tolerance = Tol())
1572      : Parent(), capacity(&_capacity), flow(&_flow), ugraph(_graph),
1573        forward_filter(_capacity, _flow, _tolerance),
1574        backward_filter(_capacity, _flow, _tolerance),
1575        edge_filter(forward_filter, backward_filter)
1576    {
1577      Parent::setGraph(ugraph);
1578      Parent::setEdgeFilterMap(edge_filter);
1579    }
1580
1581    typedef typename Parent::Edge Edge;
1582
1583    /// \brief Gives back the residual capacity of the edge.
1584    ///
1585    /// Gives back the residual capacity of the edge.
1586    Number rescap(const Edge& edge) const {
1587      if (UGraph::direction(edge)) {
1588        return (*capacity)[edge]-(*flow)[edge];
1589      } else {
1590        return (*flow)[edge];
1591      }
1592    }
1593
1594    /// \brief Augment on the given edge in the residual graph.
1595    ///
1596    /// Augment on the given edge in the residual graph. It increase
1597    /// or decrease the flow on the original edge depend on the direction
1598    /// of the residual edge.
1599    void augment(const Edge& e, Number a) const {
1600      if (UGraph::direction(e)) {
1601        flow->set(e, (*flow)[e] + a);
1602      } else { 
1603        flow->set(e, (*flow)[e] - a);
1604      }
1605    }
1606
1607    /// \brief Returns the direction of the edge.
1608    ///
1609    /// Returns true when the edge is same oriented as the original edge.
1610    static bool forward(const Edge& e) {
1611      return UGraph::direction(e);
1612    }
1613
1614    /// \brief Returns the direction of the edge.
1615    ///
1616    /// Returns true when the edge is opposite oriented as the original edge.
1617    static bool backward(const Edge& e) {
1618      return !UGraph::direction(e);
1619    }
1620
1621    /// \brief Gives back the forward oriented residual edge.
1622    ///
1623    /// Gives back the forward oriented residual edge.
1624    static Edge forward(const typename Graph::Edge& e) {
1625      return UGraph::direct(e, true);
1626    }
1627
1628    /// \brief Gives back the backward oriented residual edge.
1629    ///
1630    /// Gives back the backward oriented residual edge.
1631    static Edge backward(const typename Graph::Edge& e) {
1632      return UGraph::direct(e, false);
1633    }
1634
1635    /// \brief Residual capacity map.
1636    ///
1637    /// In generic residual graphs the residual capacity can be obtained
1638    /// as a map.
1639    class ResCap {
1640    protected:
1641      const ResGraphAdaptor* res_graph;
1642    public:
1643      typedef Number Value;
1644      typedef Edge Key;
1645      ResCap(const ResGraphAdaptor& _res_graph)
1646        : res_graph(&_res_graph) {}
1647     
1648      Number operator[](const Edge& e) const {
1649        return res_graph->rescap(e);
1650      }
1651     
1652    };
1653
1654  };
1655
1656
1657
1658  template <typename _Graph, typename FirstOutEdgesMap>
1659  class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1660  public:
1661    typedef _Graph Graph;
1662    typedef GraphAdaptorBase<_Graph> Parent;
1663  protected:
1664    FirstOutEdgesMap* first_out_edges;
1665    ErasingFirstGraphAdaptorBase() : Parent(),
1666                                     first_out_edges(0) { }
1667
1668    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1669      first_out_edges=&_first_out_edges;
1670    }
1671
1672  public:
1673
1674    typedef typename Parent::Node Node;
1675    typedef typename Parent::Edge Edge;
1676
1677    void firstOut(Edge& i, const Node& n) const {
1678      i=(*first_out_edges)[n];
1679    }
1680
1681    void erase(const Edge& e) const {
1682      Node n=source(e);
1683      Edge f=e;
1684      Parent::nextOut(f);
1685      first_out_edges->set(n, f);
1686    }   
1687  };
1688
1689
1690  ///\ingroup graph_adaptors
1691  ///
1692  ///\brief For blocking flows.
1693  ///
1694  ///This graph adaptor is used for on-the-fly
1695  ///Dinits blocking flow computations.
1696  ///For each node, an out-edge is stored which is used when the
1697  ///\code
1698  ///OutEdgeIt& first(OutEdgeIt&, const Node&)
1699  ///\endcode
1700  ///is called.
1701  ///
1702  ///\author Marton Makai
1703  ///
1704  template <typename _Graph, typename FirstOutEdgesMap>
1705  class ErasingFirstGraphAdaptor :
1706    public GraphAdaptorExtender<
1707    ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
1708  public:
1709    typedef _Graph Graph;
1710    typedef GraphAdaptorExtender<
1711      ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1712    ErasingFirstGraphAdaptor(Graph& _graph,
1713                             FirstOutEdgesMap& _first_out_edges) {
1714      setGraph(_graph);
1715      setFirstOutEdgesMap(_first_out_edges);
1716    }
1717
1718  };
1719
1720  /// \brief Base class for split graph adaptor
1721  ///
1722  /// Base class of split graph adaptor. In most case you do not need to
1723  /// use it directly but the documented member functions of this class can
1724  /// be used with the SplitGraphAdaptor class.
1725  /// \sa SplitGraphAdaptor
1726  template <typename _Graph>
1727  class SplitGraphAdaptorBase
1728    : public GraphAdaptorBase<const _Graph> {
1729  public:
1730
1731    typedef _Graph Graph;
1732
1733    typedef GraphAdaptorBase<const _Graph> Parent;
1734
1735    typedef typename Graph::Node GraphNode;
1736    typedef typename Graph::Edge GraphEdge;
1737
1738    class Node;
1739    class Edge;
1740
1741    template <typename T> class NodeMap;
1742    template <typename T> class EdgeMap;
1743   
1744
1745    class Node : public GraphNode {
1746      friend class SplitGraphAdaptorBase;
1747      template <typename T> friend class NodeMap;
1748    private:
1749
1750      bool in_node;
1751      Node(GraphNode _node, bool _in_node)
1752        : GraphNode(_node), in_node(_in_node) {}
1753     
1754    public:
1755
1756      Node() {}
1757      Node(Invalid) : GraphNode(INVALID), in_node(true) {}
1758
1759      bool operator==(const Node& node) const {
1760        return GraphNode::operator==(node) && in_node == node.in_node;
1761      }
1762     
1763      bool operator!=(const Node& node) const {
1764        return !(*this == node);
1765      }
1766     
1767      bool operator<(const Node& node) const {
1768        return GraphNode::operator<(node) ||
1769          (GraphNode::operator==(node) && in_node < node.in_node);
1770      }
1771    };
1772
1773    class Edge {
1774      friend class SplitGraphAdaptorBase;
1775      template <typename T> friend class EdgeMap;
1776    private:
1777      typedef BiVariant<GraphEdge, GraphNode> EdgeImpl;
1778
1779      explicit Edge(const GraphEdge& edge) : item(edge) {}
1780      explicit Edge(const GraphNode& node) : item(node) {}
1781     
1782      EdgeImpl item;
1783
1784    public:
1785      Edge() {}
1786      Edge(Invalid) : item(GraphEdge(INVALID)) {}
1787
1788      bool operator==(const Edge& edge) const {
1789        if (item.firstState()) {
1790          if (edge.item.firstState()) {
1791            return item.first() == edge.item.first();
1792          }
1793        } else {
1794          if (edge.item.secondState()) {
1795            return item.second() == edge.item.second();
1796          }
1797        }
1798        return false;
1799      }
1800     
1801      bool operator!=(const Edge& edge) const {
1802        return !(*this == edge);
1803      }
1804     
1805      bool operator<(const Edge& edge) const {
1806        if (item.firstState()) {
1807          if (edge.item.firstState()) {
1808            return item.first() < edge.item.first();
1809          }
1810          return false;
1811        } else {
1812          if (edge.item.secondState()) {
1813            return item.second() < edge.item.second();
1814          }
1815          return true;
1816        }
1817      }
1818
1819      operator GraphEdge() const { return item.first(); }
1820      operator GraphNode() const { return item.second(); }
1821
1822    };
1823
1824    void first(Node& n) const {
1825      Parent::first(n);
1826      n.in_node = true;
1827    }
1828
1829    void next(Node& n) const {
1830      if (n.in_node) {
1831        n.in_node = false;
1832      } else {
1833        n.in_node = true;
1834        Parent::next(n);
1835      }
1836    }
1837
1838    void first(Edge& e) const {
1839      e.item.setSecond();
1840      Parent::first(e.item.second());
1841      if (e.item.second() == INVALID) {
1842        e.item.setFirst();
1843        Parent::first(e.item.first());
1844      }
1845    }
1846
1847    void next(Edge& e) const {
1848      if (e.item.secondState()) {
1849        Parent::next(e.item.second());
1850        if (e.item.second() == INVALID) {
1851          e.item.setFirst();
1852          Parent::first(e.item.first());
1853        }
1854      } else {
1855        Parent::next(e.item.first());
1856      }     
1857    }
1858
1859    void firstOut(Edge& e, const Node& n) const {
1860      if (n.in_node) {
1861        e.item.setSecond(n);
1862      } else {
1863        e.item.setFirst();
1864        Parent::firstOut(e.item.first(), n);
1865      }
1866    }
1867
1868    void nextOut(Edge& e) const {
1869      if (!e.item.firstState()) {
1870        e.item.setFirst(INVALID);
1871      } else {
1872        Parent::nextOut(e.item.first());
1873      }     
1874    }
1875
1876    void firstIn(Edge& e, const Node& n) const {
1877      if (!n.in_node) {
1878        e.item.setSecond(n);       
1879      } else {
1880        e.item.setFirst();
1881        Parent::firstIn(e.item.first(), n);
1882      }
1883    }
1884
1885    void nextIn(Edge& e) const {
1886      if (!e.item.firstState()) {
1887        e.item.setFirst(INVALID);
1888      } else {
1889        Parent::nextIn(e.item.first());
1890      }
1891    }
1892
1893    Node source(const Edge& e) const {
1894      if (e.item.firstState()) {
1895        return Node(Parent::source(e.item.first()), false);
1896      } else {
1897        return Node(e.item.second(), true);
1898      }
1899    }
1900
1901    Node target(const Edge& e) const {
1902      if (e.item.firstState()) {
1903        return Node(Parent::target(e.item.first()), true);
1904      } else {
1905        return Node(e.item.second(), false);
1906      }
1907    }
1908
1909    int id(const Node& n) const {
1910      return (Parent::id(n) << 1) | (n.in_node ? 0 : 1);
1911    }
1912    Node nodeFromId(int ix) const {
1913      return Node(Parent::nodeFromId(ix >> 1), (ix & 1) == 0);
1914    }
1915    int maxNodeId() const {
1916      return 2 * Parent::maxNodeId() + 1;
1917    }
1918
1919    int id(const Edge& e) const {
1920      if (e.item.firstState()) {
1921        return Parent::id(e.item.first()) << 1;
1922      } else {
1923        return (Parent::id(e.item.second()) << 1) | 1;
1924      }
1925    }
1926    Edge edgeFromId(int ix) const {
1927      if ((ix & 1) == 0) {
1928        return Edge(Parent::edgeFromId(ix >> 1));
1929      } else {
1930        return Edge(Parent::nodeFromId(ix >> 1));
1931      }
1932    }
1933    int maxEdgeId() const {
1934      return std::max(Parent::maxNodeId() << 1,
1935                      (Parent::maxEdgeId() << 1) | 1);
1936    }
1937
1938    /// \brief Returns true when the node is in-node.
1939    ///
1940    /// Returns true when the node is in-node.
1941    static bool inNode(const Node& n) {
1942      return n.in_node;
1943    }
1944
1945    /// \brief Returns true when the node is out-node.
1946    ///
1947    /// Returns true when the node is out-node.
1948    static bool outNode(const Node& n) {
1949      return !n.in_node;
1950    }
1951
1952    /// \brief Returns true when the edge is edge in the original graph.
1953    ///
1954    /// Returns true when the edge is edge in the original graph.
1955    static bool origEdge(const Edge& e) {
1956      return e.item.firstState();
1957    }
1958
1959    /// \brief Returns true when the edge binds an in-node and an out-node.
1960    ///
1961    /// Returns true when the edge binds an in-node and an out-node.
1962    static bool bindEdge(const Edge& e) {
1963      return e.item.secondState();
1964    }
1965
1966    /// \brief Gives back the in-node created from the \c node.
1967    ///
1968    /// Gives back the in-node created from the \c node.
1969    static Node inNode(const GraphNode& n) {
1970      return Node(n, true);
1971    }
1972
1973    /// \brief Gives back the out-node created from the \c node.
1974    ///
1975    /// Gives back the out-node created from the \c node.
1976    static Node outNode(const GraphNode& n) {
1977      return Node(n, false);
1978    }
1979
1980    /// \brief Gives back the edge binds the two part of the node.
1981    ///
1982    /// Gives back the edge binds the two part of the node.
1983    static Edge edge(const GraphNode& n) {
1984      return Edge(n);
1985    }
1986
1987    /// \brief Gives back the edge of the original edge.
1988    ///
1989    /// Gives back the edge of the original edge.
1990    static Edge edge(const GraphEdge& e) {
1991      return Edge(e);
1992    }
1993
1994    typedef True NodeNumTag;
1995
1996    int nodeNum() const {
1997      return  2 * countNodes(*Parent::graph);
1998    }
1999
2000    typedef True EdgeNumTag;
2001   
2002    int edgeNum() const {
2003      return countEdges(*Parent::graph) + countNodes(*Parent::graph);
2004    }
2005
2006    typedef True FindEdgeTag;
2007
2008    Edge findEdge(const Node& u, const Node& v,
2009                  const Edge& prev = INVALID) const {
2010      if (inNode(u)) {
2011        if (outNode(v)) {
2012          if (static_cast<const GraphNode&>(u) ==
2013              static_cast<const GraphNode&>(v) && prev == INVALID) {
2014            return Edge(u);
2015          }
2016        }
2017      } else {
2018        if (inNode(v)) {
2019          return Edge(findEdge(*Parent::graph, u, v, prev));
2020        }
2021      }
2022      return INVALID;
2023    }
2024   
2025    template <typename T>
2026    class NodeMap : public MapBase<Node, T> {
2027      typedef typename Parent::template NodeMap<T> NodeImpl;
2028    public:
2029      NodeMap(const SplitGraphAdaptorBase& _graph)
2030        : inNodeMap(_graph), outNodeMap(_graph) {}
2031      NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
2032        : inNodeMap(_graph, t), outNodeMap(_graph, t) {}
2033     
2034      void set(const Node& key, const T& val) {
2035        if (SplitGraphAdaptorBase::inNode(key)) { inNodeMap.set(key, val); }
2036        else {outNodeMap.set(key, val); }
2037      }
2038     
2039      typename MapTraits<NodeImpl>::ReturnValue
2040      operator[](const Node& key) {
2041        if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
2042        else { return outNodeMap[key]; }
2043      }
2044
2045      typename MapTraits<NodeImpl>::ConstReturnValue
2046      operator[](const Node& key) const {
2047        if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
2048        else { return outNodeMap[key]; }
2049      }
2050
2051    private:
2052      NodeImpl inNodeMap, outNodeMap;
2053    };
2054
2055    template <typename T>
2056    class EdgeMap : public MapBase<Edge, T> {
2057      typedef typename Parent::template EdgeMap<T> EdgeMapImpl;
2058      typedef typename Parent::template NodeMap<T> NodeMapImpl;
2059    public:
2060
2061      EdgeMap(const SplitGraphAdaptorBase& _graph)
2062        : edge_map(_graph), node_map(_graph) {}
2063      EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
2064        : edge_map(_graph, t), node_map(_graph, t) {}
2065     
2066      void set(const Edge& key, const T& val) {
2067        if (SplitGraphAdaptorBase::origEdge(key)) {
2068          edge_map.set(key.item.first(), val);
2069        } else {
2070          node_map.set(key.item.second(), val);
2071        }
2072      }
2073     
2074      typename MapTraits<EdgeMapImpl>::ReturnValue
2075      operator[](const Edge& key) {
2076        if (SplitGraphAdaptorBase::origEdge(key)) {
2077          return edge_map[key.item.first()];
2078        } else {
2079          return node_map[key.item.second()];
2080        }
2081      }
2082
2083      typename MapTraits<EdgeMapImpl>::ConstReturnValue
2084      operator[](const Edge& key) const {
2085        if (SplitGraphAdaptorBase::origEdge(key)) {
2086          return edge_map[key.item.first()];
2087        } else {
2088          return node_map[key.item.second()];
2089        }
2090      }
2091
2092    private:
2093      typename Parent::template EdgeMap<T> edge_map;
2094      typename Parent::template NodeMap<T> node_map;
2095    };
2096
2097
2098  };
2099
2100  template <typename _Graph, typename NodeEnable = void,
2101            typename EdgeEnable = void>
2102  class AlterableSplitGraphAdaptor
2103    : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2104  public:
2105
2106    typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2107    typedef _Graph Graph;
2108
2109    typedef typename Graph::Node GraphNode;
2110    typedef typename Graph::Node GraphEdge;
2111
2112  protected:
2113
2114    AlterableSplitGraphAdaptor() : Parent() {}
2115
2116  public:
2117   
2118    typedef InvalidType NodeNotifier;
2119    typedef InvalidType EdgeNotifier;
2120
2121  };
2122
2123  template <typename _Graph, typename EdgeEnable>
2124  class AlterableSplitGraphAdaptor<
2125    _Graph,
2126    typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
2127    EdgeEnable>
2128      : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2129  public:
2130
2131    typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2132    typedef _Graph Graph;
2133
2134    typedef typename Graph::Node GraphNode;
2135    typedef typename Graph::Edge GraphEdge;
2136
2137    typedef typename Parent::Node Node;
2138    typedef typename Parent::Edge Edge;
2139 
2140  protected:
2141
2142    AlterableSplitGraphAdaptor()
2143      : Parent(), node_notifier(*this), node_notifier_proxy(*this) {}
2144
2145    void setGraph(_Graph& graph) {
2146      Parent::setGraph(graph);
2147      node_notifier_proxy.setNotifier(graph.notifier(GraphNode()));
2148    }
2149
2150  public:
2151
2152    ~AlterableSplitGraphAdaptor() {
2153      node_notifier.clear();
2154    }
2155
2156    typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
2157    typedef InvalidType EdgeNotifier;
2158
2159    NodeNotifier& notifier(Node) const { return node_notifier; }
2160
2161  protected:
2162
2163    class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
2164    public:
2165
2166      typedef typename Graph::NodeNotifier::ObserverBase Parent;
2167      typedef AlterableSplitGraphAdaptor AdaptorBase;
2168     
2169      NodeNotifierProxy(const AdaptorBase& _adaptor)
2170        : Parent(), adaptor(&_adaptor) {
2171      }
2172
2173      virtual ~NodeNotifierProxy() {
2174        if (Parent::attached()) {
2175          Parent::detach();
2176        }
2177      }
2178
2179      void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
2180        Parent::attach(graph_notifier);
2181      }
2182
2183     
2184    protected:
2185
2186      virtual void add(const GraphNode& gn) {
2187        std::vector<Node> nodes;
2188        nodes.push_back(AdaptorBase::Parent::inNode(gn));
2189        nodes.push_back(AdaptorBase::Parent::outNode(gn));
2190        adaptor->notifier(Node()).add(nodes);
2191      }
2192
2193      virtual void add(const std::vector<GraphNode>& gn) {
2194        std::vector<Node> nodes;
2195        for (int i = 0; i < int(gn.size()); ++i) {
2196          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2197          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2198        }
2199        adaptor->notifier(Node()).add(nodes);
2200      }
2201
2202      virtual void erase(const GraphNode& gn) {
2203        std::vector<Node> nodes;
2204        nodes.push_back(AdaptorBase::Parent::inNode(gn));
2205        nodes.push_back(AdaptorBase::Parent::outNode(gn));
2206        adaptor->notifier(Node()).erase(nodes);
2207      }
2208
2209      virtual void erase(const std::vector<GraphNode>& gn) {
2210        std::vector<Node> nodes;
2211        for (int i = 0; i < int(gn.size()); ++i) {
2212          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2213          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2214        }
2215        adaptor->notifier(Node()).erase(nodes);
2216      }
2217      virtual void build() {
2218        adaptor->notifier(Node()).build();
2219      }
2220      virtual void clear() {
2221        adaptor->notifier(Node()).clear();
2222      }
2223
2224      const AdaptorBase* adaptor;
2225    };
2226
2227
2228    mutable NodeNotifier node_notifier;
2229
2230    NodeNotifierProxy node_notifier_proxy;
2231
2232  };
2233
2234  template <typename _Graph>
2235  class AlterableSplitGraphAdaptor<
2236    _Graph,
2237    typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
2238    typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type>
2239      : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2240  public:
2241
2242    typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2243    typedef _Graph Graph;
2244
2245    typedef typename Graph::Node GraphNode;
2246    typedef typename Graph::Edge GraphEdge;
2247
2248    typedef typename Parent::Node Node;
2249    typedef typename Parent::Edge Edge;
2250 
2251  protected:
2252   
2253    AlterableSplitGraphAdaptor()
2254      : Parent(), node_notifier(*this), edge_notifier(*this),
2255        node_notifier_proxy(*this), edge_notifier_proxy(*this) {}
2256   
2257    void setGraph(_Graph& g) {
2258      Parent::setGraph(g);
2259      node_notifier_proxy.setNotifier(g.notifier(GraphNode()));
2260      edge_notifier_proxy.setNotifier(g.notifier(GraphEdge()));
2261    }
2262
2263  public:
2264
2265    ~AlterableSplitGraphAdaptor() {
2266      node_notifier.clear();
2267      edge_notifier.clear();
2268    }
2269
2270    typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
2271    typedef AlterationNotifier<AlterableSplitGraphAdaptor, Edge> EdgeNotifier;
2272
2273    NodeNotifier& notifier(Node) const { return node_notifier; }
2274    EdgeNotifier& notifier(Edge) const { return edge_notifier; }
2275
2276  protected:
2277
2278    class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
2279    public:
2280     
2281      typedef typename Graph::NodeNotifier::ObserverBase Parent;
2282      typedef AlterableSplitGraphAdaptor AdaptorBase;
2283     
2284      NodeNotifierProxy(const AdaptorBase& _adaptor)
2285        : Parent(), adaptor(&_adaptor) {
2286      }
2287
2288      virtual ~NodeNotifierProxy() {
2289        if (Parent::attached()) {
2290          Parent::detach();
2291        }
2292      }
2293
2294      void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
2295        Parent::attach(graph_notifier);
2296      }
2297
2298     
2299    protected:
2300
2301      virtual void add(const GraphNode& gn) {
2302        std::vector<Node> nodes;
2303        nodes.push_back(AdaptorBase::Parent::inNode(gn));
2304        nodes.push_back(AdaptorBase::Parent::outNode(gn));
2305        adaptor->notifier(Node()).add(nodes);
2306        adaptor->notifier(Edge()).add(AdaptorBase::Parent::edge(gn));
2307      }
2308      virtual void add(const std::vector<GraphNode>& gn) {
2309        std::vector<Node> nodes;
2310        std::vector<Edge> edges;
2311        for (int i = 0; i < int(gn.size()); ++i) {
2312          edges.push_back(AdaptorBase::Parent::edge(gn[i]));
2313          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2314          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2315        }
2316        adaptor->notifier(Node()).add(nodes);
2317        adaptor->notifier(Edge()).add(edges);
2318      }
2319      virtual void erase(const GraphNode& gn) {
2320        adaptor->notifier(Edge()).erase(AdaptorBase::Parent::edge(gn));
2321        std::vector<Node> nodes;
2322        nodes.push_back(AdaptorBase::Parent::inNode(gn));
2323        nodes.push_back(AdaptorBase::Parent::outNode(gn));
2324        adaptor->notifier(Node()).erase(nodes);
2325      }
2326      virtual void erase(const std::vector<GraphNode>& gn) {
2327        std::vector<Node> nodes;
2328        std::vector<Edge> edges;
2329        for (int i = 0; i < int(gn.size()); ++i) {
2330          edges.push_back(AdaptorBase::Parent::edge(gn[i]));
2331          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2332          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2333        }
2334        adaptor->notifier(Edge()).erase(edges);
2335        adaptor->notifier(Node()).erase(nodes);
2336      }
2337      virtual void build() {
2338        std::vector<Edge> edges;
2339        const typename Parent::Notifier* nf = Parent::notifier();
2340        GraphNode it;
2341        for (nf->first(it); it != INVALID; nf->next(it)) {
2342          edges.push_back(AdaptorBase::Parent::edge(it));
2343        }
2344        adaptor->notifier(Node()).build();
2345        adaptor->notifier(Edge()).add(edges);       
2346      }
2347      virtual void clear() {
2348        std::vector<Edge> edges;
2349        const typename Parent::Notifier* nf = Parent::notifier();
2350        GraphNode it;
2351        for (nf->first(it); it != INVALID; nf->next(it)) {
2352          edges.push_back(AdaptorBase::Parent::edge(it));
2353        }
2354        adaptor->notifier(Edge()).erase(edges);       
2355        adaptor->notifier(Node()).clear();
2356      }
2357
2358      const AdaptorBase* adaptor;
2359    };
2360
2361    class EdgeNotifierProxy : public Graph::EdgeNotifier::ObserverBase {
2362    public:
2363
2364      typedef typename Graph::EdgeNotifier::ObserverBase Parent;
2365      typedef AlterableSplitGraphAdaptor AdaptorBase;
2366     
2367      EdgeNotifierProxy(const AdaptorBase& _adaptor)
2368        : Parent(), adaptor(&_adaptor) {
2369      }
2370
2371      virtual ~EdgeNotifierProxy() {
2372        if (Parent::attached()) {
2373          Parent::detach();
2374        }
2375      }
2376
2377      void setNotifier(typename Graph::EdgeNotifier& graph_notifier) {
2378        Parent::attach(graph_notifier);
2379      }
2380
2381     
2382    protected:
2383
2384      virtual void add(const GraphEdge& ge) {
2385        adaptor->notifier(Edge()).add(AdaptorBase::edge(ge));
2386      }
2387      virtual void add(const std::vector<GraphEdge>& ge) {
2388        std::vector<Edge> edges;
2389        for (int i = 0; i < int(ge.size()); ++i) {
2390          edges.push_back(AdaptorBase::edge(ge[i]));
2391        }
2392        adaptor->notifier(Edge()).add(edges);
2393      }
2394      virtual void erase(const GraphEdge& ge) {
2395        adaptor->notifier(Edge()).erase(AdaptorBase::edge(ge));
2396      }
2397      virtual void erase(const std::vector<GraphEdge>& ge) {
2398        std::vector<Edge> edges;
2399        for (int i = 0; i < int(ge.size()); ++i) {
2400          edges.push_back(AdaptorBase::edge(ge[i]));
2401        }
2402        adaptor->notifier(Edge()).erase(edges);
2403      }
2404      virtual void build() {
2405        std::vector<Edge> edges;
2406        const typename Parent::Notifier* nf = Parent::notifier();
2407        GraphEdge it;
2408        for (nf->first(it); it != INVALID; nf->next(it)) {
2409          edges.push_back(AdaptorBase::Parent::edge(it));
2410        }
2411        adaptor->notifier(Edge()).add(edges);
2412      }
2413      virtual void clear() {
2414        std::vector<Edge> edges;
2415        const typename Parent::Notifier* nf = Parent::notifier();
2416        GraphEdge it;
2417        for (nf->first(it); it != INVALID; nf->next(it)) {
2418          edges.push_back(AdaptorBase::Parent::edge(it));
2419        }
2420        adaptor->notifier(Edge()).erase(edges);
2421      }
2422
2423      const AdaptorBase* adaptor;
2424    };
2425
2426
2427    mutable NodeNotifier node_notifier;
2428    mutable EdgeNotifier edge_notifier;
2429
2430    NodeNotifierProxy node_notifier_proxy;
2431    EdgeNotifierProxy edge_notifier_proxy;
2432
2433  };
2434
2435  /// \ingroup graph_adaptors
2436  ///
2437  /// \brief Split graph adaptor class
2438  ///
2439  /// This is an graph adaptor which splits all node into an in-node
2440  /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
2441  /// node in the graph with two node, \f$ u_{in} \f$ node and
2442  /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ edge in the
2443  /// original graph the new target of the edge will be \f$ u_{in} \f$ and
2444  /// similarly the source of the original \f$ (u, v) \f$ edge will be
2445  /// \f$ u_{out} \f$.  The adaptor will add for each node in the
2446  /// original graph an additional edge which will connect
2447  /// \f$ (u_{in}, u_{out}) \f$.
2448  ///
2449  /// The aim of this class is to run algorithm with node costs if the
2450  /// algorithm can use directly just edge costs. In this case we should use
2451  /// a \c SplitGraphAdaptor and set the node cost of the graph to the
2452  /// bind edge in the adapted graph.
2453  ///
2454  /// By example a maximum flow algoritm can compute how many edge
2455  /// disjoint paths are in the graph. But we would like to know how
2456  /// many node disjoint paths are in the graph. First we have to
2457  /// adapt the graph with the \c SplitGraphAdaptor. Then run the flow
2458  /// algorithm on the adapted graph. The bottleneck of the flow will
2459  /// be the bind edges which bounds the flow with the count of the
2460  /// node disjoint paths.
2461  ///
2462  ///\code
2463  ///
2464  /// typedef SplitGraphAdaptor<SmartGraph> SGraph;
2465  ///
2466  /// SGraph sgraph(graph);
2467  ///
2468  /// typedef ConstMap<SGraph::Edge, int> SCapacity;
2469  /// SCapacity scapacity(1);
2470  ///
2471  /// SGraph::EdgeMap<int> sflow(sgraph);
2472  ///
2473  /// Preflow<SGraph, int, SCapacity>
2474  ///   spreflow(sgraph, SGraph::outNode(source),SGraph::inNode(target), 
2475  ///            scapacity, sflow);
2476  ///                                           
2477  /// spreflow.run();
2478  ///
2479  ///\endcode
2480  ///
2481  /// The result of the mamixum flow on the original graph
2482  /// shows the next figure:
2483  ///
2484  /// \image html edge_disjoint.png
2485  /// \image latex edge_disjoint.eps "Edge disjoint paths" width=\textwidth
2486  ///
2487  /// And the maximum flow on the adapted graph:
2488  ///
2489  /// \image html node_disjoint.png
2490  /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
2491  ///
2492  /// The second solution contains just 3 disjoint paths while the first 4.
2493  /// The full code can be found in the \ref disjoint_paths_demo.cc demo file.
2494  ///
2495  /// This graph adaptor is fully conform to the
2496  /// \ref concepts::Graph "Graph" concept and
2497  /// contains some additional member functions and types. The
2498  /// documentation of some member functions may be found just in the
2499  /// SplitGraphAdaptorBase class.
2500  ///
2501  /// \sa SplitGraphAdaptorBase
2502  template <typename _Graph>
2503  class SplitGraphAdaptor : public AlterableSplitGraphAdaptor<_Graph> {
2504  public:
2505    typedef AlterableSplitGraphAdaptor<_Graph> Parent;
2506
2507    typedef typename Parent::Node Node;
2508    typedef typename Parent::Edge Edge;
2509
2510    /// \brief Constructor of the adaptor.
2511    ///
2512    /// Constructor of the adaptor.
2513    SplitGraphAdaptor(_Graph& g) {
2514      Parent::setGraph(g);
2515    }
2516
2517    /// \brief NodeMap combined from two original NodeMap
2518    ///
2519    /// This class adapt two of the original graph NodeMap to
2520    /// get a node map on the adapted graph.
2521    template <typename InNodeMap, typename OutNodeMap>
2522    class CombinedNodeMap {
2523    public:
2524
2525      typedef Node Key;
2526      typedef typename InNodeMap::Value Value;
2527
2528      /// \brief Constructor
2529      ///
2530      /// Constructor.
2531      CombinedNodeMap(InNodeMap& _inNodeMap, OutNodeMap& _outNodeMap)
2532        : inNodeMap(_inNodeMap), outNodeMap(_outNodeMap) {}
2533
2534      /// \brief The subscript operator.
2535      ///
2536      /// The subscript operator.
2537      Value& operator[](const Key& key) {
2538        if (Parent::inNode(key)) {
2539          return inNodeMap[key];
2540        } else {
2541          return outNodeMap[key];
2542        }
2543      }
2544
2545      /// \brief The const subscript operator.
2546      ///
2547      /// The const subscript operator.
2548      Value operator[](const Key& key) const {
2549        if (Parent::inNode(key)) {
2550          return inNodeMap[key];
2551        } else {
2552          return outNodeMap[key];
2553        }
2554      }
2555
2556      /// \brief The setter function of the map.
2557      ///
2558      /// The setter function of the map.
2559      void set(const Key& key, const Value& value) {
2560        if (Parent::inNode(key)) {
2561          inNodeMap.set(key, value);
2562        } else {
2563          outNodeMap.set(key, value);
2564        }
2565      }
2566     
2567    private:
2568     
2569      InNodeMap& inNodeMap;
2570      OutNodeMap& outNodeMap;
2571     
2572    };
2573
2574
2575    /// \brief Just gives back a combined node map.
2576    ///
2577    /// Just gives back a combined node map.
2578    template <typename InNodeMap, typename OutNodeMap>
2579    static CombinedNodeMap<InNodeMap, OutNodeMap>
2580    combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
2581      return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
2582    }
2583
2584    template <typename InNodeMap, typename OutNodeMap>
2585    static CombinedNodeMap<const InNodeMap, OutNodeMap>
2586    combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
2587      return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
2588    }
2589
2590    template <typename InNodeMap, typename OutNodeMap>
2591    static CombinedNodeMap<InNodeMap, const OutNodeMap>
2592    combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
2593      return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
2594    }
2595
2596    template <typename InNodeMap, typename OutNodeMap>
2597    static CombinedNodeMap<const InNodeMap, const OutNodeMap>
2598    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
2599      return CombinedNodeMap<const InNodeMap,
2600        const OutNodeMap>(in_map, out_map);
2601    }
2602
2603    /// \brief EdgeMap combined from an original EdgeMap and NodeMap
2604    ///
2605    /// This class adapt an original graph EdgeMap and NodeMap to
2606    /// get an edge map on the adapted graph.
2607    template <typename GraphEdgeMap, typename GraphNodeMap>
2608    class CombinedEdgeMap {
2609    public:
2610     
2611      typedef Edge Key;
2612      typedef typename GraphEdgeMap::Value Value;
2613     
2614      /// \brief Constructor
2615      ///
2616      /// Constructor.
2617      CombinedEdgeMap(GraphEdgeMap& _edge_map, GraphNodeMap& _node_map)
2618        : edge_map(_edge_map), node_map(_node_map) {}
2619
2620      /// \brief The subscript operator.
2621      ///
2622      /// The subscript operator.
2623      void set(const Edge& edge, const Value& val) {
2624        if (Parent::origEdge(edge)) {
2625          edge_map.set(edge, val);
2626        } else {
2627          node_map.set(edge, val);
2628        }
2629      }
2630
2631      /// \brief The const subscript operator.
2632      ///
2633      /// The const subscript operator.
2634      Value operator[](const Key& edge) const {
2635        if (Parent::origEdge(edge)) {
2636          return edge_map[edge];
2637        } else {
2638          return node_map[edge];
2639        }
2640      }     
2641
2642      /// \brief The const subscript operator.
2643      ///
2644      /// The const subscript operator.
2645      Value& operator[](const Key& edge) {
2646        if (Parent::origEdge(edge)) {
2647          return edge_map[edge];
2648        } else {
2649          return node_map[edge];
2650        }
2651      }     
2652     
2653    private:
2654      GraphEdgeMap& edge_map;
2655      GraphNodeMap& node_map;
2656    };
2657                   
2658    /// \brief Just gives back a combined edge map.
2659    ///
2660    /// Just gives back a combined edge map.
2661    template <typename GraphEdgeMap, typename GraphNodeMap>
2662    static CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>
2663    combinedEdgeMap(GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
2664      return CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>(edge_map, node_map);
2665    }
2666
2667    template <typename GraphEdgeMap, typename GraphNodeMap>
2668    static CombinedEdgeMap<const GraphEdgeMap, GraphNodeMap>
2669    combinedEdgeMap(const GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
2670      return CombinedEdgeMap<const GraphEdgeMap,
2671        GraphNodeMap>(edge_map, node_map);
2672    }
2673
2674    template <typename GraphEdgeMap, typename GraphNodeMap>
2675    static CombinedEdgeMap<GraphEdgeMap, const GraphNodeMap>
2676    combinedEdgeMap(GraphEdgeMap& edge_map, const GraphNodeMap& node_map) {
2677      return CombinedEdgeMap<GraphEdgeMap,
2678        const GraphNodeMap>(edge_map, node_map);
2679    }
2680
2681    template <typename GraphEdgeMap, typename GraphNodeMap>
2682    static CombinedEdgeMap<const GraphEdgeMap, const GraphNodeMap>
2683    combinedEdgeMap(const GraphEdgeMap& edge_map,
2684                    const GraphNodeMap& node_map) {
2685      return CombinedEdgeMap<const GraphEdgeMap,
2686        const GraphNodeMap>(edge_map, node_map);
2687    }
2688
2689  };
2690
2691  /// \brief Just gives back a split graph adaptor
2692  ///
2693  /// Just gives back a split graph adaptor
2694  template<typename Graph>
2695  SplitGraphAdaptor<Graph>
2696  splitGraphAdaptor(const Graph& graph) {
2697    return SplitGraphAdaptor<Graph>(graph);
2698  }
2699
2700
2701} //namespace lemon
2702
2703#endif //LEMON_GRAPH_ADAPTOR_H
2704
Note: See TracBrowser for help on using the repository browser.