COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/adaptors.h @ 445:75a5df083951

Last change on this file since 445:75a5df083951 was 440:88ed40ad0d4f, checked in by Alpar Juttner <alpar@…>, 15 years ago

Happy New Year again

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