COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/adaptors.h @ 559:c5fd2d996909

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

Various doc improvements (#248)

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