COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/adaptors.h @ 449:91fcb8ed4cdc

Last change on this file since 449:91fcb8ed4cdc was 449:91fcb8ed4cdc, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Various bug fixes and code improvements in adaptors.h (#67)

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