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