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