COIN-OR::LEMON - Graph Library

source: lemon/lemon/adaptors.h @ 470:3c0d39b6388c

Last change on this file since 470:3c0d39b6388c was 470:3c0d39b6388c, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Avoid warning in adaptors.h (#67)

File size: 101.0 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2008
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_ADAPTORS_H
20#define LEMON_ADAPTORS_H
21
22/// \ingroup graph_adaptors
23/// \file
24/// \brief Several graph adaptors
25///
26/// This file contains several useful adaptors for digraphs and graphs.
27
28#include <lemon/core.h>
29#include <lemon/maps.h>
30#include <lemon/bits/variant.h>
31
32#include <lemon/bits/graph_adaptor_extender.h>
33#include <lemon/tolerance.h>
34
35#include <algorithm>
36
37namespace lemon {
38
39  template<typename _Digraph>
40  class DigraphAdaptorBase {
41  public:
42    typedef _Digraph Digraph;
43    typedef DigraphAdaptorBase Adaptor;
44    typedef Digraph ParentDigraph;
45
46  protected:
47    Digraph* _digraph;
48    DigraphAdaptorBase() : _digraph(0) { }
49    void setDigraph(Digraph& digraph) { _digraph = &digraph; }
50
51  public:
52    DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
53
54    typedef typename Digraph::Node Node;
55    typedef typename Digraph::Arc Arc;
56
57    void first(Node& i) const { _digraph->first(i); }
58    void first(Arc& i) const { _digraph->first(i); }
59    void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
60    void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
61
62    void next(Node& i) const { _digraph->next(i); }
63    void next(Arc& i) const { _digraph->next(i); }
64    void nextIn(Arc& i) const { _digraph->nextIn(i); }
65    void nextOut(Arc& i) const { _digraph->nextOut(i); }
66
67    Node source(const Arc& a) const { return _digraph->source(a); }
68    Node target(const Arc& a) const { return _digraph->target(a); }
69
70    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
71    int nodeNum() const { return _digraph->nodeNum(); }
72
73    typedef ArcNumTagIndicator<Digraph> ArcNumTag;
74    int arcNum() const { return _digraph->arcNum(); }
75
76    typedef FindArcTagIndicator<Digraph> FindArcTag;
77    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
78      return _digraph->findArc(u, v, prev);
79    }
80
81    Node addNode() { return _digraph->addNode(); }
82    Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
83
84    void erase(const Node& n) const { _digraph->erase(n); }
85    void erase(const Arc& a) const { _digraph->erase(a); }
86
87    void clear() const { _digraph->clear(); }
88
89    int id(const Node& n) const { return _digraph->id(n); }
90    int id(const Arc& a) const { return _digraph->id(a); }
91
92    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
93    Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
94
95    int maxNodeId() const { return _digraph->maxNodeId(); }
96    int maxArcId() const { return _digraph->maxArcId(); }
97
98    typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
99    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
100
101    typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
102    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
103
104    template <typename _Value>
105    class NodeMap : public Digraph::template NodeMap<_Value> {
106    public:
107
108      typedef typename Digraph::template NodeMap<_Value> Parent;
109
110      explicit NodeMap(const Adaptor& adaptor)
111        : Parent(*adaptor._digraph) {}
112
113      NodeMap(const Adaptor& adaptor, const _Value& value)
114        : Parent(*adaptor._digraph, value) { }
115
116    private:
117      NodeMap& operator=(const NodeMap& cmap) {
118        return operator=<NodeMap>(cmap);
119      }
120
121      template <typename CMap>
122      NodeMap& operator=(const CMap& cmap) {
123        Parent::operator=(cmap);
124        return *this;
125      }
126
127    };
128
129    template <typename _Value>
130    class ArcMap : public Digraph::template ArcMap<_Value> {
131    public:
132
133      typedef typename Digraph::template ArcMap<_Value> Parent;
134
135      explicit ArcMap(const Adaptor& adaptor)
136        : Parent(*adaptor._digraph) {}
137
138      ArcMap(const Adaptor& adaptor, const _Value& value)
139        : Parent(*adaptor._digraph, value) {}
140
141    private:
142      ArcMap& operator=(const ArcMap& cmap) {
143        return operator=<ArcMap>(cmap);
144      }
145
146      template <typename CMap>
147      ArcMap& operator=(const CMap& cmap) {
148        Parent::operator=(cmap);
149        return *this;
150      }
151
152    };
153
154  };
155
156  template<typename _Graph>
157  class GraphAdaptorBase {
158  public:
159    typedef _Graph Graph;
160    typedef Graph ParentGraph;
161
162  protected:
163    Graph* _graph;
164
165    GraphAdaptorBase() : _graph(0) {}
166
167    void setGraph(Graph& graph) { _graph = &graph; }
168
169  public:
170    GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
171
172    typedef typename Graph::Node Node;
173    typedef typename Graph::Arc Arc;
174    typedef typename Graph::Edge Edge;
175
176    void first(Node& i) const { _graph->first(i); }
177    void first(Arc& i) const { _graph->first(i); }
178    void first(Edge& i) const { _graph->first(i); }
179    void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
180    void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
181    void firstInc(Edge &i, bool &d, const Node &n) const {
182      _graph->firstInc(i, d, n);
183    }
184
185    void next(Node& i) const { _graph->next(i); }
186    void next(Arc& i) const { _graph->next(i); }
187    void next(Edge& i) const { _graph->next(i); }
188    void nextIn(Arc& i) const { _graph->nextIn(i); }
189    void nextOut(Arc& i) const { _graph->nextOut(i); }
190    void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
191
192    Node u(const Edge& e) const { return _graph->u(e); }
193    Node v(const Edge& e) const { return _graph->v(e); }
194
195    Node source(const Arc& a) const { return _graph->source(a); }
196    Node target(const Arc& a) const { return _graph->target(a); }
197
198    typedef NodeNumTagIndicator<Graph> NodeNumTag;
199    int nodeNum() const { return _graph->nodeNum(); }
200
201    typedef ArcNumTagIndicator<Graph> ArcNumTag;
202    int arcNum() const { return _graph->arcNum(); }
203
204    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
205    int edgeNum() const { return _graph->edgeNum(); }
206
207    typedef FindArcTagIndicator<Graph> FindArcTag;
208    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
209      return _graph->findArc(u, v, prev);
210    }
211
212    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
213    Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
214      return _graph->findEdge(u, v, prev);
215    }
216
217    Node addNode() { return _graph->addNode(); }
218    Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
219
220    void erase(const Node& i) { _graph->erase(i); }
221    void erase(const Edge& i) { _graph->erase(i); }
222
223    void clear() { _graph->clear(); }
224
225    bool direction(const Arc& a) const { return _graph->direction(a); }
226    Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
227
228    int id(const Node& v) const { return _graph->id(v); }
229    int id(const Arc& a) const { return _graph->id(a); }
230    int id(const Edge& e) const { return _graph->id(e); }
231
232    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
233    Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
234    Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
235
236    int maxNodeId() const { return _graph->maxNodeId(); }
237    int maxArcId() const { return _graph->maxArcId(); }
238    int maxEdgeId() const { return _graph->maxEdgeId(); }
239
240    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
241    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
242
243    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
244    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
245
246    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
247    EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
248
249    template <typename _Value>
250    class NodeMap : public Graph::template NodeMap<_Value> {
251    public:
252      typedef typename Graph::template NodeMap<_Value> Parent;
253      explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
254        : Parent(*adapter._graph) {}
255      NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
256        : Parent(*adapter._graph, value) {}
257
258    private:
259      NodeMap& operator=(const NodeMap& cmap) {
260        return operator=<NodeMap>(cmap);
261      }
262
263      template <typename CMap>
264      NodeMap& operator=(const CMap& cmap) {
265        Parent::operator=(cmap);
266        return *this;
267      }
268
269    };
270
271    template <typename _Value>
272    class ArcMap : public Graph::template ArcMap<_Value> {
273    public:
274      typedef typename Graph::template ArcMap<_Value> Parent;
275      explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
276        : Parent(*adapter._graph) {}
277      ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
278        : Parent(*adapter._graph, value) {}
279
280    private:
281      ArcMap& operator=(const ArcMap& cmap) {
282        return operator=<ArcMap>(cmap);
283      }
284
285      template <typename CMap>
286      ArcMap& operator=(const CMap& cmap) {
287        Parent::operator=(cmap);
288        return *this;
289      }
290    };
291
292    template <typename _Value>
293    class EdgeMap : public Graph::template EdgeMap<_Value> {
294    public:
295      typedef typename Graph::template EdgeMap<_Value> Parent;
296      explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
297        : Parent(*adapter._graph) {}
298      EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
299        : Parent(*adapter._graph, value) {}
300
301    private:
302      EdgeMap& operator=(const EdgeMap& cmap) {
303        return operator=<EdgeMap>(cmap);
304      }
305
306      template <typename CMap>
307      EdgeMap& operator=(const CMap& cmap) {
308        Parent::operator=(cmap);
309        return *this;
310      }
311    };
312
313  };
314
315  template <typename _Digraph>
316  class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
317  public:
318    typedef _Digraph Digraph;
319    typedef DigraphAdaptorBase<_Digraph> Parent;
320  protected:
321    ReverseDigraphBase() : Parent() { }
322  public:
323    typedef typename Parent::Node Node;
324    typedef typename Parent::Arc Arc;
325
326    void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
327    void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
328
329    void nextIn(Arc& a) const { Parent::nextOut(a); }
330    void nextOut(Arc& a) const { Parent::nextIn(a); }
331
332    Node source(const Arc& a) const { return Parent::target(a); }
333    Node target(const Arc& a) const { return Parent::source(a); }
334
335    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
336
337    typedef FindArcTagIndicator<Digraph> FindArcTag;
338    Arc findArc(const Node& u, const Node& v,
339                const Arc& prev = INVALID) {
340      return Parent::findArc(v, u, prev);
341    }
342
343  };
344
345  /// \ingroup graph_adaptors
346  ///
347  /// \brief A digraph adaptor which reverses the orientation of the arcs.
348  ///
349  /// ReverseDigraph reverses the arcs in the adapted digraph. The
350  /// SubDigraph is conform to the \ref concepts::Digraph
351  /// "Digraph concept".
352  ///
353  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
354  /// "Digraph concept". The type can be specified to be const.
355  template<typename _Digraph>
356  class ReverseDigraph :
357    public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
358  public:
359    typedef _Digraph Digraph;
360    typedef DigraphAdaptorExtender<
361      ReverseDigraphBase<_Digraph> > Parent;
362  protected:
363    ReverseDigraph() { }
364  public:
365
366    /// \brief Constructor
367    ///
368    /// Creates a reverse digraph adaptor for the given digraph
369    explicit ReverseDigraph(Digraph& digraph) {
370      Parent::setDigraph(digraph);
371    }
372  };
373
374  /// \brief Just gives back a reverse digraph adaptor
375  ///
376  /// Just gives back a reverse digraph adaptor
377  template<typename Digraph>
378  ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
379    return ReverseDigraph<const Digraph>(digraph);
380  }
381
382  template <typename _Digraph, typename _NodeFilterMap,
383            typename _ArcFilterMap, bool _checked = true>
384  class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
385  public:
386    typedef _Digraph Digraph;
387    typedef _NodeFilterMap NodeFilterMap;
388    typedef _ArcFilterMap ArcFilterMap;
389
390    typedef SubDigraphBase Adaptor;
391    typedef DigraphAdaptorBase<_Digraph> Parent;
392  protected:
393    NodeFilterMap* _node_filter;
394    ArcFilterMap* _arc_filter;
395    SubDigraphBase()
396      : Parent(), _node_filter(0), _arc_filter(0) { }
397
398    void setNodeFilterMap(NodeFilterMap& node_filter) {
399      _node_filter = &node_filter;
400    }
401    void setArcFilterMap(ArcFilterMap& arc_filter) {
402      _arc_filter = &arc_filter;
403    }
404
405  public:
406
407    typedef typename Parent::Node Node;
408    typedef typename Parent::Arc Arc;
409
410    void first(Node& i) const {
411      Parent::first(i);
412      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
413    }
414
415    void first(Arc& i) const {
416      Parent::first(i);
417      while (i != INVALID && (!(*_arc_filter)[i]
418                              || !(*_node_filter)[Parent::source(i)]
419                              || !(*_node_filter)[Parent::target(i)]))
420        Parent::next(i);
421    }
422
423    void firstIn(Arc& i, const Node& n) const {
424      Parent::firstIn(i, n);
425      while (i != INVALID && (!(*_arc_filter)[i]
426                              || !(*_node_filter)[Parent::source(i)]))
427        Parent::nextIn(i);
428    }
429
430    void firstOut(Arc& i, const Node& n) const {
431      Parent::firstOut(i, n);
432      while (i != INVALID && (!(*_arc_filter)[i]
433                              || !(*_node_filter)[Parent::target(i)]))
434        Parent::nextOut(i);
435    }
436
437    void next(Node& i) const {
438      Parent::next(i);
439      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
440    }
441
442    void next(Arc& i) const {
443      Parent::next(i);
444      while (i != INVALID && (!(*_arc_filter)[i]
445                              || !(*_node_filter)[Parent::source(i)]
446                              || !(*_node_filter)[Parent::target(i)]))
447        Parent::next(i);
448    }
449
450    void nextIn(Arc& i) const {
451      Parent::nextIn(i);
452      while (i != INVALID && (!(*_arc_filter)[i]
453                              || !(*_node_filter)[Parent::source(i)]))
454        Parent::nextIn(i);
455    }
456
457    void nextOut(Arc& i) const {
458      Parent::nextOut(i);
459      while (i != INVALID && (!(*_arc_filter)[i]
460                              || !(*_node_filter)[Parent::target(i)]))
461        Parent::nextOut(i);
462    }
463
464    void hide(const Node& n) const { _node_filter->set(n, false); }
465    void hide(const Arc& a) const { _arc_filter->set(a, false); }
466
467    void unHide(const Node& n) const { _node_filter->set(n, true); }
468    void unHide(const Arc& a) const { _arc_filter->set(a, true); }
469
470    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
471    bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
472
473    typedef False NodeNumTag;
474    typedef False ArcNumTag;
475
476    typedef FindArcTagIndicator<Digraph> FindArcTag;
477    Arc findArc(const Node& source, const Node& target,
478                const Arc& prev = INVALID) {
479      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
480        return INVALID;
481      }
482      Arc arc = Parent::findArc(source, target, prev);
483      while (arc != INVALID && !(*_arc_filter)[arc]) {
484        arc = Parent::findArc(source, target, arc);
485      }
486      return arc;
487    }
488
489    template <typename _Value>
490    class NodeMap : public SubMapExtender<Adaptor,
491      typename Parent::template NodeMap<_Value> > {
492    public:
493      typedef _Value Value;
494      typedef SubMapExtender<Adaptor, typename Parent::
495                             template NodeMap<Value> > MapParent;
496
497      NodeMap(const Adaptor& adaptor)
498        : MapParent(adaptor) {}
499      NodeMap(const Adaptor& adaptor, const Value& value)
500        : MapParent(adaptor, value) {}
501
502    private:
503      NodeMap& operator=(const NodeMap& cmap) {
504        return operator=<NodeMap>(cmap);
505      }
506
507      template <typename CMap>
508      NodeMap& operator=(const CMap& cmap) {
509        MapParent::operator=(cmap);
510        return *this;
511      }
512    };
513
514    template <typename _Value>
515    class ArcMap : public SubMapExtender<Adaptor,
516      typename Parent::template ArcMap<_Value> > {
517    public:
518      typedef _Value Value;
519      typedef SubMapExtender<Adaptor, typename Parent::
520                             template ArcMap<Value> > MapParent;
521
522      ArcMap(const Adaptor& adaptor)
523        : MapParent(adaptor) {}
524      ArcMap(const Adaptor& adaptor, const Value& value)
525        : MapParent(adaptor, value) {}
526
527    private:
528      ArcMap& operator=(const ArcMap& cmap) {
529        return operator=<ArcMap>(cmap);
530      }
531
532      template <typename CMap>
533      ArcMap& operator=(const CMap& cmap) {
534        MapParent::operator=(cmap);
535        return *this;
536      }
537    };
538
539  };
540
541  template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
542  class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
543    : public DigraphAdaptorBase<_Digraph> {
544  public:
545    typedef _Digraph Digraph;
546    typedef _NodeFilterMap NodeFilterMap;
547    typedef _ArcFilterMap ArcFilterMap;
548
549    typedef SubDigraphBase Adaptor;
550    typedef DigraphAdaptorBase<Digraph> Parent;
551  protected:
552    NodeFilterMap* _node_filter;
553    ArcFilterMap* _arc_filter;
554    SubDigraphBase()
555      : Parent(), _node_filter(0), _arc_filter(0) { }
556
557    void setNodeFilterMap(NodeFilterMap& node_filter) {
558      _node_filter = &node_filter;
559    }
560    void setArcFilterMap(ArcFilterMap& arc_filter) {
561      _arc_filter = &arc_filter;
562    }
563
564  public:
565
566    typedef typename Parent::Node Node;
567    typedef typename Parent::Arc Arc;
568
569    void first(Node& i) const {
570      Parent::first(i);
571      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
572    }
573
574    void first(Arc& i) const {
575      Parent::first(i);
576      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
577    }
578
579    void firstIn(Arc& i, const Node& n) const {
580      Parent::firstIn(i, n);
581      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
582    }
583
584    void firstOut(Arc& i, const Node& n) const {
585      Parent::firstOut(i, n);
586      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
587    }
588
589    void next(Node& i) const {
590      Parent::next(i);
591      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
592    }
593    void next(Arc& i) const {
594      Parent::next(i);
595      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
596    }
597    void nextIn(Arc& i) const {
598      Parent::nextIn(i);
599      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
600    }
601
602    void nextOut(Arc& i) const {
603      Parent::nextOut(i);
604      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
605    }
606
607    void hide(const Node& n) const { _node_filter->set(n, false); }
608    void hide(const Arc& e) const { _arc_filter->set(e, false); }
609
610    void unHide(const Node& n) const { _node_filter->set(n, true); }
611    void unHide(const Arc& e) const { _arc_filter->set(e, true); }
612
613    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
614    bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
615
616    typedef False NodeNumTag;
617    typedef False ArcNumTag;
618
619    typedef FindArcTagIndicator<Digraph> FindArcTag;
620    Arc findArc(const Node& source, const Node& target,
621                const Arc& prev = INVALID) {
622      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
623        return INVALID;
624      }
625      Arc arc = Parent::findArc(source, target, prev);
626      while (arc != INVALID && !(*_arc_filter)[arc]) {
627        arc = Parent::findArc(source, target, arc);
628      }
629      return arc;
630    }
631
632    template <typename _Value>
633    class NodeMap : public SubMapExtender<Adaptor,
634      typename Parent::template NodeMap<_Value> > {
635    public:
636      typedef _Value Value;
637      typedef SubMapExtender<Adaptor, typename Parent::
638                             template NodeMap<Value> > MapParent;
639
640      NodeMap(const Adaptor& adaptor)
641        : MapParent(adaptor) {}
642      NodeMap(const Adaptor& adaptor, const Value& value)
643        : MapParent(adaptor, value) {}
644
645    private:
646      NodeMap& operator=(const NodeMap& cmap) {
647        return operator=<NodeMap>(cmap);
648      }
649
650      template <typename CMap>
651      NodeMap& operator=(const CMap& cmap) {
652        MapParent::operator=(cmap);
653        return *this;
654      }
655    };
656
657    template <typename _Value>
658    class ArcMap : public SubMapExtender<Adaptor,
659      typename Parent::template ArcMap<_Value> > {
660    public:
661      typedef _Value Value;
662      typedef SubMapExtender<Adaptor, typename Parent::
663                             template ArcMap<Value> > MapParent;
664
665      ArcMap(const Adaptor& adaptor)
666        : MapParent(adaptor) {}
667      ArcMap(const Adaptor& adaptor, const Value& value)
668        : MapParent(adaptor, value) {}
669
670    private:
671      ArcMap& operator=(const ArcMap& cmap) {
672        return operator=<ArcMap>(cmap);
673      }
674
675      template <typename CMap>
676      ArcMap& operator=(const CMap& cmap) {
677        MapParent::operator=(cmap);
678        return *this;
679      }
680    };
681
682  };
683
684  /// \ingroup graph_adaptors
685  ///
686  /// \brief An adaptor for hiding nodes and arcs in a digraph
687  ///
688  /// SubDigraph hides nodes and arcs in a digraph. A bool node map
689  /// and a bool arc map must be specified, which define the filters
690  /// for nodes and arcs. Just the nodes and arcs with true value are
691  /// shown in the subdigraph. The SubDigraph is conform to the \ref
692  /// concepts::Digraph "Digraph concept". If the \c _checked parameter
693  /// is true, then the arcs incident to filtered nodes are also
694  /// filtered out.
695  ///
696  /// \tparam _Digraph It must be conform to the \ref
697  /// concepts::Digraph "Digraph concept". The type can be specified
698  /// to const.
699  /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph.
700  /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph.
701  /// \tparam _checked If the parameter is false then the arc filtering
702  /// is not checked with respect to node filter. Otherwise, each arc
703  /// is automatically filtered, which is incident to a filtered node.
704  ///
705  /// \see FilterNodes
706  /// \see FilterArcs
707  template<typename _Digraph,
708           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
709           typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
710           bool _checked = true>
711  class SubDigraph
712    : public DigraphAdaptorExtender<
713      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
714  public:
715    typedef _Digraph Digraph;
716    typedef _NodeFilterMap NodeFilterMap;
717    typedef _ArcFilterMap ArcFilterMap;
718
719    typedef DigraphAdaptorExtender<
720      SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >
721    Parent;
722
723    typedef typename Parent::Node Node;
724    typedef typename Parent::Arc Arc;
725
726  protected:
727    SubDigraph() { }
728  public:
729
730    /// \brief Constructor
731    ///
732    /// Creates a subdigraph for the given digraph with
733    /// given node and arc map filters.
734    SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
735               ArcFilterMap& arc_filter) {
736      setDigraph(digraph);
737      setNodeFilterMap(node_filter);
738      setArcFilterMap(arc_filter);
739    }
740
741    /// \brief Hides the node of the graph
742    ///
743    /// This function hides \c n in the digraph, i.e. the iteration
744    /// jumps over it. This is done by simply setting the value of \c n
745    /// to be false in the corresponding node-map.
746    void hide(const Node& n) const { Parent::hide(n); }
747
748    /// \brief Hides the arc of the graph
749    ///
750    /// This function hides \c a in the digraph, i.e. the iteration
751    /// jumps over it. This is done by simply setting the value of \c a
752    /// to be false in the corresponding arc-map.
753    void hide(const Arc& a) const { Parent::hide(a); }
754
755    /// \brief Unhides the node of the graph
756    ///
757    /// The value of \c n is set to be true in the node-map which stores
758    /// hide information. If \c n was hidden previuosly, then it is shown
759    /// again
760    void unHide(const Node& n) const { Parent::unHide(n); }
761
762    /// \brief Unhides the arc of the graph
763    ///
764    /// The value of \c a is set to be true in the arc-map which stores
765    /// hide information. If \c a was hidden previuosly, then it is shown
766    /// again
767    void unHide(const Arc& a) const { Parent::unHide(a); }
768
769    /// \brief Returns true if \c n is hidden.
770    ///
771    /// Returns true if \c n is hidden.
772    ///
773    bool hidden(const Node& n) const { return Parent::hidden(n); }
774
775    /// \brief Returns true if \c a is hidden.
776    ///
777    /// Returns true if \c a is hidden.
778    ///
779    bool hidden(const Arc& a) const { return Parent::hidden(a); }
780
781  };
782
783  /// \brief Just gives back a subdigraph
784  ///
785  /// Just gives back a subdigraph
786  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
787  SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
788  subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
789    return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
790      (digraph, nfm, afm);
791  }
792
793  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
794  SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
795  subDigraph(const Digraph& digraph,
796             const NodeFilterMap& nfm, ArcFilterMap& afm) {
797    return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
798      (digraph, nfm, afm);
799  }
800
801  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
802  SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
803  subDigraph(const Digraph& digraph,
804             NodeFilterMap& nfm, const ArcFilterMap& afm) {
805    return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
806      (digraph, nfm, afm);
807  }
808
809  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
810  SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>
811  subDigraph(const Digraph& digraph,
812             const NodeFilterMap& nfm, const ArcFilterMap& afm) {
813    return SubDigraph<const Digraph, const NodeFilterMap,
814      const ArcFilterMap>(digraph, nfm, afm);
815  }
816
817
818  template <typename _Graph, typename NodeFilterMap,
819            typename EdgeFilterMap, bool _checked = true>
820  class SubGraphBase : public GraphAdaptorBase<_Graph> {
821  public:
822    typedef _Graph Graph;
823    typedef SubGraphBase Adaptor;
824    typedef GraphAdaptorBase<_Graph> Parent;
825  protected:
826
827    NodeFilterMap* _node_filter_map;
828    EdgeFilterMap* _edge_filter_map;
829
830    SubGraphBase()
831      : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
832
833    void setNodeFilterMap(NodeFilterMap& node_filter_map) {
834      _node_filter_map=&node_filter_map;
835    }
836    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
837      _edge_filter_map=&edge_filter_map;
838    }
839
840  public:
841
842    typedef typename Parent::Node Node;
843    typedef typename Parent::Arc Arc;
844    typedef typename Parent::Edge Edge;
845
846    void first(Node& i) const {
847      Parent::first(i);
848      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
849    }
850
851    void first(Arc& i) const {
852      Parent::first(i);
853      while (i!=INVALID && (!(*_edge_filter_map)[i]
854                            || !(*_node_filter_map)[Parent::source(i)]
855                            || !(*_node_filter_map)[Parent::target(i)]))
856        Parent::next(i);
857    }
858
859    void first(Edge& i) const {
860      Parent::first(i);
861      while (i!=INVALID && (!(*_edge_filter_map)[i]
862                            || !(*_node_filter_map)[Parent::u(i)]
863                            || !(*_node_filter_map)[Parent::v(i)]))
864        Parent::next(i);
865    }
866
867    void firstIn(Arc& i, const Node& n) const {
868      Parent::firstIn(i, n);
869      while (i!=INVALID && (!(*_edge_filter_map)[i]
870                            || !(*_node_filter_map)[Parent::source(i)]))
871        Parent::nextIn(i);
872    }
873
874    void firstOut(Arc& i, const Node& n) const {
875      Parent::firstOut(i, n);
876      while (i!=INVALID && (!(*_edge_filter_map)[i]
877                            || !(*_node_filter_map)[Parent::target(i)]))
878        Parent::nextOut(i);
879    }
880
881    void firstInc(Edge& i, bool& d, const Node& n) const {
882      Parent::firstInc(i, d, n);
883      while (i!=INVALID && (!(*_edge_filter_map)[i]
884                            || !(*_node_filter_map)[Parent::u(i)]
885                            || !(*_node_filter_map)[Parent::v(i)]))
886        Parent::nextInc(i, d);
887    }
888
889    void next(Node& i) const {
890      Parent::next(i);
891      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
892    }
893
894    void next(Arc& i) const {
895      Parent::next(i);
896      while (i!=INVALID && (!(*_edge_filter_map)[i]
897                            || !(*_node_filter_map)[Parent::source(i)]
898                            || !(*_node_filter_map)[Parent::target(i)]))
899        Parent::next(i);
900    }
901
902    void next(Edge& i) const {
903      Parent::next(i);
904      while (i!=INVALID && (!(*_edge_filter_map)[i]
905                            || !(*_node_filter_map)[Parent::u(i)]
906                            || !(*_node_filter_map)[Parent::v(i)]))
907        Parent::next(i);
908    }
909
910    void nextIn(Arc& i) const {
911      Parent::nextIn(i);
912      while (i!=INVALID && (!(*_edge_filter_map)[i]
913                            || !(*_node_filter_map)[Parent::source(i)]))
914        Parent::nextIn(i);
915    }
916
917    void nextOut(Arc& i) const {
918      Parent::nextOut(i);
919      while (i!=INVALID && (!(*_edge_filter_map)[i]
920                            || !(*_node_filter_map)[Parent::target(i)]))
921        Parent::nextOut(i);
922    }
923
924    void nextInc(Edge& i, bool& d) const {
925      Parent::nextInc(i, d);
926      while (i!=INVALID && (!(*_edge_filter_map)[i]
927                            || !(*_node_filter_map)[Parent::u(i)]
928                            || !(*_node_filter_map)[Parent::v(i)]))
929        Parent::nextInc(i, d);
930    }
931
932    void hide(const Node& n) const { _node_filter_map->set(n, false); }
933    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
934
935    void unHide(const Node& n) const { _node_filter_map->set(n, true); }
936    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
937
938    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
939    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
940
941    typedef False NodeNumTag;
942    typedef False ArcNumTag;
943    typedef False EdgeNumTag;
944
945    typedef FindArcTagIndicator<Graph> FindArcTag;
946    Arc findArc(const Node& u, const Node& v,
947                const Arc& prev = INVALID) {
948      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
949        return INVALID;
950      }
951      Arc arc = Parent::findArc(u, v, prev);
952      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
953        arc = Parent::findArc(u, v, arc);
954      }
955      return arc;
956    }
957
958    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
959    Edge findEdge(const Node& u, const Node& v,
960                  const Edge& prev = INVALID) {
961      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
962        return INVALID;
963      }
964      Edge edge = Parent::findEdge(u, v, prev);
965      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
966        edge = Parent::findEdge(u, v, edge);
967      }
968      return edge;
969    }
970
971    template <typename _Value>
972    class NodeMap : public SubMapExtender<Adaptor,
973      typename Parent::template NodeMap<_Value> > {
974    public:
975      typedef _Value Value;
976      typedef SubMapExtender<Adaptor, typename Parent::
977                             template NodeMap<Value> > MapParent;
978
979      NodeMap(const Adaptor& adaptor)
980        : MapParent(adaptor) {}
981      NodeMap(const Adaptor& adaptor, const Value& value)
982        : MapParent(adaptor, value) {}
983
984    private:
985      NodeMap& operator=(const NodeMap& cmap) {
986        return operator=<NodeMap>(cmap);
987      }
988
989      template <typename CMap>
990      NodeMap& operator=(const CMap& cmap) {
991        MapParent::operator=(cmap);
992        return *this;
993      }
994    };
995
996    template <typename _Value>
997    class ArcMap : public SubMapExtender<Adaptor,
998      typename Parent::template ArcMap<_Value> > {
999    public:
1000      typedef _Value Value;
1001      typedef SubMapExtender<Adaptor, typename Parent::
1002                             template ArcMap<Value> > MapParent;
1003
1004      ArcMap(const Adaptor& adaptor)
1005        : MapParent(adaptor) {}
1006      ArcMap(const Adaptor& adaptor, const Value& value)
1007        : MapParent(adaptor, value) {}
1008
1009    private:
1010      ArcMap& operator=(const ArcMap& cmap) {
1011        return operator=<ArcMap>(cmap);
1012      }
1013
1014      template <typename CMap>
1015      ArcMap& operator=(const CMap& cmap) {
1016        MapParent::operator=(cmap);
1017        return *this;
1018      }
1019    };
1020
1021    template <typename _Value>
1022    class EdgeMap : public SubMapExtender<Adaptor,
1023      typename Parent::template EdgeMap<_Value> > {
1024    public:
1025      typedef _Value Value;
1026      typedef SubMapExtender<Adaptor, typename Parent::
1027                             template EdgeMap<Value> > MapParent;
1028
1029      EdgeMap(const Adaptor& adaptor)
1030        : MapParent(adaptor) {}
1031
1032      EdgeMap(const Adaptor& adaptor, const Value& value)
1033        : MapParent(adaptor, value) {}
1034
1035    private:
1036      EdgeMap& operator=(const EdgeMap& cmap) {
1037        return operator=<EdgeMap>(cmap);
1038      }
1039
1040      template <typename CMap>
1041      EdgeMap& operator=(const CMap& cmap) {
1042        MapParent::operator=(cmap);
1043        return *this;
1044      }
1045    };
1046
1047  };
1048
1049  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
1050  class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
1051    : public GraphAdaptorBase<_Graph> {
1052  public:
1053    typedef _Graph Graph;
1054    typedef SubGraphBase Adaptor;
1055    typedef GraphAdaptorBase<_Graph> Parent;
1056  protected:
1057    NodeFilterMap* _node_filter_map;
1058    EdgeFilterMap* _edge_filter_map;
1059    SubGraphBase() : Parent(),
1060                     _node_filter_map(0), _edge_filter_map(0) { }
1061
1062    void setNodeFilterMap(NodeFilterMap& node_filter_map) {
1063      _node_filter_map=&node_filter_map;
1064    }
1065    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
1066      _edge_filter_map=&edge_filter_map;
1067    }
1068
1069  public:
1070
1071    typedef typename Parent::Node Node;
1072    typedef typename Parent::Arc Arc;
1073    typedef typename Parent::Edge Edge;
1074
1075    void first(Node& i) const {
1076      Parent::first(i);
1077      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1078    }
1079
1080    void first(Arc& i) const {
1081      Parent::first(i);
1082      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1083    }
1084
1085    void first(Edge& i) const {
1086      Parent::first(i);
1087      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1088    }
1089
1090    void firstIn(Arc& i, const Node& n) const {
1091      Parent::firstIn(i, n);
1092      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
1093    }
1094
1095    void firstOut(Arc& i, const Node& n) const {
1096      Parent::firstOut(i, n);
1097      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
1098    }
1099
1100    void firstInc(Edge& i, bool& d, const Node& n) const {
1101      Parent::firstInc(i, d, n);
1102      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1103    }
1104
1105    void next(Node& i) const {
1106      Parent::next(i);
1107      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1108    }
1109    void next(Arc& i) const {
1110      Parent::next(i);
1111      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1112    }
1113    void next(Edge& i) const {
1114      Parent::next(i);
1115      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1116    }
1117    void nextIn(Arc& i) const {
1118      Parent::nextIn(i);
1119      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
1120    }
1121
1122    void nextOut(Arc& i) const {
1123      Parent::nextOut(i);
1124      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
1125    }
1126    void nextInc(Edge& i, bool& d) const {
1127      Parent::nextInc(i, d);
1128      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1129    }
1130
1131    void hide(const Node& n) const { _node_filter_map->set(n, false); }
1132    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
1133
1134    void unHide(const Node& n) const { _node_filter_map->set(n, true); }
1135    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
1136
1137    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
1138    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
1139
1140    typedef False NodeNumTag;
1141    typedef False ArcNumTag;
1142    typedef False EdgeNumTag;
1143
1144    typedef FindArcTagIndicator<Graph> FindArcTag;
1145    Arc findArc(const Node& u, const Node& v,
1146                const Arc& prev = INVALID) {
1147      Arc arc = Parent::findArc(u, v, prev);
1148      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
1149        arc = Parent::findArc(u, v, arc);
1150      }
1151      return arc;
1152    }
1153
1154    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1155    Edge findEdge(const Node& u, const Node& v,
1156                  const Edge& prev = INVALID) {
1157      Edge edge = Parent::findEdge(u, v, prev);
1158      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
1159        edge = Parent::findEdge(u, v, edge);
1160      }
1161      return edge;
1162    }
1163
1164    template <typename _Value>
1165    class NodeMap : public SubMapExtender<Adaptor,
1166      typename Parent::template NodeMap<_Value> > {
1167    public:
1168      typedef _Value Value;
1169      typedef SubMapExtender<Adaptor, typename Parent::
1170                             template NodeMap<Value> > MapParent;
1171
1172      NodeMap(const Adaptor& adaptor)
1173        : MapParent(adaptor) {}
1174      NodeMap(const Adaptor& adaptor, const Value& value)
1175        : MapParent(adaptor, value) {}
1176
1177    private:
1178      NodeMap& operator=(const NodeMap& cmap) {
1179        return operator=<NodeMap>(cmap);
1180      }
1181
1182      template <typename CMap>
1183      NodeMap& operator=(const CMap& cmap) {
1184        MapParent::operator=(cmap);
1185        return *this;
1186      }
1187    };
1188
1189    template <typename _Value>
1190    class ArcMap : public SubMapExtender<Adaptor,
1191      typename Parent::template ArcMap<_Value> > {
1192    public:
1193      typedef _Value Value;
1194      typedef SubMapExtender<Adaptor, typename Parent::
1195                             template ArcMap<Value> > MapParent;
1196
1197      ArcMap(const Adaptor& adaptor)
1198        : MapParent(adaptor) {}
1199      ArcMap(const Adaptor& adaptor, const Value& value)
1200        : MapParent(adaptor, value) {}
1201
1202    private:
1203      ArcMap& operator=(const ArcMap& cmap) {
1204        return operator=<ArcMap>(cmap);
1205      }
1206
1207      template <typename CMap>
1208      ArcMap& operator=(const CMap& cmap) {
1209        MapParent::operator=(cmap);
1210        return *this;
1211      }
1212    };
1213
1214    template <typename _Value>
1215    class EdgeMap : public SubMapExtender<Adaptor,
1216      typename Parent::template EdgeMap<_Value> > {
1217    public:
1218      typedef _Value Value;
1219      typedef SubMapExtender<Adaptor, typename Parent::
1220                             template EdgeMap<Value> > MapParent;
1221
1222      EdgeMap(const Adaptor& adaptor)
1223        : MapParent(adaptor) {}
1224
1225      EdgeMap(const Adaptor& adaptor, const _Value& value)
1226        : MapParent(adaptor, value) {}
1227
1228    private:
1229      EdgeMap& operator=(const EdgeMap& cmap) {
1230        return operator=<EdgeMap>(cmap);
1231      }
1232
1233      template <typename CMap>
1234      EdgeMap& operator=(const CMap& cmap) {
1235        MapParent::operator=(cmap);
1236        return *this;
1237      }
1238    };
1239
1240  };
1241
1242  /// \ingroup graph_adaptors
1243  ///
1244  /// \brief A graph adaptor for hiding nodes and edges in an
1245  /// undirected graph.
1246  ///
1247  /// SubGraph hides nodes and edges in a graph. A bool node map and a
1248  /// bool edge map must be specified, which define the filters for
1249  /// nodes and edges. Just the nodes and edges with true value are
1250  /// shown in the subgraph. The SubGraph is conform to the \ref
1251  /// concepts::Graph "Graph concept". If the \c _checked parameter is
1252  /// true, then the edges incident to filtered nodes are also
1253  /// filtered out.
1254  ///
1255  /// \tparam _Graph It must be conform to the \ref
1256  /// concepts::Graph "Graph concept". The type can be specified
1257  /// to const.
1258  /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
1259  /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph.
1260  /// \tparam _checked If the parameter is false then the edge filtering
1261  /// is not checked with respect to node filter. Otherwise, each edge
1262  /// is automatically filtered, which is incident to a filtered node.
1263  ///
1264  /// \see FilterNodes
1265  /// \see FilterEdges
1266  template<typename _Graph, typename NodeFilterMap,
1267           typename EdgeFilterMap, bool _checked = true>
1268  class SubGraph
1269    : public GraphAdaptorExtender<
1270      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {
1271  public:
1272    typedef _Graph Graph;
1273    typedef GraphAdaptorExtender<
1274      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
1275
1276    typedef typename Parent::Node Node;
1277    typedef typename Parent::Edge Edge;
1278
1279  protected:
1280    SubGraph() { }
1281  public:
1282
1283    /// \brief Constructor
1284    ///
1285    /// Creates a subgraph for the given graph with given node and
1286    /// edge map filters.
1287    SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,
1288             EdgeFilterMap& edge_filter_map) {
1289      setGraph(_graph);
1290      setNodeFilterMap(node_filter_map);
1291      setEdgeFilterMap(edge_filter_map);
1292    }
1293
1294    /// \brief Hides the node of the graph
1295    ///
1296    /// This function hides \c n in the graph, i.e. the iteration
1297    /// jumps over it. This is done by simply setting the value of \c n
1298    /// to be false in the corresponding node-map.
1299    void hide(const Node& n) const { Parent::hide(n); }
1300
1301    /// \brief Hides the edge of the graph
1302    ///
1303    /// This function hides \c e in the graph, i.e. the iteration
1304    /// jumps over it. This is done by simply setting the value of \c e
1305    /// to be false in the corresponding edge-map.
1306    void hide(const Edge& e) const { Parent::hide(e); }
1307
1308    /// \brief Unhides the node of the graph
1309    ///
1310    /// The value of \c n is set to be true in the node-map which stores
1311    /// hide information. If \c n was hidden previuosly, then it is shown
1312    /// again
1313    void unHide(const Node& n) const { Parent::unHide(n); }
1314
1315    /// \brief Unhides the edge of the graph
1316    ///
1317    /// The value of \c e is set to be true in the edge-map which stores
1318    /// hide information. If \c e was hidden previuosly, then it is shown
1319    /// again
1320    void unHide(const Edge& e) const { Parent::unHide(e); }
1321
1322    /// \brief Returns true if \c n is hidden.
1323    ///
1324    /// Returns true if \c n is hidden.
1325    ///
1326    bool hidden(const Node& n) const { return Parent::hidden(n); }
1327
1328    /// \brief Returns true if \c e is hidden.
1329    ///
1330    /// Returns true if \c e is hidden.
1331    ///
1332    bool hidden(const Edge& e) const { return Parent::hidden(e); }
1333  };
1334
1335  /// \brief Just gives back a subgraph
1336  ///
1337  /// Just gives back a subgraph
1338  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1339  SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
1340  subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
1341    return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);
1342  }
1343
1344  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1345  SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
1346  subGraph(const Graph& graph,
1347           const NodeFilterMap& nfm, ArcFilterMap& efm) {
1348    return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
1349      (graph, nfm, efm);
1350  }
1351
1352  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1353  SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
1354  subGraph(const Graph& graph,
1355           NodeFilterMap& nfm, const ArcFilterMap& efm) {
1356    return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
1357      (graph, nfm, efm);
1358  }
1359
1360  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1361  SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
1362  subGraph(const Graph& graph,
1363           const NodeFilterMap& nfm, const ArcFilterMap& efm) {
1364    return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
1365      (graph, nfm, efm);
1366  }
1367
1368  /// \ingroup graph_adaptors
1369  ///
1370  /// \brief An adaptor for hiding nodes from a digraph or a graph.
1371  ///
1372  /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool
1373  /// node map must be specified, which defines the filters for
1374  /// nodes. Just the unfiltered nodes and the arcs or edges incident
1375  /// to unfiltered nodes are shown in the subdigraph or subgraph. The
1376  /// FilterNodes is conform to the \ref concepts::Digraph
1377  /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending
1378  /// on the \c _Digraph template parameter. If the \c _checked
1379  /// parameter is true, then the arc or edges incident to filtered nodes
1380  /// are also filtered out.
1381  ///
1382  /// \tparam _Digraph It must be conform to the \ref
1383  /// concepts::Digraph "Digraph concept" or \ref concepts::Graph
1384  /// "Graph concept". The type can be specified to be const.
1385  /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
1386  /// \tparam _checked If the parameter is false then the arc or edge
1387  /// filtering is not checked with respect to node filter. In this
1388  /// case just isolated nodes can be filtered out from the
1389  /// graph.
1390#ifdef DOXYGEN
1391  template<typename _Digraph,
1392           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
1393           bool _checked = true>
1394#else
1395  template<typename _Digraph,
1396           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
1397           bool _checked = true,
1398           typename Enable = void>
1399#endif
1400  class FilterNodes
1401    : public SubDigraph<_Digraph, _NodeFilterMap,
1402                        ConstMap<typename _Digraph::Arc, bool>, _checked> {
1403  public:
1404
1405    typedef _Digraph Digraph;
1406    typedef _NodeFilterMap NodeFilterMap;
1407
1408    typedef SubDigraph<Digraph, NodeFilterMap,
1409                       ConstMap<typename Digraph::Arc, bool>, _checked>
1410    Parent;
1411
1412    typedef typename Parent::Node Node;
1413
1414  protected:
1415    ConstMap<typename Digraph::Arc, bool> const_true_map;
1416
1417    FilterNodes() : const_true_map(true) {
1418      Parent::setArcFilterMap(const_true_map);
1419    }
1420
1421  public:
1422
1423    /// \brief Constructor
1424    ///
1425    /// Creates an adaptor for the given digraph or graph with
1426    /// given node filter map.
1427    FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :
1428      Parent(), const_true_map(true) {
1429      Parent::setDigraph(_digraph);
1430      Parent::setNodeFilterMap(node_filter);
1431      Parent::setArcFilterMap(const_true_map);
1432    }
1433
1434    /// \brief Hides the node of the graph
1435    ///
1436    /// This function hides \c n in the digraph or graph, i.e. the iteration
1437    /// jumps over it. This is done by simply setting the value of \c n
1438    /// to be false in the corresponding node map.
1439    void hide(const Node& n) const { Parent::hide(n); }
1440
1441    /// \brief Unhides the node of the graph
1442    ///
1443    /// The value of \c n is set to be true in the node-map which stores
1444    /// hide information. If \c n was hidden previuosly, then it is shown
1445    /// again
1446    void unHide(const Node& n) const { Parent::unHide(n); }
1447
1448    /// \brief Returns true if \c n is hidden.
1449    ///
1450    /// Returns true if \c n is hidden.
1451    ///
1452    bool hidden(const Node& n) const { return Parent::hidden(n); }
1453
1454  };
1455
1456  template<typename _Graph, typename _NodeFilterMap, bool _checked>
1457  class FilterNodes<_Graph, _NodeFilterMap, _checked,
1458                    typename enable_if<UndirectedTagIndicator<_Graph> >::type>
1459    : public SubGraph<_Graph, _NodeFilterMap,
1460                      ConstMap<typename _Graph::Edge, bool>, _checked> {
1461  public:
1462    typedef _Graph Graph;
1463    typedef _NodeFilterMap NodeFilterMap;
1464    typedef SubGraph<Graph, NodeFilterMap,
1465                     ConstMap<typename Graph::Edge, bool> > Parent;
1466
1467    typedef typename Parent::Node Node;
1468  protected:
1469    ConstMap<typename Graph::Edge, bool> const_true_map;
1470
1471    FilterNodes() : const_true_map(true) {
1472      Parent::setEdgeFilterMap(const_true_map);
1473    }
1474
1475  public:
1476
1477    FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :
1478      Parent(), const_true_map(true) {
1479      Parent::setGraph(_graph);
1480      Parent::setNodeFilterMap(node_filter_map);
1481      Parent::setEdgeFilterMap(const_true_map);
1482    }
1483
1484    void hide(const Node& n) const { Parent::hide(n); }
1485    void unHide(const Node& n) const { Parent::unHide(n); }
1486    bool hidden(const Node& n) const { return Parent::hidden(n); }
1487
1488  };
1489
1490
1491  /// \brief Just gives back a FilterNodes adaptor
1492  ///
1493  /// Just gives back a FilterNodes adaptor
1494  template<typename Digraph, typename NodeFilterMap>
1495  FilterNodes<const Digraph, NodeFilterMap>
1496  filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
1497    return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
1498  }
1499
1500  template<typename Digraph, typename NodeFilterMap>
1501  FilterNodes<const Digraph, const NodeFilterMap>
1502  filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
1503    return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
1504  }
1505
1506  /// \ingroup graph_adaptors
1507  ///
1508  /// \brief An adaptor for hiding arcs from a digraph.
1509  ///
1510  /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must
1511  /// be specified, which defines the filters for arcs. Just the
1512  /// unfiltered arcs are shown in the subdigraph. The FilterArcs is
1513  /// conform to the \ref concepts::Digraph "Digraph concept".
1514  ///
1515  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
1516  /// "Digraph concept". The type can be specified to be const.
1517  /// \tparam _ArcFilterMap A bool valued arc map of the the adapted
1518  /// graph.
1519  template<typename _Digraph, typename _ArcFilterMap>
1520  class FilterArcs :
1521    public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
1522                      _ArcFilterMap, false> {
1523  public:
1524    typedef _Digraph Digraph;
1525    typedef _ArcFilterMap ArcFilterMap;
1526
1527    typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
1528                       ArcFilterMap, false> Parent;
1529
1530    typedef typename Parent::Arc Arc;
1531
1532  protected:
1533    ConstMap<typename Digraph::Node, bool> const_true_map;
1534
1535    FilterArcs() : const_true_map(true) {
1536      Parent::setNodeFilterMap(const_true_map);
1537    }
1538
1539  public:
1540
1541    /// \brief Constructor
1542    ///
1543    /// Creates a FilterArcs adaptor for the given graph with
1544    /// given arc map filter.
1545    FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
1546      : Parent(), const_true_map(true) {
1547      Parent::setDigraph(digraph);
1548      Parent::setNodeFilterMap(const_true_map);
1549      Parent::setArcFilterMap(arc_filter);
1550    }
1551
1552    /// \brief Hides the arc of the graph
1553    ///
1554    /// This function hides \c a in the graph, i.e. the iteration
1555    /// jumps over it. This is done by simply setting the value of \c a
1556    /// to be false in the corresponding arc map.
1557    void hide(const Arc& a) const { Parent::hide(a); }
1558
1559    /// \brief Unhides the arc of the graph
1560    ///
1561    /// The value of \c a is set to be true in the arc-map which stores
1562    /// hide information. If \c a was hidden previuosly, then it is shown
1563    /// again
1564    void unHide(const Arc& a) const { Parent::unHide(a); }
1565
1566    /// \brief Returns true if \c a is hidden.
1567    ///
1568    /// Returns true if \c a is hidden.
1569    ///
1570    bool hidden(const Arc& a) const { return Parent::hidden(a); }
1571
1572  };
1573
1574  /// \brief Just gives back an FilterArcs adaptor
1575  ///
1576  /// Just gives back an FilterArcs adaptor
1577  template<typename Digraph, typename ArcFilterMap>
1578  FilterArcs<const Digraph, ArcFilterMap>
1579  filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
1580    return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
1581  }
1582
1583  template<typename Digraph, typename ArcFilterMap>
1584  FilterArcs<const Digraph, const ArcFilterMap>
1585  filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
1586    return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
1587  }
1588
1589  /// \ingroup graph_adaptors
1590  ///
1591  /// \brief An adaptor for hiding edges from a graph.
1592  ///
1593  /// FilterEdges adaptor hides edges in a digraph. A bool edge map must
1594  /// be specified, which defines the filters for edges. Just the
1595  /// unfiltered edges are shown in the subdigraph. The FilterEdges is
1596  /// conform to the \ref concepts::Graph "Graph concept".
1597  ///
1598  /// \tparam _Graph It must be conform to the \ref concepts::Graph
1599  /// "Graph concept". The type can be specified to be const.
1600  /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted
1601  /// graph.
1602  template<typename _Graph, typename _EdgeFilterMap>
1603  class FilterEdges :
1604    public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
1605                    _EdgeFilterMap, false> {
1606  public:
1607    typedef _Graph Graph;
1608    typedef _EdgeFilterMap EdgeFilterMap;
1609    typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,
1610                     EdgeFilterMap, false> Parent;
1611    typedef typename Parent::Edge Edge;
1612  protected:
1613    ConstMap<typename Graph::Node, bool> const_true_map;
1614
1615    FilterEdges() : const_true_map(true) {
1616      Parent::setNodeFilterMap(const_true_map);
1617    }
1618
1619  public:
1620
1621    /// \brief Constructor
1622    ///
1623    /// Creates a FilterEdges adaptor for the given graph with
1624    /// given edge map filters.
1625    FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :
1626      Parent(), const_true_map(true) {
1627      Parent::setGraph(_graph);
1628      Parent::setNodeFilterMap(const_true_map);
1629      Parent::setEdgeFilterMap(edge_filter_map);
1630    }
1631
1632    /// \brief Hides the edge of the graph
1633    ///
1634    /// This function hides \c e in the graph, i.e. the iteration
1635    /// jumps over it. This is done by simply setting the value of \c e
1636    /// to be false in the corresponding edge-map.
1637    void hide(const Edge& e) const { Parent::hide(e); }
1638
1639    /// \brief Unhides the edge of the graph
1640    ///
1641    /// The value of \c e is set to be true in the edge-map which stores
1642    /// hide information. If \c e was hidden previuosly, then it is shown
1643    /// again
1644    void unHide(const Edge& e) const { Parent::unHide(e); }
1645
1646    /// \brief Returns true if \c e is hidden.
1647    ///
1648    /// Returns true if \c e is hidden.
1649    ///
1650    bool hidden(const Edge& e) const { return Parent::hidden(e); }
1651
1652  };
1653
1654  /// \brief Just gives back a FilterEdges adaptor
1655  ///
1656  /// Just gives back a FilterEdges adaptor
1657  template<typename Graph, typename EdgeFilterMap>
1658  FilterEdges<const Graph, EdgeFilterMap>
1659  filterEdges(const Graph& graph, EdgeFilterMap& efm) {
1660    return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);
1661  }
1662
1663  template<typename Graph, typename EdgeFilterMap>
1664  FilterEdges<const Graph, const EdgeFilterMap>
1665  filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
1666    return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);
1667  }
1668
1669  template <typename _Digraph>
1670  class UndirectorBase {
1671  public:
1672    typedef _Digraph Digraph;
1673    typedef UndirectorBase Adaptor;
1674
1675    typedef True UndirectedTag;
1676
1677    typedef typename Digraph::Arc Edge;
1678    typedef typename Digraph::Node Node;
1679
1680    class Arc : public Edge {
1681      friend class UndirectorBase;
1682    protected:
1683      bool _forward;
1684
1685      Arc(const Edge& edge, bool forward) :
1686        Edge(edge), _forward(forward) {}
1687
1688    public:
1689      Arc() {}
1690
1691      Arc(Invalid) : Edge(INVALID), _forward(true) {}
1692
1693      bool operator==(const Arc &other) const {
1694        return _forward == other._forward &&
1695          static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
1696      }
1697      bool operator!=(const Arc &other) const {
1698        return _forward != other._forward ||
1699          static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
1700      }
1701      bool operator<(const Arc &other) const {
1702        return _forward < other._forward ||
1703          (_forward == other._forward &&
1704           static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
1705      }
1706    };
1707
1708
1709
1710    void first(Node& n) const {
1711      _digraph->first(n);
1712    }
1713
1714    void next(Node& n) const {
1715      _digraph->next(n);
1716    }
1717
1718    void first(Arc& a) const {
1719      _digraph->first(a);
1720      a._forward = true;
1721    }
1722
1723    void next(Arc& a) const {
1724      if (a._forward) {
1725        a._forward = false;
1726      } else {
1727        _digraph->next(a);
1728        a._forward = true;
1729      }
1730    }
1731
1732    void first(Edge& e) const {
1733      _digraph->first(e);
1734    }
1735
1736    void next(Edge& e) const {
1737      _digraph->next(e);
1738    }
1739
1740    void firstOut(Arc& a, const Node& n) const {
1741      _digraph->firstIn(a, n);
1742      if( static_cast<const Edge&>(a) != INVALID ) {
1743        a._forward = false;
1744      } else {
1745        _digraph->firstOut(a, n);
1746        a._forward = true;
1747      }
1748    }
1749    void nextOut(Arc &a) const {
1750      if (!a._forward) {
1751        Node n = _digraph->target(a);
1752        _digraph->nextIn(a);
1753        if (static_cast<const Edge&>(a) == INVALID ) {
1754          _digraph->firstOut(a, n);
1755          a._forward = true;
1756        }
1757      }
1758      else {
1759        _digraph->nextOut(a);
1760      }
1761    }
1762
1763    void firstIn(Arc &a, const Node &n) const {
1764      _digraph->firstOut(a, n);
1765      if (static_cast<const Edge&>(a) != INVALID ) {
1766        a._forward = false;
1767      } else {
1768        _digraph->firstIn(a, n);
1769        a._forward = true;
1770      }
1771    }
1772    void nextIn(Arc &a) const {
1773      if (!a._forward) {
1774        Node n = _digraph->source(a);
1775        _digraph->nextOut(a);
1776        if( static_cast<const Edge&>(a) == INVALID ) {
1777          _digraph->firstIn(a, n);
1778          a._forward = true;
1779        }
1780      }
1781      else {
1782        _digraph->nextIn(a);
1783      }
1784    }
1785
1786    void firstInc(Edge &e, bool &d, const Node &n) const {
1787      d = true;
1788      _digraph->firstOut(e, n);
1789      if (e != INVALID) return;
1790      d = false;
1791      _digraph->firstIn(e, n);
1792    }
1793
1794    void nextInc(Edge &e, bool &d) const {
1795      if (d) {
1796        Node s = _digraph->source(e);
1797        _digraph->nextOut(e);
1798        if (e != INVALID) return;
1799        d = false;
1800        _digraph->firstIn(e, s);
1801      } else {
1802        _digraph->nextIn(e);
1803      }
1804    }
1805
1806    Node u(const Edge& e) const {
1807      return _digraph->source(e);
1808    }
1809
1810    Node v(const Edge& e) const {
1811      return _digraph->target(e);
1812    }
1813
1814    Node source(const Arc &a) const {
1815      return a._forward ? _digraph->source(a) : _digraph->target(a);
1816    }
1817
1818    Node target(const Arc &a) const {
1819      return a._forward ? _digraph->target(a) : _digraph->source(a);
1820    }
1821
1822    static Arc direct(const Edge &e, bool d) {
1823      return Arc(e, d);
1824    }
1825    Arc direct(const Edge &e, const Node& n) const {
1826      return Arc(e, _digraph->source(e) == n);
1827    }
1828
1829    static bool direction(const Arc &a) { return a._forward; }
1830
1831    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
1832    Arc arcFromId(int ix) const {
1833      return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
1834    }
1835    Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
1836
1837    int id(const Node &n) const { return _digraph->id(n); }
1838    int id(const Arc &a) const {
1839      return  (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
1840    }
1841    int id(const Edge &e) const { return _digraph->id(e); }
1842
1843    int maxNodeId() const { return _digraph->maxNodeId(); }
1844    int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
1845    int maxEdgeId() const { return _digraph->maxArcId(); }
1846
1847    Node addNode() { return _digraph->addNode(); }
1848    Edge addEdge(const Node& u, const Node& v) {
1849      return _digraph->addArc(u, v);
1850    }
1851
1852    void erase(const Node& i) { _digraph->erase(i); }
1853    void erase(const Edge& i) { _digraph->erase(i); }
1854
1855    void clear() { _digraph->clear(); }
1856
1857    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
1858    int nodeNum() const { return 2 * _digraph->arcNum(); }
1859
1860    typedef ArcNumTagIndicator<Digraph> ArcNumTag;
1861    int arcNum() const { return 2 * _digraph->arcNum(); }
1862
1863    typedef ArcNumTag EdgeNumTag;
1864    int edgeNum() const { return _digraph->arcNum(); }
1865
1866    typedef FindArcTagIndicator<Digraph> FindArcTag;
1867    Arc findArc(Node s, Node t, Arc p = INVALID) const {
1868      if (p == INVALID) {
1869        Edge arc = _digraph->findArc(s, t);
1870        if (arc != INVALID) return direct(arc, true);
1871        arc = _digraph->findArc(t, s);
1872        if (arc != INVALID) return direct(arc, false);
1873      } else if (direction(p)) {
1874        Edge arc = _digraph->findArc(s, t, p);
1875        if (arc != INVALID) return direct(arc, true);
1876        arc = _digraph->findArc(t, s);
1877        if (arc != INVALID) return direct(arc, false);
1878      } else {
1879        Edge arc = _digraph->findArc(t, s, p);
1880        if (arc != INVALID) return direct(arc, false);
1881      }
1882      return INVALID;
1883    }
1884
1885    typedef FindArcTag FindEdgeTag;
1886    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
1887      if (s != t) {
1888        if (p == INVALID) {
1889          Edge arc = _digraph->findArc(s, t);
1890          if (arc != INVALID) return arc;
1891          arc = _digraph->findArc(t, s);
1892          if (arc != INVALID) return arc;
1893        } else if (_digraph->s(p) == s) {
1894          Edge arc = _digraph->findArc(s, t, p);
1895          if (arc != INVALID) return arc;
1896          arc = _digraph->findArc(t, s);
1897          if (arc != INVALID) return arc;
1898        } else {
1899          Edge arc = _digraph->findArc(t, s, p);
1900          if (arc != INVALID) return arc;
1901        }
1902      } else {
1903        return _digraph->findArc(s, t, p);
1904      }
1905      return INVALID;
1906    }
1907
1908  private:
1909
1910    template <typename _Value>
1911    class ArcMapBase {
1912    private:
1913
1914      typedef typename Digraph::template ArcMap<_Value> MapImpl;
1915
1916    public:
1917
1918      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1919
1920      typedef _Value Value;
1921      typedef Arc Key;
1922
1923      ArcMapBase(const Adaptor& adaptor) :
1924        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
1925
1926      ArcMapBase(const Adaptor& adaptor, const Value& v)
1927        : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
1928
1929      void set(const Arc& a, const Value& v) {
1930        if (direction(a)) {
1931          _forward.set(a, v);
1932        } else {
1933          _backward.set(a, v);
1934        }
1935      }
1936
1937      typename MapTraits<MapImpl>::ConstReturnValue
1938      operator[](const Arc& a) const {
1939        if (direction(a)) {
1940          return _forward[a];
1941        } else {
1942          return _backward[a];
1943        }
1944      }
1945
1946      typename MapTraits<MapImpl>::ReturnValue
1947      operator[](const Arc& a) {
1948        if (direction(a)) {
1949          return _forward[a];
1950        } else {
1951          return _backward[a];
1952        }
1953      }
1954
1955    protected:
1956
1957      MapImpl _forward, _backward;
1958
1959    };
1960
1961  public:
1962
1963    template <typename _Value>
1964    class NodeMap : public Digraph::template NodeMap<_Value> {
1965    public:
1966
1967      typedef _Value Value;
1968      typedef typename Digraph::template NodeMap<Value> Parent;
1969
1970      explicit NodeMap(const Adaptor& adaptor)
1971        : Parent(*adaptor._digraph) {}
1972
1973      NodeMap(const Adaptor& adaptor, const _Value& value)
1974        : Parent(*adaptor._digraph, value) { }
1975
1976    private:
1977      NodeMap& operator=(const NodeMap& cmap) {
1978        return operator=<NodeMap>(cmap);
1979      }
1980
1981      template <typename CMap>
1982      NodeMap& operator=(const CMap& cmap) {
1983        Parent::operator=(cmap);
1984        return *this;
1985      }
1986
1987    };
1988
1989    template <typename _Value>
1990    class ArcMap
1991      : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
1992    {
1993    public:
1994      typedef _Value Value;
1995      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
1996
1997      ArcMap(const Adaptor& adaptor)
1998        : Parent(adaptor) {}
1999
2000      ArcMap(const Adaptor& adaptor, const Value& value)
2001        : Parent(adaptor, value) {}
2002
2003    private:
2004      ArcMap& operator=(const ArcMap& cmap) {
2005        return operator=<ArcMap>(cmap);
2006      }
2007
2008      template <typename CMap>
2009      ArcMap& operator=(const CMap& cmap) {
2010        Parent::operator=(cmap);
2011        return *this;
2012      }
2013    };
2014
2015    template <typename _Value>
2016    class EdgeMap : public Digraph::template ArcMap<_Value> {
2017    public:
2018
2019      typedef _Value Value;
2020      typedef typename Digraph::template ArcMap<Value> Parent;
2021
2022      explicit EdgeMap(const Adaptor& adaptor)
2023        : Parent(*adaptor._digraph) {}
2024
2025      EdgeMap(const Adaptor& adaptor, const Value& value)
2026        : Parent(*adaptor._digraph, value) {}
2027
2028    private:
2029      EdgeMap& operator=(const EdgeMap& cmap) {
2030        return operator=<EdgeMap>(cmap);
2031      }
2032
2033      template <typename CMap>
2034      EdgeMap& operator=(const CMap& cmap) {
2035        Parent::operator=(cmap);
2036        return *this;
2037      }
2038
2039    };
2040
2041    typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
2042    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
2043
2044  protected:
2045
2046    UndirectorBase() : _digraph(0) {}
2047
2048    Digraph* _digraph;
2049
2050    void setDigraph(Digraph& digraph) {
2051      _digraph = &digraph;
2052    }
2053
2054  };
2055
2056  /// \ingroup graph_adaptors
2057  ///
2058  /// \brief Undirect the graph
2059  ///
2060  /// This adaptor makes an undirected graph from a directed
2061  /// graph. All arcs of the underlying digraph will be showed in the
2062  /// adaptor as an edge. The Orienter adaptor is conform to the \ref
2063  /// concepts::Graph "Graph concept".
2064  ///
2065  /// \tparam _Digraph It must be conform to the \ref
2066  /// concepts::Digraph "Digraph concept". The type can be specified
2067  /// to const.
2068  template<typename _Digraph>
2069  class Undirector
2070    : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
2071  public:
2072    typedef _Digraph Digraph;
2073    typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
2074  protected:
2075    Undirector() { }
2076  public:
2077
2078    /// \brief Constructor
2079    ///
2080    /// Creates a undirected graph from the given digraph
2081    Undirector(_Digraph& digraph) {
2082      setDigraph(digraph);
2083    }
2084
2085    /// \brief ArcMap combined from two original ArcMap
2086    ///
2087    /// This class adapts two original digraph ArcMap to
2088    /// get an arc map on the undirected graph.
2089    template <typename _ForwardMap, typename _BackwardMap>
2090    class CombinedArcMap {
2091    public:
2092
2093      typedef _ForwardMap ForwardMap;
2094      typedef _BackwardMap BackwardMap;
2095
2096      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
2097
2098      typedef typename ForwardMap::Value Value;
2099      typedef typename Parent::Arc Key;
2100
2101      /// \brief Constructor
2102      ///
2103      /// Constructor
2104      CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
2105        : _forward(&forward), _backward(&backward) {}
2106
2107
2108      /// \brief Sets the value associated with a key.
2109      ///
2110      /// Sets the value associated with a key.
2111      void set(const Key& e, const Value& a) {
2112        if (Parent::direction(e)) {
2113          _forward->set(e, a);
2114        } else {
2115          _backward->set(e, a);
2116        }
2117      }
2118
2119      /// \brief Returns the value associated with a key.
2120      ///
2121      /// Returns the value associated with a key.
2122      typename MapTraits<ForwardMap>::ConstReturnValue
2123      operator[](const Key& e) const {
2124        if (Parent::direction(e)) {
2125          return (*_forward)[e];
2126        } else {
2127          return (*_backward)[e];
2128        }
2129      }
2130
2131      /// \brief Returns the value associated with a key.
2132      ///
2133      /// Returns the value associated with a key.
2134      typename MapTraits<ForwardMap>::ReturnValue
2135      operator[](const Key& e) {
2136        if (Parent::direction(e)) {
2137          return (*_forward)[e];
2138        } else {
2139          return (*_backward)[e];
2140        }
2141      }
2142
2143    protected:
2144
2145      ForwardMap* _forward;
2146      BackwardMap* _backward;
2147
2148    };
2149
2150    /// \brief Just gives back a combined arc map
2151    ///
2152    /// Just gives back a combined arc map
2153    template <typename ForwardMap, typename BackwardMap>
2154    static CombinedArcMap<ForwardMap, BackwardMap>
2155    combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
2156      return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
2157    }
2158
2159    template <typename ForwardMap, typename BackwardMap>
2160    static CombinedArcMap<const ForwardMap, BackwardMap>
2161    combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
2162      return CombinedArcMap<const ForwardMap,
2163        BackwardMap>(forward, backward);
2164    }
2165
2166    template <typename ForwardMap, typename BackwardMap>
2167    static CombinedArcMap<ForwardMap, const BackwardMap>
2168    combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
2169      return CombinedArcMap<ForwardMap,
2170        const BackwardMap>(forward, backward);
2171    }
2172
2173    template <typename ForwardMap, typename BackwardMap>
2174    static CombinedArcMap<const ForwardMap, const BackwardMap>
2175    combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
2176      return CombinedArcMap<const ForwardMap,
2177        const BackwardMap>(forward, backward);
2178    }
2179
2180  };
2181
2182  /// \brief Just gives back an undirected view of the given digraph
2183  ///
2184  /// Just gives back an undirected view of the given digraph
2185  template<typename Digraph>
2186  Undirector<const Digraph>
2187  undirector(const Digraph& digraph) {
2188    return Undirector<const Digraph>(digraph);
2189  }
2190
2191  template <typename _Graph, typename _DirectionMap>
2192  class OrienterBase {
2193  public:
2194
2195    typedef _Graph Graph;
2196    typedef _DirectionMap DirectionMap;
2197
2198    typedef typename Graph::Node Node;
2199    typedef typename Graph::Edge Arc;
2200
2201    void reverseArc(const Arc& arc) {
2202      _direction->set(arc, !(*_direction)[arc]);
2203    }
2204
2205    void first(Node& i) const { _graph->first(i); }
2206    void first(Arc& i) const { _graph->first(i); }
2207    void firstIn(Arc& i, const Node& n) const {
2208      bool d = true;
2209      _graph->firstInc(i, d, n);
2210      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
2211    }
2212    void firstOut(Arc& i, const Node& n ) const {
2213      bool d = true;
2214      _graph->firstInc(i, d, n);
2215      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
2216    }
2217
2218    void next(Node& i) const { _graph->next(i); }
2219    void next(Arc& i) const { _graph->next(i); }
2220    void nextIn(Arc& i) const {
2221      bool d = !(*_direction)[i];
2222      _graph->nextInc(i, d);
2223      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
2224    }
2225    void nextOut(Arc& i) const {
2226      bool d = (*_direction)[i];
2227      _graph->nextInc(i, d);
2228      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
2229    }
2230
2231    Node source(const Arc& e) const {
2232      return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
2233    }
2234    Node target(const Arc& e) const {
2235      return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
2236    }
2237
2238    typedef NodeNumTagIndicator<Graph> NodeNumTag;
2239    int nodeNum() const { return _graph->nodeNum(); }
2240
2241    typedef EdgeNumTagIndicator<Graph> ArcNumTag;
2242    int arcNum() const { return _graph->edgeNum(); }
2243
2244    typedef FindEdgeTagIndicator<Graph> FindArcTag;
2245    Arc findArc(const Node& u, const Node& v,
2246                const Arc& prev = INVALID) {
2247      Arc arc = prev;
2248      bool d = arc == INVALID ? true : (*_direction)[arc];
2249      if (d) {
2250        arc = _graph->findEdge(u, v, arc);
2251        while (arc != INVALID && !(*_direction)[arc]) {
2252          _graph->findEdge(u, v, arc);
2253        }
2254        if (arc != INVALID) return arc;
2255      }
2256      _graph->findEdge(v, u, arc);
2257      while (arc != INVALID && (*_direction)[arc]) {
2258        _graph->findEdge(u, v, arc);
2259      }
2260      return arc;
2261    }
2262
2263    Node addNode() {
2264      return Node(_graph->addNode());
2265    }
2266
2267    Arc addArc(const Node& u, const Node& v) {
2268      Arc arc = _graph->addArc(u, v);
2269      _direction->set(arc, _graph->source(arc) == u);
2270      return arc;
2271    }
2272
2273    void erase(const Node& i) { _graph->erase(i); }
2274    void erase(const Arc& i) { _graph->erase(i); }
2275
2276    void clear() { _graph->clear(); }
2277
2278    int id(const Node& v) const { return _graph->id(v); }
2279    int id(const Arc& e) const { return _graph->id(e); }
2280
2281    Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
2282    Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
2283
2284    int maxNodeId() const { return _graph->maxNodeId(); }
2285    int maxArcId() const { return _graph->maxEdgeId(); }
2286
2287    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
2288    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
2289
2290    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
2291    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
2292
2293    template <typename _Value>
2294    class NodeMap : public _Graph::template NodeMap<_Value> {
2295    public:
2296
2297      typedef typename _Graph::template NodeMap<_Value> Parent;
2298
2299      explicit NodeMap(const OrienterBase& adapter)
2300        : Parent(*adapter._graph) {}
2301
2302      NodeMap(const OrienterBase& adapter, const _Value& value)
2303        : Parent(*adapter._graph, value) {}
2304
2305    private:
2306      NodeMap& operator=(const NodeMap& cmap) {
2307        return operator=<NodeMap>(cmap);
2308      }
2309
2310      template <typename CMap>
2311      NodeMap& operator=(const CMap& cmap) {
2312        Parent::operator=(cmap);
2313        return *this;
2314      }
2315
2316    };
2317
2318    template <typename _Value>
2319    class ArcMap : public _Graph::template EdgeMap<_Value> {
2320    public:
2321
2322      typedef typename Graph::template EdgeMap<_Value> Parent;
2323
2324      explicit ArcMap(const OrienterBase& adapter)
2325        : Parent(*adapter._graph) { }
2326
2327      ArcMap(const OrienterBase& adapter, const _Value& value)
2328        : Parent(*adapter._graph, value) { }
2329
2330    private:
2331      ArcMap& operator=(const ArcMap& cmap) {
2332        return operator=<ArcMap>(cmap);
2333      }
2334
2335      template <typename CMap>
2336      ArcMap& operator=(const CMap& cmap) {
2337        Parent::operator=(cmap);
2338        return *this;
2339      }
2340    };
2341
2342
2343
2344  protected:
2345    Graph* _graph;
2346    DirectionMap* _direction;
2347
2348    void setDirectionMap(DirectionMap& direction) {
2349      _direction = &direction;
2350    }
2351
2352    void setGraph(Graph& graph) {
2353      _graph = &graph;
2354    }
2355
2356  };
2357
2358  /// \ingroup graph_adaptors
2359  ///
2360  /// \brief Orients the edges of the graph to get a digraph
2361  ///
2362  /// This adaptor orients each edge in the undirected graph. The
2363  /// direction of the arcs stored in an edge node map.  The arcs can
2364  /// be easily reverted by the \c reverseArc() member function in the
2365  /// adaptor. The Orienter adaptor is conform to the \ref
2366  /// concepts::Digraph "Digraph concept".
2367  ///
2368  /// \tparam _Graph It must be conform to the \ref concepts::Graph
2369  /// "Graph concept". The type can be specified to be const.
2370  /// \tparam _DirectionMap A bool valued edge map of the the adapted
2371  /// graph.
2372  ///
2373  /// \sa orienter
2374  template<typename _Graph,
2375           typename DirectionMap = typename _Graph::template EdgeMap<bool> >
2376  class Orienter :
2377    public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {
2378  public:
2379    typedef _Graph Graph;
2380    typedef DigraphAdaptorExtender<
2381      OrienterBase<_Graph, DirectionMap> > Parent;
2382    typedef typename Parent::Arc Arc;
2383  protected:
2384    Orienter() { }
2385  public:
2386
2387    /// \brief Constructor of the adaptor
2388    ///
2389    /// Constructor of the adaptor
2390    Orienter(Graph& graph, DirectionMap& direction) {
2391      setGraph(graph);
2392      setDirectionMap(direction);
2393    }
2394
2395    /// \brief Reverse arc
2396    ///
2397    /// It reverse the given arc. It simply negate the direction in the map.
2398    void reverseArc(const Arc& a) {
2399      Parent::reverseArc(a);
2400    }
2401  };
2402
2403  /// \brief Just gives back a Orienter
2404  ///
2405  /// Just gives back a Orienter
2406  template<typename Graph, typename DirectionMap>
2407  Orienter<const Graph, DirectionMap>
2408  orienter(const Graph& graph, DirectionMap& dm) {
2409    return Orienter<const Graph, DirectionMap>(graph, dm);
2410  }
2411
2412  template<typename Graph, typename DirectionMap>
2413  Orienter<const Graph, const DirectionMap>
2414  orienter(const Graph& graph, const DirectionMap& dm) {
2415    return Orienter<const Graph, const DirectionMap>(graph, dm);
2416  }
2417
2418  namespace _adaptor_bits {
2419
2420    template<typename _Digraph,
2421             typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2422             typename _FlowMap = _CapacityMap,
2423             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
2424    class ResForwardFilter {
2425    public:
2426
2427      typedef _Digraph Digraph;
2428      typedef _CapacityMap CapacityMap;
2429      typedef _FlowMap FlowMap;
2430      typedef _Tolerance Tolerance;
2431
2432      typedef typename Digraph::Arc Key;
2433      typedef bool Value;
2434
2435    private:
2436
2437      const CapacityMap* _capacity;
2438      const FlowMap* _flow;
2439      Tolerance _tolerance;
2440    public:
2441
2442      ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
2443                       const Tolerance& tolerance = Tolerance())
2444        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
2445
2446      bool operator[](const typename Digraph::Arc& a) const {
2447        return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
2448      }
2449    };
2450
2451    template<typename _Digraph,
2452             typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2453             typename _FlowMap = _CapacityMap,
2454             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
2455    class ResBackwardFilter {
2456    public:
2457
2458      typedef _Digraph Digraph;
2459      typedef _CapacityMap CapacityMap;
2460      typedef _FlowMap FlowMap;
2461      typedef _Tolerance Tolerance;
2462
2463      typedef typename Digraph::Arc Key;
2464      typedef bool Value;
2465
2466    private:
2467
2468      const CapacityMap* _capacity;
2469      const FlowMap* _flow;
2470      Tolerance _tolerance;
2471
2472    public:
2473
2474      ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
2475                        const Tolerance& tolerance = Tolerance())
2476        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
2477
2478      bool operator[](const typename Digraph::Arc& a) const {
2479        return _tolerance.positive((*_flow)[a]);
2480      }
2481    };
2482
2483  }
2484
2485  /// \ingroup graph_adaptors
2486  ///
2487  /// \brief An adaptor for composing the residual graph for directed
2488  /// flow and circulation problems.
2489  ///
2490  /// An adaptor for composing the residual graph for directed flow and
2491  /// circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph
2492  /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
2493  /// be functions on the arc-set.
2494  ///
2495  /// Then Residual implements the digraph structure with
2496  /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$,
2497  /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
2498  /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
2499  /// called residual graph.  When we take the union
2500  /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,
2501  /// i.e.  if an arc is in both \f$ A_{forward} \f$ and
2502  /// \f$ A_{backward} \f$, then in the adaptor it appears in both
2503  /// orientation.
2504  ///
2505  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
2506  /// "Digraph concept". The type is implicitly const.
2507  /// \tparam _CapacityMap An arc map of some numeric type, it defines
2508  /// the capacities in the flow problem. The map is implicitly const.
2509  /// \tparam _FlowMap An arc map of some numeric type, it defines
2510  /// the capacities in the flow problem.
2511  /// \tparam _Tolerance Handler for inexact computation.
2512  template<typename _Digraph,
2513           typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2514           typename _FlowMap = _CapacityMap,
2515           typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
2516  class Residual :
2517    public FilterArcs<
2518    Undirector<const _Digraph>,
2519    typename Undirector<const _Digraph>::template CombinedArcMap<
2520      _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,
2521                                      _FlowMap, _Tolerance>,
2522      _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
2523                                       _FlowMap, _Tolerance> > >
2524  {
2525  public:
2526
2527    typedef _Digraph Digraph;
2528    typedef _CapacityMap CapacityMap;
2529    typedef _FlowMap FlowMap;
2530    typedef _Tolerance Tolerance;
2531
2532    typedef typename CapacityMap::Value Value;
2533    typedef Residual Adaptor;
2534
2535  protected:
2536
2537    typedef Undirector<const Digraph> Undirected;
2538
2539    typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,
2540                                            FlowMap, Tolerance> ForwardFilter;
2541
2542    typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
2543                                             FlowMap, Tolerance> BackwardFilter;
2544
2545    typedef typename Undirected::
2546    template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
2547
2548    typedef FilterArcs<Undirected, ArcFilter> Parent;
2549
2550    const CapacityMap* _capacity;
2551    FlowMap* _flow;
2552
2553    Undirected _graph;
2554    ForwardFilter _forward_filter;
2555    BackwardFilter _backward_filter;
2556    ArcFilter _arc_filter;
2557
2558  public:
2559
2560    /// \brief Constructor of the residual digraph.
2561    ///
2562    /// Constructor of the residual graph. The parameters are the digraph,
2563    /// the flow map, the capacity map and a tolerance object.
2564    Residual(const Digraph& digraph, const CapacityMap& capacity,
2565             FlowMap& flow, const Tolerance& tolerance = Tolerance())
2566      : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
2567        _forward_filter(capacity, flow, tolerance),
2568        _backward_filter(capacity, flow, tolerance),
2569        _arc_filter(_forward_filter, _backward_filter)
2570    {
2571      Parent::setDigraph(_graph);
2572      Parent::setArcFilterMap(_arc_filter);
2573    }
2574
2575    typedef typename Parent::Arc Arc;
2576
2577    /// \brief Gives back the residual capacity of the arc.
2578    ///
2579    /// Gives back the residual capacity of the arc.
2580    Value residualCapacity(const Arc& a) const {
2581      if (Undirected::direction(a)) {
2582        return (*_capacity)[a] - (*_flow)[a];
2583      } else {
2584        return (*_flow)[a];
2585      }
2586    }
2587
2588    /// \brief Augment on the given arc in the residual graph.
2589    ///
2590    /// Augment on the given arc in the residual graph. It increase
2591    /// or decrease the flow on the original arc depend on the direction
2592    /// of the residual arc.
2593    void augment(const Arc& a, const Value& v) const {
2594      if (Undirected::direction(a)) {
2595        _flow->set(a, (*_flow)[a] + v);
2596      } else {
2597        _flow->set(a, (*_flow)[a] - v);
2598      }
2599    }
2600
2601    /// \brief Returns the direction of the arc.
2602    ///
2603    /// Returns true when the arc is same oriented as the original arc.
2604    static bool forward(const Arc& a) {
2605      return Undirected::direction(a);
2606    }
2607
2608    /// \brief Returns the direction of the arc.
2609    ///
2610    /// Returns true when the arc is opposite oriented as the original arc.
2611    static bool backward(const Arc& a) {
2612      return !Undirected::direction(a);
2613    }
2614
2615    /// \brief Gives back the forward oriented residual arc.
2616    ///
2617    /// Gives back the forward oriented residual arc.
2618    static Arc forward(const typename Digraph::Arc& a) {
2619      return Undirected::direct(a, true);
2620    }
2621
2622    /// \brief Gives back the backward oriented residual arc.
2623    ///
2624    /// Gives back the backward oriented residual arc.
2625    static Arc backward(const typename Digraph::Arc& a) {
2626      return Undirected::direct(a, false);
2627    }
2628
2629    /// \brief Residual capacity map.
2630    ///
2631    /// In generic residual graph the residual capacity can be obtained
2632    /// as a map.
2633    class ResidualCapacity {
2634    protected:
2635      const Adaptor* _adaptor;
2636    public:
2637      /// The Key type
2638      typedef Arc Key;
2639      /// The Value type
2640      typedef typename _CapacityMap::Value Value;
2641
2642      /// Constructor
2643      ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
2644
2645      /// \e
2646      Value operator[](const Arc& a) const {
2647        return _adaptor->residualCapacity(a);
2648      }
2649
2650    };
2651
2652  };
2653
2654  template <typename _Digraph>
2655  class SplitNodesBase {
2656  public:
2657
2658    typedef _Digraph Digraph;
2659    typedef DigraphAdaptorBase<const _Digraph> Parent;
2660    typedef SplitNodesBase Adaptor;
2661
2662    typedef typename Digraph::Node DigraphNode;
2663    typedef typename Digraph::Arc DigraphArc;
2664
2665    class Node;
2666    class Arc;
2667
2668  private:
2669
2670    template <typename T> class NodeMapBase;
2671    template <typename T> class ArcMapBase;
2672
2673  public:
2674
2675    class Node : public DigraphNode {
2676      friend class SplitNodesBase;
2677      template <typename T> friend class NodeMapBase;
2678    private:
2679
2680      bool _in;
2681      Node(DigraphNode node, bool in)
2682        : DigraphNode(node), _in(in) {}
2683
2684    public:
2685
2686      Node() {}
2687      Node(Invalid) : DigraphNode(INVALID), _in(true) {}
2688
2689      bool operator==(const Node& node) const {
2690        return DigraphNode::operator==(node) && _in == node._in;
2691      }
2692
2693      bool operator!=(const Node& node) const {
2694        return !(*this == node);
2695      }
2696
2697      bool operator<(const Node& node) const {
2698        return DigraphNode::operator<(node) ||
2699          (DigraphNode::operator==(node) && _in < node._in);
2700      }
2701    };
2702
2703    class Arc {
2704      friend class SplitNodesBase;
2705      template <typename T> friend class ArcMapBase;
2706    private:
2707      typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
2708
2709      explicit Arc(const DigraphArc& arc) : _item(arc) {}
2710      explicit Arc(const DigraphNode& node) : _item(node) {}
2711
2712      ArcImpl _item;
2713
2714    public:
2715      Arc() {}
2716      Arc(Invalid) : _item(DigraphArc(INVALID)) {}
2717
2718      bool operator==(const Arc& arc) const {
2719        if (_item.firstState()) {
2720          if (arc._item.firstState()) {
2721            return _item.first() == arc._item.first();
2722          }
2723        } else {
2724          if (arc._item.secondState()) {
2725            return _item.second() == arc._item.second();
2726          }
2727        }
2728        return false;
2729      }
2730
2731      bool operator!=(const Arc& arc) const {
2732        return !(*this == arc);
2733      }
2734
2735      bool operator<(const Arc& arc) const {
2736        if (_item.firstState()) {
2737          if (arc._item.firstState()) {
2738            return _item.first() < arc._item.first();
2739          }
2740          return false;
2741        } else {
2742          if (arc._item.secondState()) {
2743            return _item.second() < arc._item.second();
2744          }
2745          return true;
2746        }
2747      }
2748
2749      operator DigraphArc() const { return _item.first(); }
2750      operator DigraphNode() const { return _item.second(); }
2751
2752    };
2753
2754    void first(Node& n) const {
2755      _digraph->first(n);
2756      n._in = true;
2757    }
2758
2759    void next(Node& n) const {
2760      if (n._in) {
2761        n._in = false;
2762      } else {
2763        n._in = true;
2764        _digraph->next(n);
2765      }
2766    }
2767
2768    void first(Arc& e) const {
2769      e._item.setSecond();
2770      _digraph->first(e._item.second());
2771      if (e._item.second() == INVALID) {
2772        e._item.setFirst();
2773        _digraph->first(e._item.first());
2774      }
2775    }
2776
2777    void next(Arc& e) const {
2778      if (e._item.secondState()) {
2779        _digraph->next(e._item.second());
2780        if (e._item.second() == INVALID) {
2781          e._item.setFirst();
2782          _digraph->first(e._item.first());
2783        }
2784      } else {
2785        _digraph->next(e._item.first());
2786      }
2787    }
2788
2789    void firstOut(Arc& e, const Node& n) const {
2790      if (n._in) {
2791        e._item.setSecond(n);
2792      } else {
2793        e._item.setFirst();
2794        _digraph->firstOut(e._item.first(), n);
2795      }
2796    }
2797
2798    void nextOut(Arc& e) const {
2799      if (!e._item.firstState()) {
2800        e._item.setFirst(INVALID);
2801      } else {
2802        _digraph->nextOut(e._item.first());
2803      }
2804    }
2805
2806    void firstIn(Arc& e, const Node& n) const {
2807      if (!n._in) {
2808        e._item.setSecond(n);
2809      } else {
2810        e._item.setFirst();
2811        _digraph->firstIn(e._item.first(), n);
2812      }
2813    }
2814
2815    void nextIn(Arc& e) const {
2816      if (!e._item.firstState()) {
2817        e._item.setFirst(INVALID);
2818      } else {
2819        _digraph->nextIn(e._item.first());
2820      }
2821    }
2822
2823    Node source(const Arc& e) const {
2824      if (e._item.firstState()) {
2825        return Node(_digraph->source(e._item.first()), false);
2826      } else {
2827        return Node(e._item.second(), true);
2828      }
2829    }
2830
2831    Node target(const Arc& e) const {
2832      if (e._item.firstState()) {
2833        return Node(_digraph->target(e._item.first()), true);
2834      } else {
2835        return Node(e._item.second(), false);
2836      }
2837    }
2838
2839    int id(const Node& n) const {
2840      return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
2841    }
2842    Node nodeFromId(int ix) const {
2843      return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
2844    }
2845    int maxNodeId() const {
2846      return 2 * _digraph->maxNodeId() + 1;
2847    }
2848
2849    int id(const Arc& e) const {
2850      if (e._item.firstState()) {
2851        return _digraph->id(e._item.first()) << 1;
2852      } else {
2853        return (_digraph->id(e._item.second()) << 1) | 1;
2854      }
2855    }
2856    Arc arcFromId(int ix) const {
2857      if ((ix & 1) == 0) {
2858        return Arc(_digraph->arcFromId(ix >> 1));
2859      } else {
2860        return Arc(_digraph->nodeFromId(ix >> 1));
2861      }
2862    }
2863    int maxArcId() const {
2864      return std::max(_digraph->maxNodeId() << 1,
2865                      (_digraph->maxArcId() << 1) | 1);
2866    }
2867
2868    static bool inNode(const Node& n) {
2869      return n._in;
2870    }
2871
2872    static bool outNode(const Node& n) {
2873      return !n._in;
2874    }
2875
2876    static bool origArc(const Arc& e) {
2877      return e._item.firstState();
2878    }
2879
2880    static bool bindArc(const Arc& e) {
2881      return e._item.secondState();
2882    }
2883
2884    static Node inNode(const DigraphNode& n) {
2885      return Node(n, true);
2886    }
2887
2888    static Node outNode(const DigraphNode& n) {
2889      return Node(n, false);
2890    }
2891
2892    static Arc arc(const DigraphNode& n) {
2893      return Arc(n);
2894    }
2895
2896    static Arc arc(const DigraphArc& e) {
2897      return Arc(e);
2898    }
2899
2900    typedef True NodeNumTag;
2901    int nodeNum() const {
2902      return  2 * countNodes(*_digraph);
2903    }
2904
2905    typedef True ArcNumTag;
2906    int arcNum() const {
2907      return countArcs(*_digraph) + countNodes(*_digraph);
2908    }
2909
2910    typedef True FindArcTag;
2911    Arc findArc(const Node& u, const Node& v,
2912                const Arc& prev = INVALID) const {
2913      if (inNode(u)) {
2914        if (outNode(v)) {
2915          if (static_cast<const DigraphNode&>(u) ==
2916              static_cast<const DigraphNode&>(v) && prev == INVALID) {
2917            return Arc(u);
2918          }
2919        }
2920      } else {
2921        if (inNode(v)) {
2922          return Arc(::lemon::findArc(*_digraph, u, v, prev));
2923        }
2924      }
2925      return INVALID;
2926    }
2927
2928  private:
2929
2930    template <typename _Value>
2931    class NodeMapBase
2932      : public MapTraits<typename Parent::template NodeMap<_Value> > {
2933      typedef typename Parent::template NodeMap<_Value> NodeImpl;
2934    public:
2935      typedef Node Key;
2936      typedef _Value Value;
2937
2938      NodeMapBase(const Adaptor& adaptor)
2939        : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
2940      NodeMapBase(const Adaptor& adaptor, const Value& value)
2941        : _in_map(*adaptor._digraph, value),
2942          _out_map(*adaptor._digraph, value) {}
2943
2944      void set(const Node& key, const Value& val) {
2945        if (Adaptor::inNode(key)) { _in_map.set(key, val); }
2946        else {_out_map.set(key, val); }
2947      }
2948
2949      typename MapTraits<NodeImpl>::ReturnValue
2950      operator[](const Node& key) {
2951        if (Adaptor::inNode(key)) { return _in_map[key]; }
2952        else { return _out_map[key]; }
2953      }
2954
2955      typename MapTraits<NodeImpl>::ConstReturnValue
2956      operator[](const Node& key) const {
2957        if (Adaptor::inNode(key)) { return _in_map[key]; }
2958        else { return _out_map[key]; }
2959      }
2960
2961    private:
2962      NodeImpl _in_map, _out_map;
2963    };
2964
2965    template <typename _Value>
2966    class ArcMapBase
2967      : public MapTraits<typename Parent::template ArcMap<_Value> > {
2968      typedef typename Parent::template ArcMap<_Value> ArcImpl;
2969      typedef typename Parent::template NodeMap<_Value> NodeImpl;
2970    public:
2971      typedef Arc Key;
2972      typedef _Value Value;
2973
2974      ArcMapBase(const Adaptor& adaptor)
2975        : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
2976      ArcMapBase(const Adaptor& adaptor, const Value& value)
2977        : _arc_map(*adaptor._digraph, value),
2978          _node_map(*adaptor._digraph, value) {}
2979
2980      void set(const Arc& key, const Value& val) {
2981        if (Adaptor::origArc(key)) {
2982          _arc_map.set(key._item.first(), val);
2983        } else {
2984          _node_map.set(key._item.second(), val);
2985        }
2986      }
2987
2988      typename MapTraits<ArcImpl>::ReturnValue
2989      operator[](const Arc& key) {
2990        if (Adaptor::origArc(key)) {
2991          return _arc_map[key._item.first()];
2992        } else {
2993          return _node_map[key._item.second()];
2994        }
2995      }
2996
2997      typename MapTraits<ArcImpl>::ConstReturnValue
2998      operator[](const Arc& key) const {
2999        if (Adaptor::origArc(key)) {
3000          return _arc_map[key._item.first()];
3001        } else {
3002          return _node_map[key._item.second()];
3003        }
3004      }
3005
3006    private:
3007      ArcImpl _arc_map;
3008      NodeImpl _node_map;
3009    };
3010
3011  public:
3012
3013    template <typename _Value>
3014    class NodeMap
3015      : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
3016    {
3017    public:
3018      typedef _Value Value;
3019      typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
3020
3021      NodeMap(const Adaptor& adaptor)
3022        : Parent(adaptor) {}
3023
3024      NodeMap(const Adaptor& adaptor, const Value& value)
3025        : Parent(adaptor, value) {}
3026
3027    private:
3028      NodeMap& operator=(const NodeMap& cmap) {
3029        return operator=<NodeMap>(cmap);
3030      }
3031
3032      template <typename CMap>
3033      NodeMap& operator=(const CMap& cmap) {
3034        Parent::operator=(cmap);
3035        return *this;
3036      }
3037    };
3038
3039    template <typename _Value>
3040    class ArcMap
3041      : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
3042    {
3043    public:
3044      typedef _Value Value;
3045      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
3046
3047      ArcMap(const Adaptor& adaptor)
3048        : Parent(adaptor) {}
3049
3050      ArcMap(const Adaptor& adaptor, const Value& value)
3051        : Parent(adaptor, value) {}
3052
3053    private:
3054      ArcMap& operator=(const ArcMap& cmap) {
3055        return operator=<ArcMap>(cmap);
3056      }
3057
3058      template <typename CMap>
3059      ArcMap& operator=(const CMap& cmap) {
3060        Parent::operator=(cmap);
3061        return *this;
3062      }
3063    };
3064
3065  protected:
3066
3067    SplitNodesBase() : _digraph(0) {}
3068
3069    Digraph* _digraph;
3070
3071    void setDigraph(Digraph& digraph) {
3072      _digraph = &digraph;
3073    }
3074
3075  };
3076
3077  /// \ingroup graph_adaptors
3078  ///
3079  /// \brief Split the nodes of a directed graph
3080  ///
3081  /// The SplitNodes adaptor splits each node into an in-node and an
3082  /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in
3083  /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node
3084  /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the
3085  /// original digraph the new target of the arc will be \f$ u_{in} \f$
3086  /// and similarly the source of the original \f$ (u, v) \f$ arc
3087  /// will be \f$ u_{out} \f$.  The adaptor will add for each node in
3088  /// the original digraph an additional arc which connects
3089  /// \f$ (u_{in}, u_{out}) \f$.
3090  ///
3091  /// The aim of this class is to run algorithm with node costs if the
3092  /// algorithm can use directly just arc costs. In this case we should use
3093  /// a \c SplitNodes and set the node cost of the graph to the
3094  /// bind arc in the adapted graph.
3095  ///
3096  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
3097  /// "Digraph concept". The type can be specified to be const.
3098  template <typename _Digraph>
3099  class SplitNodes
3100    : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > {
3101  public:
3102    typedef _Digraph Digraph;
3103    typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent;
3104
3105    typedef typename Digraph::Node DigraphNode;
3106    typedef typename Digraph::Arc DigraphArc;
3107
3108    typedef typename Parent::Node Node;
3109    typedef typename Parent::Arc Arc;
3110
3111    /// \brief Constructor of the adaptor.
3112    ///
3113    /// Constructor of the adaptor.
3114    SplitNodes(Digraph& g) {
3115      Parent::setDigraph(g);
3116    }
3117
3118    /// \brief Returns true when the node is in-node.
3119    ///
3120    /// Returns true when the node is in-node.
3121    static bool inNode(const Node& n) {
3122      return Parent::inNode(n);
3123    }
3124
3125    /// \brief Returns true when the node is out-node.
3126    ///
3127    /// Returns true when the node is out-node.
3128    static bool outNode(const Node& n) {
3129      return Parent::outNode(n);
3130    }
3131
3132    /// \brief Returns true when the arc is arc in the original digraph.
3133    ///
3134    /// Returns true when the arc is arc in the original digraph.
3135    static bool origArc(const Arc& a) {
3136      return Parent::origArc(a);
3137    }
3138
3139    /// \brief Returns true when the arc binds an in-node and an out-node.
3140    ///
3141    /// Returns true when the arc binds an in-node and an out-node.
3142    static bool bindArc(const Arc& a) {
3143      return Parent::bindArc(a);
3144    }
3145
3146    /// \brief Gives back the in-node created from the \c node.
3147    ///
3148    /// Gives back the in-node created from the \c node.
3149    static Node inNode(const DigraphNode& n) {
3150      return Parent::inNode(n);
3151    }
3152
3153    /// \brief Gives back the out-node created from the \c node.
3154    ///
3155    /// Gives back the out-node created from the \c node.
3156    static Node outNode(const DigraphNode& n) {
3157      return Parent::outNode(n);
3158    }
3159
3160    /// \brief Gives back the arc binds the two part of the node.
3161    ///
3162    /// Gives back the arc binds the two part of the node.
3163    static Arc arc(const DigraphNode& n) {
3164      return Parent::arc(n);
3165    }
3166
3167    /// \brief Gives back the arc of the original arc.
3168    ///
3169    /// Gives back the arc of the original arc.
3170    static Arc arc(const DigraphArc& a) {
3171      return Parent::arc(a);
3172    }
3173
3174    /// \brief NodeMap combined from two original NodeMap
3175    ///
3176    /// This class adapt two of the original digraph NodeMap to
3177    /// get a node map on the adapted digraph.
3178    template <typename InNodeMap, typename OutNodeMap>
3179    class CombinedNodeMap {
3180    public:
3181
3182      typedef Node Key;
3183      typedef typename InNodeMap::Value Value;
3184
3185      /// \brief Constructor
3186      ///
3187      /// Constructor.
3188      CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
3189        : _in_map(in_map), _out_map(out_map) {}
3190
3191      /// \brief The subscript operator.
3192      ///
3193      /// The subscript operator.
3194      Value& operator[](const Key& key) {
3195        if (Parent::inNode(key)) {
3196          return _in_map[key];
3197        } else {
3198          return _out_map[key];
3199        }
3200      }
3201
3202      /// \brief The const subscript operator.
3203      ///
3204      /// The const subscript operator.
3205      Value operator[](const Key& key) const {
3206        if (Parent::inNode(key)) {
3207          return _in_map[key];
3208        } else {
3209          return _out_map[key];
3210        }
3211      }
3212
3213      /// \brief The setter function of the map.
3214      ///
3215      /// The setter function of the map.
3216      void set(const Key& key, const Value& value) {
3217        if (Parent::inNode(key)) {
3218          _in_map.set(key, value);
3219        } else {
3220          _out_map.set(key, value);
3221        }
3222      }
3223
3224    private:
3225
3226      InNodeMap& _in_map;
3227      OutNodeMap& _out_map;
3228
3229    };
3230
3231
3232    /// \brief Just gives back a combined node map
3233    ///
3234    /// Just gives back a combined node map
3235    template <typename InNodeMap, typename OutNodeMap>
3236    static CombinedNodeMap<InNodeMap, OutNodeMap>
3237    combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
3238      return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
3239    }
3240
3241    template <typename InNodeMap, typename OutNodeMap>
3242    static CombinedNodeMap<const InNodeMap, OutNodeMap>
3243    combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
3244      return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
3245    }
3246
3247    template <typename InNodeMap, typename OutNodeMap>
3248    static CombinedNodeMap<InNodeMap, const OutNodeMap>
3249    combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
3250      return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
3251    }
3252
3253    template <typename InNodeMap, typename OutNodeMap>
3254    static CombinedNodeMap<const InNodeMap, const OutNodeMap>
3255    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
3256      return CombinedNodeMap<const InNodeMap,
3257        const OutNodeMap>(in_map, out_map);
3258    }
3259
3260    /// \brief ArcMap combined from an original ArcMap and a NodeMap
3261    ///
3262    /// This class adapt an original ArcMap and a NodeMap to get an
3263    /// arc map on the adapted digraph
3264    template <typename DigraphArcMap, typename DigraphNodeMap>
3265    class CombinedArcMap {
3266    public:
3267
3268      typedef Arc Key;
3269      typedef typename DigraphArcMap::Value Value;
3270
3271      /// \brief Constructor
3272      ///
3273      /// Constructor.
3274      CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
3275        : _arc_map(arc_map), _node_map(node_map) {}
3276
3277      /// \brief The subscript operator.
3278      ///
3279      /// The subscript operator.
3280      void set(const Arc& arc, const Value& val) {
3281        if (Parent::origArc(arc)) {
3282          _arc_map.set(arc, val);
3283        } else {
3284          _node_map.set(arc, val);
3285        }
3286      }
3287
3288      /// \brief The const subscript operator.
3289      ///
3290      /// The const subscript operator.
3291      Value operator[](const Key& arc) const {
3292        if (Parent::origArc(arc)) {
3293          return _arc_map[arc];
3294        } else {
3295          return _node_map[arc];
3296        }
3297      }
3298
3299      /// \brief The const subscript operator.
3300      ///
3301      /// The const subscript operator.
3302      Value& operator[](const Key& arc) {
3303        if (Parent::origArc(arc)) {
3304          return _arc_map[arc];
3305        } else {
3306          return _node_map[arc];
3307        }
3308      }
3309
3310    private:
3311      DigraphArcMap& _arc_map;
3312      DigraphNodeMap& _node_map;
3313    };
3314
3315    /// \brief Just gives back a combined arc map
3316    ///
3317    /// Just gives back a combined arc map
3318    template <typename DigraphArcMap, typename DigraphNodeMap>
3319    static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
3320    combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
3321      return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
3322    }
3323
3324    template <typename DigraphArcMap, typename DigraphNodeMap>
3325    static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
3326    combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
3327      return CombinedArcMap<const DigraphArcMap,
3328        DigraphNodeMap>(arc_map, node_map);
3329    }
3330
3331    template <typename DigraphArcMap, typename DigraphNodeMap>
3332    static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
3333    combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
3334      return CombinedArcMap<DigraphArcMap,
3335        const DigraphNodeMap>(arc_map, node_map);
3336    }
3337
3338    template <typename DigraphArcMap, typename DigraphNodeMap>
3339    static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
3340    combinedArcMap(const DigraphArcMap& arc_map,
3341                   const DigraphNodeMap& node_map) {
3342      return CombinedArcMap<const DigraphArcMap,
3343        const DigraphNodeMap>(arc_map, node_map);
3344    }
3345
3346  };
3347
3348  /// \brief Just gives back a node splitter
3349  ///
3350  /// Just gives back a node splitter
3351  template<typename Digraph>
3352  SplitNodes<Digraph>
3353  splitNodes(const Digraph& digraph) {
3354    return SplitNodes<Digraph>(digraph);
3355  }
3356
3357
3358} //namespace lemon
3359
3360#endif //LEMON_ADAPTORS_H
Note: See TracBrowser for help on using the repository browser.