COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 2529:93de38566e6c

Last change on this file since 2529:93de38566e6c was 2529:93de38566e6c, checked in by Balazs Dezso, 12 years ago

Minor changes

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