lemon/adaptors.h
author Peter Kovacs <kpeter@inf.elte.hu>
Wed, 15 Apr 2009 02:04:37 +0200
changeset 584 33c6b6e755cd
parent 559 c5fd2d996909
child 617 4137ef9aacc6
permissions -rw-r--r--
Small doc improvements (#263)
     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     typedef EdgeNotifier ArcNotifier;
  2197     ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
  2198 
  2199   protected:
  2200 
  2201     UndirectorBase() : _digraph(0) {}
  2202 
  2203     DGR* _digraph;
  2204 
  2205     void initialize(DGR& digraph) {
  2206       _digraph = &digraph;
  2207     }
  2208 
  2209   };
  2210 
  2211   /// \ingroup graph_adaptors
  2212   ///
  2213   /// \brief Adaptor class for viewing a digraph as an undirected graph.
  2214   ///
  2215   /// Undirector adaptor can be used for viewing a digraph as an undirected
  2216   /// graph. All arcs of the underlying digraph are showed in the
  2217   /// adaptor as an edge (and also as a pair of arcs, of course).
  2218   /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
  2219   ///
  2220   /// The adapted digraph can also be modified through this adaptor
  2221   /// by adding or removing nodes or edges, unless the \c GR template
  2222   /// parameter is set to be \c const.
  2223   ///
  2224   /// \tparam DGR The type of the adapted digraph.
  2225   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
  2226   /// It can also be specified to be \c const.
  2227   ///
  2228   /// \note The \c Node type of this adaptor and the adapted digraph are
  2229   /// convertible to each other, moreover the \c Edge type of the adaptor
  2230   /// and the \c Arc type of the adapted digraph are also convertible to
  2231   /// each other.
  2232   /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
  2233   /// of the adapted digraph.)
  2234   template<typename DGR>
  2235 #ifdef DOXYGEN
  2236   class Undirector {
  2237 #else
  2238   class Undirector :
  2239     public GraphAdaptorExtender<UndirectorBase<DGR> > {
  2240 #endif
  2241   public:
  2242     /// The type of the adapted digraph.
  2243     typedef DGR Digraph;
  2244     typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
  2245   protected:
  2246     Undirector() { }
  2247   public:
  2248 
  2249     /// \brief Constructor
  2250     ///
  2251     /// Creates an undirected graph from the given digraph.
  2252     Undirector(DGR& digraph) {
  2253       initialize(digraph);
  2254     }
  2255 
  2256     /// \brief Arc map combined from two original arc maps
  2257     ///
  2258     /// This map adaptor class adapts two arc maps of the underlying
  2259     /// digraph to get an arc map of the undirected graph.
  2260     /// Its value type is inherited from the first arc map type (\c FW).
  2261     /// \tparam FW The type of the "foward" arc map.
  2262     /// \tparam BK The type of the "backward" arc map.
  2263     template <typename FW, typename BK>
  2264     class CombinedArcMap {
  2265     public:
  2266 
  2267       /// The key type of the map
  2268       typedef typename Parent::Arc Key;
  2269       /// The value type of the map
  2270       typedef typename FW::Value Value;
  2271 
  2272       typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag;
  2273 
  2274       typedef typename MapTraits<FW>::ReturnValue ReturnValue;
  2275       typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue;
  2276       typedef typename MapTraits<FW>::ReturnValue Reference;
  2277       typedef typename MapTraits<FW>::ConstReturnValue ConstReference;
  2278 
  2279       /// Constructor
  2280       CombinedArcMap(FW& forward, BK& backward)
  2281         : _forward(&forward), _backward(&backward) {}
  2282 
  2283       /// Sets the value associated with the given key.
  2284       void set(const Key& e, const Value& a) {
  2285         if (Parent::direction(e)) {
  2286           _forward->set(e, a);
  2287         } else {
  2288           _backward->set(e, a);
  2289         }
  2290       }
  2291 
  2292       /// Returns the value associated with the given key.
  2293       ConstReturnValue operator[](const Key& e) const {
  2294         if (Parent::direction(e)) {
  2295           return (*_forward)[e];
  2296         } else {
  2297           return (*_backward)[e];
  2298         }
  2299       }
  2300 
  2301       /// Returns a reference to the value associated with the given key.
  2302       ReturnValue operator[](const Key& e) {
  2303         if (Parent::direction(e)) {
  2304           return (*_forward)[e];
  2305         } else {
  2306           return (*_backward)[e];
  2307         }
  2308       }
  2309 
  2310     protected:
  2311 
  2312       FW* _forward;
  2313       BK* _backward;
  2314 
  2315     };
  2316 
  2317     /// \brief Returns a combined arc map
  2318     ///
  2319     /// This function just returns a combined arc map.
  2320     template <typename FW, typename BK>
  2321     static CombinedArcMap<FW, BK>
  2322     combinedArcMap(FW& forward, BK& backward) {
  2323       return CombinedArcMap<FW, BK>(forward, backward);
  2324     }
  2325 
  2326     template <typename FW, typename BK>
  2327     static CombinedArcMap<const FW, BK>
  2328     combinedArcMap(const FW& forward, BK& backward) {
  2329       return CombinedArcMap<const FW, BK>(forward, backward);
  2330     }
  2331 
  2332     template <typename FW, typename BK>
  2333     static CombinedArcMap<FW, const BK>
  2334     combinedArcMap(FW& forward, const BK& backward) {
  2335       return CombinedArcMap<FW, const BK>(forward, backward);
  2336     }
  2337 
  2338     template <typename FW, typename BK>
  2339     static CombinedArcMap<const FW, const BK>
  2340     combinedArcMap(const FW& forward, const BK& backward) {
  2341       return CombinedArcMap<const FW, const BK>(forward, backward);
  2342     }
  2343 
  2344   };
  2345 
  2346   /// \brief Returns a read-only Undirector adaptor
  2347   ///
  2348   /// This function just returns a read-only \ref Undirector adaptor.
  2349   /// \ingroup graph_adaptors
  2350   /// \relates Undirector
  2351   template<typename DGR>
  2352   Undirector<const DGR> undirector(const DGR& digraph) {
  2353     return Undirector<const DGR>(digraph);
  2354   }
  2355 
  2356 
  2357   template <typename GR, typename DM>
  2358   class OrienterBase {
  2359   public:
  2360 
  2361     typedef GR Graph;
  2362     typedef DM DirectionMap;
  2363 
  2364     typedef typename GR::Node Node;
  2365     typedef typename GR::Edge Arc;
  2366 
  2367     void reverseArc(const Arc& arc) {
  2368       _direction->set(arc, !(*_direction)[arc]);
  2369     }
  2370 
  2371     void first(Node& i) const { _graph->first(i); }
  2372     void first(Arc& i) const { _graph->first(i); }
  2373     void firstIn(Arc& i, const Node& n) const {
  2374       bool d = true;
  2375       _graph->firstInc(i, d, n);
  2376       while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
  2377     }
  2378     void firstOut(Arc& i, const Node& n ) const {
  2379       bool d = true;
  2380       _graph->firstInc(i, d, n);
  2381       while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
  2382     }
  2383 
  2384     void next(Node& i) const { _graph->next(i); }
  2385     void next(Arc& i) const { _graph->next(i); }
  2386     void nextIn(Arc& i) const {
  2387       bool d = !(*_direction)[i];
  2388       _graph->nextInc(i, d);
  2389       while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
  2390     }
  2391     void nextOut(Arc& i) const {
  2392       bool d = (*_direction)[i];
  2393       _graph->nextInc(i, d);
  2394       while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
  2395     }
  2396 
  2397     Node source(const Arc& e) const {
  2398       return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
  2399     }
  2400     Node target(const Arc& e) const {
  2401       return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
  2402     }
  2403 
  2404     typedef NodeNumTagIndicator<Graph> NodeNumTag;
  2405     int nodeNum() const { return _graph->nodeNum(); }
  2406 
  2407     typedef EdgeNumTagIndicator<Graph> ArcNumTag;
  2408     int arcNum() const { return _graph->edgeNum(); }
  2409 
  2410     typedef FindEdgeTagIndicator<Graph> FindArcTag;
  2411     Arc findArc(const Node& u, const Node& v,
  2412                 const Arc& prev = INVALID) const {
  2413       Arc arc = _graph->findEdge(u, v, prev);
  2414       while (arc != INVALID && source(arc) != u) {
  2415         arc = _graph->findEdge(u, v, arc);
  2416       }
  2417       return arc;
  2418     }
  2419 
  2420     Node addNode() {
  2421       return Node(_graph->addNode());
  2422     }
  2423 
  2424     Arc addArc(const Node& u, const Node& v) {
  2425       Arc arc = _graph->addEdge(u, v);
  2426       _direction->set(arc, _graph->u(arc) == u);
  2427       return arc;
  2428     }
  2429 
  2430     void erase(const Node& i) { _graph->erase(i); }
  2431     void erase(const Arc& i) { _graph->erase(i); }
  2432 
  2433     void clear() { _graph->clear(); }
  2434 
  2435     int id(const Node& v) const { return _graph->id(v); }
  2436     int id(const Arc& e) const { return _graph->id(e); }
  2437 
  2438     Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
  2439     Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
  2440 
  2441     int maxNodeId() const { return _graph->maxNodeId(); }
  2442     int maxArcId() const { return _graph->maxEdgeId(); }
  2443 
  2444     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
  2445     NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
  2446 
  2447     typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
  2448     ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
  2449 
  2450     template <typename V>
  2451     class NodeMap : public GR::template NodeMap<V> {
  2452     public:
  2453 
  2454       typedef typename GR::template NodeMap<V> Parent;
  2455 
  2456       explicit NodeMap(const OrienterBase<GR, DM>& adapter)
  2457         : Parent(*adapter._graph) {}
  2458 
  2459       NodeMap(const OrienterBase<GR, DM>& adapter, const V& value)
  2460         : Parent(*adapter._graph, value) {}
  2461 
  2462     private:
  2463       NodeMap& operator=(const NodeMap& cmap) {
  2464         return operator=<NodeMap>(cmap);
  2465       }
  2466 
  2467       template <typename CMap>
  2468       NodeMap& operator=(const CMap& cmap) {
  2469         Parent::operator=(cmap);
  2470         return *this;
  2471       }
  2472 
  2473     };
  2474 
  2475     template <typename V>
  2476     class ArcMap : public GR::template EdgeMap<V> {
  2477     public:
  2478 
  2479       typedef typename Graph::template EdgeMap<V> Parent;
  2480 
  2481       explicit ArcMap(const OrienterBase<GR, DM>& adapter)
  2482         : Parent(*adapter._graph) { }
  2483 
  2484       ArcMap(const OrienterBase<GR, DM>& adapter, const V& value)
  2485         : Parent(*adapter._graph, value) { }
  2486 
  2487     private:
  2488       ArcMap& operator=(const ArcMap& cmap) {
  2489         return operator=<ArcMap>(cmap);
  2490       }
  2491 
  2492       template <typename CMap>
  2493       ArcMap& operator=(const CMap& cmap) {
  2494         Parent::operator=(cmap);
  2495         return *this;
  2496       }
  2497     };
  2498 
  2499 
  2500 
  2501   protected:
  2502     Graph* _graph;
  2503     DM* _direction;
  2504 
  2505     void initialize(GR& graph, DM& direction) {
  2506       _graph = &graph;
  2507       _direction = &direction;
  2508     }
  2509 
  2510   };
  2511 
  2512   /// \ingroup graph_adaptors
  2513   ///
  2514   /// \brief Adaptor class for orienting the edges of a graph to get a digraph
  2515   ///
  2516   /// Orienter adaptor can be used for orienting the edges of a graph to
  2517   /// get a digraph. A \c bool edge map of the underlying graph must be
  2518   /// specified, which define the direction of the arcs in the adaptor.
  2519   /// The arcs can be easily reversed by the \c reverseArc() member function
  2520   /// of the adaptor.
  2521   /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
  2522   ///
  2523   /// The adapted graph can also be modified through this adaptor
  2524   /// by adding or removing nodes or arcs, unless the \c GR template
  2525   /// parameter is set to be \c const.
  2526   ///
  2527   /// \tparam GR The type of the adapted graph.
  2528   /// It must conform to the \ref concepts::Graph "Graph" concept.
  2529   /// It can also be specified to be \c const.
  2530   /// \tparam DM The type of the direction map.
  2531   /// It must be a \c bool (or convertible) edge map of the
  2532   /// adapted graph. The default type is
  2533   /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
  2534   ///
  2535   /// \note The \c Node type of this adaptor and the adapted graph are
  2536   /// convertible to each other, moreover the \c Arc type of the adaptor
  2537   /// and the \c Edge type of the adapted graph are also convertible to
  2538   /// each other.
  2539 #ifdef DOXYGEN
  2540   template<typename GR,
  2541            typename DM>
  2542   class Orienter {
  2543 #else
  2544   template<typename GR,
  2545            typename DM = typename GR::template EdgeMap<bool> >
  2546   class Orienter :
  2547     public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
  2548 #endif
  2549   public:
  2550 
  2551     /// The type of the adapted graph.
  2552     typedef GR Graph;
  2553     /// The type of the direction edge map.
  2554     typedef DM DirectionMap;
  2555 
  2556     typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
  2557     typedef typename Parent::Arc Arc;
  2558   protected:
  2559     Orienter() { }
  2560   public:
  2561 
  2562     /// \brief Constructor
  2563     ///
  2564     /// Constructor of the adaptor.
  2565     Orienter(GR& graph, DM& direction) {
  2566       Parent::initialize(graph, direction);
  2567     }
  2568 
  2569     /// \brief Reverses the given arc
  2570     ///
  2571     /// This function reverses the given arc.
  2572     /// It is done by simply negate the assigned value of \c a
  2573     /// in the direction map.
  2574     void reverseArc(const Arc& a) {
  2575       Parent::reverseArc(a);
  2576     }
  2577   };
  2578 
  2579   /// \brief Returns a read-only Orienter adaptor
  2580   ///
  2581   /// This function just returns a read-only \ref Orienter adaptor.
  2582   /// \ingroup graph_adaptors
  2583   /// \relates Orienter
  2584   template<typename GR, typename DM>
  2585   Orienter<const GR, DM>
  2586   orienter(const GR& graph, DM& direction) {
  2587     return Orienter<const GR, DM>(graph, direction);
  2588   }
  2589 
  2590   template<typename GR, typename DM>
  2591   Orienter<const GR, const DM>
  2592   orienter(const GR& graph, const DM& direction) {
  2593     return Orienter<const GR, const DM>(graph, direction);
  2594   }
  2595 
  2596   namespace _adaptor_bits {
  2597 
  2598     template <typename DGR, typename CM, typename FM, typename TL>
  2599     class ResForwardFilter {
  2600     public:
  2601 
  2602       typedef typename DGR::Arc Key;
  2603       typedef bool Value;
  2604 
  2605     private:
  2606 
  2607       const CM* _capacity;
  2608       const FM* _flow;
  2609       TL _tolerance;
  2610 
  2611     public:
  2612 
  2613       ResForwardFilter(const CM& capacity, const FM& flow,
  2614                        const TL& tolerance = TL())
  2615         : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
  2616 
  2617       bool operator[](const typename DGR::Arc& a) const {
  2618         return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
  2619       }
  2620     };
  2621 
  2622     template<typename DGR,typename CM, typename FM, typename TL>
  2623     class ResBackwardFilter {
  2624     public:
  2625 
  2626       typedef typename DGR::Arc Key;
  2627       typedef bool Value;
  2628 
  2629     private:
  2630 
  2631       const CM* _capacity;
  2632       const FM* _flow;
  2633       TL _tolerance;
  2634 
  2635     public:
  2636 
  2637       ResBackwardFilter(const CM& capacity, const FM& flow,
  2638                         const TL& tolerance = TL())
  2639         : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
  2640 
  2641       bool operator[](const typename DGR::Arc& a) const {
  2642         return _tolerance.positive((*_flow)[a]);
  2643       }
  2644     };
  2645 
  2646   }
  2647 
  2648   /// \ingroup graph_adaptors
  2649   ///
  2650   /// \brief Adaptor class for composing the residual digraph for directed
  2651   /// flow and circulation problems.
  2652   ///
  2653   /// ResidualDigraph can be used for composing the \e residual digraph
  2654   /// for directed flow and circulation problems. Let \f$ G=(V, A) \f$
  2655   /// be a directed graph and let \f$ F \f$ be a number type.
  2656   /// Let \f$ flow, cap: A\to F \f$ be functions on the arcs.
  2657   /// This adaptor implements a digraph structure with node set \f$ V \f$
  2658   /// and arc set \f$ A_{forward}\cup A_{backward} \f$,
  2659   /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and
  2660   /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so
  2661   /// called residual digraph.
  2662   /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,
  2663   /// multiplicities are counted, i.e. the adaptor has exactly
  2664   /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel
  2665   /// arcs).
  2666   /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
  2667   ///
  2668   /// \tparam DGR The type of the adapted digraph.
  2669   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
  2670   /// It is implicitly \c const.
  2671   /// \tparam CM The type of the capacity map.
  2672   /// It must be an arc map of some numerical type, which defines
  2673   /// the capacities in the flow problem. It is implicitly \c const.
  2674   /// The default type is
  2675   /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
  2676   /// \tparam FM The type of the flow map.
  2677   /// It must be an arc map of some numerical type, which defines
  2678   /// the flow values in the flow problem. The default type is \c CM.
  2679   /// \tparam TL The tolerance type for handling inexact computation.
  2680   /// The default tolerance type depends on the value type of the
  2681   /// capacity map.
  2682   ///
  2683   /// \note This adaptor is implemented using Undirector and FilterArcs
  2684   /// adaptors.
  2685   ///
  2686   /// \note The \c Node type of this adaptor and the adapted digraph are
  2687   /// convertible to each other, moreover the \c Arc type of the adaptor
  2688   /// is convertible to the \c Arc type of the adapted digraph.
  2689 #ifdef DOXYGEN
  2690   template<typename DGR, typename CM, typename FM, typename TL>
  2691   class ResidualDigraph
  2692 #else
  2693   template<typename DGR,
  2694            typename CM = typename DGR::template ArcMap<int>,
  2695            typename FM = CM,
  2696            typename TL = Tolerance<typename CM::Value> >
  2697   class ResidualDigraph 
  2698     : public SubDigraph<
  2699         Undirector<const DGR>,
  2700         ConstMap<typename DGR::Node, Const<bool, true> >,
  2701         typename Undirector<const DGR>::template CombinedArcMap<
  2702           _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,
  2703           _adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > >
  2704 #endif
  2705   {
  2706   public:
  2707 
  2708     /// The type of the underlying digraph.
  2709     typedef DGR Digraph;
  2710     /// The type of the capacity map.
  2711     typedef CM CapacityMap;
  2712     /// The type of the flow map.
  2713     typedef FM FlowMap;
  2714     /// The tolerance type.
  2715     typedef TL Tolerance;
  2716 
  2717     typedef typename CapacityMap::Value Value;
  2718     typedef ResidualDigraph Adaptor;
  2719 
  2720   protected:
  2721 
  2722     typedef Undirector<const Digraph> Undirected;
  2723 
  2724     typedef ConstMap<typename DGR::Node, Const<bool, true> > NodeFilter;
  2725 
  2726     typedef _adaptor_bits::ResForwardFilter<const DGR, CM,
  2727                                             FM, TL> ForwardFilter;
  2728 
  2729     typedef _adaptor_bits::ResBackwardFilter<const DGR, CM,
  2730                                              FM, TL> BackwardFilter;
  2731 
  2732     typedef typename Undirected::
  2733       template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
  2734 
  2735     typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent;
  2736 
  2737     const CapacityMap* _capacity;
  2738     FlowMap* _flow;
  2739 
  2740     Undirected _graph;
  2741     NodeFilter _node_filter;
  2742     ForwardFilter _forward_filter;
  2743     BackwardFilter _backward_filter;
  2744     ArcFilter _arc_filter;
  2745 
  2746   public:
  2747 
  2748     /// \brief Constructor
  2749     ///
  2750     /// Constructor of the residual digraph adaptor. The parameters are the
  2751     /// digraph, the capacity map, the flow map, and a tolerance object.
  2752     ResidualDigraph(const DGR& digraph, const CM& capacity,
  2753                     FM& flow, const TL& tolerance = Tolerance())
  2754       : Parent(), _capacity(&capacity), _flow(&flow), 
  2755         _graph(digraph), _node_filter(),
  2756         _forward_filter(capacity, flow, tolerance),
  2757         _backward_filter(capacity, flow, tolerance),
  2758         _arc_filter(_forward_filter, _backward_filter)
  2759     {
  2760       Parent::initialize(_graph, _node_filter, _arc_filter);
  2761     }
  2762 
  2763     typedef typename Parent::Arc Arc;
  2764 
  2765     /// \brief Returns the residual capacity of the given arc.
  2766     ///
  2767     /// Returns the residual capacity of the given arc.
  2768     Value residualCapacity(const Arc& a) const {
  2769       if (Undirected::direction(a)) {
  2770         return (*_capacity)[a] - (*_flow)[a];
  2771       } else {
  2772         return (*_flow)[a];
  2773       }
  2774     }
  2775 
  2776     /// \brief Augments on the given arc in the residual digraph.
  2777     ///
  2778     /// Augments on the given arc in the residual digraph. It increases
  2779     /// or decreases the flow value on the original arc according to the
  2780     /// direction of the residual arc.
  2781     void augment(const Arc& a, const Value& v) const {
  2782       if (Undirected::direction(a)) {
  2783         _flow->set(a, (*_flow)[a] + v);
  2784       } else {
  2785         _flow->set(a, (*_flow)[a] - v);
  2786       }
  2787     }
  2788 
  2789     /// \brief Returns \c true if the given residual arc is a forward arc.
  2790     ///
  2791     /// Returns \c true if the given residual arc has the same orientation
  2792     /// as the original arc, i.e. it is a so called forward arc.
  2793     static bool forward(const Arc& a) {
  2794       return Undirected::direction(a);
  2795     }
  2796 
  2797     /// \brief Returns \c true if the given residual arc is a backward arc.
  2798     ///
  2799     /// Returns \c true if the given residual arc has the opposite orientation
  2800     /// than the original arc, i.e. it is a so called backward arc.
  2801     static bool backward(const Arc& a) {
  2802       return !Undirected::direction(a);
  2803     }
  2804 
  2805     /// \brief Returns the forward oriented residual arc.
  2806     ///
  2807     /// Returns the forward oriented residual arc related to the given
  2808     /// arc of the underlying digraph.
  2809     static Arc forward(const typename Digraph::Arc& a) {
  2810       return Undirected::direct(a, true);
  2811     }
  2812 
  2813     /// \brief Returns the backward oriented residual arc.
  2814     ///
  2815     /// Returns the backward oriented residual arc related to the given
  2816     /// arc of the underlying digraph.
  2817     static Arc backward(const typename Digraph::Arc& a) {
  2818       return Undirected::direct(a, false);
  2819     }
  2820 
  2821     /// \brief Residual capacity map.
  2822     ///
  2823     /// This map adaptor class can be used for obtaining the residual
  2824     /// capacities as an arc map of the residual digraph.
  2825     /// Its value type is inherited from the capacity map.
  2826     class ResidualCapacity {
  2827     protected:
  2828       const Adaptor* _adaptor;
  2829     public:
  2830       /// The key type of the map
  2831       typedef Arc Key;
  2832       /// The value type of the map
  2833       typedef typename CapacityMap::Value Value;
  2834 
  2835       /// Constructor
  2836       ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 
  2837         : _adaptor(&adaptor) {}
  2838 
  2839       /// Returns the value associated with the given residual arc
  2840       Value operator[](const Arc& a) const {
  2841         return _adaptor->residualCapacity(a);
  2842       }
  2843 
  2844     };
  2845 
  2846     /// \brief Returns a residual capacity map
  2847     ///
  2848     /// This function just returns a residual capacity map.
  2849     ResidualCapacity residualCapacity() const {
  2850       return ResidualCapacity(*this);
  2851     }
  2852 
  2853   };
  2854 
  2855   /// \brief Returns a (read-only) Residual adaptor
  2856   ///
  2857   /// This function just returns a (read-only) \ref ResidualDigraph adaptor.
  2858   /// \ingroup graph_adaptors
  2859   /// \relates ResidualDigraph
  2860     template<typename DGR, typename CM, typename FM>
  2861   ResidualDigraph<DGR, CM, FM>
  2862   residualDigraph(const DGR& digraph, const CM& capacity_map, FM& flow_map) {
  2863     return ResidualDigraph<DGR, CM, FM> (digraph, capacity_map, flow_map);
  2864   }
  2865 
  2866 
  2867   template <typename DGR>
  2868   class SplitNodesBase {
  2869   public:
  2870 
  2871     typedef DGR Digraph;
  2872     typedef DigraphAdaptorBase<const DGR> Parent;
  2873     typedef SplitNodesBase Adaptor;
  2874 
  2875     typedef typename DGR::Node DigraphNode;
  2876     typedef typename DGR::Arc DigraphArc;
  2877 
  2878     class Node;
  2879     class Arc;
  2880 
  2881   private:
  2882 
  2883     template <typename T> class NodeMapBase;
  2884     template <typename T> class ArcMapBase;
  2885 
  2886   public:
  2887 
  2888     class Node : public DigraphNode {
  2889       friend class SplitNodesBase;
  2890       template <typename T> friend class NodeMapBase;
  2891     private:
  2892 
  2893       bool _in;
  2894       Node(DigraphNode node, bool in)
  2895         : DigraphNode(node), _in(in) {}
  2896 
  2897     public:
  2898 
  2899       Node() {}
  2900       Node(Invalid) : DigraphNode(INVALID), _in(true) {}
  2901 
  2902       bool operator==(const Node& node) const {
  2903         return DigraphNode::operator==(node) && _in == node._in;
  2904       }
  2905 
  2906       bool operator!=(const Node& node) const {
  2907         return !(*this == node);
  2908       }
  2909 
  2910       bool operator<(const Node& node) const {
  2911         return DigraphNode::operator<(node) ||
  2912           (DigraphNode::operator==(node) && _in < node._in);
  2913       }
  2914     };
  2915 
  2916     class Arc {
  2917       friend class SplitNodesBase;
  2918       template <typename T> friend class ArcMapBase;
  2919     private:
  2920       typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
  2921 
  2922       explicit Arc(const DigraphArc& arc) : _item(arc) {}
  2923       explicit Arc(const DigraphNode& node) : _item(node) {}
  2924 
  2925       ArcImpl _item;
  2926 
  2927     public:
  2928       Arc() {}
  2929       Arc(Invalid) : _item(DigraphArc(INVALID)) {}
  2930 
  2931       bool operator==(const Arc& arc) const {
  2932         if (_item.firstState()) {
  2933           if (arc._item.firstState()) {
  2934             return _item.first() == arc._item.first();
  2935           }
  2936         } else {
  2937           if (arc._item.secondState()) {
  2938             return _item.second() == arc._item.second();
  2939           }
  2940         }
  2941         return false;
  2942       }
  2943 
  2944       bool operator!=(const Arc& arc) const {
  2945         return !(*this == arc);
  2946       }
  2947 
  2948       bool operator<(const Arc& arc) const {
  2949         if (_item.firstState()) {
  2950           if (arc._item.firstState()) {
  2951             return _item.first() < arc._item.first();
  2952           }
  2953           return false;
  2954         } else {
  2955           if (arc._item.secondState()) {
  2956             return _item.second() < arc._item.second();
  2957           }
  2958           return true;
  2959         }
  2960       }
  2961 
  2962       operator DigraphArc() const { return _item.first(); }
  2963       operator DigraphNode() const { return _item.second(); }
  2964 
  2965     };
  2966 
  2967     void first(Node& n) const {
  2968       _digraph->first(n);
  2969       n._in = true;
  2970     }
  2971 
  2972     void next(Node& n) const {
  2973       if (n._in) {
  2974         n._in = false;
  2975       } else {
  2976         n._in = true;
  2977         _digraph->next(n);
  2978       }
  2979     }
  2980 
  2981     void first(Arc& e) const {
  2982       e._item.setSecond();
  2983       _digraph->first(e._item.second());
  2984       if (e._item.second() == INVALID) {
  2985         e._item.setFirst();
  2986         _digraph->first(e._item.first());
  2987       }
  2988     }
  2989 
  2990     void next(Arc& e) const {
  2991       if (e._item.secondState()) {
  2992         _digraph->next(e._item.second());
  2993         if (e._item.second() == INVALID) {
  2994           e._item.setFirst();
  2995           _digraph->first(e._item.first());
  2996         }
  2997       } else {
  2998         _digraph->next(e._item.first());
  2999       }
  3000     }
  3001 
  3002     void firstOut(Arc& e, const Node& n) const {
  3003       if (n._in) {
  3004         e._item.setSecond(n);
  3005       } else {
  3006         e._item.setFirst();
  3007         _digraph->firstOut(e._item.first(), n);
  3008       }
  3009     }
  3010 
  3011     void nextOut(Arc& e) const {
  3012       if (!e._item.firstState()) {
  3013         e._item.setFirst(INVALID);
  3014       } else {
  3015         _digraph->nextOut(e._item.first());
  3016       }
  3017     }
  3018 
  3019     void firstIn(Arc& e, const Node& n) const {
  3020       if (!n._in) {
  3021         e._item.setSecond(n);
  3022       } else {
  3023         e._item.setFirst();
  3024         _digraph->firstIn(e._item.first(), n);
  3025       }
  3026     }
  3027 
  3028     void nextIn(Arc& e) const {
  3029       if (!e._item.firstState()) {
  3030         e._item.setFirst(INVALID);
  3031       } else {
  3032         _digraph->nextIn(e._item.first());
  3033       }
  3034     }
  3035 
  3036     Node source(const Arc& e) const {
  3037       if (e._item.firstState()) {
  3038         return Node(_digraph->source(e._item.first()), false);
  3039       } else {
  3040         return Node(e._item.second(), true);
  3041       }
  3042     }
  3043 
  3044     Node target(const Arc& e) const {
  3045       if (e._item.firstState()) {
  3046         return Node(_digraph->target(e._item.first()), true);
  3047       } else {
  3048         return Node(e._item.second(), false);
  3049       }
  3050     }
  3051 
  3052     int id(const Node& n) const {
  3053       return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
  3054     }
  3055     Node nodeFromId(int ix) const {
  3056       return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
  3057     }
  3058     int maxNodeId() const {
  3059       return 2 * _digraph->maxNodeId() + 1;
  3060     }
  3061 
  3062     int id(const Arc& e) const {
  3063       if (e._item.firstState()) {
  3064         return _digraph->id(e._item.first()) << 1;
  3065       } else {
  3066         return (_digraph->id(e._item.second()) << 1) | 1;
  3067       }
  3068     }
  3069     Arc arcFromId(int ix) const {
  3070       if ((ix & 1) == 0) {
  3071         return Arc(_digraph->arcFromId(ix >> 1));
  3072       } else {
  3073         return Arc(_digraph->nodeFromId(ix >> 1));
  3074       }
  3075     }
  3076     int maxArcId() const {
  3077       return std::max(_digraph->maxNodeId() << 1,
  3078                       (_digraph->maxArcId() << 1) | 1);
  3079     }
  3080 
  3081     static bool inNode(const Node& n) {
  3082       return n._in;
  3083     }
  3084 
  3085     static bool outNode(const Node& n) {
  3086       return !n._in;
  3087     }
  3088 
  3089     static bool origArc(const Arc& e) {
  3090       return e._item.firstState();
  3091     }
  3092 
  3093     static bool bindArc(const Arc& e) {
  3094       return e._item.secondState();
  3095     }
  3096 
  3097     static Node inNode(const DigraphNode& n) {
  3098       return Node(n, true);
  3099     }
  3100 
  3101     static Node outNode(const DigraphNode& n) {
  3102       return Node(n, false);
  3103     }
  3104 
  3105     static Arc arc(const DigraphNode& n) {
  3106       return Arc(n);
  3107     }
  3108 
  3109     static Arc arc(const DigraphArc& e) {
  3110       return Arc(e);
  3111     }
  3112 
  3113     typedef True NodeNumTag;
  3114     int nodeNum() const {
  3115       return  2 * countNodes(*_digraph);
  3116     }
  3117 
  3118     typedef True ArcNumTag;
  3119     int arcNum() const {
  3120       return countArcs(*_digraph) + countNodes(*_digraph);
  3121     }
  3122 
  3123     typedef True FindArcTag;
  3124     Arc findArc(const Node& u, const Node& v,
  3125                 const Arc& prev = INVALID) const {
  3126       if (inNode(u) && outNode(v)) {
  3127         if (static_cast<const DigraphNode&>(u) ==
  3128             static_cast<const DigraphNode&>(v) && prev == INVALID) {
  3129           return Arc(u);
  3130         }
  3131       }
  3132       else if (outNode(u) && inNode(v)) {
  3133         return Arc(::lemon::findArc(*_digraph, u, v, prev));
  3134       }
  3135       return INVALID;
  3136     }
  3137 
  3138   private:
  3139 
  3140     template <typename V>
  3141     class NodeMapBase
  3142       : public MapTraits<typename Parent::template NodeMap<V> > {
  3143       typedef typename Parent::template NodeMap<V> NodeImpl;
  3144     public:
  3145       typedef Node Key;
  3146       typedef V Value;
  3147       typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
  3148       typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
  3149       typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;
  3150       typedef typename MapTraits<NodeImpl>::ReturnValue Reference;
  3151       typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
  3152 
  3153       NodeMapBase(const SplitNodesBase<DGR>& adaptor)
  3154         : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
  3155       NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
  3156         : _in_map(*adaptor._digraph, value),
  3157           _out_map(*adaptor._digraph, value) {}
  3158 
  3159       void set(const Node& key, const V& val) {
  3160         if (SplitNodesBase<DGR>::inNode(key)) { _in_map.set(key, val); }
  3161         else {_out_map.set(key, val); }
  3162       }
  3163 
  3164       ReturnValue operator[](const Node& key) {
  3165         if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; }
  3166         else { return _out_map[key]; }
  3167       }
  3168 
  3169       ConstReturnValue operator[](const Node& key) const {
  3170         if (Adaptor::inNode(key)) { return _in_map[key]; }
  3171         else { return _out_map[key]; }
  3172       }
  3173 
  3174     private:
  3175       NodeImpl _in_map, _out_map;
  3176     };
  3177 
  3178     template <typename V>
  3179     class ArcMapBase
  3180       : public MapTraits<typename Parent::template ArcMap<V> > {
  3181       typedef typename Parent::template ArcMap<V> ArcImpl;
  3182       typedef typename Parent::template NodeMap<V> NodeImpl;
  3183     public:
  3184       typedef Arc Key;
  3185       typedef V Value;
  3186       typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
  3187       typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
  3188       typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;
  3189       typedef typename MapTraits<ArcImpl>::ReturnValue Reference;
  3190       typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
  3191 
  3192       ArcMapBase(const SplitNodesBase<DGR>& adaptor)
  3193         : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
  3194       ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
  3195         : _arc_map(*adaptor._digraph, value),
  3196           _node_map(*adaptor._digraph, value) {}
  3197 
  3198       void set(const Arc& key, const V& val) {
  3199         if (SplitNodesBase<DGR>::origArc(key)) {
  3200           _arc_map.set(static_cast<const DigraphArc&>(key), val);
  3201         } else {
  3202           _node_map.set(static_cast<const DigraphNode&>(key), val);
  3203         }
  3204       }
  3205 
  3206       ReturnValue operator[](const Arc& key) {
  3207         if (SplitNodesBase<DGR>::origArc(key)) {
  3208           return _arc_map[static_cast<const DigraphArc&>(key)];
  3209         } else {
  3210           return _node_map[static_cast<const DigraphNode&>(key)];
  3211         }
  3212       }
  3213 
  3214       ConstReturnValue operator[](const Arc& key) const {
  3215         if (SplitNodesBase<DGR>::origArc(key)) {
  3216           return _arc_map[static_cast<const DigraphArc&>(key)];
  3217         } else {
  3218           return _node_map[static_cast<const DigraphNode&>(key)];
  3219         }
  3220       }
  3221 
  3222     private:
  3223       ArcImpl _arc_map;
  3224       NodeImpl _node_map;
  3225     };
  3226 
  3227   public:
  3228 
  3229     template <typename V>
  3230     class NodeMap
  3231       : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> >
  3232     {
  3233     public:
  3234       typedef V Value;
  3235       typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<Value> > Parent;
  3236 
  3237       NodeMap(const SplitNodesBase<DGR>& adaptor)
  3238         : Parent(adaptor) {}
  3239 
  3240       NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)
  3241         : Parent(adaptor, value) {}
  3242 
  3243     private:
  3244       NodeMap& operator=(const NodeMap& cmap) {
  3245         return operator=<NodeMap>(cmap);
  3246       }
  3247 
  3248       template <typename CMap>
  3249       NodeMap& operator=(const CMap& cmap) {
  3250         Parent::operator=(cmap);
  3251         return *this;
  3252       }
  3253     };
  3254 
  3255     template <typename V>
  3256     class ArcMap
  3257       : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> >
  3258     {
  3259     public:
  3260       typedef V Value;
  3261       typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<Value> > Parent;
  3262 
  3263       ArcMap(const SplitNodesBase<DGR>& adaptor)
  3264         : Parent(adaptor) {}
  3265 
  3266       ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)
  3267         : Parent(adaptor, value) {}
  3268 
  3269     private:
  3270       ArcMap& operator=(const ArcMap& cmap) {
  3271         return operator=<ArcMap>(cmap);
  3272       }
  3273 
  3274       template <typename CMap>
  3275       ArcMap& operator=(const CMap& cmap) {
  3276         Parent::operator=(cmap);
  3277         return *this;
  3278       }
  3279     };
  3280 
  3281   protected:
  3282 
  3283     SplitNodesBase() : _digraph(0) {}
  3284 
  3285     DGR* _digraph;
  3286 
  3287     void initialize(Digraph& digraph) {
  3288       _digraph = &digraph;
  3289     }
  3290 
  3291   };
  3292 
  3293   /// \ingroup graph_adaptors
  3294   ///
  3295   /// \brief Adaptor class for splitting the nodes of a digraph.
  3296   ///
  3297   /// SplitNodes adaptor can be used for splitting each node into an
  3298   /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor
  3299   /// replaces each node \f$ u \f$ in the digraph with two nodes,
  3300   /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.
  3301   /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the
  3302   /// new target of the arc will be \f$ u_{in} \f$ and similarly the
  3303   /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.
  3304   /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$
  3305   /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.
  3306   ///
  3307   /// The aim of this class is running an algorithm with respect to node
  3308   /// costs or capacities if the algorithm considers only arc costs or
  3309   /// capacities directly.
  3310   /// In this case you can use \c SplitNodes adaptor, and set the node
  3311   /// costs/capacities of the original digraph to the \e bind \e arcs
  3312   /// in the adaptor.
  3313   ///
  3314   /// \tparam DGR The type of the adapted digraph.
  3315   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
  3316   /// It is implicitly \c const.
  3317   ///
  3318   /// \note The \c Node type of this adaptor is converible to the \c Node
  3319   /// type of the adapted digraph.
  3320   template <typename DGR>
  3321 #ifdef DOXYGEN
  3322   class SplitNodes {
  3323 #else
  3324   class SplitNodes
  3325     : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {
  3326 #endif
  3327   public:
  3328     typedef DGR Digraph;
  3329     typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
  3330 
  3331     typedef typename DGR::Node DigraphNode;
  3332     typedef typename DGR::Arc DigraphArc;
  3333 
  3334     typedef typename Parent::Node Node;
  3335     typedef typename Parent::Arc Arc;
  3336 
  3337     /// \brief Constructor
  3338     ///
  3339     /// Constructor of the adaptor.
  3340     SplitNodes(const DGR& g) {
  3341       Parent::initialize(g);
  3342     }
  3343 
  3344     /// \brief Returns \c true if the given node is an in-node.
  3345     ///
  3346     /// Returns \c true if the given node is an in-node.
  3347     static bool inNode(const Node& n) {
  3348       return Parent::inNode(n);
  3349     }
  3350 
  3351     /// \brief Returns \c true if the given node is an out-node.
  3352     ///
  3353     /// Returns \c true if the given node is an out-node.
  3354     static bool outNode(const Node& n) {
  3355       return Parent::outNode(n);
  3356     }
  3357 
  3358     /// \brief Returns \c true if the given arc is an original arc.
  3359     ///
  3360     /// Returns \c true if the given arc is one of the arcs in the
  3361     /// original digraph.
  3362     static bool origArc(const Arc& a) {
  3363       return Parent::origArc(a);
  3364     }
  3365 
  3366     /// \brief Returns \c true if the given arc is a bind arc.
  3367     ///
  3368     /// Returns \c true if the given arc is a bind arc, i.e. it connects
  3369     /// an in-node and an out-node.
  3370     static bool bindArc(const Arc& a) {
  3371       return Parent::bindArc(a);
  3372     }
  3373 
  3374     /// \brief Returns the in-node created from the given original node.
  3375     ///
  3376     /// Returns the in-node created from the given original node.
  3377     static Node inNode(const DigraphNode& n) {
  3378       return Parent::inNode(n);
  3379     }
  3380 
  3381     /// \brief Returns the out-node created from the given original node.
  3382     ///
  3383     /// Returns the out-node created from the given original node.
  3384     static Node outNode(const DigraphNode& n) {
  3385       return Parent::outNode(n);
  3386     }
  3387 
  3388     /// \brief Returns the bind arc that corresponds to the given
  3389     /// original node.
  3390     ///
  3391     /// Returns the bind arc in the adaptor that corresponds to the given
  3392     /// original node, i.e. the arc connecting the in-node and out-node
  3393     /// of \c n.
  3394     static Arc arc(const DigraphNode& n) {
  3395       return Parent::arc(n);
  3396     }
  3397 
  3398     /// \brief Returns the arc that corresponds to the given original arc.
  3399     ///
  3400     /// Returns the arc in the adaptor that corresponds to the given
  3401     /// original arc.
  3402     static Arc arc(const DigraphArc& a) {
  3403       return Parent::arc(a);
  3404     }
  3405 
  3406     /// \brief Node map combined from two original node maps
  3407     ///
  3408     /// This map adaptor class adapts two node maps of the original digraph
  3409     /// to get a node map of the split digraph.
  3410     /// Its value type is inherited from the first node map type (\c IN).
  3411     /// \tparam IN The type of the node map for the in-nodes. 
  3412     /// \tparam OUT The type of the node map for the out-nodes.
  3413     template <typename IN, typename OUT>
  3414     class CombinedNodeMap {
  3415     public:
  3416 
  3417       /// The key type of the map
  3418       typedef Node Key;
  3419       /// The value type of the map
  3420       typedef typename IN::Value Value;
  3421 
  3422       typedef typename MapTraits<IN>::ReferenceMapTag ReferenceMapTag;
  3423       typedef typename MapTraits<IN>::ReturnValue ReturnValue;
  3424       typedef typename MapTraits<IN>::ConstReturnValue ConstReturnValue;
  3425       typedef typename MapTraits<IN>::ReturnValue Reference;
  3426       typedef typename MapTraits<IN>::ConstReturnValue ConstReference;
  3427 
  3428       /// Constructor
  3429       CombinedNodeMap(IN& in_map, OUT& out_map)
  3430         : _in_map(in_map), _out_map(out_map) {}
  3431 
  3432       /// Returns the value associated with the given key.
  3433       Value operator[](const Key& key) const {
  3434         if (SplitNodesBase<const DGR>::inNode(key)) {
  3435           return _in_map[key];
  3436         } else {
  3437           return _out_map[key];
  3438         }
  3439       }
  3440 
  3441       /// Returns a reference to the value associated with the given key.
  3442       Value& operator[](const Key& key) {
  3443         if (SplitNodesBase<const DGR>::inNode(key)) {
  3444           return _in_map[key];
  3445         } else {
  3446           return _out_map[key];
  3447         }
  3448       }
  3449 
  3450       /// Sets the value associated with the given key.
  3451       void set(const Key& key, const Value& value) {
  3452         if (SplitNodesBase<const DGR>::inNode(key)) {
  3453           _in_map.set(key, value);
  3454         } else {
  3455           _out_map.set(key, value);
  3456         }
  3457       }
  3458 
  3459     private:
  3460 
  3461       IN& _in_map;
  3462       OUT& _out_map;
  3463 
  3464     };
  3465 
  3466 
  3467     /// \brief Returns a combined node map
  3468     ///
  3469     /// This function just returns a combined node map.
  3470     template <typename IN, typename OUT>
  3471     static CombinedNodeMap<IN, OUT>
  3472     combinedNodeMap(IN& in_map, OUT& out_map) {
  3473       return CombinedNodeMap<IN, OUT>(in_map, out_map);
  3474     }
  3475 
  3476     template <typename IN, typename OUT>
  3477     static CombinedNodeMap<const IN, OUT>
  3478     combinedNodeMap(const IN& in_map, OUT& out_map) {
  3479       return CombinedNodeMap<const IN, OUT>(in_map, out_map);
  3480     }
  3481 
  3482     template <typename IN, typename OUT>
  3483     static CombinedNodeMap<IN, const OUT>
  3484     combinedNodeMap(IN& in_map, const OUT& out_map) {
  3485       return CombinedNodeMap<IN, const OUT>(in_map, out_map);
  3486     }
  3487 
  3488     template <typename IN, typename OUT>
  3489     static CombinedNodeMap<const IN, const OUT>
  3490     combinedNodeMap(const IN& in_map, const OUT& out_map) {
  3491       return CombinedNodeMap<const IN, const OUT>(in_map, out_map);
  3492     }
  3493 
  3494     /// \brief Arc map combined from an arc map and a node map of the
  3495     /// original digraph.
  3496     ///
  3497     /// This map adaptor class adapts an arc map and a node map of the
  3498     /// original digraph to get an arc map of the split digraph.
  3499     /// Its value type is inherited from the original arc map type (\c AM).
  3500     /// \tparam AM The type of the arc map.
  3501     /// \tparam NM the type of the node map.
  3502     template <typename AM, typename NM>
  3503     class CombinedArcMap {
  3504     public:
  3505 
  3506       /// The key type of the map
  3507       typedef Arc Key;
  3508       /// The value type of the map
  3509       typedef typename AM::Value Value;
  3510 
  3511       typedef typename MapTraits<AM>::ReferenceMapTag ReferenceMapTag;
  3512       typedef typename MapTraits<AM>::ReturnValue ReturnValue;
  3513       typedef typename MapTraits<AM>::ConstReturnValue ConstReturnValue;
  3514       typedef typename MapTraits<AM>::ReturnValue Reference;
  3515       typedef typename MapTraits<AM>::ConstReturnValue ConstReference;
  3516 
  3517       /// Constructor
  3518       CombinedArcMap(AM& arc_map, NM& node_map)
  3519         : _arc_map(arc_map), _node_map(node_map) {}
  3520 
  3521       /// Returns the value associated with the given key.
  3522       Value operator[](const Key& arc) const {
  3523         if (SplitNodesBase<const DGR>::origArc(arc)) {
  3524           return _arc_map[arc];
  3525         } else {
  3526           return _node_map[arc];
  3527         }
  3528       }
  3529 
  3530       /// Returns a reference to the value associated with the given key.
  3531       Value& operator[](const Key& arc) {
  3532         if (SplitNodesBase<const DGR>::origArc(arc)) {
  3533           return _arc_map[arc];
  3534         } else {
  3535           return _node_map[arc];
  3536         }
  3537       }
  3538 
  3539       /// Sets the value associated with the given key.
  3540       void set(const Arc& arc, const Value& val) {
  3541         if (SplitNodesBase<const DGR>::origArc(arc)) {
  3542           _arc_map.set(arc, val);
  3543         } else {
  3544           _node_map.set(arc, val);
  3545         }
  3546       }
  3547 
  3548     private:
  3549 
  3550       AM& _arc_map;
  3551       NM& _node_map;
  3552 
  3553     };
  3554 
  3555     /// \brief Returns a combined arc map
  3556     ///
  3557     /// This function just returns a combined arc map.
  3558     template <typename ArcMap, typename NodeMap>
  3559     static CombinedArcMap<ArcMap, NodeMap>
  3560     combinedArcMap(ArcMap& arc_map, NodeMap& node_map) {
  3561       return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map);
  3562     }
  3563 
  3564     template <typename ArcMap, typename NodeMap>
  3565     static CombinedArcMap<const ArcMap, NodeMap>
  3566     combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) {
  3567       return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map);
  3568     }
  3569 
  3570     template <typename ArcMap, typename NodeMap>
  3571     static CombinedArcMap<ArcMap, const NodeMap>
  3572     combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) {
  3573       return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map);
  3574     }
  3575 
  3576     template <typename ArcMap, typename NodeMap>
  3577     static CombinedArcMap<const ArcMap, const NodeMap>
  3578     combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) {
  3579       return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map);
  3580     }
  3581 
  3582   };
  3583 
  3584   /// \brief Returns a (read-only) SplitNodes adaptor
  3585   ///
  3586   /// This function just returns a (read-only) \ref SplitNodes adaptor.
  3587   /// \ingroup graph_adaptors
  3588   /// \relates SplitNodes
  3589   template<typename DGR>
  3590   SplitNodes<DGR>
  3591   splitNodes(const DGR& digraph) {
  3592     return SplitNodes<DGR>(digraph);
  3593   }
  3594 
  3595 #undef LEMON_SCOPE_FIX
  3596 
  3597 } //namespace lemon
  3598 
  3599 #endif //LEMON_ADAPTORS_H