COIN-OR::LEMON - Graph Library

source: lemon/lemon/adaptors.h @ 475:aea2dc0518ce

Last change on this file since 475:aea2dc0518ce was 475:aea2dc0518ce, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Rename convenience functions in subgraph adaptors (#67)

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