lemon/adaptors.h
author Balazs Dezso <deba@inf.elte.hu>
Tue, 02 Dec 2008 22:48:28 +0100
changeset 459 ed54c0d13df0
parent 440 88ed40ad0d4f
parent 454 f599fa651202
child 464 acfb0f24d178
permissions -rw-r--r--
Thorough redesign of the LP/MIP interface (#44)

- Redesigned class structure
- Redesigned iterators
- Some functions in the basic interface redesigned
- More complete setting functions
- Ray retrieving functions
- Lot of improvements
- Cplex common env
- CLP macro definition to config.h.in
- Update lp.h to also use soplex and clp
- Remove default_solver_name
- New solverName() function in solvers
- Handle exceptions for MipCplex test
- Rename tolerance parameter to epsilon
- Rename MapIt to CoeffIt
- Lot of documentation improvements
- Various bugfixes
     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   /// Residual can be used for composing the \e residual digraph for directed
  2670   /// flow and circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
  2671   /// and let \f$ F \f$ be a number type. Let \f$ flow, cap: A\to F \f$ be
  2672   /// 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 Residual
  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 Residual :
  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 Residual 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     Residual(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   Residual<GR, CM, FM> residual(const GR& digraph,
  2873                                 const CM& capacity_map,
  2874                                 FM& flow_map) {
  2875     return Residual<GR, CM, FM> (digraph, capacity_map, flow_map);
  2876   }
  2877 
  2878 
  2879   template <typename _Digraph>
  2880   class SplitNodesBase {
  2881   public:
  2882 
  2883     typedef _Digraph Digraph;
  2884     typedef DigraphAdaptorBase<const _Digraph> Parent;
  2885     typedef SplitNodesBase Adaptor;
  2886 
  2887     typedef typename Digraph::Node DigraphNode;
  2888     typedef typename Digraph::Arc DigraphArc;
  2889 
  2890     class Node;
  2891     class Arc;
  2892 
  2893   private:
  2894 
  2895     template <typename T> class NodeMapBase;
  2896     template <typename T> class ArcMapBase;
  2897 
  2898   public:
  2899 
  2900     class Node : public DigraphNode {
  2901       friend class SplitNodesBase;
  2902       template <typename T> friend class NodeMapBase;
  2903     private:
  2904 
  2905       bool _in;
  2906       Node(DigraphNode node, bool in)
  2907         : DigraphNode(node), _in(in) {}
  2908 
  2909     public:
  2910 
  2911       Node() {}
  2912       Node(Invalid) : DigraphNode(INVALID), _in(true) {}
  2913 
  2914       bool operator==(const Node& node) const {
  2915         return DigraphNode::operator==(node) && _in == node._in;
  2916       }
  2917 
  2918       bool operator!=(const Node& node) const {
  2919         return !(*this == node);
  2920       }
  2921 
  2922       bool operator<(const Node& node) const {
  2923         return DigraphNode::operator<(node) ||
  2924           (DigraphNode::operator==(node) && _in < node._in);
  2925       }
  2926     };
  2927 
  2928     class Arc {
  2929       friend class SplitNodesBase;
  2930       template <typename T> friend class ArcMapBase;
  2931     private:
  2932       typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
  2933 
  2934       explicit Arc(const DigraphArc& arc) : _item(arc) {}
  2935       explicit Arc(const DigraphNode& node) : _item(node) {}
  2936 
  2937       ArcImpl _item;
  2938 
  2939     public:
  2940       Arc() {}
  2941       Arc(Invalid) : _item(DigraphArc(INVALID)) {}
  2942 
  2943       bool operator==(const Arc& arc) const {
  2944         if (_item.firstState()) {
  2945           if (arc._item.firstState()) {
  2946             return _item.first() == arc._item.first();
  2947           }
  2948         } else {
  2949           if (arc._item.secondState()) {
  2950             return _item.second() == arc._item.second();
  2951           }
  2952         }
  2953         return false;
  2954       }
  2955 
  2956       bool operator!=(const Arc& arc) const {
  2957         return !(*this == arc);
  2958       }
  2959 
  2960       bool operator<(const Arc& arc) const {
  2961         if (_item.firstState()) {
  2962           if (arc._item.firstState()) {
  2963             return _item.first() < arc._item.first();
  2964           }
  2965           return false;
  2966         } else {
  2967           if (arc._item.secondState()) {
  2968             return _item.second() < arc._item.second();
  2969           }
  2970           return true;
  2971         }
  2972       }
  2973 
  2974       operator DigraphArc() const { return _item.first(); }
  2975       operator DigraphNode() const { return _item.second(); }
  2976 
  2977     };
  2978 
  2979     void first(Node& n) const {
  2980       _digraph->first(n);
  2981       n._in = true;
  2982     }
  2983 
  2984     void next(Node& n) const {
  2985       if (n._in) {
  2986         n._in = false;
  2987       } else {
  2988         n._in = true;
  2989         _digraph->next(n);
  2990       }
  2991     }
  2992 
  2993     void first(Arc& e) const {
  2994       e._item.setSecond();
  2995       _digraph->first(e._item.second());
  2996       if (e._item.second() == INVALID) {
  2997         e._item.setFirst();
  2998         _digraph->first(e._item.first());
  2999       }
  3000     }
  3001 
  3002     void next(Arc& e) const {
  3003       if (e._item.secondState()) {
  3004         _digraph->next(e._item.second());
  3005         if (e._item.second() == INVALID) {
  3006           e._item.setFirst();
  3007           _digraph->first(e._item.first());
  3008         }
  3009       } else {
  3010         _digraph->next(e._item.first());
  3011       }
  3012     }
  3013 
  3014     void firstOut(Arc& e, const Node& n) const {
  3015       if (n._in) {
  3016         e._item.setSecond(n);
  3017       } else {
  3018         e._item.setFirst();
  3019         _digraph->firstOut(e._item.first(), n);
  3020       }
  3021     }
  3022 
  3023     void nextOut(Arc& e) const {
  3024       if (!e._item.firstState()) {
  3025         e._item.setFirst(INVALID);
  3026       } else {
  3027         _digraph->nextOut(e._item.first());
  3028       }
  3029     }
  3030 
  3031     void firstIn(Arc& e, const Node& n) const {
  3032       if (!n._in) {
  3033         e._item.setSecond(n);
  3034       } else {
  3035         e._item.setFirst();
  3036         _digraph->firstIn(e._item.first(), n);
  3037       }
  3038     }
  3039 
  3040     void nextIn(Arc& e) const {
  3041       if (!e._item.firstState()) {
  3042         e._item.setFirst(INVALID);
  3043       } else {
  3044         _digraph->nextIn(e._item.first());
  3045       }
  3046     }
  3047 
  3048     Node source(const Arc& e) const {
  3049       if (e._item.firstState()) {
  3050         return Node(_digraph->source(e._item.first()), false);
  3051       } else {
  3052         return Node(e._item.second(), true);
  3053       }
  3054     }
  3055 
  3056     Node target(const Arc& e) const {
  3057       if (e._item.firstState()) {
  3058         return Node(_digraph->target(e._item.first()), true);
  3059       } else {
  3060         return Node(e._item.second(), false);
  3061       }
  3062     }
  3063 
  3064     int id(const Node& n) const {
  3065       return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
  3066     }
  3067     Node nodeFromId(int ix) const {
  3068       return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
  3069     }
  3070     int maxNodeId() const {
  3071       return 2 * _digraph->maxNodeId() + 1;
  3072     }
  3073 
  3074     int id(const Arc& e) const {
  3075       if (e._item.firstState()) {
  3076         return _digraph->id(e._item.first()) << 1;
  3077       } else {
  3078         return (_digraph->id(e._item.second()) << 1) | 1;
  3079       }
  3080     }
  3081     Arc arcFromId(int ix) const {
  3082       if ((ix & 1) == 0) {
  3083         return Arc(_digraph->arcFromId(ix >> 1));
  3084       } else {
  3085         return Arc(_digraph->nodeFromId(ix >> 1));
  3086       }
  3087     }
  3088     int maxArcId() const {
  3089       return std::max(_digraph->maxNodeId() << 1,
  3090                       (_digraph->maxArcId() << 1) | 1);
  3091     }
  3092 
  3093     static bool inNode(const Node& n) {
  3094       return n._in;
  3095     }
  3096 
  3097     static bool outNode(const Node& n) {
  3098       return !n._in;
  3099     }
  3100 
  3101     static bool origArc(const Arc& e) {
  3102       return e._item.firstState();
  3103     }
  3104 
  3105     static bool bindArc(const Arc& e) {
  3106       return e._item.secondState();
  3107     }
  3108 
  3109     static Node inNode(const DigraphNode& n) {
  3110       return Node(n, true);
  3111     }
  3112 
  3113     static Node outNode(const DigraphNode& n) {
  3114       return Node(n, false);
  3115     }
  3116 
  3117     static Arc arc(const DigraphNode& n) {
  3118       return Arc(n);
  3119     }
  3120 
  3121     static Arc arc(const DigraphArc& e) {
  3122       return Arc(e);
  3123     }
  3124 
  3125     typedef True NodeNumTag;
  3126     int nodeNum() const {
  3127       return  2 * countNodes(*_digraph);
  3128     }
  3129 
  3130     typedef True ArcNumTag;
  3131     int arcNum() const {
  3132       return countArcs(*_digraph) + countNodes(*_digraph);
  3133     }
  3134 
  3135     typedef True FindArcTag;
  3136     Arc findArc(const Node& u, const Node& v,
  3137                 const Arc& prev = INVALID) const {
  3138       if (inNode(u) && outNode(v)) {
  3139         if (static_cast<const DigraphNode&>(u) ==
  3140             static_cast<const DigraphNode&>(v) && prev == INVALID) {
  3141           return Arc(u);
  3142         }
  3143       }
  3144       else if (outNode(u) && inNode(v)) {
  3145         return Arc(::lemon::findArc(*_digraph, u, v, prev));
  3146       }
  3147       return INVALID;
  3148     }
  3149 
  3150   private:
  3151 
  3152     template <typename _Value>
  3153     class NodeMapBase
  3154       : public MapTraits<typename Parent::template NodeMap<_Value> > {
  3155       typedef typename Parent::template NodeMap<_Value> NodeImpl;
  3156     public:
  3157       typedef Node Key;
  3158       typedef _Value Value;
  3159       typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
  3160       typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
  3161       typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;
  3162       typedef typename MapTraits<NodeImpl>::ReturnValue Reference;
  3163       typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
  3164 
  3165       NodeMapBase(const Adaptor& adaptor)
  3166         : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
  3167       NodeMapBase(const Adaptor& adaptor, const Value& value)
  3168         : _in_map(*adaptor._digraph, value),
  3169           _out_map(*adaptor._digraph, value) {}
  3170 
  3171       void set(const Node& key, const Value& val) {
  3172         if (Adaptor::inNode(key)) { _in_map.set(key, val); }
  3173         else {_out_map.set(key, val); }
  3174       }
  3175 
  3176       ReturnValue operator[](const Node& key) {
  3177         if (Adaptor::inNode(key)) { return _in_map[key]; }
  3178         else { return _out_map[key]; }
  3179       }
  3180 
  3181       ConstReturnValue operator[](const Node& key) const {
  3182         if (Adaptor::inNode(key)) { return _in_map[key]; }
  3183         else { return _out_map[key]; }
  3184       }
  3185 
  3186     private:
  3187       NodeImpl _in_map, _out_map;
  3188     };
  3189 
  3190     template <typename _Value>
  3191     class ArcMapBase
  3192       : public MapTraits<typename Parent::template ArcMap<_Value> > {
  3193       typedef typename Parent::template ArcMap<_Value> ArcImpl;
  3194       typedef typename Parent::template NodeMap<_Value> NodeImpl;
  3195     public:
  3196       typedef Arc Key;
  3197       typedef _Value Value;
  3198       typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
  3199       typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
  3200       typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;
  3201       typedef typename MapTraits<ArcImpl>::ReturnValue Reference;
  3202       typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
  3203 
  3204       ArcMapBase(const Adaptor& adaptor)
  3205         : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
  3206       ArcMapBase(const Adaptor& adaptor, const Value& value)
  3207         : _arc_map(*adaptor._digraph, value),
  3208           _node_map(*adaptor._digraph, value) {}
  3209 
  3210       void set(const Arc& key, const Value& val) {
  3211         if (Adaptor::origArc(key)) {
  3212           _arc_map.set(key._item.first(), val);
  3213         } else {
  3214           _node_map.set(key._item.second(), val);
  3215         }
  3216       }
  3217 
  3218       ReturnValue operator[](const Arc& key) {
  3219         if (Adaptor::origArc(key)) {
  3220           return _arc_map[key._item.first()];
  3221         } else {
  3222           return _node_map[key._item.second()];
  3223         }
  3224       }
  3225 
  3226       ConstReturnValue operator[](const Arc& key) const {
  3227         if (Adaptor::origArc(key)) {
  3228           return _arc_map[key._item.first()];
  3229         } else {
  3230           return _node_map[key._item.second()];
  3231         }
  3232       }
  3233 
  3234     private:
  3235       ArcImpl _arc_map;
  3236       NodeImpl _node_map;
  3237     };
  3238 
  3239   public:
  3240 
  3241     template <typename _Value>
  3242     class NodeMap
  3243       : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
  3244     {
  3245     public:
  3246       typedef _Value Value;
  3247       typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
  3248 
  3249       NodeMap(const Adaptor& adaptor)
  3250         : Parent(adaptor) {}
  3251 
  3252       NodeMap(const Adaptor& adaptor, const Value& value)
  3253         : Parent(adaptor, value) {}
  3254 
  3255     private:
  3256       NodeMap& operator=(const NodeMap& cmap) {
  3257         return operator=<NodeMap>(cmap);
  3258       }
  3259 
  3260       template <typename CMap>
  3261       NodeMap& operator=(const CMap& cmap) {
  3262         Parent::operator=(cmap);
  3263         return *this;
  3264       }
  3265     };
  3266 
  3267     template <typename _Value>
  3268     class ArcMap
  3269       : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
  3270     {
  3271     public:
  3272       typedef _Value Value;
  3273       typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
  3274 
  3275       ArcMap(const Adaptor& adaptor)
  3276         : Parent(adaptor) {}
  3277 
  3278       ArcMap(const Adaptor& adaptor, const Value& value)
  3279         : Parent(adaptor, value) {}
  3280 
  3281     private:
  3282       ArcMap& operator=(const ArcMap& cmap) {
  3283         return operator=<ArcMap>(cmap);
  3284       }
  3285 
  3286       template <typename CMap>
  3287       ArcMap& operator=(const CMap& cmap) {
  3288         Parent::operator=(cmap);
  3289         return *this;
  3290       }
  3291     };
  3292 
  3293   protected:
  3294 
  3295     SplitNodesBase() : _digraph(0) {}
  3296 
  3297     Digraph* _digraph;
  3298 
  3299     void setDigraph(Digraph& digraph) {
  3300       _digraph = &digraph;
  3301     }
  3302 
  3303   };
  3304 
  3305   /// \ingroup graph_adaptors
  3306   ///
  3307   /// \brief Adaptor class for splitting the nodes of a digraph.
  3308   ///
  3309   /// SplitNodes adaptor can be used for splitting each node into an
  3310   /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor
  3311   /// replaces each node \f$ u \f$ in the digraph with two nodes,
  3312   /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.
  3313   /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the
  3314   /// new target of the arc will be \f$ u_{in} \f$ and similarly the
  3315   /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.
  3316   /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$
  3317   /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.
  3318   ///
  3319   /// The aim of this class is running an algorithm with respect to node
  3320   /// costs or capacities if the algorithm considers only arc costs or
  3321   /// capacities directly.
  3322   /// In this case you can use \c SplitNodes adaptor, and set the node
  3323   /// costs/capacities of the original digraph to the \e bind \e arcs
  3324   /// in the adaptor.
  3325   ///
  3326   /// \tparam GR The type of the adapted digraph.
  3327   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
  3328   /// It is implicitly \c const.
  3329   ///
  3330   /// \note The \c Node type of this adaptor is converible to the \c Node
  3331   /// type of the adapted digraph.
  3332   template <typename GR>
  3333 #ifdef DOXYGEN
  3334   class SplitNodes {
  3335 #else
  3336   class SplitNodes
  3337     : public DigraphAdaptorExtender<SplitNodesBase<const GR> > {
  3338 #endif
  3339   public:
  3340     typedef GR Digraph;
  3341     typedef DigraphAdaptorExtender<SplitNodesBase<const GR> > Parent;
  3342 
  3343     typedef typename Digraph::Node DigraphNode;
  3344     typedef typename Digraph::Arc DigraphArc;
  3345 
  3346     typedef typename Parent::Node Node;
  3347     typedef typename Parent::Arc Arc;
  3348 
  3349     /// \brief Constructor
  3350     ///
  3351     /// Constructor of the adaptor.
  3352     SplitNodes(const Digraph& g) {
  3353       Parent::setDigraph(g);
  3354     }
  3355 
  3356     /// \brief Returns \c true if the given node is an in-node.
  3357     ///
  3358     /// Returns \c true if the given node is an in-node.
  3359     static bool inNode(const Node& n) {
  3360       return Parent::inNode(n);
  3361     }
  3362 
  3363     /// \brief Returns \c true if the given node is an out-node.
  3364     ///
  3365     /// Returns \c true if the given node is an out-node.
  3366     static bool outNode(const Node& n) {
  3367       return Parent::outNode(n);
  3368     }
  3369 
  3370     /// \brief Returns \c true if the given arc is an original arc.
  3371     ///
  3372     /// Returns \c true if the given arc is one of the arcs in the
  3373     /// original digraph.
  3374     static bool origArc(const Arc& a) {
  3375       return Parent::origArc(a);
  3376     }
  3377 
  3378     /// \brief Returns \c true if the given arc is a bind arc.
  3379     ///
  3380     /// Returns \c true if the given arc is a bind arc, i.e. it connects
  3381     /// an in-node and an out-node.
  3382     static bool bindArc(const Arc& a) {
  3383       return Parent::bindArc(a);
  3384     }
  3385 
  3386     /// \brief Returns the in-node created from the given original node.
  3387     ///
  3388     /// Returns the in-node created from the given original node.
  3389     static Node inNode(const DigraphNode& n) {
  3390       return Parent::inNode(n);
  3391     }
  3392 
  3393     /// \brief Returns the out-node created from the given original node.
  3394     ///
  3395     /// Returns the out-node created from the given original node.
  3396     static Node outNode(const DigraphNode& n) {
  3397       return Parent::outNode(n);
  3398     }
  3399 
  3400     /// \brief Returns the bind arc that corresponds to the given
  3401     /// original node.
  3402     ///
  3403     /// Returns the bind arc in the adaptor that corresponds to the given
  3404     /// original node, i.e. the arc connecting the in-node and out-node
  3405     /// of \c n.
  3406     static Arc arc(const DigraphNode& n) {
  3407       return Parent::arc(n);
  3408     }
  3409 
  3410     /// \brief Returns the arc that corresponds to the given original arc.
  3411     ///
  3412     /// Returns the arc in the adaptor that corresponds to the given
  3413     /// original arc.
  3414     static Arc arc(const DigraphArc& a) {
  3415       return Parent::arc(a);
  3416     }
  3417 
  3418     /// \brief Node map combined from two original node maps
  3419     ///
  3420     /// This map adaptor class adapts two node maps of the original digraph
  3421     /// to get a node map of the split digraph.
  3422     /// Its value type is inherited from the first node map type
  3423     /// (\c InNodeMap).
  3424     template <typename InNodeMap, typename OutNodeMap>
  3425     class CombinedNodeMap {
  3426     public:
  3427 
  3428       /// The key type of the map
  3429       typedef Node Key;
  3430       /// The value type of the map
  3431       typedef typename InNodeMap::Value Value;
  3432 
  3433       typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
  3434       typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
  3435       typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
  3436       typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
  3437       typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
  3438 
  3439       /// Constructor
  3440       CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
  3441         : _in_map(in_map), _out_map(out_map) {}
  3442 
  3443       /// Returns the value associated with the given key.
  3444       Value operator[](const Key& key) const {
  3445         if (Parent::inNode(key)) {
  3446           return _in_map[key];
  3447         } else {
  3448           return _out_map[key];
  3449         }
  3450       }
  3451 
  3452       /// Returns a reference to the value associated with the given key.
  3453       Value& operator[](const Key& key) {
  3454         if (Parent::inNode(key)) {
  3455           return _in_map[key];
  3456         } else {
  3457           return _out_map[key];
  3458         }
  3459       }
  3460 
  3461       /// Sets the value associated with the given key.
  3462       void set(const Key& key, const Value& value) {
  3463         if (Parent::inNode(key)) {
  3464           _in_map.set(key, value);
  3465         } else {
  3466           _out_map.set(key, value);
  3467         }
  3468       }
  3469 
  3470     private:
  3471 
  3472       InNodeMap& _in_map;
  3473       OutNodeMap& _out_map;
  3474 
  3475     };
  3476 
  3477 
  3478     /// \brief Returns a combined node map
  3479     ///
  3480     /// This function just returns a combined node map.
  3481     template <typename InNodeMap, typename OutNodeMap>
  3482     static CombinedNodeMap<InNodeMap, OutNodeMap>
  3483     combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
  3484       return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
  3485     }
  3486 
  3487     template <typename InNodeMap, typename OutNodeMap>
  3488     static CombinedNodeMap<const InNodeMap, OutNodeMap>
  3489     combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
  3490       return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
  3491     }
  3492 
  3493     template <typename InNodeMap, typename OutNodeMap>
  3494     static CombinedNodeMap<InNodeMap, const OutNodeMap>
  3495     combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
  3496       return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
  3497     }
  3498 
  3499     template <typename InNodeMap, typename OutNodeMap>
  3500     static CombinedNodeMap<const InNodeMap, const OutNodeMap>
  3501     combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
  3502       return CombinedNodeMap<const InNodeMap,
  3503         const OutNodeMap>(in_map, out_map);
  3504     }
  3505 
  3506     /// \brief Arc map combined from an arc map and a node map of the
  3507     /// original digraph.
  3508     ///
  3509     /// This map adaptor class adapts an arc map and a node map of the
  3510     /// original digraph to get an arc map of the split digraph.
  3511     /// Its value type is inherited from the original arc map type
  3512     /// (\c ArcMap).
  3513     template <typename ArcMap, typename NodeMap>
  3514     class CombinedArcMap {
  3515     public:
  3516 
  3517       /// The key type of the map
  3518       typedef Arc Key;
  3519       /// The value type of the map
  3520       typedef typename ArcMap::Value Value;
  3521 
  3522       typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag;
  3523       typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue;
  3524       typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue;
  3525       typedef typename MapTraits<ArcMap>::ReturnValue Reference;
  3526       typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference;
  3527 
  3528       /// Constructor
  3529       CombinedArcMap(ArcMap& arc_map, NodeMap& node_map)
  3530         : _arc_map(arc_map), _node_map(node_map) {}
  3531 
  3532       /// Returns the value associated with the given key.
  3533       Value operator[](const Key& arc) const {
  3534         if (Parent::origArc(arc)) {
  3535           return _arc_map[arc];
  3536         } else {
  3537           return _node_map[arc];
  3538         }
  3539       }
  3540 
  3541       /// Returns a reference to the value associated with the given key.
  3542       Value& operator[](const Key& arc) {
  3543         if (Parent::origArc(arc)) {
  3544           return _arc_map[arc];
  3545         } else {
  3546           return _node_map[arc];
  3547         }
  3548       }
  3549 
  3550       /// Sets the value associated with the given key.
  3551       void set(const Arc& arc, const Value& val) {
  3552         if (Parent::origArc(arc)) {
  3553           _arc_map.set(arc, val);
  3554         } else {
  3555           _node_map.set(arc, val);
  3556         }
  3557       }
  3558 
  3559     private:
  3560       ArcMap& _arc_map;
  3561       NodeMap& _node_map;
  3562     };
  3563 
  3564     /// \brief Returns a combined arc map
  3565     ///
  3566     /// This function just returns a combined arc map.
  3567     template <typename ArcMap, typename NodeMap>
  3568     static CombinedArcMap<ArcMap, NodeMap>
  3569     combinedArcMap(ArcMap& arc_map, NodeMap& node_map) {
  3570       return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map);
  3571     }
  3572 
  3573     template <typename ArcMap, typename NodeMap>
  3574     static CombinedArcMap<const ArcMap, NodeMap>
  3575     combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) {
  3576       return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map);
  3577     }
  3578 
  3579     template <typename ArcMap, typename NodeMap>
  3580     static CombinedArcMap<ArcMap, const NodeMap>
  3581     combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) {
  3582       return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map);
  3583     }
  3584 
  3585     template <typename ArcMap, typename NodeMap>
  3586     static CombinedArcMap<const ArcMap, const NodeMap>
  3587     combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) {
  3588       return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map);
  3589     }
  3590 
  3591   };
  3592 
  3593   /// \brief Returns a (read-only) SplitNodes adaptor
  3594   ///
  3595   /// This function just returns a (read-only) \ref SplitNodes adaptor.
  3596   /// \ingroup graph_adaptors
  3597   /// \relates SplitNodes
  3598   template<typename GR>
  3599   SplitNodes<GR>
  3600   splitNodes(const GR& digraph) {
  3601     return SplitNodes<GR>(digraph);
  3602   }
  3603 
  3604 } //namespace lemon
  3605 
  3606 #endif //LEMON_ADAPTORS_H