lemon/adaptors.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 25 Apr 2009 02:12:41 +0200
changeset 623 7c1324b35d89
parent 579 d11bf7998905
child 656 cb38ccedd2c1
permissions -rw-r--r--
Modify the interface of Suurballe (#266, #181)

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