COIN-OR::LEMON - Graph Library

source: lemon/lemon/adaptors.h @ 474:fbd6e04acf44

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

Various doc improvements for graph adaptors (#67)

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