RhodeCode

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

 *

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

 *

 * Copyright (C) 2003-2008

 * 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/tolerance.h>

#include <algorithm>

namespace lemon {

  template<typename _Digraph>

  class DigraphAdaptorBase {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorBase Adaptor;

    typedef Digraph ParentDigraph;

  protected:

    Digraph* _digraph;

    DigraphAdaptorBase() : _digraph(0) { }

    void setDigraph(Digraph& digraph) { _digraph = &digraph; }

  public:

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

    typedef typename Digraph::Node Node;

    typedef typename Digraph::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<Digraph> NodeNumTag;

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

    typedef ArcNumTagIndicator<Digraph> ArcNumTag;

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

    typedef FindArcTagIndicator<Digraph> 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<Digraph, Node>::ItemNotifier NodeNotifier;

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

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

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

    template <typename _Value>

    class NodeMap : public Digraph::template NodeMap<_Value> {

    public:

      typedef typename Digraph::template NodeMap<_Value> Parent;

      explicit NodeMap(const Adaptor& adaptor)

        : Parent(*adaptor._digraph) {}

      NodeMap(const Adaptor& adaptor, const _Value& 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 _Value>

    class ArcMap : public Digraph::template ArcMap<_Value> {

    public:

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

      explicit ArcMap(const Adaptor& adaptor)

        : Parent(*adaptor._digraph) {}

      ArcMap(const Adaptor& adaptor, const _Value& 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 _Graph>

  class GraphAdaptorBase {

  public:

    typedef _Graph Graph;

    typedef Graph ParentGraph;

  protected:

    Graph* _graph;

    GraphAdaptorBase() : _graph(0) {}

    void setGraph(Graph& graph) { _graph = &graph; }

  public:

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

    typedef typename Graph::Node Node;

    typedef typename Graph::Arc Arc;

    typedef typename Graph::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<Graph, Node>::ItemNotifier NodeNotifier;

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

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

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

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

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

    template <typename _Value>

    class NodeMap : public Graph::template NodeMap<_Value> {

    public:

      typedef typename Graph::template NodeMap<_Value> Parent;

      explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)

        : Parent(*adapter._graph) {}

      NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& 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 _Value>

    class ArcMap : public Graph::template ArcMap<_Value> {

    public:

      typedef typename Graph::template ArcMap<_Value> Parent;

      explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)

        : Parent(*adapter._graph) {}

      ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& 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 _Value>

    class EdgeMap : public Graph::template EdgeMap<_Value> {

    public:

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

      explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)

        : Parent(*adapter._graph) {}

      EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& 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 _Digraph>

  class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorBase<_Digraph> Parent;

  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<Digraph> 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 _Digraph template

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

  ///

  /// \tparam _Digraph 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 _Digraph>

  class ReverseDigraph :

    public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorExtender<

      ReverseDigraphBase<_Digraph> > Parent;

  protected:

    ReverseDigraph() { }

  public:

    /// \brief Constructor

    ///

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

    explicit ReverseDigraph(Digraph& digraph) {

      Parent::setDigraph(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 Digraph>

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

    return ReverseDigraph<const Digraph>(digraph);

  }

  template <typename _Digraph, typename _NodeFilterMap,

            typename _ArcFilterMap, bool _checked = true>

  class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {

  public:

    typedef _Digraph Digraph;

    typedef _NodeFilterMap NodeFilterMap;

    typedef _ArcFilterMap ArcFilterMap;

    typedef SubDigraphBase Adaptor;

    typedef DigraphAdaptorBase<_Digraph> Parent;

  protected:

    NodeFilterMap* _node_filter;

    ArcFilterMap* _arc_filter;

    SubDigraphBase()

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

    void setNodeFilterMap(NodeFilterMap& node_filter) {

      _node_filter = &node_filter;

    }

    void setArcFilterMap(ArcFilterMap& arc_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);

    }

    typedef False NodeNumTag;

    typedef False ArcNumTag;

    typedef FindArcTagIndicator<Digraph> 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 _Value>

    class NodeMap : public SubMapExtender<Adaptor,

      typename Parent::template NodeMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template NodeMap<Value> > MapParent;

      NodeMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

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

        : MapParent(adaptor, value) {}

    private:

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

        return *this;

      }

    };

    template <typename _Value>

    class ArcMap : public SubMapExtender<Adaptor,

      typename Parent::template ArcMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template ArcMap<Value> > MapParent;

      ArcMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

      ArcMap(const Adaptor& adaptor, const Value& value)

        : MapParent(adaptor, value) {}

    private:

      ArcMap& operator=(const ArcMap& cmap) {

        return operator=<ArcMap>(cmap);

      }

      template <typename CMap>

      ArcMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

        return *this;

      }

    };

  };

  template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>

  class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>

    : public DigraphAdaptorBase<_Digraph> {

  public:

    typedef _Digraph Digraph;

    typedef _NodeFilterMap NodeFilterMap;

    typedef _ArcFilterMap ArcFilterMap;

    typedef SubDigraphBase Adaptor;

    typedef DigraphAdaptorBase<Digraph> Parent;

  protected:

    NodeFilterMap* _node_filter;

    ArcFilterMap* _arc_filter;

    SubDigraphBase()

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

    void setNodeFilterMap(NodeFilterMap& node_filter) {

      _node_filter = &node_filter;

    }

    void setArcFilterMap(ArcFilterMap& arc_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);

    }

    typedef False NodeNumTag;

    typedef False ArcNumTag;

    typedef FindArcTagIndicator<Digraph> 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 _Value>

    class NodeMap : public SubMapExtender<Adaptor,

      typename Parent::template NodeMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template NodeMap<Value> > MapParent;

      NodeMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

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

        : MapParent(adaptor, value) {}

    private:

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

        return *this;

      }

    };

    template <typename _Value>

    class ArcMap : public SubMapExtender<Adaptor,

      typename Parent::template ArcMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template ArcMap<Value> > MapParent;

      ArcMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

      ArcMap(const Adaptor& adaptor, const Value& value)

        : MapParent(adaptor, value) {}

    private:

      ArcMap& operator=(const ArcMap& cmap) {

        return operator=<ArcMap>(cmap);

      }

      template <typename CMap>

      ArcMap& operator=(const CMap& cmap) {

        MapParent::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. This adaptor conforms to the \ref

  /// concepts::Digraph "Digraph" concept. If the \c _checked parameter

  /// is \c true, then the arcs incident to hidden nodes are also

  /// filtered out.

  ///

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

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

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

  ///

  /// \tparam _Digraph 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 _NodeFilterMap A \c bool (or convertible) node map of the

  /// adapted digraph. The default map type is

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

  /// \tparam _ArcFilterMap A \c bool (or convertible) arc map of the

  /// adapted digraph. The default map type is

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

  /// \tparam _checked If this parameter is set to \c false, then the arc

  /// filtering is not checked with respect to the node filter.

  /// Otherwise, each arc that is incident to a hidden node is automatically

  /// filtered out. This is the default option.

  ///

  /// \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 _Digraph,

           typename _NodeFilterMap,

           typename _ArcFilterMap,

           bool _checked>

#else

  template<typename _Digraph,

           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,

           typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,

           bool _checked = true>

#endif

  class SubDigraph

    : public DigraphAdaptorExtender<

      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {

  public:

    /// The type of the adapted digraph.

    typedef _Digraph Digraph;

    /// The type of the node filter map.

    typedef _NodeFilterMap NodeFilterMap;

    /// The type of the arc filter map.

    typedef _ArcFilterMap ArcFilterMap;

    typedef DigraphAdaptorExtender<

      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> >

    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(Digraph& digraph, NodeFilterMap& node_filter,

               ArcFilterMap& arc_filter) {

      setDigraph(digraph);

      setNodeFilterMap(node_filter);

      setArcFilterMap(arc_filter);

    }

    ///

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

    ///

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

    ///

    ///

    ///

    ///

  };

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

  ///

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

  /// \ingroup graph_adaptors

  /// \relates SubDigraph

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

  SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>

  subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {

    return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>

      (digraph, nfm, afm);

  }

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

  SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>

  subDigraph(const Digraph& digraph,

             const NodeFilterMap& nfm, ArcFilterMap& afm) {

    return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>

      (digraph, nfm, afm);

  }

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

  SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>

  subDigraph(const Digraph& digraph,

             NodeFilterMap& nfm, const ArcFilterMap& afm) {

    return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>

      (digraph, nfm, afm);

  }

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

  SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>

  subDigraph(const Digraph& digraph,

             const NodeFilterMap& nfm, const ArcFilterMap& afm) {

    return SubDigraph<const Digraph, const NodeFilterMap,

      const ArcFilterMap>(digraph, nfm, afm);

  }

  template <typename _Graph, typename _NodeFilterMap,

            typename _EdgeFilterMap, bool _checked = true>

  class SubGraphBase : public GraphAdaptorBase<_Graph> {

  public:

    typedef _Graph Graph;

    typedef _NodeFilterMap NodeFilterMap;

    typedef _EdgeFilterMap EdgeFilterMap;

    typedef SubGraphBase Adaptor;

    typedef GraphAdaptorBase<_Graph> Parent;

  protected:

    NodeFilterMap* _node_filter_map;

    EdgeFilterMap* _edge_filter_map;

    SubGraphBase()

      : Parent(), _node_filter_map(0), _edge_filter_map(0) { }

    void setNodeFilterMap(NodeFilterMap& node_filter_map) {

      _node_filter_map=&node_filter_map;

    }

    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {

      _edge_filter_map=&edge_filter_map;

    }

  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_map)[i]) Parent::next(i);

    }

    void first(Arc& i) const {

      Parent::first(i);

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

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

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

        Parent::next(i);

    }

    void first(Edge& i) const {

      Parent::first(i);

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

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

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

        Parent::next(i);

    }

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

      Parent::firstIn(i, n);

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

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

        Parent::nextIn(i);

    }

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

      Parent::firstOut(i, n);

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

                            || !(*_node_filter_map)[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_map)[i]

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

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

        Parent::nextInc(i, d);

    }

    void next(Node& i) const {

      Parent::next(i);

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

    }

    void next(Arc& i) const {

      Parent::next(i);

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

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

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

        Parent::next(i);

    }

    void next(Edge& i) const {

      Parent::next(i);

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

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

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

        Parent::next(i);

    }

    void nextIn(Arc& i) const {

      Parent::nextIn(i);

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

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

        Parent::nextIn(i);

    }

    void nextOut(Arc& i) const {

      Parent::nextOut(i);

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

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

        Parent::nextOut(i);

    }

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

      Parent::nextInc(i, d);

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

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

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

        Parent::nextInc(i, d);

    }

    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_map)[u] || !(*_node_filter_map)[v]) {

        return INVALID;

      }

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

      while (arc != INVALID && !(*_edge_filter_map)[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_map)[u] || !(*_node_filter_map)[v]) {

        return INVALID;

      }

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

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

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

      }

      return edge;

    }

    template <typename _Value>

    class NodeMap : public SubMapExtender<Adaptor,

      typename Parent::template NodeMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template NodeMap<Value> > MapParent;

      NodeMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

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

        : MapParent(adaptor, value) {}

    private:

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

        return *this;

      }

    };

    template <typename _Value>

    class ArcMap : public SubMapExtender<Adaptor,

      typename Parent::template ArcMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template ArcMap<Value> > MapParent;

      ArcMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

      ArcMap(const Adaptor& adaptor, const Value& value)

        : MapParent(adaptor, value) {}

    private:

      ArcMap& operator=(const ArcMap& cmap) {

        return operator=<ArcMap>(cmap);

      }

      template <typename CMap>

      ArcMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

        return *this;

      }

    };