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
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_ADAPTORS_H
20#define LEMON_ADAPTORS_H
21
22/// \ingroup graph_adaptors
23/// \file
24/// \brief Adaptor classes for digraphs and graphs
25///
26/// This file contains several useful adaptors for digraphs and graphs.
27
28#include <lemon/core.h>
29#include <lemon/maps.h>
30#include <lemon/bits/variant.h>
31
32#include <lemon/bits/graph_adaptor_extender.h>
33#include <lemon/tolerance.h>
34
35#include <algorithm>
36
37namespace lemon {
38
39  template<typename _Digraph>
40  class DigraphAdaptorBase {
41  public:
42    typedef _Digraph Digraph;
43    typedef DigraphAdaptorBase Adaptor;
44    typedef Digraph ParentDigraph;
45
46  protected:
47    Digraph* _digraph;
48    DigraphAdaptorBase() : _digraph(0) { }
49    void setDigraph(Digraph& digraph) { _digraph = &digraph; }
50
51  public:
52    DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
53
54    typedef typename Digraph::Node Node;
55    typedef typename Digraph::Arc Arc;
56
57    void first(Node& i) const { _digraph->first(i); }
58    void first(Arc& i) const { _digraph->first(i); }
59    void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
60    void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
61
62    void next(Node& i) const { _digraph->next(i); }
63    void next(Arc& i) const { _digraph->next(i); }
64    void nextIn(Arc& i) const { _digraph->nextIn(i); }
65    void nextOut(Arc& i) const { _digraph->nextOut(i); }
66
67    Node source(const Arc& a) const { return _digraph->source(a); }
68    Node target(const Arc& a) const { return _digraph->target(a); }
69
70    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
71    int nodeNum() const { return _digraph->nodeNum(); }
72
73    typedef ArcNumTagIndicator<Digraph> ArcNumTag;
74    int arcNum() const { return _digraph->arcNum(); }
75
76    typedef FindArcTagIndicator<Digraph> FindArcTag;
77    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {
78      return _digraph->findArc(u, v, prev);
79    }
80
81    Node addNode() { return _digraph->addNode(); }
82    Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
83
84    void erase(const Node& n) { _digraph->erase(n); }
85    void erase(const Arc& a) { _digraph->erase(a); }
86
87    void clear() { _digraph->clear(); }
88
89    int id(const Node& n) const { return _digraph->id(n); }
90    int id(const Arc& a) const { return _digraph->id(a); }
91
92    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
93    Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
94
95    int maxNodeId() const { return _digraph->maxNodeId(); }
96    int maxArcId() const { return _digraph->maxArcId(); }
97
98    typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
99    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
100
101    typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
102    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
103
104    template <typename _Value>
105    class NodeMap : public Digraph::template NodeMap<_Value> {
106    public:
107
108      typedef typename Digraph::template NodeMap<_Value> Parent;
109
110      explicit NodeMap(const Adaptor& adaptor)
111        : Parent(*adaptor._digraph) {}
112
113      NodeMap(const Adaptor& adaptor, const _Value& value)
114        : Parent(*adaptor._digraph, value) { }
115
116    private:
117      NodeMap& operator=(const NodeMap& cmap) {
118        return operator=<NodeMap>(cmap);
119      }
120
121      template <typename CMap>
122      NodeMap& operator=(const CMap& cmap) {
123        Parent::operator=(cmap);
124        return *this;
125      }
126
127    };
128
129    template <typename _Value>
130    class ArcMap : public Digraph::template ArcMap<_Value> {
131    public:
132
133      typedef typename Digraph::template ArcMap<_Value> Parent;
134
135      explicit ArcMap(const Adaptor& adaptor)
136        : Parent(*adaptor._digraph) {}
137
138      ArcMap(const Adaptor& adaptor, const _Value& value)
139        : Parent(*adaptor._digraph, value) {}
140
141    private:
142      ArcMap& operator=(const ArcMap& cmap) {
143        return operator=<ArcMap>(cmap);
144      }
145
146      template <typename CMap>
147      ArcMap& operator=(const CMap& cmap) {
148        Parent::operator=(cmap);
149        return *this;
150      }
151
152    };
153
154  };
155
156  template<typename _Graph>
157  class GraphAdaptorBase {
158  public:
159    typedef _Graph Graph;
160    typedef Graph ParentGraph;
161
162  protected:
163    Graph* _graph;
164
165    GraphAdaptorBase() : _graph(0) {}
166
167    void setGraph(Graph& graph) { _graph = &graph; }
168
169  public:
170    GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
171
172    typedef typename Graph::Node Node;
173    typedef typename Graph::Arc Arc;
174    typedef typename Graph::Edge Edge;
175
176    void first(Node& i) const { _graph->first(i); }
177    void first(Arc& i) const { _graph->first(i); }
178    void first(Edge& i) const { _graph->first(i); }
179    void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
180    void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
181    void firstInc(Edge &i, bool &d, const Node &n) const {
182      _graph->firstInc(i, d, n);
183    }
184
185    void next(Node& i) const { _graph->next(i); }
186    void next(Arc& i) const { _graph->next(i); }
187    void next(Edge& i) const { _graph->next(i); }
188    void nextIn(Arc& i) const { _graph->nextIn(i); }
189    void nextOut(Arc& i) const { _graph->nextOut(i); }
190    void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
191
192    Node u(const Edge& e) const { return _graph->u(e); }
193    Node v(const Edge& e) const { return _graph->v(e); }
194
195    Node source(const Arc& a) const { return _graph->source(a); }
196    Node target(const Arc& a) const { return _graph->target(a); }
197
198    typedef NodeNumTagIndicator<Graph> NodeNumTag;
199    int nodeNum() const { return _graph->nodeNum(); }
200
201    typedef ArcNumTagIndicator<Graph> ArcNumTag;
202    int arcNum() const { return _graph->arcNum(); }
203
204    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
205    int edgeNum() const { return _graph->edgeNum(); }
206
207    typedef FindArcTagIndicator<Graph> FindArcTag;
208    Arc findArc(const Node& u, const Node& v,
209                const Arc& prev = INVALID) const {
210      return _graph->findArc(u, v, prev);
211    }
212
213    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
214    Edge findEdge(const Node& u, const Node& v,
215                  const Edge& prev = INVALID) const {
216      return _graph->findEdge(u, v, prev);
217    }
218
219    Node addNode() { return _graph->addNode(); }
220    Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
221
222    void erase(const Node& i) { _graph->erase(i); }
223    void erase(const Edge& i) { _graph->erase(i); }
224
225    void clear() { _graph->clear(); }
226
227    bool direction(const Arc& a) const { return _graph->direction(a); }
228    Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
229
230    int id(const Node& v) const { return _graph->id(v); }
231    int id(const Arc& a) const { return _graph->id(a); }
232    int id(const Edge& e) const { return _graph->id(e); }
233
234    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
235    Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
236    Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
237
238    int maxNodeId() const { return _graph->maxNodeId(); }
239    int maxArcId() const { return _graph->maxArcId(); }
240    int maxEdgeId() const { return _graph->maxEdgeId(); }
241
242    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
243    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
244
245    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
246    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
247
248    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
249    EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
250
251    template <typename _Value>
252    class NodeMap : public Graph::template NodeMap<_Value> {
253    public:
254      typedef typename Graph::template NodeMap<_Value> Parent;
255      explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
256        : Parent(*adapter._graph) {}
257      NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
258        : Parent(*adapter._graph, value) {}
259
260    private:
261      NodeMap& operator=(const NodeMap& cmap) {
262        return operator=<NodeMap>(cmap);
263      }
264
265      template <typename CMap>
266      NodeMap& operator=(const CMap& cmap) {
267        Parent::operator=(cmap);
268        return *this;
269      }
270
271    };
272
273    template <typename _Value>
274    class ArcMap : public Graph::template ArcMap<_Value> {
275    public:
276      typedef typename Graph::template ArcMap<_Value> Parent;
277      explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
278        : Parent(*adapter._graph) {}
279      ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
280        : Parent(*adapter._graph, value) {}
281
282    private:
283      ArcMap& operator=(const ArcMap& cmap) {
284        return operator=<ArcMap>(cmap);
285      }
286
287      template <typename CMap>
288      ArcMap& operator=(const CMap& cmap) {
289        Parent::operator=(cmap);
290        return *this;
291      }
292    };
293
294    template <typename _Value>
295    class EdgeMap : public Graph::template EdgeMap<_Value> {
296    public:
297      typedef typename Graph::template EdgeMap<_Value> Parent;
298      explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
299        : Parent(*adapter._graph) {}
300      EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
301        : Parent(*adapter._graph, value) {}
302
303    private:
304      EdgeMap& operator=(const EdgeMap& cmap) {
305        return operator=<EdgeMap>(cmap);
306      }
307
308      template <typename CMap>
309      EdgeMap& operator=(const CMap& cmap) {
310        Parent::operator=(cmap);
311        return *this;
312      }
313    };
314
315  };
316
317  template <typename _Digraph>
318  class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
319  public:
320    typedef _Digraph Digraph;
321    typedef DigraphAdaptorBase<_Digraph> Parent;
322  protected:
323    ReverseDigraphBase() : Parent() { }
324  public:
325    typedef typename Parent::Node Node;
326    typedef typename Parent::Arc Arc;
327
328    void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
329    void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
330
331    void nextIn(Arc& a) const { Parent::nextOut(a); }
332    void nextOut(Arc& a) const { Parent::nextIn(a); }
333
334    Node source(const Arc& a) const { return Parent::target(a); }
335    Node target(const Arc& a) const { return Parent::source(a); }
336
337    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
338
339    typedef FindArcTagIndicator<Digraph> FindArcTag;
340    Arc findArc(const Node& u, const Node& v,
341                const Arc& prev = INVALID) const {
342      return Parent::findArc(v, u, prev);
343    }
344
345  };
346
347  /// \ingroup graph_adaptors
348  ///
349  /// \brief Adaptor class for reversing the orientation of the arcs in
350  /// a digraph.
351  ///
352  /// ReverseDigraph can be used for reversing the arcs in a digraph.
353  /// It conforms to the \ref concepts::Digraph "Digraph" concept.
354  ///
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.
365  template<typename _Digraph>
366  class ReverseDigraph :
367    public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
368  public:
369    typedef _Digraph Digraph;
370    typedef DigraphAdaptorExtender<
371      ReverseDigraphBase<_Digraph> > Parent;
372  protected:
373    ReverseDigraph() { }
374  public:
375
376    /// \brief Constructor
377    ///
378    /// Creates a reverse digraph adaptor for the given digraph.
379    explicit ReverseDigraph(Digraph& digraph) {
380      Parent::setDigraph(digraph);
381    }
382  };
383
384  /// \brief Returns a read-only ReverseDigraph adaptor
385  ///
386  /// This function just returns a read-only \ref ReverseDigraph adaptor.
387  /// \ingroup graph_adaptors
388  /// \relates ReverseDigraph
389  template<typename Digraph>
390  ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
391    return ReverseDigraph<const Digraph>(digraph);
392  }
393
394
395  template <typename _Digraph, typename _NodeFilterMap,
396            typename _ArcFilterMap, bool _checked = true>
397  class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
398  public:
399    typedef _Digraph Digraph;
400    typedef _NodeFilterMap NodeFilterMap;
401    typedef _ArcFilterMap ArcFilterMap;
402
403    typedef SubDigraphBase Adaptor;
404    typedef DigraphAdaptorBase<_Digraph> Parent;
405  protected:
406    NodeFilterMap* _node_filter;
407    ArcFilterMap* _arc_filter;
408    SubDigraphBase()
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
423    void first(Node& i) const {
424      Parent::first(i);
425      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
426    }
427
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);
434    }
435
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);
441    }
442
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);
448    }
449
450    void next(Node& i) const {
451      Parent::next(i);
452      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
453    }
454
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);
461    }
462
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);
468    }
469
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);
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
480    void unHide(const Node& n) const { _node_filter->set(n, true); }
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;
487    typedef False ArcNumTag;
488
489    typedef FindArcTagIndicator<Digraph> FindArcTag;
490    Arc findArc(const Node& source, const Node& target,
491                const Arc& prev = INVALID) const {
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>
503    class NodeMap : public SubMapExtender<Adaptor,
504      typename Parent::template NodeMap<_Value> > {
505    public:
506      typedef _Value Value;
507      typedef SubMapExtender<Adaptor, typename Parent::
508                             template NodeMap<Value> > MapParent;
509
510      NodeMap(const Adaptor& adaptor)
511        : MapParent(adaptor) {}
512      NodeMap(const Adaptor& adaptor, const Value& value)
513        : MapParent(adaptor, value) {}
514
515    private:
516      NodeMap& operator=(const NodeMap& cmap) {
517        return operator=<NodeMap>(cmap);
518      }
519
520      template <typename CMap>
521      NodeMap& operator=(const CMap& cmap) {
522        MapParent::operator=(cmap);
523        return *this;
524      }
525    };
526
527    template <typename _Value>
528    class ArcMap : public SubMapExtender<Adaptor,
529      typename Parent::template ArcMap<_Value> > {
530    public:
531      typedef _Value Value;
532      typedef SubMapExtender<Adaptor, typename Parent::
533                             template ArcMap<Value> > MapParent;
534
535      ArcMap(const Adaptor& adaptor)
536        : MapParent(adaptor) {}
537      ArcMap(const Adaptor& adaptor, const Value& value)
538        : MapParent(adaptor, value) {}
539
540    private:
541      ArcMap& operator=(const ArcMap& cmap) {
542        return operator=<ArcMap>(cmap);
543      }
544
545      template <typename CMap>
546      ArcMap& operator=(const CMap& cmap) {
547        MapParent::operator=(cmap);
548        return *this;
549      }
550    };
551
552  };
553
554  template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
555  class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
556    : public DigraphAdaptorBase<_Digraph> {
557  public:
558    typedef _Digraph Digraph;
559    typedef _NodeFilterMap NodeFilterMap;
560    typedef _ArcFilterMap ArcFilterMap;
561
562    typedef SubDigraphBase Adaptor;
563    typedef DigraphAdaptorBase<Digraph> Parent;
564  protected:
565    NodeFilterMap* _node_filter;
566    ArcFilterMap* _arc_filter;
567    SubDigraphBase()
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
582    void first(Node& i) const {
583      Parent::first(i);
584      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
585    }
586
587    void first(Arc& i) const {
588      Parent::first(i);
589      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
590    }
591
592    void firstIn(Arc& i, const Node& n) const {
593      Parent::firstIn(i, n);
594      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
595    }
596
597    void firstOut(Arc& i, const Node& n) const {
598      Parent::firstOut(i, n);
599      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
600    }
601
602    void next(Node& i) const {
603      Parent::next(i);
604      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
605    }
606    void next(Arc& i) const {
607      Parent::next(i);
608      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
609    }
610    void nextIn(Arc& i) const {
611      Parent::nextIn(i);
612      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
613    }
614
615    void nextOut(Arc& i) const {
616      Parent::nextOut(i);
617      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
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
623    void unHide(const Node& n) const { _node_filter->set(n, true); }
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;
630    typedef False ArcNumTag;
631
632    typedef FindArcTagIndicator<Digraph> FindArcTag;
633    Arc findArc(const Node& source, const Node& target,
634                const Arc& prev = INVALID) const {
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>
646    class NodeMap : public SubMapExtender<Adaptor,
647      typename Parent::template NodeMap<_Value> > {
648    public:
649      typedef _Value Value;
650      typedef SubMapExtender<Adaptor, typename Parent::
651                             template NodeMap<Value> > MapParent;
652
653      NodeMap(const Adaptor& adaptor)
654        : MapParent(adaptor) {}
655      NodeMap(const Adaptor& adaptor, const Value& value)
656        : MapParent(adaptor, value) {}
657
658    private:
659      NodeMap& operator=(const NodeMap& cmap) {
660        return operator=<NodeMap>(cmap);
661      }
662
663      template <typename CMap>
664      NodeMap& operator=(const CMap& cmap) {
665        MapParent::operator=(cmap);
666        return *this;
667      }
668    };
669
670    template <typename _Value>
671    class ArcMap : public SubMapExtender<Adaptor,
672      typename Parent::template ArcMap<_Value> > {
673    public:
674      typedef _Value Value;
675      typedef SubMapExtender<Adaptor, typename Parent::
676                             template ArcMap<Value> > MapParent;
677
678      ArcMap(const Adaptor& adaptor)
679        : MapParent(adaptor) {}
680      ArcMap(const Adaptor& adaptor, const Value& value)
681        : MapParent(adaptor, value) {}
682
683    private:
684      ArcMap& operator=(const ArcMap& cmap) {
685        return operator=<ArcMap>(cmap);
686      }
687
688      template <typename CMap>
689      ArcMap& operator=(const CMap& cmap) {
690        MapParent::operator=(cmap);
691        return *this;
692      }
693    };
694
695  };
696
697  /// \ingroup graph_adaptors
698  ///
699  /// \brief Adaptor class for hiding nodes and arcs in a digraph
700  ///
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
708  /// filtered out.
709  ///
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.
730  ///
731  /// \see FilterNodes
732  /// \see FilterArcs
733#ifdef DOXYGEN
734  template<typename _Digraph,
735           typename _NodeFilterMap,
736           typename _ArcFilterMap,
737           bool _checked>
738#else
739  template<typename _Digraph,
740           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
741           typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
742           bool _checked = true>
743#endif
744  class SubDigraph
745    : public DigraphAdaptorExtender<
746      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
747  public:
748    /// The type of the adapted digraph.
749    typedef _Digraph Digraph;
750    /// The type of the node filter map.
751    typedef _NodeFilterMap NodeFilterMap;
752    /// The type of the arc filter map.
753    typedef _ArcFilterMap ArcFilterMap;
754
755    typedef DigraphAdaptorExtender<
756      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> >
757    Parent;
758
759    typedef typename Parent::Node Node;
760    typedef typename Parent::Arc Arc;
761
762  protected:
763    SubDigraph() { }
764  public:
765
766    /// \brief Constructor
767    ///
768    /// Creates a subdigraph for the given digraph with the
769    /// given node and arc filter maps.
770    SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
771               ArcFilterMap& arc_filter) {
772      setDigraph(digraph);
773      setNodeFilterMap(node_filter);
774      setArcFilterMap(arc_filter);
775    }
776
777    /// \brief Hides the given node
778    ///
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.
783    void hide(const Node& n) const { Parent::hide(n); }
784
785    /// \brief Hides the given arc
786    ///
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.
791    void hide(const Arc& a) const { Parent::hide(a); }
792
793    /// \brief Shows the given node
794    ///
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.
798    void unHide(const Node& n) const { Parent::unHide(n); }
799
800    /// \brief Shows the given arc
801    ///
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.
805    void unHide(const Arc& a) const { Parent::unHide(a); }
806
807    /// \brief Returns \c true if the given node is hidden.
808    ///
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.
813    ///
814    /// This function returns \c true if the given arc is hidden.
815    bool hidden(const Arc& a) const { return Parent::hidden(a); }
816
817  };
818
819  /// \brief Returns a read-only SubDigraph adaptor
820  ///
821  /// This function just returns a read-only \ref SubDigraph adaptor.
822  /// \ingroup graph_adaptors
823  /// \relates SubDigraph
824  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
825  SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
826  subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
827    return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
828      (digraph, nfm, afm);
829  }
830
831  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
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>
836      (digraph, nfm, afm);
837  }
838
839  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
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>
844      (digraph, nfm, afm);
845  }
846
847  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
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,
852      const ArcFilterMap>(digraph, nfm, afm);
853  }
854
855
856  template <typename _Graph, typename _NodeFilterMap,
857            typename _EdgeFilterMap, bool _checked = true>
858  class SubGraphBase : public GraphAdaptorBase<_Graph> {
859  public:
860    typedef _Graph Graph;
861    typedef _NodeFilterMap NodeFilterMap;
862    typedef _EdgeFilterMap EdgeFilterMap;
863
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;
983    typedef False ArcNumTag;
984    typedef False EdgeNumTag;
985
986    typedef FindArcTagIndicator<Graph> FindArcTag;
987    Arc findArc(const Node& u, const Node& v,
988                const Arc& prev = INVALID) const {
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    }
998
999    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1000    Edge findEdge(const Node& u, const Node& v,
1001                  const Edge& prev = INVALID) const {
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
1090  template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>
1091  class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false>
1092    : public GraphAdaptorBase<_Graph> {
1093  public:
1094    typedef _Graph Graph;
1095    typedef _NodeFilterMap NodeFilterMap;
1096    typedef _EdgeFilterMap EdgeFilterMap;
1097
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;
1185    typedef False ArcNumTag;
1186    typedef False EdgeNumTag;
1187
1188    typedef FindArcTagIndicator<Graph> FindArcTag;
1189    Arc findArc(const Node& u, const Node& v,
1190                const Arc& prev = INVALID) const {
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    }
1197
1198    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1199    Edge findEdge(const Node& u, const Node& v,
1200                  const Edge& prev = INVALID) const {
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
1287  ///
1288  /// \brief Adaptor class for hiding nodes and edges in an undirected
1289  /// graph.
1290  ///
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
1298  /// filtered out.
1299  ///
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.
1320  ///
1321  /// \see FilterNodes
1322  /// \see FilterEdges
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
1334  class SubGraph
1335    : public GraphAdaptorExtender<
1336      SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, _checked> > {
1337  public:
1338    /// The type of the adapted graph.
1339    typedef _Graph Graph;
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
1345    typedef GraphAdaptorExtender<
1346      SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, _checked> > Parent;
1347
1348    typedef typename Parent::Node Node;
1349    typedef typename Parent::Edge Edge;
1350
1351  protected:
1352    SubGraph() { }
1353  public:
1354
1355    /// \brief Constructor
1356    ///
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,
1360             EdgeFilterMap& edge_filter_map) {
1361      setGraph(graph);
1362      setNodeFilterMap(node_filter_map);
1363      setEdgeFilterMap(edge_filter_map);
1364    }
1365
1366    /// \brief Hides the given node
1367    ///
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.
1372    void hide(const Node& n) const { Parent::hide(n); }
1373
1374    /// \brief Hides the given edge
1375    ///
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.
1380    void hide(const Edge& e) const { Parent::hide(e); }
1381
1382    /// \brief Shows the given node
1383    ///
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.
1387    void unHide(const Node& n) const { Parent::unHide(n); }
1388
1389    /// \brief Shows the given edge
1390    ///
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.
1394    void unHide(const Edge& e) const { Parent::unHide(e); }
1395
1396    /// \brief Returns \c true if the given node is hidden.
1397    ///
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.
1402    ///
1403    /// This function returns \c true if the given edge is hidden.
1404    bool hidden(const Edge& e) const { return Parent::hidden(e); }
1405  };
1406
1407  /// \brief Returns a read-only SubGraph adaptor
1408  ///
1409  /// This function just returns a read-only \ref SubGraph adaptor.
1410  /// \ingroup graph_adaptors
1411  /// \relates SubGraph
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
1442
1443  /// \ingroup graph_adaptors
1444  ///
1445  /// \brief Adaptor class for hiding nodes in a digraph or a graph.
1446  ///
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.
1454  ///
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.
1474#ifdef DOXYGEN
1475  template<typename _Graph,
1476           typename _NodeFilterMap,
1477           bool _checked>
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    ///
1509    /// Creates a subgraph for the given digraph or graph with the
1510    /// given node filter map.
1511#ifdef DOXYGEN
1512    FilterNodes(_Graph& graph, _NodeFilterMap& node_filter) :
1513#else
1514    FilterNodes(Digraph& graph, NodeFilterMap& node_filter) :
1515#endif
1516      Parent(), const_true_map(true) {
1517      Parent::setDigraph(graph);
1518      Parent::setNodeFilterMap(node_filter);
1519      Parent::setArcFilterMap(const_true_map);
1520    }
1521
1522    /// \brief Hides the given node
1523    ///
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.
1528    void hide(const Node& n) const { Parent::hide(n); }
1529
1530    /// \brief Shows the given node
1531    ///
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.
1535    void unHide(const Node& n) const { Parent::unHide(n); }
1536
1537    /// \brief Returns \c true if the given node is hidden.
1538    ///
1539    /// This function returns \c true if the given node is hidden.
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
1579  /// \brief Returns a read-only FilterNodes adaptor
1580  ///
1581  /// This function just returns a read-only \ref FilterNodes adaptor.
1582  /// \ingroup graph_adaptors
1583  /// \relates FilterNodes
1584  template<typename Digraph, typename NodeFilterMap>
1585  FilterNodes<const Digraph, NodeFilterMap>
1586  filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
1587    return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
1588  }
1589
1590  template<typename Digraph, typename NodeFilterMap>
1591  FilterNodes<const Digraph, const NodeFilterMap>
1592  filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
1593    return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
1594  }
1595
1596  /// \ingroup graph_adaptors
1597  ///
1598  /// \brief Adaptor class for hiding arcs in a digraph.
1599  ///
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.
1605  ///
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
1626  class FilterArcs :
1627    public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
1628                      _ArcFilterMap, false> {
1629  public:
1630
1631    typedef _Digraph Digraph;
1632    typedef _ArcFilterMap ArcFilterMap;
1633
1634    typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
1635                       ArcFilterMap, false> Parent;
1636
1637    typedef typename Parent::Arc Arc;
1638
1639  protected:
1640    ConstMap<typename Digraph::Node, bool> const_true_map;
1641
1642    FilterArcs() : const_true_map(true) {
1643      Parent::setNodeFilterMap(const_true_map);
1644    }
1645
1646  public:
1647
1648    /// \brief Constructor
1649    ///
1650    /// Creates a subdigraph for the given digraph with the given arc
1651    /// filter map.
1652    FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
1653      : Parent(), const_true_map(true) {
1654      Parent::setDigraph(digraph);
1655      Parent::setNodeFilterMap(const_true_map);
1656      Parent::setArcFilterMap(arc_filter);
1657    }
1658
1659    /// \brief Hides the given arc
1660    ///
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.
1665    void hide(const Arc& a) const { Parent::hide(a); }
1666
1667    /// \brief Shows the given arc
1668    ///
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.
1672    void unHide(const Arc& a) const { Parent::unHide(a); }
1673
1674    /// \brief Returns \c true if the given arc is hidden.
1675    ///
1676    /// This function returns \c true if the given arc is hidden.
1677    bool hidden(const Arc& a) const { return Parent::hidden(a); }
1678
1679  };
1680
1681  /// \brief Returns a read-only FilterArcs adaptor
1682  ///
1683  /// This function just returns a read-only \ref FilterArcs adaptor.
1684  /// \ingroup graph_adaptors
1685  /// \relates FilterArcs
1686  template<typename Digraph, typename ArcFilterMap>
1687  FilterArcs<const Digraph, ArcFilterMap>
1688  filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
1689    return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
1690  }
1691
1692  template<typename Digraph, typename ArcFilterMap>
1693  FilterArcs<const Digraph, const ArcFilterMap>
1694  filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
1695    return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
1696  }
1697
1698  /// \ingroup graph_adaptors
1699  ///
1700  /// \brief Adaptor class for hiding edges in a graph.
1701  ///
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.
1707  ///
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
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    ///
1748    /// Creates a subgraph for the given graph with the given edge
1749    /// filter map.
1750    FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) :
1751      Parent(), const_true_map(true) {
1752      Parent::setGraph(graph);
1753      Parent::setNodeFilterMap(const_true_map);
1754      Parent::setEdgeFilterMap(edge_filter_map);
1755    }
1756
1757    /// \brief Hides the given edge
1758    ///
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.
1763    void hide(const Edge& e) const { Parent::hide(e); }
1764
1765    /// \brief Shows the given edge
1766    ///
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.
1770    void unHide(const Edge& e) const { Parent::unHide(e); }
1771
1772    /// \brief Returns \c true if the given edge is hidden.
1773    ///
1774    /// This function returns \c true if the given edge is hidden.
1775    bool hidden(const Edge& e) const { return Parent::hidden(e); }
1776
1777  };
1778
1779  /// \brief Returns a read-only FilterEdges adaptor
1780  ///
1781  /// This function just returns a read-only \ref FilterEdges adaptor.
1782  /// \ingroup graph_adaptors
1783  /// \relates FilterEdges
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
1796
1797  template <typename _Digraph>
1798  class UndirectorBase {
1799  public:
1800    typedef _Digraph Digraph;
1801    typedef UndirectorBase Adaptor;
1802
1803    typedef True UndirectedTag;
1804
1805    typedef typename Digraph::Arc Edge;
1806    typedef typename Digraph::Node Node;
1807
1808    class Arc : public Edge {
1809      friend class UndirectorBase;
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 {
1822        return _forward == other._forward &&
1823          static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
1824      }
1825      bool operator!=(const Arc &other) const {
1826        return _forward != other._forward ||
1827          static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
1828      }
1829      bool operator<(const Arc &other) const {
1830        return _forward < other._forward ||
1831          (_forward == other._forward &&
1832           static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
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) {
1851        a._forward = false;
1852      } else {
1853        _digraph->next(a);
1854        a._forward = true;
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 ) {
1869        a._forward = false;
1870      } else {
1871        _digraph->firstOut(a, n);
1872        a._forward = true;
1873      }
1874    }
1875    void nextOut(Arc &a) const {
1876      if (!a._forward) {
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        }
1883      }
1884      else {
1885        _digraph->nextOut(a);
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 ) {
1892        a._forward = false;
1893      } else {
1894        _digraph->firstIn(a, n);
1895        a._forward = true;
1896      }
1897    }
1898    void nextIn(Arc &a) const {
1899      if (!a._forward) {
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        }
1906      }
1907      else {
1908        _digraph->nextIn(a);
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) {
1922        Node s = _digraph->source(e);
1923        _digraph->nextOut(e);
1924        if (e != INVALID) return;
1925        d = false;
1926        _digraph->firstIn(e, s);
1927      } else {
1928        _digraph->nextIn(e);
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(); }
1974    Edge addEdge(const Node& u, const Node& v) {
1975      return _digraph->addArc(u, v);
1976    }
1977
1978    void erase(const Node& i) { _digraph->erase(i); }
1979    void erase(const Edge& i) { _digraph->erase(i); }
1980
1981    void clear() { _digraph->clear(); }
1982
1983    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
1984    int nodeNum() const { return _digraph->nodeNum(); }
1985
1986    typedef ArcNumTagIndicator<Digraph> ArcNumTag;
1987    int arcNum() const { return 2 * _digraph->arcNum(); }
1988
1989    typedef ArcNumTag EdgeNumTag;
1990    int edgeNum() const { return _digraph->arcNum(); }
1991
1992    typedef FindArcTagIndicator<Digraph> FindArcTag;
1993    Arc findArc(Node s, Node t, Arc p = INVALID) const {
1994      if (p == INVALID) {
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);
1999      } else if (direction(p)) {
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);
2004      } else {
2005        Edge arc = _digraph->findArc(t, s, p);
2006        if (arc != INVALID) return direct(arc, false);
2007      }
2008      return INVALID;
2009    }
2010
2011    typedef FindArcTag FindEdgeTag;
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;
2019        } else if (_digraph->source(p) == s) {
2020          Edge arc = _digraph->findArc(s, t, p);
2021          if (arc != INVALID) return arc;
2022          arc = _digraph->findArc(t, s);
2023          if (arc != INVALID) return arc;
2024        } else {
2025          Edge arc = _digraph->findArc(t, s, p);
2026          if (arc != INVALID) return arc;
2027        }
2028      } else {
2029        return _digraph->findArc(s, t, p);
2030      }
2031      return INVALID;
2032    }
2033
2034  private:
2035
2036    template <typename _Value>
2037    class ArcMapBase {
2038    private:
2039
2040      typedef typename Digraph::template ArcMap<_Value> MapImpl;
2041
2042    public:
2043
2044      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
2045
2046      typedef _Value Value;
2047      typedef Arc Key;
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;
2052
2053      ArcMapBase(const Adaptor& adaptor) :
2054        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
2055
2056      ArcMapBase(const Adaptor& adaptor, const Value& v)
2057        : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
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);
2064        }
2065      }
2066
2067      ConstReturnValue operator[](const Arc& a) const {
2068        if (direction(a)) {
2069          return _forward[a];
2070        } else {
2071          return _backward[a];
2072        }
2073      }
2074
2075      ReturnValue operator[](const Arc& a) {
2076        if (direction(a)) {
2077          return _forward[a];
2078        } else {
2079          return _backward[a];
2080        }
2081      }
2082
2083    protected:
2084
2085      MapImpl _forward, _backward;
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
2098      explicit NodeMap(const Adaptor& adaptor)
2099        : Parent(*adaptor._digraph) {}
2100
2101      NodeMap(const Adaptor& adaptor, const _Value& value)
2102        : Parent(*adaptor._digraph, value) { }
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      }
2114
2115    };
2116
2117    template <typename _Value>
2118    class ArcMap
2119      : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
2120    {
2121    public:
2122      typedef _Value Value;
2123      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
2124
2125      explicit ArcMap(const Adaptor& adaptor)
2126        : Parent(adaptor) {}
2127
2128      ArcMap(const Adaptor& adaptor, const Value& value)
2129        : Parent(adaptor, value) {}
2130
2131    private:
2132      ArcMap& operator=(const ArcMap& cmap) {
2133        return operator=<ArcMap>(cmap);
2134      }
2135
2136      template <typename CMap>
2137      ArcMap& operator=(const CMap& cmap) {
2138        Parent::operator=(cmap);
2139        return *this;
2140      }
2141    };
2142
2143    template <typename _Value>
2144    class EdgeMap : public Digraph::template ArcMap<_Value> {
2145    public:
2146
2147      typedef _Value Value;
2148      typedef typename Digraph::template ArcMap<Value> Parent;
2149
2150      explicit EdgeMap(const Adaptor& adaptor)
2151        : Parent(*adaptor._digraph) {}
2152
2153      EdgeMap(const Adaptor& adaptor, const Value& value)
2154        : Parent(*adaptor._digraph, value) {}
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;
2170    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
2171
2172    typedef typename ItemSetTraits<Digraph, Edge>::ItemNotifier EdgeNotifier;
2173    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
2174
2175  protected:
2176
2177    UndirectorBase() : _digraph(0) {}
2178
2179    Digraph* _digraph;
2180
2181    void setDigraph(Digraph& digraph) {
2182      _digraph = &digraph;
2183    }
2184
2185  };
2186
2187  /// \ingroup graph_adaptors
2188  ///
2189  /// \brief Adaptor class for viewing a digraph as an undirected graph.
2190  ///
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.
2195  ///
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.)
2210  template<typename _Digraph>
2211  class Undirector
2212    : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
2213  public:
2214    typedef _Digraph Digraph;
2215    typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
2216  protected:
2217    Undirector() { }
2218  public:
2219
2220    /// \brief Constructor
2221    ///
2222    /// Creates an undirected graph from the given digraph.
2223    Undirector(_Digraph& digraph) {
2224      setDigraph(digraph);
2225    }
2226
2227    /// \brief Arc map combined from two original arc maps
2228    ///
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).
2233    template <typename _ForwardMap, typename _BackwardMap>
2234    class CombinedArcMap {
2235    public:
2236
2237      typedef _ForwardMap ForwardMap;
2238      typedef _BackwardMap BackwardMap;
2239
2240      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
2241
2242      /// The key type of the map
2243      typedef typename Parent::Arc Key;
2244      /// The value type of the map
2245      typedef typename ForwardMap::Value Value;
2246
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
2252      /// Constructor
2253      CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
2254        : _forward(&forward), _backward(&backward) {}
2255
2256      /// Sets the value associated with the given key.
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        }
2263      }
2264
2265      /// Returns the value associated with the given key.
2266      ConstReturnValue operator[](const Key& e) const {
2267        if (Parent::direction(e)) {
2268          return (*_forward)[e];
2269        } else {
2270          return (*_backward)[e];
2271        }
2272      }
2273
2274      /// Returns a reference to the value associated with the given key.
2275      ReturnValue operator[](const Key& e) {
2276        if (Parent::direction(e)) {
2277          return (*_forward)[e];
2278        } else {
2279          return (*_backward)[e];
2280        }
2281      }
2282
2283    protected:
2284
2285      ForwardMap* _forward;
2286      BackwardMap* _backward;
2287
2288    };
2289
2290    /// \brief Returns a combined arc map
2291    ///
2292    /// This function just returns a combined arc map.
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
2322  /// \brief Returns a read-only Undirector adaptor
2323  ///
2324  /// This function just returns a read-only \ref Undirector adaptor.
2325  /// \ingroup graph_adaptors
2326  /// \relates Undirector
2327  template<typename Digraph>
2328  Undirector<const Digraph>
2329  undirector(const Digraph& digraph) {
2330    return Undirector<const Digraph>(digraph);
2331  }
2332
2333
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 {
2351      bool d = true;
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 {
2356      bool d = true;
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
2384    typedef EdgeNumTagIndicator<Graph> ArcNumTag;
2385    int arcNum() const { return _graph->edgeNum(); }
2386
2387    typedef FindEdgeTagIndicator<Graph> FindArcTag;
2388    Arc findArc(const Node& u, const Node& v,
2389                const Arc& prev = INVALID) const {
2390      Arc arc = _graph->findEdge(u, v, prev);
2391      while (arc != INVALID && source(arc) != u) {
2392        arc = _graph->findEdge(u, v, arc);
2393      }
2394      return arc;
2395    }
2396
2397    Node addNode() {
2398      return Node(_graph->addNode());
2399    }
2400
2401    Arc addArc(const Node& u, const Node& v) {
2402      Arc arc = _graph->addEdge(u, v);
2403      _direction->set(arc, _graph->u(arc) == u);
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      }
2449
2450    };
2451
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
2490  };
2491
2492  /// \ingroup graph_adaptors
2493  ///
2494  /// \brief Adaptor class for orienting the edges of a graph to get a digraph
2495  ///
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.
2502  ///
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.
2506  ///
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
2519  template<typename _Graph,
2520           typename _DirectionMap>
2521#else
2522  template<typename _Graph,
2523           typename _DirectionMap = typename _Graph::template EdgeMap<bool> >
2524#endif
2525  class Orienter :
2526    public DigraphAdaptorExtender<OrienterBase<_Graph, _DirectionMap> > {
2527  public:
2528
2529    /// The type of the adapted graph.
2530    typedef _Graph Graph;
2531    /// The type of the direction edge map.
2532    typedef _DirectionMap DirectionMap;
2533
2534    typedef DigraphAdaptorExtender<
2535      OrienterBase<_Graph, _DirectionMap> > Parent;
2536    typedef typename Parent::Arc Arc;
2537  protected:
2538    Orienter() { }
2539  public:
2540
2541    /// \brief Constructor
2542    ///
2543    /// Constructor of the adaptor.
2544    Orienter(Graph& graph, DirectionMap& direction) {
2545      setGraph(graph);
2546      setDirectionMap(direction);
2547    }
2548
2549    /// \brief Reverses the given arc
2550    ///
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.
2554    void reverseArc(const Arc& a) {
2555      Parent::reverseArc(a);
2556    }
2557  };
2558
2559  /// \brief Returns a read-only Orienter adaptor
2560  ///
2561  /// This function just returns a read-only \ref Orienter adaptor.
2562  /// \ingroup graph_adaptors
2563  /// \relates Orienter
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);
2568  }
2569
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  ///
2645  /// \brief Adaptor class for composing the residual digraph for directed
2646  /// flow and circulation problems.
2647  ///
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.
2662  ///
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.
2676  ///
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
2690  template<typename _Digraph,
2691           typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2692           typename _FlowMap = _CapacityMap,
2693           typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
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> > >
2702#endif
2703  {
2704  public:
2705
2706    /// The type of the underlying digraph.
2707    typedef _Digraph Digraph;
2708    /// The type of the capacity map.
2709    typedef _CapacityMap CapacityMap;
2710    /// The type of the flow map.
2711    typedef _FlowMap FlowMap;
2712    typedef _Tolerance Tolerance;
2713
2714    typedef typename CapacityMap::Value Value;
2715    typedef Residual Adaptor;
2716
2717  protected:
2718
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::
2728    template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
2729
2730    typedef FilterArcs<Undirected, ArcFilter> Parent;
2731
2732    const CapacityMap* _capacity;
2733    FlowMap* _flow;
2734
2735    Undirected _graph;
2736    ForwardFilter _forward_filter;
2737    BackwardFilter _backward_filter;
2738    ArcFilter _arc_filter;
2739
2740  public:
2741
2742    /// \brief Constructor
2743    ///
2744    /// Constructor of the residual digraph adaptor. The parameters are the
2745    /// digraph, the capacity map, the flow map, and a tolerance object.
2746    Residual(const Digraph& digraph, const CapacityMap& capacity,
2747             FlowMap& flow, const Tolerance& tolerance = Tolerance())
2748      : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
2749        _forward_filter(capacity, flow, tolerance),
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
2759    /// \brief Returns the residual capacity of the given arc.
2760    ///
2761    /// Returns the residual capacity of the given arc.
2762    Value residualCapacity(const Arc& a) const {
2763      if (Undirected::direction(a)) {
2764        return (*_capacity)[a] - (*_flow)[a];
2765      } else {
2766        return (*_flow)[a];
2767      }
2768    }
2769
2770    /// \brief Augment on the given arc in the residual digraph.
2771    ///
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.
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);
2780      }
2781    }
2782
2783    /// \brief Returns \c true if the given residual arc is a forward arc.
2784    ///
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.
2787    static bool forward(const Arc& a) {
2788      return Undirected::direction(a);
2789    }
2790
2791    /// \brief Returns \c true if the given residual arc is a backward arc.
2792    ///
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.
2795    static bool backward(const Arc& a) {
2796      return !Undirected::direction(a);
2797    }
2798
2799    /// \brief Returns the forward oriented residual arc.
2800    ///
2801    /// Returns the forward oriented residual arc related to the given
2802    /// arc of the underlying digraph.
2803    static Arc forward(const typename Digraph::Arc& a) {
2804      return Undirected::direct(a, true);
2805    }
2806
2807    /// \brief Returns the backward oriented residual arc.
2808    ///
2809    /// Returns the backward oriented residual arc related to the given
2810    /// arc of the underlying digraph.
2811    static Arc backward(const typename Digraph::Arc& a) {
2812      return Undirected::direct(a, false);
2813    }
2814
2815    /// \brief Residual capacity map.
2816    ///
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.
2820    class ResidualCapacity {
2821    protected:
2822      const Adaptor* _adaptor;
2823    public:
2824      /// The key type of the map
2825      typedef Arc Key;
2826      /// The value type of the map
2827      typedef typename _CapacityMap::Value Value;
2828
2829      /// Constructor
2830      ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
2831
2832      /// Returns the value associated with the given residual arc
2833      Value operator[](const Arc& a) const {
2834        return _adaptor->residualCapacity(a);
2835      }
2836
2837    };
2838
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
2846  };
2847
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
2863  template <typename _Digraph>
2864  class SplitNodesBase {
2865  public:
2866
2867    typedef _Digraph Digraph;
2868    typedef DigraphAdaptorBase<const _Digraph> Parent;
2869    typedef SplitNodesBase Adaptor;
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:
2883
2884    class Node : public DigraphNode {
2885      friend class SplitNodesBase;
2886      template <typename T> friend class NodeMapBase;
2887    private:
2888
2889      bool _in;
2890      Node(DigraphNode node, bool in)
2891        : DigraphNode(node), _in(in) {}
2892
2893    public:
2894
2895      Node() {}
2896      Node(Invalid) : DigraphNode(INVALID), _in(true) {}
2897
2898      bool operator==(const Node& node) const {
2899        return DigraphNode::operator==(node) && _in == node._in;
2900      }
2901
2902      bool operator!=(const Node& node) const {
2903        return !(*this == node);
2904      }
2905
2906      bool operator<(const Node& node) const {
2907        return DigraphNode::operator<(node) ||
2908          (DigraphNode::operator==(node) && _in < node._in);
2909      }
2910    };
2911
2912    class Arc {
2913      friend class SplitNodesBase;
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) {}
2920
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      }
2939
2940      bool operator!=(const Arc& arc) const {
2941        return !(*this == arc);
2942      }
2943
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) {
2970        n._in = false;
2971      } else {
2972        n._in = true;
2973        _digraph->next(n);
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();
2982        _digraph->first(e._item.first());
2983      }
2984    }
2985
2986    void next(Arc& e) const {
2987      if (e._item.secondState()) {
2988        _digraph->next(e._item.second());
2989        if (e._item.second() == INVALID) {
2990          e._item.setFirst();
2991          _digraph->first(e._item.first());
2992        }
2993      } else {
2994        _digraph->next(e._item.first());
2995      }
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();
3003        _digraph->firstOut(e._item.first(), n);
3004      }
3005    }
3006
3007    void nextOut(Arc& e) const {
3008      if (!e._item.firstState()) {
3009        e._item.setFirst(INVALID);
3010      } else {
3011        _digraph->nextOut(e._item.first());
3012      }
3013    }
3014
3015    void firstIn(Arc& e, const Node& n) const {
3016      if (!n._in) {
3017        e._item.setSecond(n);
3018      } else {
3019        e._item.setFirst();
3020        _digraph->firstIn(e._item.first(), n);
3021      }
3022    }
3023
3024    void nextIn(Arc& e) const {
3025      if (!e._item.firstState()) {
3026        e._item.setFirst(INVALID);
3027      } else {
3028        _digraph->nextIn(e._item.first());
3029      }
3030    }
3031
3032    Node source(const Arc& e) const {
3033      if (e._item.firstState()) {
3034        return Node(_digraph->source(e._item.first()), false);
3035      } else {
3036        return Node(e._item.second(), true);
3037      }
3038    }
3039
3040    Node target(const Arc& e) const {
3041      if (e._item.firstState()) {
3042        return Node(_digraph->target(e._item.first()), true);
3043      } else {
3044        return Node(e._item.second(), false);
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 {
3073      return std::max(_digraph->maxNodeId() << 1,
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
3114    typedef True ArcNumTag;
3115    int arcNum() const {
3116      return countArcs(*_digraph) + countNodes(*_digraph);
3117    }
3118
3119    typedef True FindArcTag;
3120    Arc findArc(const Node& u, const Node& v,
3121                const Arc& prev = INVALID) const {
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);
3126        }
3127      }
3128      else if (outNode(u) && inNode(v)) {
3129        return Arc(::lemon::findArc(*_digraph, u, v, prev));
3130      }
3131      return INVALID;
3132    }
3133
3134  private:
3135
3136    template <typename _Value>
3137    class NodeMapBase
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;
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;
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) {}
3154
3155      void set(const Node& key, const Value& val) {
3156        if (Adaptor::inNode(key)) { _in_map.set(key, val); }
3157        else {_out_map.set(key, val); }
3158      }
3159
3160      ReturnValue operator[](const Node& key) {
3161        if (Adaptor::inNode(key)) { return _in_map[key]; }
3162        else { return _out_map[key]; }
3163      }
3164
3165      ConstReturnValue operator[](const Node& key) const {
3166        if (Adaptor::inNode(key)) { return _in_map[key]; }
3167        else { return _out_map[key]; }
3168      }
3169
3170    private:
3171      NodeImpl _in_map, _out_map;
3172    };
3173
3174    template <typename _Value>
3175    class ArcMapBase
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;
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;
3187
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) {}
3193
3194      void set(const Arc& key, const Value& val) {
3195        if (Adaptor::origArc(key)) {
3196          _arc_map.set(key._item.first(), val);
3197        } else {
3198          _node_map.set(key._item.second(), val);
3199        }
3200      }
3201
3202      ReturnValue operator[](const Arc& key) {
3203        if (Adaptor::origArc(key)) {
3204          return _arc_map[key._item.first()];
3205        } else {
3206          return _node_map[key._item.second()];
3207        }
3208      }
3209
3210      ConstReturnValue operator[](const Arc& key) const {
3211        if (Adaptor::origArc(key)) {
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>
3226    class NodeMap
3227      : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
3228    {
3229    public:
3230      typedef _Value Value;
3231      typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
3232
3233      NodeMap(const Adaptor& adaptor)
3234        : Parent(adaptor) {}
3235
3236      NodeMap(const Adaptor& adaptor, const Value& value)
3237        : Parent(adaptor, value) {}
3238
3239    private:
3240      NodeMap& operator=(const NodeMap& cmap) {
3241        return operator=<NodeMap>(cmap);
3242      }
3243
3244      template <typename CMap>
3245      NodeMap& operator=(const CMap& cmap) {
3246        Parent::operator=(cmap);
3247        return *this;
3248      }
3249    };
3250
3251    template <typename _Value>
3252    class ArcMap
3253      : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
3254    {
3255    public:
3256      typedef _Value Value;
3257      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
3258
3259      ArcMap(const Adaptor& adaptor)
3260        : Parent(adaptor) {}
3261
3262      ArcMap(const Adaptor& adaptor, const Value& value)
3263        : Parent(adaptor, value) {}
3264
3265    private:
3266      ArcMap& operator=(const ArcMap& cmap) {
3267        return operator=<ArcMap>(cmap);
3268      }
3269
3270      template <typename CMap>
3271      ArcMap& operator=(const CMap& cmap) {
3272        Parent::operator=(cmap);
3273        return *this;
3274      }
3275    };
3276
3277  protected:
3278
3279    SplitNodesBase() : _digraph(0) {}
3280
3281    Digraph* _digraph;
3282
3283    void setDigraph(Digraph& digraph) {
3284      _digraph = &digraph;
3285    }
3286
3287  };
3288
3289  /// \ingroup graph_adaptors
3290  ///
3291  /// \brief Adaptor class for splitting the nodes of a digraph.
3292  ///
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.
3302  ///
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.
3309  ///
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.
3316  template <typename _Digraph>
3317  class SplitNodes
3318    : public DigraphAdaptorExtender<SplitNodesBase<const _Digraph> > {
3319  public:
3320    typedef _Digraph Digraph;
3321    typedef DigraphAdaptorExtender<SplitNodesBase<const Digraph> > Parent;
3322
3323    typedef typename Digraph::Node DigraphNode;
3324    typedef typename Digraph::Arc DigraphArc;
3325
3326    typedef typename Parent::Node Node;
3327    typedef typename Parent::Arc Arc;
3328
3329    /// \brief Constructor
3330    ///
3331    /// Constructor of the adaptor.
3332    SplitNodes(const Digraph& g) {
3333      Parent::setDigraph(g);
3334    }
3335
3336    /// \brief Returns \c true if the given node is an in-node.
3337    ///
3338    /// Returns \c true if the given node is an in-node.
3339    static bool inNode(const Node& n) {
3340      return Parent::inNode(n);
3341    }
3342
3343    /// \brief Returns \c true if the given node is an out-node.
3344    ///
3345    /// Returns \c true if the given node is an out-node.
3346    static bool outNode(const Node& n) {
3347      return Parent::outNode(n);
3348    }
3349
3350    /// \brief Returns \c true if the given arc is an original arc.
3351    ///
3352    /// Returns \c true if the given arc is one of the arcs in the
3353    /// original digraph.
3354    static bool origArc(const Arc& a) {
3355      return Parent::origArc(a);
3356    }
3357
3358    /// \brief Returns \c true if the given arc is a bind arc.
3359    ///
3360    /// Returns \c true if the given arc is a bind arc, i.e. it connects
3361    /// an in-node and an out-node.
3362    static bool bindArc(const Arc& a) {
3363      return Parent::bindArc(a);
3364    }
3365
3366    /// \brief Returns the in-node created from the given original node.
3367    ///
3368    /// Returns the in-node created from the given original node.
3369    static Node inNode(const DigraphNode& n) {
3370      return Parent::inNode(n);
3371    }
3372
3373    /// \brief Returns the out-node created from the given original node.
3374    ///
3375    /// Returns the out-node created from the given original node.
3376    static Node outNode(const DigraphNode& n) {
3377      return Parent::outNode(n);
3378    }
3379
3380    /// \brief Returns the bind arc that corresponds to the given
3381    /// original node.
3382    ///
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.
3386    static Arc arc(const DigraphNode& n) {
3387      return Parent::arc(n);
3388    }
3389
3390    /// \brief Returns the arc that corresponds to the given original arc.
3391    ///
3392    /// Returns the arc in the adaptor that corresponds to the given
3393    /// original arc.
3394    static Arc arc(const DigraphArc& a) {
3395      return Parent::arc(a);
3396    }
3397
3398    /// \brief Node map combined from two original node maps
3399    ///
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).
3404    template <typename InNodeMap, typename OutNodeMap>
3405    class CombinedNodeMap {
3406    public:
3407
3408      /// The key type of the map
3409      typedef Node Key;
3410      /// The value type of the map
3411      typedef typename InNodeMap::Value Value;
3412
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
3419      /// Constructor
3420      CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
3421        : _in_map(in_map), _out_map(out_map) {}
3422
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.
3433      Value& operator[](const Key& key) {
3434        if (Parent::inNode(key)) {
3435          return _in_map[key];
3436        } else {
3437          return _out_map[key];
3438        }
3439      }
3440
3441      /// Sets the value associated with the given key.
3442      void set(const Key& key, const Value& value) {
3443        if (Parent::inNode(key)) {
3444          _in_map.set(key, value);
3445        } else {
3446          _out_map.set(key, value);
3447        }
3448      }
3449
3450    private:
3451
3452      InNodeMap& _in_map;
3453      OutNodeMap& _out_map;
3454
3455    };
3456
3457
3458    /// \brief Returns a combined node map
3459    ///
3460    /// This function just returns a combined node map.
3461    template <typename InNodeMap, typename OutNodeMap>
3462    static CombinedNodeMap<InNodeMap, OutNodeMap>
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>
3468    static CombinedNodeMap<const InNodeMap, OutNodeMap>
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>
3474    static CombinedNodeMap<InNodeMap, const OutNodeMap>
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>
3480    static CombinedNodeMap<const InNodeMap, const OutNodeMap>
3481    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
3482      return CombinedNodeMap<const InNodeMap,
3483        const OutNodeMap>(in_map, out_map);
3484    }
3485
3486    /// \brief Arc map combined from an arc map and a node map of the
3487    /// original digraph.
3488    ///
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).
3493    template <typename DigraphArcMap, typename DigraphNodeMap>
3494    class CombinedArcMap {
3495    public:
3496
3497      /// The key type of the map
3498      typedef Arc Key;
3499      /// The value type of the map
3500      typedef typename DigraphArcMap::Value Value;
3501
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
3513      /// Constructor
3514      CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
3515        : _arc_map(arc_map), _node_map(node_map) {}
3516
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.
3536      void set(const Arc& arc, const Value& val) {
3537        if (Parent::origArc(arc)) {
3538          _arc_map.set(arc, val);
3539        } else {
3540          _node_map.set(arc, val);
3541        }
3542      }
3543
3544    private:
3545      DigraphArcMap& _arc_map;
3546      DigraphNodeMap& _node_map;
3547    };
3548
3549    /// \brief Returns a combined arc map
3550    ///
3551    /// This function just returns a combined arc map.
3552    template <typename DigraphArcMap, typename DigraphNodeMap>
3553    static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
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>
3559    static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
3560    combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
3561      return CombinedArcMap<const DigraphArcMap,
3562        DigraphNodeMap>(arc_map, node_map);
3563    }
3564
3565    template <typename DigraphArcMap, typename DigraphNodeMap>
3566    static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
3567    combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
3568      return CombinedArcMap<DigraphArcMap,
3569        const DigraphNodeMap>(arc_map, node_map);
3570    }
3571
3572    template <typename DigraphArcMap, typename DigraphNodeMap>
3573    static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
3574    combinedArcMap(const DigraphArcMap& arc_map,
3575                   const DigraphNodeMap& node_map) {
3576      return CombinedArcMap<const DigraphArcMap,
3577        const DigraphNodeMap>(arc_map, node_map);
3578    }
3579
3580  };
3581
3582  /// \brief Returns a (read-only) SplitNodes adaptor
3583  ///
3584  /// This function just returns a (read-only) \ref SplitNodes adaptor.
3585  /// \ingroup graph_adaptors
3586  /// \relates SplitNodes
3587  template<typename Digraph>
3588  SplitNodes<Digraph>
3589  splitNodes(const Digraph& digraph) {
3590    return SplitNodes<Digraph>(digraph);
3591  }
3592
3593
3594} //namespace lemon
3595
3596#endif //LEMON_ADAPTORS_H
Note: See TracBrowser for help on using the repository browser.