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