/* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  * Copyright (C) 2003-2011

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #ifndef LEMON_ADAPTORS_H

 #define LEMON_ADAPTORS_H

 /// \ingroup graph_adaptors

 /// \file

 /// \brief Adaptor classes for digraphs and graphs

 ///

 /// This file contains several useful adaptors for digraphs and graphs.

 #include <lemon/core.h>

 #include <lemon/maps.h>

 #include <lemon/bits/variant.h>

 #include <lemon/bits/graph_adaptor_extender.h>

 #include <lemon/bits/map_extender.h>

 #include <lemon/tolerance.h>

 #include <algorithm>

 namespace lemon {

 #ifdef _MSC_VER

 #define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED

 #else

 #define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED

 #endif

   template<typename DGR>

   class DigraphAdaptorBase {

   public:

     typedef DGR Digraph;

     typedef DigraphAdaptorBase Adaptor;

   protected:

     DGR* _digraph;

     DigraphAdaptorBase() : _digraph(0) { }

     void initialize(DGR& digraph) { _digraph = &digraph; }

   public:

     DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { }

     typedef typename DGR::Node Node;

     typedef typename DGR::Arc Arc;

     void first(Node& i) const { _digraph->first(i); }

     void first(Arc& i) const { _digraph->first(i); }

     void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }

     void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }

     void next(Node& i) const { _digraph->next(i); }

     void next(Arc& i) const { _digraph->next(i); }

     void nextIn(Arc& i) const { _digraph->nextIn(i); }

     void nextOut(Arc& i) const { _digraph->nextOut(i); }

     Node source(const Arc& a) const { return _digraph->source(a); }

     Node target(const Arc& a) const { return _digraph->target(a); }

     typedef NodeNumTagIndicator<DGR> NodeNumTag;

     int nodeNum() const { return _digraph->nodeNum(); }

     typedef ArcNumTagIndicator<DGR> ArcNumTag;

     int arcNum() const { return _digraph->arcNum(); }

     typedef FindArcTagIndicator<DGR> FindArcTag;

     Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {

       return _digraph->findArc(u, v, prev);

     }

     Node addNode() { return _digraph->addNode(); }

     Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }

     void erase(const Node& n) { _digraph->erase(n); }

     void erase(const Arc& a) { _digraph->erase(a); }

     void clear() { _digraph->clear(); }

     int id(const Node& n) const { return _digraph->id(n); }

     int id(const Arc& a) const { return _digraph->id(a); }

     Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }

     Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }

     int maxNodeId() const { return _digraph->maxNodeId(); }

     int maxArcId() const { return _digraph->maxArcId(); }

     typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;

     NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }

     typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier;

     ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }

     template <typename V>

     class NodeMap : public DGR::template NodeMap<V> {

       typedef typename DGR::template NodeMap<V> Parent;

     public:

       explicit NodeMap(const Adaptor& adaptor)

         : Parent(*adaptor._digraph) {}

       NodeMap(const Adaptor& adaptor, const V& value)

         : Parent(*adaptor._digraph, value) { }

     private:

       NodeMap& operator=(const NodeMap& cmap) {

         return operator=<NodeMap>(cmap);

       }

       template <typename CMap>

       NodeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

     template <typename V>

     class ArcMap : public DGR::template ArcMap<V> {

       typedef typename DGR::template ArcMap<V> Parent;

     public:

       explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)

         : Parent(*adaptor._digraph) {}

       ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value)

         : Parent(*adaptor._digraph, value) {}

     private:

       ArcMap& operator=(const ArcMap& cmap) {

         return operator=<ArcMap>(cmap);

       }

       template <typename CMap>

       ArcMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

   };

   template<typename GR>

   class GraphAdaptorBase {

   public:

     typedef GR Graph;

   protected:

     GR* _graph;

     GraphAdaptorBase() : _graph(0) {}

     void initialize(GR& graph) { _graph = &graph; }

   public:

     GraphAdaptorBase(GR& graph) : _graph(&graph) {}

     typedef typename GR::Node Node;

     typedef typename GR::Arc Arc;

     typedef typename GR::Edge Edge;

     void first(Node& i) const { _graph->first(i); }

     void first(Arc& i) const { _graph->first(i); }

     void first(Edge& i) const { _graph->first(i); }

     void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }

     void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }

     void firstInc(Edge &i, bool &d, const Node &n) const {

       _graph->firstInc(i, d, n);

     }

     void next(Node& i) const { _graph->next(i); }

     void next(Arc& i) const { _graph->next(i); }

     void next(Edge& i) const { _graph->next(i); }

     void nextIn(Arc& i) const { _graph->nextIn(i); }

     void nextOut(Arc& i) const { _graph->nextOut(i); }

     void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }

     Node u(const Edge& e) const { return _graph->u(e); }

     Node v(const Edge& e) const { return _graph->v(e); }

     Node source(const Arc& a) const { return _graph->source(a); }

     Node target(const Arc& a) const { return _graph->target(a); }

     typedef NodeNumTagIndicator<Graph> NodeNumTag;

     int nodeNum() const { return _graph->nodeNum(); }

     typedef ArcNumTagIndicator<Graph> ArcNumTag;

     int arcNum() const { return _graph->arcNum(); }

     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

     int edgeNum() const { return _graph->edgeNum(); }

     typedef FindArcTagIndicator<Graph> FindArcTag;

     Arc findArc(const Node& u, const Node& v,

                 const Arc& prev = INVALID) const {

       return _graph->findArc(u, v, prev);

     }

     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

     Edge findEdge(const Node& u, const Node& v,

                   const Edge& prev = INVALID) const {

       return _graph->findEdge(u, v, prev);

     }

     Node addNode() { return _graph->addNode(); }

     Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }

     void erase(const Node& i) { _graph->erase(i); }

     void erase(const Edge& i) { _graph->erase(i); }

     void clear() { _graph->clear(); }

     bool direction(const Arc& a) const { return _graph->direction(a); }

     Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }

     int id(const Node& v) const { return _graph->id(v); }

     int id(const Arc& a) const { return _graph->id(a); }

     int id(const Edge& e) const { return _graph->id(e); }

     Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }

     Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }

     Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }

     int maxNodeId() const { return _graph->maxNodeId(); }

     int maxArcId() const { return _graph->maxArcId(); }

     int maxEdgeId() const { return _graph->maxEdgeId(); }

     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;

     NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }

     typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;

     ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }

     typedef typename ItemSetTraits<GR, Edge>::ItemNotifier EdgeNotifier;

     EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }

     template <typename V>

     class NodeMap : public GR::template NodeMap<V> {

       typedef typename GR::template NodeMap<V> Parent;

     public:

       explicit NodeMap(const GraphAdaptorBase<GR>& adapter)

         : Parent(*adapter._graph) {}

       NodeMap(const GraphAdaptorBase<GR>& adapter, const V& value)

         : Parent(*adapter._graph, value) {}

     private:

       NodeMap& operator=(const NodeMap& cmap) {

         return operator=<NodeMap>(cmap);

       }

       template <typename CMap>

       NodeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

     template <typename V>

     class ArcMap : public GR::template ArcMap<V> {

       typedef typename GR::template ArcMap<V> Parent;

     public:

       explicit ArcMap(const GraphAdaptorBase<GR>& adapter)

         : Parent(*adapter._graph) {}

       ArcMap(const GraphAdaptorBase<GR>& adapter, const V& value)

         : Parent(*adapter._graph, value) {}

     private:

       ArcMap& operator=(const ArcMap& cmap) {

         return operator=<ArcMap>(cmap);

       }

       template <typename CMap>

       ArcMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

     template <typename V>

     class EdgeMap : public GR::template EdgeMap<V> {

       typedef typename GR::template EdgeMap<V> Parent;

     public:

       explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)

         : Parent(*adapter._graph) {}

       EdgeMap(const GraphAdaptorBase<GR>& adapter, const V& value)

         : Parent(*adapter._graph, value) {}

     private:

       EdgeMap& operator=(const EdgeMap& cmap) {

         return operator=<EdgeMap>(cmap);

       }

       template <typename CMap>

       EdgeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

   };

   template <typename DGR>

   class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {

     typedef DigraphAdaptorBase<DGR> Parent;

   public:

     typedef DGR Digraph;

   protected:

     ReverseDigraphBase() : Parent() { }

   public:

     typedef typename Parent::Node Node;

     typedef typename Parent::Arc Arc;

     void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }

     void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }

     void nextIn(Arc& a) const { Parent::nextOut(a); }

     void nextOut(Arc& a) const { Parent::nextIn(a); }

     Node source(const Arc& a) const { return Parent::target(a); }

     Node target(const Arc& a) const { return Parent::source(a); }

     Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }

     typedef FindArcTagIndicator<DGR> FindArcTag;

     Arc findArc(const Node& u, const Node& v,

                 const Arc& prev = INVALID) const {

       return Parent::findArc(v, u, prev);

     }

   };

   /// \ingroup graph_adaptors

   ///

   /// \brief Adaptor class for reversing the orientation of the arcs in

   /// a digraph.

   ///

   /// ReverseDigraph can be used for reversing the arcs in a digraph.

   /// It conforms to the \ref concepts::Digraph "Digraph" concept.

   ///

   /// The adapted digraph can also be modified through this adaptor

   /// by adding or removing nodes or arcs, unless the \c GR template

   /// parameter is set to be \c const.

   ///

   /// \tparam DGR The type of the adapted digraph.

   /// It must conform to the \ref concepts::Digraph "Digraph" concept.

   /// It can also be specified to be \c const.

   ///

   /// \note The \c Node and \c Arc types of this adaptor and the adapted

   /// digraph are convertible to each other.

   template<typename DGR>

 #ifdef DOXYGEN

   class ReverseDigraph {

 #else

   class ReverseDigraph :

     public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {

 #endif

     typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;

   public:

     /// The type of the adapted digraph.

     typedef DGR Digraph;

   protected:

     ReverseDigraph() { }

   public:

     /// \brief Constructor

     ///

     /// Creates a reverse digraph adaptor for the given digraph.

     explicit ReverseDigraph(DGR& digraph) {

       Parent::initialize(digraph);

     }

   };

   /// \brief Returns a read-only ReverseDigraph adaptor

   ///

   /// This function just returns a read-only \ref ReverseDigraph adaptor.

   /// \ingroup graph_adaptors

   /// \relates ReverseDigraph

   template<typename DGR>

   ReverseDigraph<const DGR> reverseDigraph(const DGR& digraph) {

     return ReverseDigraph<const DGR>(digraph);

   }

   template <typename DGR, typename NF, typename AF, bool ch = true>

   class SubDigraphBase : public DigraphAdaptorBase<DGR> {

     typedef DigraphAdaptorBase<DGR> Parent;

   public:

     typedef DGR Digraph;

     typedef NF NodeFilterMap;

     typedef AF ArcFilterMap;

     typedef SubDigraphBase Adaptor;

   protected:

     NF* _node_filter;

     AF* _arc_filter;

     SubDigraphBase()

       : Parent(), _node_filter(0), _arc_filter(0) { }

     void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {

       Parent::initialize(digraph);

       _node_filter = &node_filter;

       _arc_filter = &arc_filter;

     }

   public:

     typedef typename Parent::Node Node;

     typedef typename Parent::Arc Arc;

     void first(Node& i) const {

       Parent::first(i);

       while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);

     }

     void first(Arc& i) const {

       Parent::first(i);

       while (i != INVALID && (!(*_arc_filter)[i]

                               || !(*_node_filter)[Parent::source(i)]

                               || !(*_node_filter)[Parent::target(i)]))

         Parent::next(i);

     }

     void firstIn(Arc& i, const Node& n) const {

       Parent::firstIn(i, n);

       while (i != INVALID && (!(*_arc_filter)[i]

                               || !(*_node_filter)[Parent::source(i)]))

         Parent::nextIn(i);

     }

     void firstOut(Arc& i, const Node& n) const {

       Parent::firstOut(i, n);

       while (i != INVALID && (!(*_arc_filter)[i]

                               || !(*_node_filter)[Parent::target(i)]))

         Parent::nextOut(i);

     }

     void next(Node& i) const {

       Parent::next(i);

       while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);

     }

     void next(Arc& i) const {

       Parent::next(i);

       while (i != INVALID && (!(*_arc_filter)[i]

                               || !(*_node_filter)[Parent::source(i)]

                               || !(*_node_filter)[Parent::target(i)]))

         Parent::next(i);

     }

     void nextIn(Arc& i) const {

       Parent::nextIn(i);

       while (i != INVALID && (!(*_arc_filter)[i]

                               || !(*_node_filter)[Parent::source(i)]))

         Parent::nextIn(i);

     }

     void nextOut(Arc& i) const {

       Parent::nextOut(i);

       while (i != INVALID && (!(*_arc_filter)[i]

                               || !(*_node_filter)[Parent::target(i)]))

         Parent::nextOut(i);

     }

     void status(const Node& n, bool v) const { _node_filter->set(n, v); }

     void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }

     bool status(const Node& n) const { return (*_node_filter)[n]; }

     bool status(const Arc& a) const { return (*_arc_filter)[a]; }

     typedef False NodeNumTag;

     typedef False ArcNumTag;

     typedef FindArcTagIndicator<DGR> FindArcTag;

     Arc findArc(const Node& source, const Node& target,

                 const Arc& prev = INVALID) const {

       if (!(*_node_filter)[source] || !(*_node_filter)[target]) {

         return INVALID;

       }

       Arc arc = Parent::findArc(source, target, prev);

       while (arc != INVALID && !(*_arc_filter)[arc]) {

         arc = Parent::findArc(source, target, arc);

       }

       return arc;

     }

   public:

     template <typename V>

     class NodeMap

       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,

               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {

       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,

         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;

     public:

       typedef V Value;

       NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)

         : Parent(adaptor) {}

       NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)

         : Parent(adaptor, value) {}

     private:

       NodeMap& operator=(const NodeMap& cmap) {

         return operator=<NodeMap>(cmap);

       }

       template <typename CMap>

       NodeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

     template <typename V>

     class ArcMap

       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,

               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {

       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,

         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;

     public:

       typedef V Value;

       ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)

         : Parent(adaptor) {}

       ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)

         : Parent(adaptor, value) {}

     private:

       ArcMap& operator=(const ArcMap& cmap) {

         return operator=<ArcMap>(cmap);

       }

       template <typename CMap>

       ArcMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

   };

   template <typename DGR, typename NF, typename AF>

   class SubDigraphBase<DGR, NF, AF, false>

     : public DigraphAdaptorBase<DGR> {

     typedef DigraphAdaptorBase<DGR> Parent;

   public:

     typedef DGR Digraph;

     typedef NF NodeFilterMap;

     typedef AF ArcFilterMap;

     typedef SubDigraphBase Adaptor;

   protected:

     NF* _node_filter;

     AF* _arc_filter;

     SubDigraphBase()

       : Parent(), _node_filter(0), _arc_filter(0) { }

     void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {

       Parent::initialize(digraph);

       _node_filter = &node_filter;

       _arc_filter = &arc_filter;

     }

   public:

     typedef typename Parent::Node Node;

     typedef typename Parent::Arc Arc;

     void first(Node& i) const {

       Parent::first(i);

       while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);

     }

     void first(Arc& i) const {

       Parent::first(i);

       while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);

     }

     void firstIn(Arc& i, const Node& n) const {

       Parent::firstIn(i, n);

       while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);

     }

     void firstOut(Arc& i, const Node& n) const {

       Parent::firstOut(i, n);

       while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);

     }

     void next(Node& i) const {

       Parent::next(i);

       while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);

     }

     void next(Arc& i) const {

       Parent::next(i);

       while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);

     }

     void nextIn(Arc& i) const {

       Parent::nextIn(i);

       while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);

     }

     void nextOut(Arc& i) const {

       Parent::nextOut(i);

       while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);

     }

     void status(const Node& n, bool v) const { _node_filter->set(n, v); }

     void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }

     bool status(const Node& n) const { return (*_node_filter)[n]; }

     bool status(const Arc& a) const { return (*_arc_filter)[a]; }

     typedef False NodeNumTag;

     typedef False ArcNumTag;

     typedef FindArcTagIndicator<DGR> FindArcTag;

     Arc findArc(const Node& source, const Node& target,

                 const Arc& prev = INVALID) const {

       if (!(*_node_filter)[source] || !(*_node_filter)[target]) {

         return INVALID;

       }

       Arc arc = Parent::findArc(source, target, prev);

       while (arc != INVALID && !(*_arc_filter)[arc]) {

         arc = Parent::findArc(source, target, arc);

       }

       return arc;

     }

     template <typename V>

     class NodeMap

       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,

           LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {

       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,

         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;

     public:

       typedef V Value;

       NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)

         : Parent(adaptor) {}

       NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)

         : Parent(adaptor, value) {}

     private:

       NodeMap& operator=(const NodeMap& cmap) {

         return operator=<NodeMap>(cmap);

       }

       template <typename CMap>

       NodeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

     template <typename V>

     class ArcMap

       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,

           LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {

       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,

         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;

     public:

       typedef V Value;

       ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)

         : Parent(adaptor) {}

       ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)

         : Parent(adaptor, value) {}

     private:

       ArcMap& operator=(const ArcMap& cmap) {

         return operator=<ArcMap>(cmap);

       }

       template <typename CMap>

       ArcMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

   };

   /// \ingroup graph_adaptors

   ///

   /// \brief Adaptor class for hiding nodes and arcs in a digraph

   ///

   /// SubDigraph can be used for hiding nodes and arcs in a digraph.

   /// A \c bool node map and a \c bool arc map must be specified, which

   /// define the filters for nodes and arcs.

   /// Only the nodes and arcs with \c true filter value are

   /// shown in the subdigraph. The arcs that are incident to hidden

   /// nodes are also filtered out.

   /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept.

   ///

   /// The adapted digraph can also be modified through this adaptor

   /// by adding or removing nodes or arcs, unless the \c GR template

   /// parameter is set to be \c const.

   ///

   /// \tparam DGR The type of the adapted digraph.

   /// It must conform to the \ref concepts::Digraph "Digraph" concept.

   /// It can also be specified to be \c const.

   /// \tparam NF The type of the node filter map.

   /// It must be a \c bool (or convertible) node map of the

   /// adapted digraph. The default type is

   /// \ref concepts::Digraph::NodeMap "DGR::NodeMap<bool>".

   /// \tparam AF The type of the arc filter map.

   /// It must be \c bool (or convertible) arc map of the

   /// adapted digraph. The default type is

   /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".

   ///

   /// \note The \c Node and \c Arc types of this adaptor and the adapted

   /// digraph are convertible to each other.

   ///

   /// \see FilterNodes

   /// \see FilterArcs

 #ifdef DOXYGEN

   template<typename DGR, typename NF, typename AF>

   class SubDigraph {

 #else

   template<typename DGR,

            typename NF = typename DGR::template NodeMap<bool>,

            typename AF = typename DGR::template ArcMap<bool> >

   class SubDigraph :

     public DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> > {

 #endif

   public:

     /// The type of the adapted digraph.

     typedef DGR Digraph;

     /// The type of the node filter map.

     typedef NF NodeFilterMap;

     /// The type of the arc filter map.

     typedef AF ArcFilterMap;

     typedef DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> >

       Parent;

     typedef typename Parent::Node Node;

     typedef typename Parent::Arc Arc;

   protected:

     SubDigraph() { }

   public:

     /// \brief Constructor

     ///

     /// Creates a subdigraph for the given digraph with the

     /// given node and arc filter maps.

     SubDigraph(DGR& digraph, NF& node_filter, AF& arc_filter) {

       Parent::initialize(digraph, node_filter, arc_filter);

     }

     /// \brief Sets the status of the given node

     ///

     /// This function sets the status of the given node.

     /// It is done by simply setting the assigned value of \c n

     /// to \c v in the node filter map.

     void status(const Node& n, bool v) const { Parent::status(n, v); }

     /// \brief Sets the status of the given arc

     ///

     /// This function sets the status of the given arc.

     /// It is done by simply setting the assigned value of \c a

     /// to \c v in the arc filter map.

     void status(const Arc& a, bool v) const { Parent::status(a, v); }

     /// \brief Returns the status of the given node

     ///

     /// This function returns the status of the given node.

     /// It is \c true if the given node is enabled (i.e. not hidden).

     bool status(const Node& n) const { return Parent::status(n); }

     /// \brief Returns the status of the given arc

     ///

     /// This function returns the status of the given arc.

     /// It is \c true if the given arc is enabled (i.e. not hidden).

     bool status(const Arc& a) const { return Parent::status(a); }

     /// \brief Disables the given node

     ///

     /// This function disables the given node in the subdigraph,

     /// so the iteration jumps over it.

     /// It is the same as \ref status() "status(n, false)".

     void disable(const Node& n) const { Parent::status(n, false); }

     /// \brief Disables the given arc

     ///

     /// This function disables the given arc in the subdigraph,

     /// so the iteration jumps over it.

     /// It is the same as \ref status() "status(a, false)".

     void disable(const Arc& a) const { Parent::status(a, false); }

     /// \brief Enables the given node

     ///

     /// This function enables the given node in the subdigraph.

     /// It is the same as \ref status() "status(n, true)".

     void enable(const Node& n) const { Parent::status(n, true); }

     /// \brief Enables the given arc

     ///

     /// This function enables the given arc in the subdigraph.

     /// It is the same as \ref status() "status(a, true)".

     void enable(const Arc& a) const { Parent::status(a, true); }

   };

   /// \brief Returns a read-only SubDigraph adaptor

   ///

   /// This function just returns a read-only \ref SubDigraph adaptor.

   /// \ingroup graph_adaptors

   /// \relates SubDigraph

   template<typename DGR, typename NF, typename AF>

   SubDigraph<const DGR, NF, AF>

   subDigraph(const DGR& digraph,

              NF& node_filter, AF& arc_filter) {

     return SubDigraph<const DGR, NF, AF>

       (digraph, node_filter, arc_filter);

   }

   template<typename DGR, typename NF, typename AF>

   SubDigraph<const DGR, const NF, AF>

   subDigraph(const DGR& digraph,

              const NF& node_filter, AF& arc_filter) {

     return SubDigraph<const DGR, const NF, AF>

       (digraph, node_filter, arc_filter);

   }

   template<typename DGR, typename NF, typename AF>

   SubDigraph<const DGR, NF, const AF>

   subDigraph(const DGR& digraph,

              NF& node_filter, const AF& arc_filter) {

     return SubDigraph<const DGR, NF, const AF>

       (digraph, node_filter, arc_filter);

   }

   template<typename DGR, typename NF, typename AF>

   SubDigraph<const DGR, const NF, const AF>

   subDigraph(const DGR& digraph,

              const NF& node_filter, const AF& arc_filter) {

     return SubDigraph<const DGR, const NF, const AF>

       (digraph, node_filter, arc_filter);

   }

   template <typename GR, typename NF, typename EF, bool ch = true>

   class SubGraphBase : public GraphAdaptorBase<GR> {

     typedef GraphAdaptorBase<GR> Parent;

   public:

     typedef GR Graph;

     typedef NF NodeFilterMap;

     typedef EF EdgeFilterMap;

     typedef SubGraphBase Adaptor;

   protected:

     NF* _node_filter;

     EF* _edge_filter;

     SubGraphBase()

       : Parent(), _node_filter(0), _edge_filter(0) { }

     void initialize(GR& graph, NF& node_filter, EF& edge_filter) {

       Parent::initialize(graph);

       _node_filter = &node_filter;

       _edge_filter = &edge_filter;

     }

   public:

     typedef typename Parent::Node Node;

     typedef typename Parent::Arc Arc;

     typedef typename Parent::Edge Edge;

     void first(Node& i) const {

       Parent::first(i);

       while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);

     }

     void first(Arc& i) const {

       Parent::first(i);

       while (i!=INVALID && (!(*_edge_filter)[i]

                             || !(*_node_filter)[Parent::source(i)]

                             || !(*_node_filter)[Parent::target(i)]))

         Parent::next(i);

     }

     void first(Edge& i) const {

       Parent::first(i);

       while (i!=INVALID && (!(*_edge_filter)[i]

                             || !(*_node_filter)[Parent::u(i)]

                             || !(*_node_filter)[Parent::v(i)]))

         Parent::next(i);

     }

     void firstIn(Arc& i, const Node& n) const {

       Parent::firstIn(i, n);

       while (i!=INVALID && (!(*_edge_filter)[i]

                             || !(*_node_filter)[Parent::source(i)]))

         Parent::nextIn(i);

     }

     void firstOut(Arc& i, const Node& n) const {

       Parent::firstOut(i, n);

       while (i!=INVALID && (!(*_edge_filter)[i]

                             || !(*_node_filter)[Parent::target(i)]))

         Parent::nextOut(i);

     }

     void firstInc(Edge& i, bool& d, const Node& n) const {

       Parent::firstInc(i, d, n);

       while (i!=INVALID && (!(*_edge_filter)[i]

                             || !(*_node_filter)[Parent::u(i)]

                             || !(*_node_filter)[Parent::v(i)]))

         Parent::nextInc(i, d);

     }

     void next(Node& i) const {

       Parent::next(i);

       while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);

     }

     void next(Arc& i) const {

       Parent::next(i);

       while (i!=INVALID && (!(*_edge_filter)[i]

                             || !(*_node_filter)[Parent::source(i)]

                             || !(*_node_filter)[Parent::target(i)]))

         Parent::next(i);

     }

     void next(Edge& i) const {

       Parent::next(i);

       while (i!=INVALID && (!(*_edge_filter)[i]

                             || !(*_node_filter)[Parent::u(i)]

                             || !(*_node_filter)[Parent::v(i)]))

         Parent::next(i);

     }

     void nextIn(Arc& i) const {

       Parent::nextIn(i);

       while (i!=INVALID && (!(*_edge_filter)[i]

                             || !(*_node_filter)[Parent::source(i)]))

         Parent::nextIn(i);

     }

     void nextOut(Arc& i) const {

       Parent::nextOut(i);

       while (i!=INVALID && (!(*_edge_filter)[i]

                             || !(*_node_filter)[Parent::target(i)]))

         Parent::nextOut(i);

     }

     void nextInc(Edge& i, bool& d) const {

       Parent::nextInc(i, d);

       while (i!=INVALID && (!(*_edge_filter)[i]

                             || !(*_node_filter)[Parent::u(i)]

                             || !(*_node_filter)[Parent::v(i)]))

         Parent::nextInc(i, d);

     }

     void status(const Node& n, bool v) const { _node_filter->set(n, v); }

     void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }

     bool status(const Node& n) const { return (*_node_filter)[n]; }

     bool status(const Edge& e) const { return (*_edge_filter)[e]; }

     typedef False NodeNumTag;

     typedef False ArcNumTag;

     typedef False EdgeNumTag;

     typedef FindArcTagIndicator<Graph> FindArcTag;

     Arc findArc(const Node& u, const Node& v,

                 const Arc& prev = INVALID) const {

       if (!(*_node_filter)[u] || !(*_node_filter)[v]) {

         return INVALID;

       }

       Arc arc = Parent::findArc(u, v, prev);

       while (arc != INVALID && !(*_edge_filter)[arc]) {

         arc = Parent::findArc(u, v, arc);

       }

       return arc;

     }

     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

     Edge findEdge(const Node& u, const Node& v,

                   const Edge& prev = INVALID) const {

       if (!(*_node_filter)[u] || !(*_node_filter)[v]) {

         return INVALID;

       }

       Edge edge = Parent::findEdge(u, v, prev);

       while (edge != INVALID && !(*_edge_filter)[edge]) {

         edge = Parent::findEdge(u, v, edge);

       }

       return edge;

     }

     template <typename V>

     class NodeMap

       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {

       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;

     public:

       typedef V Value;

       NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)

         : Parent(adaptor) {}

       NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)

         : Parent(adaptor, value) {}

     private:

       NodeMap& operator=(const NodeMap& cmap) {

         return operator=<NodeMap>(cmap);

       }

       template <typename CMap>

       NodeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

     template <typename V>

     class ArcMap

       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {

       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;

     public:

       typedef V Value;

       ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)

         : Parent(adaptor) {}

       ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)

         : Parent(adaptor, value) {}

     private:

       ArcMap& operator=(const ArcMap& cmap) {

         return operator=<ArcMap>(cmap);

       }

       template <typename CMap>

       ArcMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

     template <typename V>

     class EdgeMap

       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {

       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;

     public:

       typedef V Value;

       EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)

         : Parent(adaptor) {}

       EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)

         : Parent(adaptor, value) {}

     private:

       EdgeMap& operator=(const EdgeMap& cmap) {

         return operator=<EdgeMap>(cmap);

       }

       template <typename CMap>

       EdgeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

   };

   template <typename GR, typename NF, typename EF>

   class SubGraphBase<GR, NF, EF, false>

     : public GraphAdaptorBase<GR> {

     typedef GraphAdaptorBase<GR> Parent;

   public:

     typedef GR Graph;

     typedef NF NodeFilterMap;

     typedef EF EdgeFilterMap;

     typedef SubGraphBase Adaptor;

   protected:

     NF* _node_filter;

     EF* _edge_filter;

     SubGraphBase()

           : Parent(), _node_filter(0), _edge_filter(0) { }

     void initialize(GR& graph, NF& node_filter, EF& edge_filter) {

       Parent::initialize(graph);

       _node_filter = &node_filter;

       _edge_filter = &edge_filter;

     }

   public:

     typedef typename Parent::Node Node;

     typedef typename Parent::Arc Arc;

     typedef typename Parent::Edge Edge;

     void first(Node& i) const {

       Parent::first(i);

       while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);

     }

     void first(Arc& i) const {

       Parent::first(i);

       while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);

     }

     void first(Edge& i) const {

       Parent::first(i);

       while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);

     }

     void firstIn(Arc& i, const Node& n) const {

       Parent::firstIn(i, n);

       while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);

     }

     void firstOut(Arc& i, const Node& n) const {

       Parent::firstOut(i, n);

       while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);

     }

     void firstInc(Edge& i, bool& d, const Node& n) const {

       Parent::firstInc(i, d, n);

       while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);

     }

     void next(Node& i) const {

       Parent::next(i);

       while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);

     }

     void next(Arc& i) const {

       Parent::next(i);

       while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);

     }

     void next(Edge& i) const {

       Parent::next(i);

       while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);

     }

     void nextIn(Arc& i) const {

       Parent::nextIn(i);

       while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);

     }

     void nextOut(Arc& i) const {

       Parent::nextOut(i);

       while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);

     }

     void nextInc(Edge& i, bool& d) const {

       Parent::nextInc(i, d);

       while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);

     }

     void status(const Node& n, bool v) const { _node_filter->set(n, v); }

     void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }

     bool status(const Node& n) const { return (*_node_filter)[n]; }

     bool status(const Edge& e) const { return (*_edge_filter)[e]; }

     typedef False NodeNumTag;

     typedef False ArcNumTag;

     typedef False EdgeNumTag;

     typedef FindArcTagIndicator<Graph> FindArcTag;

     Arc findArc(const Node& u, const Node& v,

                 const Arc& prev = INVALID) const {

       Arc arc = Parent::findArc(u, v, prev);

       while (arc != INVALID && !(*_edge_filter)[arc]) {

         arc = Parent::findArc(u, v, arc);

       }

       return arc;

     }

     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

     Edge findEdge(const Node& u, const Node& v,

                   const Edge& prev = INVALID) const {

       Edge edge = Parent::findEdge(u, v, prev);

       while (edge != INVALID && !(*_edge_filter)[edge]) {

         edge = Parent::findEdge(u, v, edge);

       }

       return edge;

     }

     template <typename V>

     class NodeMap

       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,

           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {

       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,

         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;

     public:

       typedef V Value;

       NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)

         : Parent(adaptor) {}

       NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)

         : Parent(adaptor, value) {}

     private:

       NodeMap& operator=(const NodeMap& cmap) {

         return operator=<NodeMap>(cmap);

       }

       template <typename CMap>

       NodeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

     template <typename V>

     class ArcMap

       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,

           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {

       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,

         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;

     public:

       typedef V Value;

       ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)

         : Parent(adaptor) {}

       ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)

         : Parent(adaptor, value) {}

     private:

       ArcMap& operator=(const ArcMap& cmap) {

         return operator=<ArcMap>(cmap);

       }

       template <typename CMap>

       ArcMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

     template <typename V>

     class EdgeMap

       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,

         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {

       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,

         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;

     public:

       typedef V Value;

       EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)

         : Parent(adaptor) {}

       EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)

         : Parent(adaptor, value) {}

     private:

       EdgeMap& operator=(const EdgeMap& cmap) {

         return operator=<EdgeMap>(cmap);

       }

       template <typename CMap>

       EdgeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

   };

   /// \ingroup graph_adaptors

   ///

   /// \brief Adaptor class for hiding nodes and edges in an undirected

   /// graph.

   ///

   /// SubGraph can be used for hiding nodes and edges in a graph.

   /// A \c bool node map and a \c bool edge map must be specified, which

   /// define the filters for nodes and edges.

   /// Only the nodes and edges with \c true filter value are

   /// shown in the subgraph. The edges that are incident to hidden

   /// nodes are also filtered out.

   /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.

   ///

   /// The adapted graph can also be modified through this adaptor

   /// by adding or removing nodes or edges, unless the \c GR template

   /// parameter is set to be \c const.

   ///

   /// \tparam GR The type of the adapted graph.

   /// It must conform to the \ref concepts::Graph "Graph" concept.

   /// It can also be specified to be \c const.

   /// \tparam NF The type of the node filter map.

   /// It must be a \c bool (or convertible) node map of the

   /// adapted graph. The default type is

   /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".

   /// \tparam EF The type of the edge filter map.

   /// It must be a \c bool (or convertible) edge map of the

   /// adapted graph. The default type is

   /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".

   ///

   /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the

   /// adapted graph are convertible to each other.

   ///

   /// \see FilterNodes

   /// \see FilterEdges

 #ifdef DOXYGEN

   template<typename GR, typename NF, typename EF>

   class SubGraph {

 #else

   template<typename GR,

            typename NF = typename GR::template NodeMap<bool>,

            typename EF = typename GR::template EdgeMap<bool> >

   class SubGraph :

     public GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> > {

 #endif

   public:

     /// The type of the adapted graph.

     typedef GR Graph;

     /// The type of the node filter map.

     typedef NF NodeFilterMap;

     /// The type of the edge filter map.

     typedef EF EdgeFilterMap;

     typedef GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> >

       Parent;

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

   protected:

     SubGraph() { }

   public:

     /// \brief Constructor

     ///

     /// Creates a subgraph for the given graph with the given node

     /// and edge filter maps.

     SubGraph(GR& graph, NF& node_filter, EF& edge_filter) {

       initialize(graph, node_filter, edge_filter);

     }

     /// \brief Sets the status of the given node

     ///

     /// This function sets the status of the given node.

     /// It is done by simply setting the assigned value of \c n

     /// to \c v in the node filter map.

     void status(const Node& n, bool v) const { Parent::status(n, v); }

     /// \brief Sets the status of the given edge

     ///

     /// This function sets the status of the given edge.

     /// It is done by simply setting the assigned value of \c e

     /// to \c v in the edge filter map.

     void status(const Edge& e, bool v) const { Parent::status(e, v); }

     /// \brief Returns the status of the given node

     ///

     /// This function returns the status of the given node.

     /// It is \c true if the given node is enabled (i.e. not hidden).

     bool status(const Node& n) const { return Parent::status(n); }

     /// \brief Returns the status of the given edge

     ///

     /// This function returns the status of the given edge.

     /// It is \c true if the given edge is enabled (i.e. not hidden).

     bool status(const Edge& e) const { return Parent::status(e); }

     /// \brief Disables the given node

     ///

     /// This function disables the given node in the subdigraph,

     /// so the iteration jumps over it.

     /// It is the same as \ref status() "status(n, false)".

     void disable(const Node& n) const { Parent::status(n, false); }

     /// \brief Disables the given edge

     ///

     /// This function disables the given edge in the subgraph,

     /// so the iteration jumps over it.

     /// It is the same as \ref status() "status(e, false)".

     void disable(const Edge& e) const { Parent::status(e, false); }

     /// \brief Enables the given node

     ///

     /// This function enables the given node in the subdigraph.

     /// It is the same as \ref status() "status(n, true)".

     void enable(const Node& n) const { Parent::status(n, true); }

     /// \brief Enables the given edge

     ///

     /// This function enables the given edge in the subgraph.

     /// It is the same as \ref status() "status(e, true)".

     void enable(const Edge& e) const { Parent::status(e, true); }

   };

   /// \brief Returns a read-only SubGraph adaptor

   ///

   /// This function just returns a read-only \ref SubGraph adaptor.

   /// \ingroup graph_adaptors

   /// \relates SubGraph

   template<typename GR, typename NF, typename EF>

   SubGraph<const GR, NF, EF>

   subGraph(const GR& graph, NF& node_filter, EF& edge_filter) {

     return SubGraph<const GR, NF, EF>

       (graph, node_filter, edge_filter);

   }

   template<typename GR, typename NF, typename EF>

   SubGraph<const GR, const NF, EF>

   subGraph(const GR& graph, const NF& node_filter, EF& edge_filter) {

     return SubGraph<const GR, const NF, EF>

       (graph, node_filter, edge_filter);

   }

   template<typename GR, typename NF, typename EF>

   SubGraph<const GR, NF, const EF>

   subGraph(const GR& graph, NF& node_filter, const EF& edge_filter) {

     return SubGraph<const GR, NF, const EF>

       (graph, node_filter, edge_filter);

   }

   template<typename GR, typename NF, typename EF>

   SubGraph<const GR, const NF, const EF>

   subGraph(const GR& graph, const NF& node_filter, const EF& edge_filter) {

     return SubGraph<const GR, const NF, const EF>

       (graph, node_filter, edge_filter);

   }

   /// \ingroup graph_adaptors

   ///

   /// \brief Adaptor class for hiding nodes in a digraph or a graph.

   ///

   /// FilterNodes adaptor can be used for hiding nodes in a digraph or a

   /// graph. A \c bool node map must be specified, which defines the filter

   /// for the nodes. Only the nodes with \c true filter value and the

   /// arcs/edges incident to nodes both with \c true filter value are shown

   /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph

   /// "Digraph" concept or the \ref concepts::Graph "Graph" concept

   /// depending on the \c GR template parameter.

   ///

   /// The adapted (di)graph can also be modified through this adaptor

   /// by adding or removing nodes or arcs/edges, unless the \c GR template

   /// parameter is set to be \c const.

   ///

   /// \tparam GR The type of the adapted digraph or graph.

   /// It must conform to the \ref concepts::Digraph "Digraph" concept

   /// or the \ref concepts::Graph "Graph" concept.

   /// It can also be specified to be \c const.

   /// \tparam NF The type of the node filter map.

   /// It must be a \c bool (or convertible) node map of the

   /// adapted (di)graph. The default type is

   /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".

   ///

   /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the

   /// adapted (di)graph are convertible to each other.

 #ifdef DOXYGEN

   template<typename GR, typename NF>

   class FilterNodes {

 #else

   template<typename GR,

            typename NF = typename GR::template NodeMap<bool>,

            typename Enable = void>

   class FilterNodes :

     public DigraphAdaptorExtender<

       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,

                      true> > {

 #endif

     typedef DigraphAdaptorExtender<

       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,

                      true> > Parent;

   public:

     typedef GR Digraph;

     typedef NF NodeFilterMap;

     typedef typename Parent::Node Node;

   protected:

     ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map;

     FilterNodes() : const_true_map() {}

   public:

     /// \brief Constructor

     ///

     /// Creates a subgraph for the given digraph or graph with the

     /// given node filter map.

     FilterNodes(GR& graph, NF& node_filter)

       : Parent(), const_true_map()

     {

       Parent::initialize(graph, node_filter, const_true_map);

     }

     /// \brief Sets the status of the given node

     ///

     /// This function sets the status of the given node.

     /// It is done by simply setting the assigned value of \c n

     /// to \c v in the node filter map.

     void status(const Node& n, bool v) const { Parent::status(n, v); }

     /// \brief Returns the status of the given node

     ///

     /// This function returns the status of the given node.

     /// It is \c true if the given node is enabled (i.e. not hidden).

     bool status(const Node& n) const { return Parent::status(n); }

     /// \brief Disables the given node

     ///

     /// This function disables the given node, so the iteration

     /// jumps over it.

     /// It is the same as \ref status() "status(n, false)".

     void disable(const Node& n) const { Parent::status(n, false); }

     /// \brief Enables the given node

     ///

     /// This function enables the given node.

     /// It is the same as \ref status() "status(n, true)".

     void enable(const Node& n) const { Parent::status(n, true); }

   };

   template<typename GR, typename NF>

   class FilterNodes<GR, NF,

                     typename enable_if<UndirectedTagIndicator<GR> >::type> :

     public GraphAdaptorExtender<

       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,

                    true> > {

     typedef GraphAdaptorExtender<

       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,

                    true> > Parent;

   public:

     typedef GR Graph;

     typedef NF NodeFilterMap;

     typedef typename Parent::Node Node;

   protected:

     ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;

     FilterNodes() : const_true_map() {}

   public:

     FilterNodes(GR& graph, NodeFilterMap& node_filter) :

       Parent(), const_true_map() {

       Parent::initialize(graph, node_filter, const_true_map);

     }

     void status(const Node& n, bool v) const { Parent::status(n, v); }

     bool status(const Node& n) const { return Parent::status(n); }

     void disable(const Node& n) const { Parent::status(n, false); }

     void enable(const Node& n) const { Parent::status(n, true); }

   };

   /// \brief Returns a read-only FilterNodes adaptor

   ///

   /// This function just returns a read-only \ref FilterNodes adaptor.

   /// \ingroup graph_adaptors

   /// \relates FilterNodes

   template<typename GR, typename NF>

   FilterNodes<const GR, NF>

   filterNodes(const GR& graph, NF& node_filter) {

     return FilterNodes<const GR, NF>(graph, node_filter);

   }

   template<typename GR, typename NF>

   FilterNodes<const GR, const NF>

   filterNodes(const GR& graph, const NF& node_filter) {

     return FilterNodes<const GR, const NF>(graph, node_filter);

   }

   /// \ingroup graph_adaptors

   ///

   /// \brief Adaptor class for hiding arcs in a digraph.

   ///

   /// FilterArcs adaptor can be used for hiding arcs in a digraph.

   /// A \c bool arc map must be specified, which defines the filter for

   /// the arcs. Only the arcs with \c true filter value are shown in the

   /// subdigraph. This adaptor conforms to the \ref concepts::Digraph

   /// "Digraph" concept.

   ///

   /// The adapted digraph can also be modified through this adaptor

   /// by adding or removing nodes or arcs, unless the \c GR template

   /// parameter is set to be \c const.

   ///

   /// \tparam DGR The type of the adapted digraph.

   /// It must conform to the \ref concepts::Digraph "Digraph" concept.

   /// It can also be specified to be \c const.

   /// \tparam AF The type of the arc filter map.

   /// It must be a \c bool (or convertible) arc map of the

   /// adapted digraph. The default type is

   /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".

   ///

   /// \note The \c Node and \c Arc types of this adaptor and the adapted

   /// digraph are convertible to each other.

 #ifdef DOXYGEN

   template<typename DGR,

            typename AF>

   class FilterArcs {

 #else

   template<typename DGR,

            typename AF = typename DGR::template ArcMap<bool> >

   class FilterArcs :

     public DigraphAdaptorExtender<

       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,

                      AF, false> > {

 #endif

     typedef DigraphAdaptorExtender<

       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,

                      AF, false> > Parent;

   public:

     /// The type of the adapted digraph.

     typedef DGR Digraph;

     /// The type of the arc filter map.

     typedef AF ArcFilterMap;

     typedef typename Parent::Arc Arc;

   protected:

     ConstMap<typename DGR::Node, Const<bool, true> > const_true_map;

     FilterArcs() : const_true_map() {}

   public:

     /// \brief Constructor

     ///

     /// Creates a subdigraph for the given digraph with the given arc

     /// filter map.

     FilterArcs(DGR& digraph, ArcFilterMap& arc_filter)

       : Parent(), const_true_map() {

       Parent::initialize(digraph, const_true_map, arc_filter);

     }

     /// \brief Sets the status of the given arc

     ///

     /// This function sets the status of the given arc.

     /// It is done by simply setting the assigned value of \c a

     /// to \c v in the arc filter map.

     void status(const Arc& a, bool v) const { Parent::status(a, v); }

     /// \brief Returns the status of the given arc

     ///

     /// This function returns the status of the given arc.

     /// It is \c true if the given arc is enabled (i.e. not hidden).

     bool status(const Arc& a) const { return Parent::status(a); }

     /// \brief Disables the given arc

     ///

     /// This function disables the given arc in the subdigraph,

     /// so the iteration jumps over it.

     /// It is the same as \ref status() "status(a, false)".

     void disable(const Arc& a) const { Parent::status(a, false); }

     /// \brief Enables the given arc

     ///

     /// This function enables the given arc in the subdigraph.

     /// It is the same as \ref status() "status(a, true)".

     void enable(const Arc& a) const { Parent::status(a, true); }

   };

   /// \brief Returns a read-only FilterArcs adaptor

   ///

   /// This function just returns a read-only \ref FilterArcs adaptor.

   /// \ingroup graph_adaptors

   /// \relates FilterArcs

   template<typename DGR, typename AF>

   FilterArcs<const DGR, AF>

   filterArcs(const DGR& digraph, AF& arc_filter) {

     return FilterArcs<const DGR, AF>(digraph, arc_filter);

   }

   template<typename DGR, typename AF>

   FilterArcs<const DGR, const AF>

   filterArcs(const DGR& digraph, const AF& arc_filter) {

     return FilterArcs<const DGR, const AF>(digraph, arc_filter);

   }

   /// \ingroup graph_adaptors

   ///

   /// \brief Adaptor class for hiding edges in a graph.

   ///

   /// FilterEdges adaptor can be used for hiding edges in a graph.

   /// A \c bool edge map must be specified, which defines the filter for

   /// the edges. Only the edges with \c true filter value are shown in the

   /// subgraph. This adaptor conforms to the \ref concepts::Graph

   /// "Graph" concept.

   ///

   /// The adapted graph can also be modified through this adaptor

   /// by adding or removing nodes or edges, unless the \c GR template

   /// parameter is set to be \c const.

   ///

   /// \tparam GR The type of the adapted graph.

   /// It must conform to the \ref concepts::Graph "Graph" concept.

   /// It can also be specified to be \c const.

   /// \tparam EF The type of the edge filter map.

   /// It must be a \c bool (or convertible) edge map of the

   /// adapted graph. The default type is

   /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".

   ///

   /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the

   /// adapted graph are convertible to each other.

 #ifdef DOXYGEN

   template<typename GR,

            typename EF>

   class FilterEdges {

 #else

   template<typename GR,

            typename EF = typename GR::template EdgeMap<bool> >

   class FilterEdges :

     public GraphAdaptorExtender<

       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,

                    EF, false> > {

 #endif

     typedef GraphAdaptorExtender<

       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,

                    EF, false> > Parent;

   public:

     /// The type of the adapted graph.

     typedef GR Graph;

     /// The type of the edge filter map.

     typedef EF EdgeFilterMap;

     typedef typename Parent::Edge Edge;

   protected:

     ConstMap<typename GR::Node, Const<bool, true> > const_true_map;

     FilterEdges() : const_true_map(true) {

       Parent::setNodeFilterMap(const_true_map);

     }

   public:

     /// \brief Constructor

     ///

     /// Creates a subgraph for the given graph with the given edge

     /// filter map.

     FilterEdges(GR& graph, EF& edge_filter)

       : Parent(), const_true_map() {

       Parent::initialize(graph, const_true_map, edge_filter);

     }

     /// \brief Sets the status of the given edge

     ///

     /// This function sets the status of the given edge.

     /// It is done by simply setting the assigned value of \c e

     /// to \c v in the edge filter map.

     void status(const Edge& e, bool v) const { Parent::status(e, v); }

     /// \brief Returns the status of the given edge

     ///

     /// This function returns the status of the given edge.

     /// It is \c true if the given edge is enabled (i.e. not hidden).

     bool status(const Edge& e) const { return Parent::status(e); }

     /// \brief Disables the given edge

     ///

     /// This function disables the given edge in the subgraph,

     /// so the iteration jumps over it.

     /// It is the same as \ref status() "status(e, false)".

     void disable(const Edge& e) const { Parent::status(e, false); }

     /// \brief Enables the given edge

     ///

     /// This function enables the given edge in the subgraph.

     /// It is the same as \ref status() "status(e, true)".

     void enable(const Edge& e) const { Parent::status(e, true); }

   };

   /// \brief Returns a read-only FilterEdges adaptor

   ///

   /// This function just returns a read-only \ref FilterEdges adaptor.

   /// \ingroup graph_adaptors

   /// \relates FilterEdges

   template<typename GR, typename EF>

   FilterEdges<const GR, EF>

   filterEdges(const GR& graph, EF& edge_filter) {

     return FilterEdges<const GR, EF>(graph, edge_filter);

   }

   template<typename GR, typename EF>

   FilterEdges<const GR, const EF>

   filterEdges(const GR& graph, const EF& edge_filter) {

     return FilterEdges<const GR, const EF>(graph, edge_filter);

   }

   template <typename DGR>

   class UndirectorBase {

   public:

     typedef DGR Digraph;

     typedef UndirectorBase Adaptor;

     typedef True UndirectedTag;

     typedef typename Digraph::Arc Edge;

     typedef typename Digraph::Node Node;

     class Arc {

       friend class UndirectorBase;

     protected:

       Edge _edge;

       bool _forward;

       Arc(const Edge& edge, bool forward)

         : _edge(edge), _forward(forward) {}

     public:

       Arc() {}

       Arc(Invalid) : _edge(INVALID), _forward(true) {}

       operator const Edge&() const { return _edge; }

       bool operator==(const Arc &other) const {

         return _forward == other._forward && _edge == other._edge;

       }

       bool operator!=(const Arc &other) const {

         return _forward != other._forward || _edge != other._edge;

       }

       bool operator<(const Arc &other) const {

         return _forward < other._forward ||

           (_forward == other._forward && _edge < other._edge);

       }

     };

     void first(Node& n) const {

       _digraph->first(n);

     }

     void next(Node& n) const {

       _digraph->next(n);

     }

     void first(Arc& a) const {

       _digraph->first(a._edge);

       a._forward = true;

     }

     void next(Arc& a) const {

       if (a._forward) {

         a._forward = false;

       } else {

         _digraph->next(a._edge);

         a._forward = true;

       }

     }

     void first(Edge& e) const {

       _digraph->first(e);

     }

     void next(Edge& e) const {

       _digraph->next(e);

     }

     void firstOut(Arc& a, const Node& n) const {

       _digraph->firstIn(a._edge, n);

       if (a._edge != INVALID ) {

         a._forward = false;

       } else {

         _digraph->firstOut(a._edge, n);

         a._forward = true;

       }

     }

     void nextOut(Arc &a) const {

       if (!a._forward) {

         Node n = _digraph->target(a._edge);

         _digraph->nextIn(a._edge);

         if (a._edge == INVALID) {

           _digraph->firstOut(a._edge, n);

           a._forward = true;

         }

       }

       else {

         _digraph->nextOut(a._edge);

       }

     }

     void firstIn(Arc &a, const Node &n) const {

       _digraph->firstOut(a._edge, n);

       if (a._edge != INVALID ) {

         a._forward = false;

       } else {

         _digraph->firstIn(a._edge, n);

         a._forward = true;

       }

     }

     void nextIn(Arc &a) const {

       if (!a._forward) {

         Node n = _digraph->source(a._edge);

         _digraph->nextOut(a._edge);

         if (a._edge == INVALID ) {

           _digraph->firstIn(a._edge, n);

           a._forward = true;

         }

       }

       else {

         _digraph->nextIn(a._edge);

       }

     }

     void firstInc(Edge &e, bool &d, const Node &n) const {

       d = true;

       _digraph->firstOut(e, n);

       if (e != INVALID) return;

       d = false;

       _digraph->firstIn(e, n);

     }

     void nextInc(Edge &e, bool &d) const {

       if (d) {

         Node s = _digraph->source(e);

         _digraph->nextOut(e);

         if (e != INVALID) return;

         d = false;

         _digraph->firstIn(e, s);

       } else {

         _digraph->nextIn(e);

       }

     }

     Node u(const Edge& e) const {

       return _digraph->source(e);

     }

     Node v(const Edge& e) const {

       return _digraph->target(e);

     }

     Node source(const Arc &a) const {

       return a._forward ? _digraph->source(a._edge) : _digraph->target(a._edge);

     }

     Node target(const Arc &a) const {

       return a._forward ? _digraph->target(a._edge) : _digraph->source(a._edge);

     }

     static Arc direct(const Edge &e, bool d) {

       return Arc(e, d);

     }

     static bool direction(const Arc &a) { return a._forward; }

     Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }

     Arc arcFromId(int ix) const {

       return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));

     }

     Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }

     int id(const Node &n) const { return _digraph->id(n); }

     int id(const Arc &a) const {

       return  (_digraph->id(a) << 1) | (a._forward ? 1 : 0);

     }

     int id(const Edge &e) const { return _digraph->id(e); }

     int maxNodeId() const { return _digraph->maxNodeId(); }

     int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }

     int maxEdgeId() const { return _digraph->maxArcId(); }

     Node addNode() { return _digraph->addNode(); }

     Edge addEdge(const Node& u, const Node& v) {

       return _digraph->addArc(u, v);

     }

     void erase(const Node& i) { _digraph->erase(i); }

     void erase(const Edge& i) { _digraph->erase(i); }

     void clear() { _digraph->clear(); }

     typedef NodeNumTagIndicator<Digraph> NodeNumTag;

     int nodeNum() const { return _digraph->nodeNum(); }

     typedef ArcNumTagIndicator<Digraph> ArcNumTag;

     int arcNum() const { return 2 * _digraph->arcNum(); }

     typedef ArcNumTag EdgeNumTag;

     int edgeNum() const { return _digraph->arcNum(); }

     typedef FindArcTagIndicator<Digraph> FindArcTag;

     Arc findArc(Node s, Node t, Arc p = INVALID) const {

       if (p == INVALID) {

         Edge arc = _digraph->findArc(s, t);

         if (arc != INVALID) return direct(arc, true);

         arc = _digraph->findArc(t, s);

         if (arc != INVALID) return direct(arc, false);

       } else if (direction(p)) {

         Edge arc = _digraph->findArc(s, t, p);

         if (arc != INVALID) return direct(arc, true);

         arc = _digraph->findArc(t, s);

         if (arc != INVALID) return direct(arc, false);

       } else {

         Edge arc = _digraph->findArc(t, s, p);

         if (arc != INVALID) return direct(arc, false);

       }

       return INVALID;

     }

     typedef FindArcTag FindEdgeTag;

     Edge findEdge(Node s, Node t, Edge p = INVALID) const {

       if (s != t) {

         if (p == INVALID) {

           Edge arc = _digraph->findArc(s, t);

           if (arc != INVALID) return arc;

           arc = _digraph->findArc(t, s);

           if (arc != INVALID) return arc;

         } else if (_digraph->source(p) == s) {

           Edge arc = _digraph->findArc(s, t, p);

           if (arc != INVALID) return arc;

           arc = _digraph->findArc(t, s);

           if (arc != INVALID) return arc;

         } else {

           Edge arc = _digraph->findArc(t, s, p);

           if (arc != INVALID) return arc;

         }

       } else {

         return _digraph->findArc(s, t, p);

       }

       return INVALID;

     }

   private:

     template <typename V>

     class ArcMapBase {

     private:

       typedef typename DGR::template ArcMap<V> MapImpl;

     public:

       typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;

       typedef V Value;

       typedef Arc Key;

       typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;

       typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;

       typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;

       typedef typename MapTraits<MapImpl>::ReturnValue Reference;

       ArcMapBase(const UndirectorBase<DGR>& adaptor) :

         _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}

       ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)

         : _forward(*adaptor._digraph, value),

           _backward(*adaptor._digraph, value) {}

       void set(const Arc& a, const V& value) {

         if (direction(a)) {

           _forward.set(a, value);

         } else {

           _backward.set(a, value);

         }

       }

       ConstReturnValue operator[](const Arc& a) const {

         if (direction(a)) {

           return _forward[a];

         } else {

           return _backward[a];

         }

       }

       ReturnValue operator[](const Arc& a) {

         if (direction(a)) {

           return _forward[a];

         } else {

           return _backward[a];

         }

       }

     protected:

       MapImpl _forward, _backward;

     };

   public:

     template <typename V>

     class NodeMap : public DGR::template NodeMap<V> {

       typedef typename DGR::template NodeMap<V> Parent;

     public:

       typedef V Value;

       explicit NodeMap(const UndirectorBase<DGR>& adaptor)

         : Parent(*adaptor._digraph) {}

       NodeMap(const UndirectorBase<DGR>& adaptor, const V& value)

         : Parent(*adaptor._digraph, value) { }

     private:

       NodeMap& operator=(const NodeMap& cmap) {

         return operator=<NodeMap>(cmap);

       }

       template <typename CMap>

       NodeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

     template <typename V>

     class ArcMap

       : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > {

       typedef SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > Parent;

     public:

       typedef V Value;

       explicit ArcMap(const UndirectorBase<DGR>& adaptor)

         : Parent(adaptor) {}

       ArcMap(const UndirectorBase<DGR>& adaptor, const V& value)

         : Parent(adaptor, value) {}

     private:

       ArcMap& operator=(const ArcMap& cmap) {

         return operator=<ArcMap>(cmap);

       }

       template <typename CMap>

       ArcMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

     template <typename V>

     class EdgeMap : public Digraph::template ArcMap<V> {

       typedef typename Digraph::template ArcMap<V> Parent;

     public:

       typedef V Value;

       explicit EdgeMap(const UndirectorBase<DGR>& adaptor)

         : Parent(*adaptor._digraph) {}

       EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)

         : Parent(*adaptor._digraph, value) {}

     private:

       EdgeMap& operator=(const EdgeMap& cmap) {

         return operator=<EdgeMap>(cmap);

       }

       template <typename CMap>

       EdgeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

     typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;

     NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }

     typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;

     EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }

     typedef EdgeNotifier ArcNotifier;

     ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }

   protected:

     UndirectorBase() : _digraph(0) {}

     DGR* _digraph;

     void initialize(DGR& digraph) {

       _digraph = &digraph;

     }

   };

   /// \ingroup graph_adaptors

   ///

   /// \brief Adaptor class for viewing a digraph as an undirected graph.

   ///

   /// Undirector adaptor can be used for viewing a digraph as an undirected

   /// graph. All arcs of the underlying digraph are showed in the

   /// adaptor as an edge (and also as a pair of arcs, of course).

   /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.

   ///

   /// The adapted digraph can also be modified through this adaptor

   /// by adding or removing nodes or edges, unless the \c GR template

   /// parameter is set to be \c const.

   ///

   /// \tparam DGR The type of the adapted digraph.

   /// It must conform to the \ref concepts::Digraph "Digraph" concept.

   /// It can also be specified to be \c const.

   ///

   /// \note The \c Node type of this adaptor and the adapted digraph are

   /// convertible to each other, moreover the \c Edge type of the adaptor

   /// and the \c Arc type of the adapted digraph are also convertible to

   /// each other.

   /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type

   /// of the adapted digraph.)

   template<typename DGR>

 #ifdef DOXYGEN

   class Undirector {

 #else

   class Undirector :

     public GraphAdaptorExtender<UndirectorBase<DGR> > {

 #endif

     typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;

   public:

     /// The type of the adapted digraph.

     typedef DGR Digraph;

   protected:

     Undirector() { }

   public:

     /// \brief Constructor

     ///

     /// Creates an undirected graph from the given digraph.

     Undirector(DGR& digraph) {

       initialize(digraph);

     }

     /// \brief Arc map combined from two original arc maps

     ///

     /// This map adaptor class adapts two arc maps of the underlying

     /// digraph to get an arc map of the undirected graph.

     /// Its value type is inherited from the first arc map type (\c FW).

     /// \tparam FW The type of the "foward" arc map.

     /// \tparam BK The type of the "backward" arc map.

     template <typename FW, typename BK>

     class CombinedArcMap {

     public:

       /// The key type of the map

       typedef typename Parent::Arc Key;

       /// The value type of the map

       typedef typename FW::Value Value;

       typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag;

       typedef typename MapTraits<FW>::ReturnValue ReturnValue;

       typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue;

       typedef typename MapTraits<FW>::ReturnValue Reference;

       typedef typename MapTraits<FW>::ConstReturnValue ConstReference;

       /// Constructor

       CombinedArcMap(FW& forward, BK& backward)

         : _forward(&forward), _backward(&backward) {}

       /// Sets the value associated with the given key.

       void set(const Key& e, const Value& a) {

         if (Parent::direction(e)) {

           _forward->set(e, a);

         } else {

           _backward->set(e, a);

         }

       }

       /// Returns the value associated with the given key.

       ConstReturnValue operator[](const Key& e) const {

         if (Parent::direction(e)) {

           return (*_forward)[e];

         } else {

           return (*_backward)[e];

         }

       }

       /// Returns a reference to the value associated with the given key.

       ReturnValue operator[](const Key& e) {

         if (Parent::direction(e)) {

           return (*_forward)[e];

         } else {

           return (*_backward)[e];

         }

       }

     protected:

       FW* _forward;

       BK* _backward;

     };

     /// \brief Returns a combined arc map

     ///

     /// This function just returns a combined arc map.

     template <typename FW, typename BK>

     static CombinedArcMap<FW, BK>

     combinedArcMap(FW& forward, BK& backward) {

       return CombinedArcMap<FW, BK>(forward, backward);

     }

     template <typename FW, typename BK>

     static CombinedArcMap<const FW, BK>

     combinedArcMap(const FW& forward, BK& backward) {

       return CombinedArcMap<const FW, BK>(forward, backward);

     }

     template <typename FW, typename BK>

     static CombinedArcMap<FW, const BK>

     combinedArcMap(FW& forward, const BK& backward) {

       return CombinedArcMap<FW, const BK>(forward, backward);

     }

     template <typename FW, typename BK>

     static CombinedArcMap<const FW, const BK>

     combinedArcMap(const FW& forward, const BK& backward) {

       return CombinedArcMap<const FW, const BK>(forward, backward);

     }

   };

   /// \brief Returns a read-only Undirector adaptor

   ///

   /// This function just returns a read-only \ref Undirector adaptor.

   /// \ingroup graph_adaptors

   /// \relates Undirector

   template<typename DGR>

   Undirector<const DGR> undirector(const DGR& digraph) {

     return Undirector<const DGR>(digraph);

   }

   template <typename GR, typename DM>

   class OrienterBase {

   public:

     typedef GR Graph;

     typedef DM DirectionMap;

     typedef typename GR::Node Node;

     typedef typename GR::Edge Arc;

     void reverseArc(const Arc& arc) {

       _direction->set(arc, !(*_direction)[arc]);

     }

     void first(Node& i) const { _graph->first(i); }

     void first(Arc& i) const { _graph->first(i); }

     void firstIn(Arc& i, const Node& n) const {

       bool d = true;

       _graph->firstInc(i, d, n);

       while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);

     }

     void firstOut(Arc& i, const Node& n ) const {

       bool d = true;

       _graph->firstInc(i, d, n);

       while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);

     }

     void next(Node& i) const { _graph->next(i); }

     void next(Arc& i) const { _graph->next(i); }

     void nextIn(Arc& i) const {

       bool d = !(*_direction)[i];

       _graph->nextInc(i, d);

       while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);

     }

     void nextOut(Arc& i) const {

       bool d = (*_direction)[i];

       _graph->nextInc(i, d);

       while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);

     }

     Node source(const Arc& e) const {

       return (*_direction)[e] ? _graph->u(e) : _graph->v(e);

     }

     Node target(const Arc& e) const {

       return (*_direction)[e] ? _graph->v(e) : _graph->u(e);

     }

     typedef NodeNumTagIndicator<Graph> NodeNumTag;

     int nodeNum() const { return _graph->nodeNum(); }

     typedef EdgeNumTagIndicator<Graph> ArcNumTag;

     int arcNum() const { return _graph->edgeNum(); }

     typedef FindEdgeTagIndicator<Graph> FindArcTag;

     Arc findArc(const Node& u, const Node& v,

                 const Arc& prev = INVALID) const {

       Arc arc = _graph->findEdge(u, v, prev);

       while (arc != INVALID && source(arc) != u) {

         arc = _graph->findEdge(u, v, arc);

       }

       return arc;

     }

     Node addNode() {

       return Node(_graph->addNode());

     }

     Arc addArc(const Node& u, const Node& v) {

       Arc arc = _graph->addEdge(u, v);

       _direction->set(arc, _graph->u(arc) == u);

       return arc;

     }

     void erase(const Node& i) { _graph->erase(i); }

     void erase(const Arc& i) { _graph->erase(i); }

     void clear() { _graph->clear(); }

     int id(const Node& v) const { return _graph->id(v); }

     int id(const Arc& e) const { return _graph->id(e); }

     Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }

     Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }

     int maxNodeId() const { return _graph->maxNodeId(); }

     int maxArcId() const { return _graph->maxEdgeId(); }

     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;

     NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }

     typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;

     ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }

     template <typename V>

     class NodeMap : public GR::template NodeMap<V> {

       typedef typename GR::template NodeMap<V> Parent;

     public:

       explicit NodeMap(const OrienterBase<GR, DM>& adapter)

         : Parent(*adapter._graph) {}

       NodeMap(const OrienterBase<GR, DM>& adapter, const V& value)

         : Parent(*adapter._graph, value) {}

     private:

       NodeMap& operator=(const NodeMap& cmap) {

         return operator=<NodeMap>(cmap);

       }

       template <typename CMap>

       NodeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

     template <typename V>

     class ArcMap : public GR::template EdgeMap<V> {

       typedef typename Graph::template EdgeMap<V> Parent;

     public:

       explicit ArcMap(const OrienterBase<GR, DM>& adapter)

         : Parent(*adapter._graph) { }

       ArcMap(const OrienterBase<GR, DM>& adapter, const V& value)

         : Parent(*adapter._graph, value) { }

     private:

       ArcMap& operator=(const ArcMap& cmap) {

         return operator=<ArcMap>(cmap);

       }

       template <typename CMap>

       ArcMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

   protected:

     Graph* _graph;

     DM* _direction;

     void initialize(GR& graph, DM& direction) {

       _graph = &graph;

       _direction = &direction;

     }

   };

   /// \ingroup graph_adaptors

   ///

   /// \brief Adaptor class for orienting the edges of a graph to get a digraph

   ///

   /// Orienter adaptor can be used for orienting the edges of a graph to

   /// get a digraph. A \c bool edge map of the underlying graph must be

   /// specified, which define the direction of the arcs in the adaptor.

   /// The arcs can be easily reversed by the \c reverseArc() member function

   /// of the adaptor.

   /// This class conforms to the \ref concepts::Digraph "Digraph" concept.

   ///

   /// The adapted graph can also be modified through this adaptor

   /// by adding or removing nodes or arcs, unless the \c GR template

   /// parameter is set to be \c const.

   ///

   /// \tparam GR The type of the adapted graph.

   /// It must conform to the \ref concepts::Graph "Graph" concept.

   /// It can also be specified to be \c const.

   /// \tparam DM The type of the direction map.

   /// It must be a \c bool (or convertible) edge map of the

   /// adapted graph. The default type is

   /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".

   ///

   /// \note The \c Node type of this adaptor and the adapted graph are

   /// convertible to each other, moreover the \c Arc type of the adaptor

   /// and the \c Edge type of the adapted graph are also convertible to

   /// each other.

 #ifdef DOXYGEN

   template<typename GR,

            typename DM>

   class Orienter {

 #else

   template<typename GR,

            typename DM = typename GR::template EdgeMap<bool> >

   class Orienter :

     public DigraphAdaptorExtender<OrienterBase<GR, DM> > {

 #endif

     typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;

   public:

     /// The type of the adapted graph.

     typedef GR Graph;

     /// The type of the direction edge map.

     typedef DM DirectionMap;

     typedef typename Parent::Arc Arc;

   protected:

     Orienter() { }

   public:

     /// \brief Constructor

     ///

     /// Constructor of the adaptor.

     Orienter(GR& graph, DM& direction) {

       Parent::initialize(graph, direction);

     }

     /// \brief Reverses the given arc

     ///

     /// This function reverses the given arc.

     /// It is done by simply negate the assigned value of \c a

     /// in the direction map.

     void reverseArc(const Arc& a) {

       Parent::reverseArc(a);

     }

   };

   /// \brief Returns a read-only Orienter adaptor

   ///

   /// This function just returns a read-only \ref Orienter adaptor.

   /// \ingroup graph_adaptors

   /// \relates Orienter

   template<typename GR, typename DM>

   Orienter<const GR, DM>

   orienter(const GR& graph, DM& direction) {

     return Orienter<const GR, DM>(graph, direction);

   }

   template<typename GR, typename DM>

   Orienter<const GR, const DM>

   orienter(const GR& graph, const DM& direction) {

     return Orienter<const GR, const DM>(graph, direction);

   }

   namespace _adaptor_bits {

     template <typename DGR, typename CM, typename FM, typename TL>

     class ResForwardFilter {

     public:

       typedef typename DGR::Arc Key;

       typedef bool Value;

     private:

       const CM* _capacity;

       const FM* _flow;

       TL _tolerance;

     public:

       ResForwardFilter(const CM& capacity, const FM& flow,

                        const TL& tolerance = TL())

         : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }

       bool operator[](const typename DGR::Arc& a) const {

         return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);

       }

     };

     template<typename DGR,typename CM, typename FM, typename TL>

     class ResBackwardFilter {

     public:

       typedef typename DGR::Arc Key;

       typedef bool Value;

     private:

       const CM* _capacity;

       const FM* _flow;

       TL _tolerance;

     public: