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