Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Sun, 11 Jan 2009 15:09:53 +0000
changeset 4555a1e9fdcfd3a
parent 445 75a5df083951
parent 454 f599fa651202
child 456 aff6888e71c9
child 463 a2fd8b8d0b30
Merge
doc/groups.dox
lemon/adaptors.h
lemon/bits/graph_adaptor_extender.h
     1.1 --- a/doc/groups.dox	Thu Jan 08 17:19:26 2009 +0000
     1.2 +++ b/doc/groups.dox	Sun Jan 11 15:09:53 2009 +0000
     1.3 @@ -62,18 +62,20 @@
     1.4  */
     1.5  
     1.6  /**
     1.7 -@defgroup graph_adaptors Adaptor Classes for graphs
     1.8 +@defgroup graph_adaptors Adaptor Classes for Graphs
     1.9  @ingroup graphs
    1.10 -\brief This group contains several adaptor classes for digraphs and graphs
    1.11 +\brief Adaptor classes for digraphs and graphs
    1.12 +
    1.13 +This group contains several useful adaptor classes for digraphs and graphs.
    1.14  
    1.15  The main parts of LEMON are the different graph structures, generic
    1.16 -graph algorithms, graph concepts which couple these, and graph
    1.17 +graph algorithms, graph concepts, which couple them, and graph
    1.18  adaptors. While the previous notions are more or less clear, the
    1.19  latter one needs further explanation. Graph adaptors are graph classes
    1.20  which serve for considering graph structures in different ways.
    1.21  
    1.22  A short example makes this much clearer.  Suppose that we have an
    1.23 -instance \c g of a directed graph type say ListDigraph and an algorithm
    1.24 +instance \c g of a directed graph type, say ListDigraph and an algorithm
    1.25  \code
    1.26  template <typename Digraph>
    1.27  int algorithm(const Digraph&);
    1.28 @@ -81,13 +83,13 @@
    1.29  is needed to run on the reverse oriented graph.  It may be expensive
    1.30  (in time or in memory usage) to copy \c g with the reversed
    1.31  arcs.  In this case, an adaptor class is used, which (according
    1.32 -to LEMON digraph concepts) works as a digraph.  The adaptor uses the
    1.33 -original digraph structure and digraph operations when methods of the
    1.34 -reversed oriented graph are called.  This means that the adaptor have
    1.35 -minor memory usage, and do not perform sophisticated algorithmic
    1.36 +to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
    1.37 +The adaptor uses the original digraph structure and digraph operations when
    1.38 +methods of the reversed oriented graph are called.  This means that the adaptor
    1.39 +have minor memory usage, and do not perform sophisticated algorithmic
    1.40  actions.  The purpose of it is to give a tool for the cases when a
    1.41  graph have to be used in a specific alteration.  If this alteration is
    1.42 -obtained by a usual construction like filtering the arc-set or
    1.43 +obtained by a usual construction like filtering the node or the arc set or
    1.44  considering a new orientation, then an adaptor is worthwhile to use.
    1.45  To come back to the reverse oriented graph, in this situation
    1.46  \code
    1.47 @@ -96,39 +98,40 @@
    1.48  template class can be used. The code looks as follows
    1.49  \code
    1.50  ListDigraph g;
    1.51 -ReverseDigraph<ListGraph> rg(g);
    1.52 +ReverseDigraph<ListDigraph> rg(g);
    1.53  int result = algorithm(rg);
    1.54  \endcode
    1.55 -After running the algorithm, the original graph \c g is untouched.
    1.56 -This techniques gives rise to an elegant code, and based on stable
    1.57 +During running the algorithm, the original digraph \c g is untouched.
    1.58 +This techniques give rise to an elegant code, and based on stable
    1.59  graph adaptors, complex algorithms can be implemented easily.
    1.60  
    1.61 -In flow, circulation and bipartite matching problems, the residual
    1.62 +In flow, circulation and matching problems, the residual
    1.63  graph is of particular importance. Combining an adaptor implementing
    1.64 -this, shortest path algorithms and minimum mean cycle algorithms,
    1.65 +this with shortest path algorithms or minimum mean cycle algorithms,
    1.66  a range of weighted and cardinality optimization algorithms can be
    1.67  obtained. For other examples, the interested user is referred to the
    1.68  detailed documentation of particular adaptors.
    1.69  
    1.70  The behavior of graph adaptors can be very different. Some of them keep
    1.71  capabilities of the original graph while in other cases this would be
    1.72 -meaningless. This means that the concepts that they are models of depend
    1.73 -on the graph adaptor, and the wrapped graph(s).
    1.74 -If an arc of \c rg is deleted, this is carried out by deleting the
    1.75 -corresponding arc of \c g, thus the adaptor modifies the original graph.
    1.76 +meaningless. This means that the concepts that they meet depend
    1.77 +on the graph adaptor, and the wrapped graph.
    1.78 +For example, if an arc of a reversed digraph is deleted, this is carried
    1.79 +out by deleting the corresponding arc of the original digraph, thus the
    1.80 +adaptor modifies the original digraph.
    1.81 +However in case of a residual digraph, this operation has no sense.
    1.82  
    1.83 -But for a residual graph, this operation has no sense.
    1.84  Let us stand one more example here to simplify your work.
    1.85 -RevGraphAdaptor has constructor
    1.86 +ReverseDigraph has constructor
    1.87  \code
    1.88  ReverseDigraph(Digraph& digraph);
    1.89  \endcode
    1.90 -This means that in a situation, when a <tt>const ListDigraph&</tt>
    1.91 +This means that in a situation, when a <tt>const %ListDigraph&</tt>
    1.92  reference to a graph is given, then it have to be instantiated with
    1.93 -<tt>Digraph=const ListDigraph</tt>.
    1.94 +<tt>Digraph=const %ListDigraph</tt>.
    1.95  \code
    1.96  int algorithm1(const ListDigraph& g) {
    1.97 -  RevGraphAdaptor<const ListDigraph> rg(g);
    1.98 +  ReverseDigraph<const ListDigraph> rg(g);
    1.99    return algorithm2(rg);
   1.100  }
   1.101  \endcode
     2.1 --- a/lemon/adaptors.h	Thu Jan 08 17:19:26 2009 +0000
     2.2 +++ b/lemon/adaptors.h	Sun Jan 11 15:09:53 2009 +0000
     2.3 @@ -21,7 +21,7 @@
     2.4  
     2.5  /// \ingroup graph_adaptors
     2.6  /// \file
     2.7 -/// \brief Several graph adaptors
     2.8 +/// \brief Adaptor classes for digraphs and graphs
     2.9  ///
    2.10  /// This file contains several useful adaptors for digraphs and graphs.
    2.11  
    2.12 @@ -70,21 +70,21 @@
    2.13      typedef NodeNumTagIndicator<Digraph> NodeNumTag;
    2.14      int nodeNum() const { return _digraph->nodeNum(); }
    2.15  
    2.16 -    typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
    2.17 +    typedef ArcNumTagIndicator<Digraph> ArcNumTag;
    2.18      int arcNum() const { return _digraph->arcNum(); }
    2.19  
    2.20 -    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
    2.21 -    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
    2.22 +    typedef FindArcTagIndicator<Digraph> FindArcTag;
    2.23 +    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {
    2.24        return _digraph->findArc(u, v, prev);
    2.25      }
    2.26  
    2.27      Node addNode() { return _digraph->addNode(); }
    2.28      Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
    2.29  
    2.30 -    void erase(const Node& n) const { _digraph->erase(n); }
    2.31 -    void erase(const Arc& a) const { _digraph->erase(a); }
    2.32 -
    2.33 -    void clear() const { _digraph->clear(); }
    2.34 +    void erase(const Node& n) { _digraph->erase(n); }
    2.35 +    void erase(const Arc& a) { _digraph->erase(a); }
    2.36 +
    2.37 +    void clear() { _digraph->clear(); }
    2.38  
    2.39      int id(const Node& n) const { return _digraph->id(n); }
    2.40      int id(const Arc& a) const { return _digraph->id(a); }
    2.41 @@ -198,15 +198,21 @@
    2.42      typedef NodeNumTagIndicator<Graph> NodeNumTag;
    2.43      int nodeNum() const { return _graph->nodeNum(); }
    2.44  
    2.45 +    typedef ArcNumTagIndicator<Graph> ArcNumTag;
    2.46 +    int arcNum() const { return _graph->arcNum(); }
    2.47 +
    2.48      typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
    2.49 -    int arcNum() const { return _graph->arcNum(); }
    2.50      int edgeNum() const { return _graph->edgeNum(); }
    2.51  
    2.52 -    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
    2.53 -    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
    2.54 +    typedef FindArcTagIndicator<Graph> FindArcTag;
    2.55 +    Arc findArc(const Node& u, const Node& v,
    2.56 +                const Arc& prev = INVALID) const {
    2.57        return _graph->findArc(u, v, prev);
    2.58      }
    2.59 -    Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
    2.60 +
    2.61 +    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
    2.62 +    Edge findEdge(const Node& u, const Node& v,
    2.63 +                  const Edge& prev = INVALID) const {
    2.64        return _graph->findEdge(u, v, prev);
    2.65      }
    2.66  
    2.67 @@ -330,9 +336,9 @@
    2.68  
    2.69      Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
    2.70  
    2.71 -    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
    2.72 +    typedef FindArcTagIndicator<Digraph> FindArcTag;
    2.73      Arc findArc(const Node& u, const Node& v,
    2.74 -                const Arc& prev = INVALID) {
    2.75 +                const Arc& prev = INVALID) const {
    2.76        return Parent::findArc(v, u, prev);
    2.77      }
    2.78  
    2.79 @@ -340,41 +346,56 @@
    2.80  
    2.81    /// \ingroup graph_adaptors
    2.82    ///
    2.83 -  /// \brief A digraph adaptor which reverses the orientation of the arcs.
    2.84 +  /// \brief Adaptor class for reversing the orientation of the arcs in
    2.85 +  /// a digraph.
    2.86    ///
    2.87 -  /// ReverseDigraph reverses the arcs in the adapted digraph. The
    2.88 -  /// SubDigraph is conform to the \ref concepts::Digraph
    2.89 -  /// "Digraph concept".
    2.90 +  /// ReverseDigraph can be used for reversing the arcs in a digraph.
    2.91 +  /// It conforms to the \ref concepts::Digraph "Digraph" concept.
    2.92    ///
    2.93 -  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
    2.94 -  /// "Digraph concept". The type can be specified to be const.
    2.95 -  template<typename _Digraph>
    2.96 +  /// The adapted digraph can also be modified through this adaptor
    2.97 +  /// by adding or removing nodes or arcs, unless the \c GR template
    2.98 +  /// parameter is set to be \c const.
    2.99 +  ///
   2.100 +  /// \tparam GR The type of the adapted digraph.
   2.101 +  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
   2.102 +  /// It can also be specified to be \c const.
   2.103 +  ///
   2.104 +  /// \note The \c Node and \c Arc types of this adaptor and the adapted
   2.105 +  /// digraph are convertible to each other.
   2.106 +  template<typename GR>
   2.107 +#ifdef DOXYGEN
   2.108 +  class ReverseDigraph {
   2.109 +#else
   2.110    class ReverseDigraph :
   2.111 -    public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
   2.112 +    public DigraphAdaptorExtender<ReverseDigraphBase<GR> > {
   2.113 +#endif
   2.114    public:
   2.115 -    typedef _Digraph Digraph;
   2.116 -    typedef DigraphAdaptorExtender<
   2.117 -      ReverseDigraphBase<_Digraph> > Parent;
   2.118 +    /// The type of the adapted digraph.
   2.119 +    typedef GR Digraph;
   2.120 +    typedef DigraphAdaptorExtender<ReverseDigraphBase<GR> > Parent;
   2.121    protected:
   2.122      ReverseDigraph() { }
   2.123    public:
   2.124  
   2.125      /// \brief Constructor
   2.126      ///
   2.127 -    /// Creates a reverse digraph adaptor for the given digraph
   2.128 +    /// Creates a reverse digraph adaptor for the given digraph.
   2.129      explicit ReverseDigraph(Digraph& digraph) {
   2.130        Parent::setDigraph(digraph);
   2.131      }
   2.132    };
   2.133  
   2.134 -  /// \brief Just gives back a reverse digraph adaptor
   2.135 +  /// \brief Returns a read-only ReverseDigraph adaptor
   2.136    ///
   2.137 -  /// Just gives back a reverse digraph adaptor
   2.138 -  template<typename Digraph>
   2.139 -  ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
   2.140 -    return ReverseDigraph<const Digraph>(digraph);
   2.141 +  /// This function just returns a read-only \ref ReverseDigraph adaptor.
   2.142 +  /// \ingroup graph_adaptors
   2.143 +  /// \relates ReverseDigraph
   2.144 +  template<typename GR>
   2.145 +  ReverseDigraph<const GR> reverseDigraph(const GR& digraph) {
   2.146 +    return ReverseDigraph<const GR>(digraph);
   2.147    }
   2.148  
   2.149 +
   2.150    template <typename _Digraph, typename _NodeFilterMap,
   2.151              typename _ArcFilterMap, bool _checked = true>
   2.152    class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
   2.153 @@ -457,21 +478,18 @@
   2.154          Parent::nextOut(i);
   2.155      }
   2.156  
   2.157 -    void hide(const Node& n) const { _node_filter->set(n, false); }
   2.158 -    void hide(const Arc& a) const { _arc_filter->set(a, false); }
   2.159 -
   2.160 -    void unHide(const Node& n) const { _node_filter->set(n, true); }
   2.161 -    void unHide(const Arc& a) const { _arc_filter->set(a, true); }
   2.162 -
   2.163 -    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
   2.164 -    bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
   2.165 +    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
   2.166 +    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
   2.167 +
   2.168 +    bool status(const Node& n) const { return (*_node_filter)[n]; }
   2.169 +    bool status(const Arc& a) const { return (*_arc_filter)[a]; }
   2.170  
   2.171      typedef False NodeNumTag;
   2.172 -    typedef False EdgeNumTag;
   2.173 -
   2.174 -    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
   2.175 +    typedef False ArcNumTag;
   2.176 +
   2.177 +    typedef FindArcTagIndicator<Digraph> FindArcTag;
   2.178      Arc findArc(const Node& source, const Node& target,
   2.179 -                const Arc& prev = INVALID) {
   2.180 +                const Arc& prev = INVALID) const {
   2.181        if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
   2.182          return INVALID;
   2.183        }
   2.184 @@ -600,21 +618,18 @@
   2.185        while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
   2.186      }
   2.187  
   2.188 -    void hide(const Node& n) const { _node_filter->set(n, false); }
   2.189 -    void hide(const Arc& e) const { _arc_filter->set(e, false); }
   2.190 -
   2.191 -    void unHide(const Node& n) const { _node_filter->set(n, true); }
   2.192 -    void unHide(const Arc& e) const { _arc_filter->set(e, true); }
   2.193 -
   2.194 -    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
   2.195 -    bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
   2.196 +    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
   2.197 +    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
   2.198 +
   2.199 +    bool status(const Node& n) const { return (*_node_filter)[n]; }
   2.200 +    bool status(const Arc& a) const { return (*_arc_filter)[a]; }
   2.201  
   2.202      typedef False NodeNumTag;
   2.203 -    typedef False EdgeNumTag;
   2.204 -
   2.205 -    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
   2.206 +    typedef False ArcNumTag;
   2.207 +
   2.208 +    typedef FindArcTagIndicator<Digraph> FindArcTag;
   2.209      Arc findArc(const Node& source, const Node& target,
   2.210 -                const Arc& prev = INVALID) {
   2.211 +                const Arc& prev = INVALID) const {
   2.212        if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
   2.213          return INVALID;
   2.214        }
   2.215 @@ -679,42 +694,57 @@
   2.216  
   2.217    /// \ingroup graph_adaptors
   2.218    ///
   2.219 -  /// \brief An adaptor for hiding nodes and arcs in a digraph
   2.220 +  /// \brief Adaptor class for hiding nodes and arcs in a digraph
   2.221    ///
   2.222 -  /// SubDigraph hides nodes and arcs in a digraph. A bool node map
   2.223 -  /// and a bool arc map must be specified, which define the filters
   2.224 -  /// for nodes and arcs. Just the nodes and arcs with true value are
   2.225 -  /// shown in the subdigraph. The SubDigraph is conform to the \ref
   2.226 -  /// concepts::Digraph "Digraph concept". If the \c _checked parameter
   2.227 -  /// is true, then the arcs incident to filtered nodes are also
   2.228 -  /// filtered out.
   2.229 +  /// SubDigraph can be used for hiding nodes and arcs in a digraph.
   2.230 +  /// A \c bool node map and a \c bool arc map must be specified, which
   2.231 +  /// define the filters for nodes and arcs.
   2.232 +  /// Only the nodes and arcs with \c true filter value are
   2.233 +  /// shown in the subdigraph. The arcs that are incident to hidden
   2.234 +  /// nodes are also filtered out.
   2.235 +  /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept.
   2.236    ///
   2.237 -  /// \tparam _Digraph It must be conform to the \ref
   2.238 -  /// concepts::Digraph "Digraph concept". The type can be specified
   2.239 -  /// to const.
   2.240 -  /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph.
   2.241 -  /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph.
   2.242 -  /// \tparam _checked If the parameter is false then the arc filtering
   2.243 -  /// is not checked with respect to node filter. Otherwise, each arc
   2.244 -  /// is automatically filtered, which is incident to a filtered node.
   2.245 +  /// The adapted digraph can also be modified through this adaptor
   2.246 +  /// by adding or removing nodes or arcs, unless the \c GR template
   2.247 +  /// parameter is set to be \c const.
   2.248 +  ///
   2.249 +  /// \tparam GR The type of the adapted digraph.
   2.250 +  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
   2.251 +  /// It can also be specified to be \c const.
   2.252 +  /// \tparam NF The type of the node filter map.
   2.253 +  /// It must be a \c bool (or convertible) node map of the
   2.254 +  /// adapted digraph. The default type is
   2.255 +  /// \ref concepts::Digraph::NodeMap "GR::NodeMap<bool>".
   2.256 +  /// \tparam AF The type of the arc filter map.
   2.257 +  /// It must be \c bool (or convertible) arc map of the
   2.258 +  /// adapted digraph. The default type is
   2.259 +  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>".
   2.260 +  ///
   2.261 +  /// \note The \c Node and \c Arc types of this adaptor and the adapted
   2.262 +  /// digraph are convertible to each other.
   2.263    ///
   2.264    /// \see FilterNodes
   2.265    /// \see FilterArcs
   2.266 -  template<typename _Digraph,
   2.267 -           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
   2.268 -           typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
   2.269 -           bool _checked = true>
   2.270 -  class SubDigraph
   2.271 -    : public DigraphAdaptorExtender<
   2.272 -      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
   2.273 +#ifdef DOXYGEN
   2.274 +  template<typename GR, typename NF, typename AF>
   2.275 +  class SubDigraph {
   2.276 +#else
   2.277 +  template<typename GR,
   2.278 +           typename NF = typename GR::template NodeMap<bool>,
   2.279 +           typename AF = typename GR::template ArcMap<bool> >
   2.280 +  class SubDigraph :
   2.281 +    public DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> > {
   2.282 +#endif
   2.283    public:
   2.284 -    typedef _Digraph Digraph;
   2.285 -    typedef _NodeFilterMap NodeFilterMap;
   2.286 -    typedef _ArcFilterMap ArcFilterMap;
   2.287 -
   2.288 -    typedef DigraphAdaptorExtender<
   2.289 -      SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >
   2.290 -    Parent;
   2.291 +    /// The type of the adapted digraph.
   2.292 +    typedef GR Digraph;
   2.293 +    /// The type of the node filter map.
   2.294 +    typedef NF NodeFilterMap;
   2.295 +    /// The type of the arc filter map.
   2.296 +    typedef AF ArcFilterMap;
   2.297 +
   2.298 +    typedef DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> >
   2.299 +      Parent;
   2.300  
   2.301      typedef typename Parent::Node Node;
   2.302      typedef typename Parent::Arc Arc;
   2.303 @@ -725,8 +755,8 @@
   2.304  
   2.305      /// \brief Constructor
   2.306      ///
   2.307 -    /// Creates a subdigraph for the given digraph with
   2.308 -    /// given node and arc map filters.
   2.309 +    /// Creates a subdigraph for the given digraph with the
   2.310 +    /// given node and arc filter maps.
   2.311      SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
   2.312                 ArcFilterMap& arc_filter) {
   2.313        setDigraph(digraph);
   2.314 @@ -734,88 +764,106 @@
   2.315        setArcFilterMap(arc_filter);
   2.316      }
   2.317  
   2.318 -    /// \brief Hides the node of the graph
   2.319 +    /// \brief Sets the status of the given node
   2.320      ///
   2.321 -    /// This function hides \c n in the digraph, i.e. the iteration
   2.322 -    /// jumps over it. This is done by simply setting the value of \c n
   2.323 -    /// to be false in the corresponding node-map.
   2.324 -    void hide(const Node& n) const { Parent::hide(n); }
   2.325 -
   2.326 -    /// \brief Hides the arc of the graph
   2.327 +    /// This function sets the status of the given node.
   2.328 +    /// It is done by simply setting the assigned value of \c n
   2.329 +    /// to \c v in the node filter map.
   2.330 +    void status(const Node& n, bool v) const { Parent::status(n, v); }
   2.331 +
   2.332 +    /// \brief Sets the status of the given arc
   2.333      ///
   2.334 -    /// This function hides \c a in the digraph, i.e. the iteration
   2.335 -    /// jumps over it. This is done by simply setting the value of \c a
   2.336 -    /// to be false in the corresponding arc-map.
   2.337 -    void hide(const Arc& a) const { Parent::hide(a); }
   2.338 -
   2.339 -    /// \brief Unhides the node of the graph
   2.340 +    /// This function sets the status of the given arc.
   2.341 +    /// It is done by simply setting the assigned value of \c a
   2.342 +    /// to \c v in the arc filter map.
   2.343 +    void status(const Arc& a, bool v) const { Parent::status(a, v); }
   2.344 +
   2.345 +    /// \brief Returns the status of the given node
   2.346      ///
   2.347 -    /// The value of \c n is set to be true in the node-map which stores
   2.348 -    /// hide information. If \c n was hidden previuosly, then it is shown
   2.349 -    /// again
   2.350 -    void unHide(const Node& n) const { Parent::unHide(n); }
   2.351 -
   2.352 -    /// \brief Unhides the arc of the graph
   2.353 +    /// This function returns the status of the given node.
   2.354 +    /// It is \c true if the given node is enabled (i.e. not hidden).
   2.355 +    bool status(const Node& n) const { return Parent::status(n); }
   2.356 +
   2.357 +    /// \brief Returns the status of the given arc
   2.358      ///
   2.359 -    /// The value of \c a is set to be true in the arc-map which stores
   2.360 -    /// hide information. If \c a was hidden previuosly, then it is shown
   2.361 -    /// again
   2.362 -    void unHide(const Arc& a) const { Parent::unHide(a); }
   2.363 -
   2.364 -    /// \brief Returns true if \c n is hidden.
   2.365 +    /// This function returns the status of the given arc.
   2.366 +    /// It is \c true if the given arc is enabled (i.e. not hidden).
   2.367 +    bool status(const Arc& a) const { return Parent::status(a); }
   2.368 +
   2.369 +    /// \brief Disables the given node
   2.370      ///
   2.371 -    /// Returns true if \c n is hidden.
   2.372 +    /// This function disables the given node in the subdigraph,
   2.373 +    /// so the iteration jumps over it.
   2.374 +    /// It is the same as \ref status() "status(n, false)".
   2.375 +    void disable(const Node& n) const { Parent::status(n, false); }
   2.376 +
   2.377 +    /// \brief Disables the given arc
   2.378      ///
   2.379 -    bool hidden(const Node& n) const { return Parent::hidden(n); }
   2.380 -
   2.381 -    /// \brief Returns true if \c a is hidden.
   2.382 +    /// This function disables the given arc in the subdigraph,
   2.383 +    /// so the iteration jumps over it.
   2.384 +    /// It is the same as \ref status() "status(a, false)".
   2.385 +    void disable(const Arc& a) const { Parent::status(a, false); }
   2.386 +
   2.387 +    /// \brief Enables the given node
   2.388      ///
   2.389 -    /// Returns true if \c a is hidden.
   2.390 +    /// This function enables the given node in the subdigraph.
   2.391 +    /// It is the same as \ref status() "status(n, true)".
   2.392 +    void enable(const Node& n) const { Parent::status(n, true); }
   2.393 +
   2.394 +    /// \brief Enables the given arc
   2.395      ///
   2.396 -    bool hidden(const Arc& a) const { return Parent::hidden(a); }
   2.397 +    /// This function enables the given arc in the subdigraph.
   2.398 +    /// It is the same as \ref status() "status(a, true)".
   2.399 +    void enable(const Arc& a) const { Parent::status(a, true); }
   2.400  
   2.401    };
   2.402  
   2.403 -  /// \brief Just gives back a subdigraph
   2.404 +  /// \brief Returns a read-only SubDigraph adaptor
   2.405    ///
   2.406 -  /// Just gives back a subdigraph
   2.407 -  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
   2.408 -  SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
   2.409 -  subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
   2.410 -    return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
   2.411 -      (digraph, nfm, afm);
   2.412 +  /// This function just returns a read-only \ref SubDigraph adaptor.
   2.413 +  /// \ingroup graph_adaptors
   2.414 +  /// \relates SubDigraph
   2.415 +  template<typename GR, typename NF, typename AF>
   2.416 +  SubDigraph<const GR, NF, AF>
   2.417 +  subDigraph(const GR& digraph,
   2.418 +             NF& node_filter_map, AF& arc_filter_map) {
   2.419 +    return SubDigraph<const GR, NF, AF>
   2.420 +      (digraph, node_filter_map, arc_filter_map);
   2.421    }
   2.422  
   2.423 -  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
   2.424 -  SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
   2.425 -  subDigraph(const Digraph& digraph,
   2.426 -             const NodeFilterMap& nfm, ArcFilterMap& afm) {
   2.427 -    return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
   2.428 -      (digraph, nfm, afm);
   2.429 +  template<typename GR, typename NF, typename AF>
   2.430 +  SubDigraph<const GR, const NF, AF>
   2.431 +  subDigraph(const GR& digraph,
   2.432 +             const NF& node_filter_map, AF& arc_filter_map) {
   2.433 +    return SubDigraph<const GR, const NF, AF>
   2.434 +      (digraph, node_filter_map, arc_filter_map);
   2.435    }
   2.436  
   2.437 -  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
   2.438 -  SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
   2.439 -  subDigraph(const Digraph& digraph,
   2.440 -             NodeFilterMap& nfm, const ArcFilterMap& afm) {
   2.441 -    return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
   2.442 -      (digraph, nfm, afm);
   2.443 +  template<typename GR, typename NF, typename AF>
   2.444 +  SubDigraph<const GR, NF, const AF>
   2.445 +  subDigraph(const GR& digraph,
   2.446 +             NF& node_filter_map, const AF& arc_filter_map) {
   2.447 +    return SubDigraph<const GR, NF, const AF>
   2.448 +      (digraph, node_filter_map, arc_filter_map);
   2.449    }
   2.450  
   2.451 -  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
   2.452 -  SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>
   2.453 -  subDigraph(const Digraph& digraph,
   2.454 -             const NodeFilterMap& nfm, const ArcFilterMap& afm) {
   2.455 -    return SubDigraph<const Digraph, const NodeFilterMap,
   2.456 -      const ArcFilterMap>(digraph, nfm, afm);
   2.457 +  template<typename GR, typename NF, typename AF>
   2.458 +  SubDigraph<const GR, const NF, const AF>
   2.459 +  subDigraph(const GR& digraph,
   2.460 +             const NF& node_filter_map, const AF& arc_filter_map) {
   2.461 +    return SubDigraph<const GR, const NF, const AF>
   2.462 +      (digraph, node_filter_map, arc_filter_map);
   2.463    }
   2.464  
   2.465  
   2.466 -  template <typename _Graph, typename NodeFilterMap,
   2.467 -            typename EdgeFilterMap, bool _checked = true>
   2.468 +  template <typename _Graph, typename _NodeFilterMap,
   2.469 +            typename _EdgeFilterMap, bool _checked = true>
   2.470    class SubGraphBase : public GraphAdaptorBase<_Graph> {
   2.471    public:
   2.472      typedef _Graph Graph;
   2.473 +    typedef _NodeFilterMap NodeFilterMap;
   2.474 +    typedef _EdgeFilterMap EdgeFilterMap;
   2.475 +
   2.476      typedef SubGraphBase Adaptor;
   2.477      typedef GraphAdaptorBase<_Graph> Parent;
   2.478    protected:
   2.479 @@ -925,21 +973,19 @@
   2.480          Parent::nextInc(i, d);
   2.481      }
   2.482  
   2.483 -    void hide(const Node& n) const { _node_filter_map->set(n, false); }
   2.484 -    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
   2.485 -
   2.486 -    void unHide(const Node& n) const { _node_filter_map->set(n, true); }
   2.487 -    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
   2.488 -
   2.489 -    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
   2.490 -    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
   2.491 +    void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
   2.492 +    void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
   2.493 +
   2.494 +    bool status(const Node& n) const { return (*_node_filter_map)[n]; }
   2.495 +    bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
   2.496  
   2.497      typedef False NodeNumTag;
   2.498 +    typedef False ArcNumTag;
   2.499      typedef False EdgeNumTag;
   2.500  
   2.501 -    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
   2.502 +    typedef FindArcTagIndicator<Graph> FindArcTag;
   2.503      Arc findArc(const Node& u, const Node& v,
   2.504 -                const Arc& prev = INVALID) {
   2.505 +                const Arc& prev = INVALID) const {
   2.506        if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
   2.507          return INVALID;
   2.508        }
   2.509 @@ -949,8 +995,10 @@
   2.510        }
   2.511        return arc;
   2.512      }
   2.513 +
   2.514 +    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
   2.515      Edge findEdge(const Node& u, const Node& v,
   2.516 -                  const Edge& prev = INVALID) {
   2.517 +                  const Edge& prev = INVALID) const {
   2.518        if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
   2.519          return INVALID;
   2.520        }
   2.521 @@ -1039,11 +1087,14 @@
   2.522  
   2.523    };
   2.524  
   2.525 -  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
   2.526 -  class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
   2.527 +  template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>
   2.528 +  class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false>
   2.529      : public GraphAdaptorBase<_Graph> {
   2.530    public:
   2.531      typedef _Graph Graph;
   2.532 +    typedef _NodeFilterMap NodeFilterMap;
   2.533 +    typedef _EdgeFilterMap EdgeFilterMap;
   2.534 +
   2.535      typedef SubGraphBase Adaptor;
   2.536      typedef GraphAdaptorBase<_Graph> Parent;
   2.537    protected:
   2.538 @@ -1121,29 +1172,29 @@
   2.539        while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
   2.540      }
   2.541  
   2.542 -    void hide(const Node& n) const { _node_filter_map->set(n, false); }
   2.543 -    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
   2.544 -
   2.545 -    void unHide(const Node& n) const { _node_filter_map->set(n, true); }
   2.546 -    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
   2.547 -
   2.548 -    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
   2.549 -    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
   2.550 +    void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
   2.551 +    void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
   2.552 +
   2.553 +    bool status(const Node& n) const { return (*_node_filter_map)[n]; }
   2.554 +    bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
   2.555  
   2.556      typedef False NodeNumTag;
   2.557 +    typedef False ArcNumTag;
   2.558      typedef False EdgeNumTag;
   2.559  
   2.560 -    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
   2.561 +    typedef FindArcTagIndicator<Graph> FindArcTag;
   2.562      Arc findArc(const Node& u, const Node& v,
   2.563 -                const Arc& prev = INVALID) {
   2.564 +                const Arc& prev = INVALID) const {
   2.565        Arc arc = Parent::findArc(u, v, prev);
   2.566        while (arc != INVALID && !(*_edge_filter_map)[arc]) {
   2.567          arc = Parent::findArc(u, v, arc);
   2.568        }
   2.569        return arc;
   2.570      }
   2.571 +
   2.572 +    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
   2.573      Edge findEdge(const Node& u, const Node& v,
   2.574 -                  const Edge& prev = INVALID) {
   2.575 +                  const Edge& prev = INVALID) const {
   2.576        Edge edge = Parent::findEdge(u, v, prev);
   2.577        while (edge != INVALID && !(*_edge_filter_map)[edge]) {
   2.578          edge = Parent::findEdge(u, v, edge);
   2.579 @@ -1231,37 +1282,58 @@
   2.580  
   2.581    /// \ingroup graph_adaptors
   2.582    ///
   2.583 -  /// \brief A graph adaptor for hiding nodes and edges in an
   2.584 -  /// undirected graph.
   2.585 +  /// \brief Adaptor class for hiding nodes and edges in an undirected
   2.586 +  /// graph.
   2.587    ///
   2.588 -  /// SubGraph hides nodes and edges in a graph. A bool node map and a
   2.589 -  /// bool edge map must be specified, which define the filters for
   2.590 -  /// nodes and edges. Just the nodes and edges with true value are
   2.591 -  /// shown in the subgraph. The SubGraph is conform to the \ref
   2.592 -  /// concepts::Graph "Graph concept". If the \c _checked parameter is
   2.593 -  /// true, then the edges incident to filtered nodes are also
   2.594 -  /// filtered out.
   2.595 +  /// SubGraph can be used for hiding nodes and edges in a graph.
   2.596 +  /// A \c bool node map and a \c bool edge map must be specified, which
   2.597 +  /// define the filters for nodes and edges.
   2.598 +  /// Only the nodes and edges with \c true filter value are
   2.599 +  /// shown in the subgraph. The edges that are incident to hidden
   2.600 +  /// nodes are also filtered out.
   2.601 +  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
   2.602    ///
   2.603 -  /// \tparam _Graph It must be conform to the \ref
   2.604 -  /// concepts::Graph "Graph concept". The type can be specified
   2.605 -  /// to const.
   2.606 -  /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
   2.607 -  /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph.
   2.608 -  /// \tparam _checked If the parameter is false then the edge filtering
   2.609 -  /// is not checked with respect to node filter. Otherwise, each edge
   2.610 -  /// is automatically filtered, which is incident to a filtered node.
   2.611 +  /// The adapted graph can also be modified through this adaptor
   2.612 +  /// by adding or removing nodes or edges, unless the \c GR template
   2.613 +  /// parameter is set to be \c const.
   2.614 +  ///
   2.615 +  /// \tparam GR The type of the adapted graph.
   2.616 +  /// It must conform to the \ref concepts::Graph "Graph" concept.
   2.617 +  /// It can also be specified to be \c const.
   2.618 +  /// \tparam NF The type of the node filter map.
   2.619 +  /// It must be a \c bool (or convertible) node map of the
   2.620 +  /// adapted graph. The default type is
   2.621 +  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
   2.622 +  /// \tparam EF The type of the edge filter map.
   2.623 +  /// It must be a \c bool (or convertible) edge map of the
   2.624 +  /// adapted graph. The default type is
   2.625 +  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
   2.626 +  ///
   2.627 +  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
   2.628 +  /// adapted graph are convertible to each other.
   2.629    ///
   2.630    /// \see FilterNodes
   2.631    /// \see FilterEdges
   2.632 -  template<typename _Graph, typename NodeFilterMap,
   2.633 -           typename EdgeFilterMap, bool _checked = true>
   2.634 -  class SubGraph
   2.635 -    : public GraphAdaptorExtender<
   2.636 -      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {
   2.637 +#ifdef DOXYGEN
   2.638 +  template<typename GR, typename NF, typename EF>
   2.639 +  class SubGraph {
   2.640 +#else
   2.641 +  template<typename GR,
   2.642 +           typename NF = typename GR::template NodeMap<bool>,
   2.643 +           typename EF = typename GR::template EdgeMap<bool> >
   2.644 +  class SubGraph :
   2.645 +    public GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> > {
   2.646 +#endif
   2.647    public:
   2.648 -    typedef _Graph Graph;
   2.649 -    typedef GraphAdaptorExtender<
   2.650 -      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
   2.651 +    /// The type of the adapted graph.
   2.652 +    typedef GR Graph;
   2.653 +    /// The type of the node filter map.
   2.654 +    typedef NF NodeFilterMap;
   2.655 +    /// The type of the edge filter map.
   2.656 +    typedef EF EdgeFilterMap;
   2.657 +
   2.658 +    typedef GraphAdaptorExtender< SubGraphBase<GR, NF, EF, true> >
   2.659 +      Parent;
   2.660  
   2.661      typedef typename Parent::Node Node;
   2.662      typedef typename Parent::Edge Edge;
   2.663 @@ -1272,132 +1344,153 @@
   2.664  
   2.665      /// \brief Constructor
   2.666      ///
   2.667 -    /// Creates a subgraph for the given graph with given node and
   2.668 -    /// edge map filters.
   2.669 -    SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,
   2.670 +    /// Creates a subgraph for the given graph with the given node
   2.671 +    /// and edge filter maps.
   2.672 +    SubGraph(Graph& graph, NodeFilterMap& node_filter_map,
   2.673               EdgeFilterMap& edge_filter_map) {
   2.674 -      setGraph(_graph);
   2.675 +      setGraph(graph);
   2.676        setNodeFilterMap(node_filter_map);
   2.677        setEdgeFilterMap(edge_filter_map);
   2.678      }
   2.679  
   2.680 -    /// \brief Hides the node of the graph
   2.681 +    /// \brief Sets the status of the given node
   2.682      ///
   2.683 -    /// This function hides \c n in the graph, i.e. the iteration
   2.684 -    /// jumps over it. This is done by simply setting the value of \c n
   2.685 -    /// to be false in the corresponding node-map.
   2.686 -    void hide(const Node& n) const { Parent::hide(n); }
   2.687 -
   2.688 -    /// \brief Hides the edge of the graph
   2.689 +    /// This function sets the status of the given node.
   2.690 +    /// It is done by simply setting the assigned value of \c n
   2.691 +    /// to \c v in the node filter map.
   2.692 +    void status(const Node& n, bool v) const { Parent::status(n, v); }
   2.693 +
   2.694 +    /// \brief Sets the status of the given edge
   2.695      ///
   2.696 -    /// This function hides \c e in the graph, i.e. the iteration
   2.697 -    /// jumps over it. This is done by simply setting the value of \c e
   2.698 -    /// to be false in the corresponding edge-map.
   2.699 -    void hide(const Edge& e) const { Parent::hide(e); }
   2.700 -
   2.701 -    /// \brief Unhides the node of the graph
   2.702 +    /// This function sets the status of the given edge.
   2.703 +    /// It is done by simply setting the assigned value of \c e
   2.704 +    /// to \c v in the edge filter map.
   2.705 +    void status(const Edge& e, bool v) const { Parent::status(e, v); }
   2.706 +
   2.707 +    /// \brief Returns the status of the given node
   2.708      ///
   2.709 -    /// The value of \c n is set to be true in the node-map which stores
   2.710 -    /// hide information. If \c n was hidden previuosly, then it is shown
   2.711 -    /// again
   2.712 -    void unHide(const Node& n) const { Parent::unHide(n); }
   2.713 -
   2.714 -    /// \brief Unhides the edge of the graph
   2.715 +    /// This function returns the status of the given node.
   2.716 +    /// It is \c true if the given node is enabled (i.e. not hidden).
   2.717 +    bool status(const Node& n) const { return Parent::status(n); }
   2.718 +
   2.719 +    /// \brief Returns the status of the given edge
   2.720      ///
   2.721 -    /// The value of \c e is set to be true in the edge-map which stores
   2.722 -    /// hide information. If \c e was hidden previuosly, then it is shown
   2.723 -    /// again
   2.724 -    void unHide(const Edge& e) const { Parent::unHide(e); }
   2.725 -
   2.726 -    /// \brief Returns true if \c n is hidden.
   2.727 +    /// This function returns the status of the given edge.
   2.728 +    /// It is \c true if the given edge is enabled (i.e. not hidden).
   2.729 +    bool status(const Edge& e) const { return Parent::status(e); }
   2.730 +
   2.731 +    /// \brief Disables the given node
   2.732      ///
   2.733 -    /// Returns true if \c n is hidden.
   2.734 +    /// This function disables the given node in the subdigraph,
   2.735 +    /// so the iteration jumps over it.
   2.736 +    /// It is the same as \ref status() "status(n, false)".
   2.737 +    void disable(const Node& n) const { Parent::status(n, false); }
   2.738 +
   2.739 +    /// \brief Disables the given edge
   2.740      ///
   2.741 -    bool hidden(const Node& n) const { return Parent::hidden(n); }
   2.742 -
   2.743 -    /// \brief Returns true if \c e is hidden.
   2.744 +    /// This function disables the given edge in the subgraph,
   2.745 +    /// so the iteration jumps over it.
   2.746 +    /// It is the same as \ref status() "status(e, false)".
   2.747 +    void disable(const Edge& e) const { Parent::status(e, false); }
   2.748 +
   2.749 +    /// \brief Enables the given node
   2.750      ///
   2.751 -    /// Returns true if \c e is hidden.
   2.752 +    /// This function enables the given node in the subdigraph.
   2.753 +    /// It is the same as \ref status() "status(n, true)".
   2.754 +    void enable(const Node& n) const { Parent::status(n, true); }
   2.755 +
   2.756 +    /// \brief Enables the given edge
   2.757      ///
   2.758 -    bool hidden(const Edge& e) const { return Parent::hidden(e); }
   2.759 +    /// This function enables the given edge in the subgraph.
   2.760 +    /// It is the same as \ref status() "status(e, true)".
   2.761 +    void enable(const Edge& e) const { Parent::status(e, true); }
   2.762 +
   2.763    };
   2.764  
   2.765 -  /// \brief Just gives back a subgraph
   2.766 +  /// \brief Returns a read-only SubGraph adaptor
   2.767    ///
   2.768 -  /// Just gives back a subgraph
   2.769 -  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
   2.770 -  SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
   2.771 -  subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
   2.772 -    return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);
   2.773 +  /// This function just returns a read-only \ref SubGraph adaptor.
   2.774 +  /// \ingroup graph_adaptors
   2.775 +  /// \relates SubGraph
   2.776 +  template<typename GR, typename NF, typename EF>
   2.777 +  SubGraph<const GR, NF, EF>
   2.778 +  subGraph(const GR& graph,
   2.779 +           NF& node_filter_map, EF& edge_filter_map) {
   2.780 +    return SubGraph<const GR, NF, EF>
   2.781 +      (graph, node_filter_map, edge_filter_map);
   2.782    }
   2.783  
   2.784 -  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
   2.785 -  SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
   2.786 -  subGraph(const Graph& graph,
   2.787 -           const NodeFilterMap& nfm, ArcFilterMap& efm) {
   2.788 -    return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
   2.789 -      (graph, nfm, efm);
   2.790 +  template<typename GR, typename NF, typename EF>
   2.791 +  SubGraph<const GR, const NF, EF>
   2.792 +  subGraph(const GR& graph,
   2.793 +           const NF& node_filter_map, EF& edge_filter_map) {
   2.794 +    return SubGraph<const GR, const NF, EF>
   2.795 +      (graph, node_filter_map, edge_filter_map);
   2.796    }
   2.797  
   2.798 -  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
   2.799 -  SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
   2.800 -  subGraph(const Graph& graph,
   2.801 -           NodeFilterMap& nfm, const ArcFilterMap& efm) {
   2.802 -    return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
   2.803 -      (graph, nfm, efm);
   2.804 +  template<typename GR, typename NF, typename EF>
   2.805 +  SubGraph<const GR, NF, const EF>
   2.806 +  subGraph(const GR& graph,
   2.807 +           NF& node_filter_map, const EF& edge_filter_map) {
   2.808 +    return SubGraph<const GR, NF, const EF>
   2.809 +      (graph, node_filter_map, edge_filter_map);
   2.810    }
   2.811  
   2.812 -  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
   2.813 -  SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
   2.814 -  subGraph(const Graph& graph,
   2.815 -           const NodeFilterMap& nfm, const ArcFilterMap& efm) {
   2.816 -    return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
   2.817 -      (graph, nfm, efm);
   2.818 +  template<typename GR, typename NF, typename EF>
   2.819 +  SubGraph<const GR, const NF, const EF>
   2.820 +  subGraph(const GR& graph,
   2.821 +           const NF& node_filter_map, const EF& edge_filter_map) {
   2.822 +    return SubGraph<const GR, const NF, const EF>
   2.823 +      (graph, node_filter_map, edge_filter_map);
   2.824    }
   2.825  
   2.826 +
   2.827    /// \ingroup graph_adaptors
   2.828    ///
   2.829 -  /// \brief An adaptor for hiding nodes from a digraph or a graph.
   2.830 +  /// \brief Adaptor class for hiding nodes in a digraph or a graph.
   2.831    ///
   2.832 -  /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool
   2.833 -  /// node map must be specified, which defines the filters for
   2.834 -  /// nodes. Just the unfiltered nodes and the arcs or edges incident
   2.835 -  /// to unfiltered nodes are shown in the subdigraph or subgraph. The
   2.836 -  /// FilterNodes is conform to the \ref concepts::Digraph
   2.837 -  /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending
   2.838 -  /// on the \c _Digraph template parameter. If the \c _checked
   2.839 -  /// parameter is true, then the arc or edges incident to filtered nodes
   2.840 -  /// are also filtered out.
   2.841 +  /// FilterNodes adaptor can be used for hiding nodes in a digraph or a
   2.842 +  /// graph. A \c bool node map must be specified, which defines the filter
   2.843 +  /// for the nodes. Only the nodes with \c true filter value and the
   2.844 +  /// arcs/edges incident to nodes both with \c true filter value are shown
   2.845 +  /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph
   2.846 +  /// "Digraph" concept or the \ref concepts::Graph "Graph" concept
   2.847 +  /// depending on the \c GR template parameter.
   2.848    ///
   2.849 -  /// \tparam _Digraph It must be conform to the \ref
   2.850 -  /// concepts::Digraph "Digraph concept" or \ref concepts::Graph
   2.851 -  /// "Graph concept". The type can be specified to be const.
   2.852 -  /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
   2.853 -  /// \tparam _checked If the parameter is false then the arc or edge
   2.854 -  /// filtering is not checked with respect to node filter. In this
   2.855 -  /// case just isolated nodes can be filtered out from the
   2.856 -  /// graph.
   2.857 +  /// The adapted (di)graph can also be modified through this adaptor
   2.858 +  /// by adding or removing nodes or arcs/edges, unless the \c GR template
   2.859 +  /// parameter is set to be \c const.
   2.860 +  ///
   2.861 +  /// \tparam GR The type of the adapted digraph or graph.
   2.862 +  /// It must conform to the \ref concepts::Digraph "Digraph" concept
   2.863 +  /// or the \ref concepts::Graph "Graph" concept.
   2.864 +  /// It can also be specified to be \c const.
   2.865 +  /// \tparam NF The type of the node filter map.
   2.866 +  /// It must be a \c bool (or convertible) node map of the
   2.867 +  /// adapted (di)graph. The default type is
   2.868 +  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
   2.869 +  ///
   2.870 +  /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the
   2.871 +  /// adapted (di)graph are convertible to each other.
   2.872  #ifdef DOXYGEN
   2.873 -  template<typename _Digraph,
   2.874 -           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
   2.875 -           bool _checked = true>
   2.876 +  template<typename GR, typename NF>
   2.877 +  class FilterNodes {
   2.878  #else
   2.879 -  template<typename _Digraph,
   2.880 -           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
   2.881 -           bool _checked = true,
   2.882 +  template<typename GR,
   2.883 +           typename NF = typename GR::template NodeMap<bool>,
   2.884             typename Enable = void>
   2.885 +  class FilterNodes :
   2.886 +    public DigraphAdaptorExtender<
   2.887 +      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> > {
   2.888  #endif
   2.889 -  class FilterNodes
   2.890 -    : public SubDigraph<_Digraph, _NodeFilterMap,
   2.891 -                        ConstMap<typename _Digraph::Arc, bool>, _checked> {
   2.892    public:
   2.893  
   2.894 -    typedef _Digraph Digraph;
   2.895 -    typedef _NodeFilterMap NodeFilterMap;
   2.896 -
   2.897 -    typedef SubDigraph<Digraph, NodeFilterMap,
   2.898 -                       ConstMap<typename Digraph::Arc, bool>, _checked>
   2.899 -    Parent;
   2.900 +    typedef GR Digraph;
   2.901 +    typedef NF NodeFilterMap;
   2.902 +
   2.903 +    typedef DigraphAdaptorExtender<
   2.904 +      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> >
   2.905 +      Parent;
   2.906  
   2.907      typedef typename Parent::Node Node;
   2.908  
   2.909 @@ -1412,47 +1505,56 @@
   2.910  
   2.911      /// \brief Constructor
   2.912      ///
   2.913 -    /// Creates an adaptor for the given digraph or graph with
   2.914 +    /// Creates a subgraph for the given digraph or graph with the
   2.915      /// given node filter map.
   2.916 -    FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :
   2.917 -      Parent(), const_true_map(true) {
   2.918 -      Parent::setDigraph(_digraph);
   2.919 +    FilterNodes(GR& graph, NodeFilterMap& node_filter) :
   2.920 +      Parent(), const_true_map(true)
   2.921 +    {
   2.922 +      Parent::setDigraph(graph);
   2.923        Parent::setNodeFilterMap(node_filter);
   2.924        Parent::setArcFilterMap(const_true_map);
   2.925      }
   2.926  
   2.927 -    /// \brief Hides the node of the graph
   2.928 +    /// \brief Sets the status of the given node
   2.929      ///
   2.930 -    /// This function hides \c n in the digraph or graph, i.e. the iteration
   2.931 -    /// jumps over it. This is done by simply setting the value of \c n
   2.932 -    /// to be false in the corresponding node map.
   2.933 -    void hide(const Node& n) const { Parent::hide(n); }
   2.934 -
   2.935 -    /// \brief Unhides the node of the graph
   2.936 +    /// This function sets the status of the given node.
   2.937 +    /// It is done by simply setting the assigned value of \c n
   2.938 +    /// to \c v in the node filter map.
   2.939 +    void status(const Node& n, bool v) const { Parent::status(n, v); }
   2.940 +
   2.941 +    /// \brief Returns the status of the given node
   2.942      ///
   2.943 -    /// The value of \c n is set to be true in the node-map which stores
   2.944 -    /// hide information. If \c n was hidden previuosly, then it is shown
   2.945 -    /// again
   2.946 -    void unHide(const Node& n) const { Parent::unHide(n); }
   2.947 -
   2.948 -    /// \brief Returns true if \c n is hidden.
   2.949 +    /// This function returns the status of the given node.
   2.950 +    /// It is \c true if the given node is enabled (i.e. not hidden).
   2.951 +    bool status(const Node& n) const { return Parent::status(n); }
   2.952 +
   2.953 +    /// \brief Disables the given node
   2.954      ///
   2.955 -    /// Returns true if \c n is hidden.
   2.956 +    /// This function disables the given node, so the iteration
   2.957 +    /// jumps over it.
   2.958 +    /// It is the same as \ref status() "status(n, false)".
   2.959 +    void disable(const Node& n) const { Parent::status(n, false); }
   2.960 +
   2.961 +    /// \brief Enables the given node
   2.962      ///
   2.963 -    bool hidden(const Node& n) const { return Parent::hidden(n); }
   2.964 +    /// This function enables the given node.
   2.965 +    /// It is the same as \ref status() "status(n, true)".
   2.966 +    void enable(const Node& n) const { Parent::status(n, true); }
   2.967  
   2.968    };
   2.969  
   2.970 -  template<typename _Graph, typename _NodeFilterMap, bool _checked>
   2.971 -  class FilterNodes<_Graph, _NodeFilterMap, _checked,
   2.972 -                    typename enable_if<UndirectedTagIndicator<_Graph> >::type>
   2.973 -    : public SubGraph<_Graph, _NodeFilterMap,
   2.974 -                      ConstMap<typename _Graph::Edge, bool>, _checked> {
   2.975 +  template<typename GR, typename NF>
   2.976 +  class FilterNodes<GR, NF,
   2.977 +                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
   2.978 +    public GraphAdaptorExtender<
   2.979 +      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> > {
   2.980 +
   2.981    public:
   2.982 -    typedef _Graph Graph;
   2.983 -    typedef _NodeFilterMap NodeFilterMap;
   2.984 -    typedef SubGraph<Graph, NodeFilterMap,
   2.985 -                     ConstMap<typename Graph::Edge, bool> > Parent;
   2.986 +    typedef GR Graph;
   2.987 +    typedef NF NodeFilterMap;
   2.988 +    typedef GraphAdaptorExtender<
   2.989 +      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> >
   2.990 +      Parent;
   2.991  
   2.992      typedef typename Parent::Node Node;
   2.993    protected:
   2.994 @@ -1471,51 +1573,75 @@
   2.995        Parent::setEdgeFilterMap(const_true_map);
   2.996      }
   2.997  
   2.998 -    void hide(const Node& n) const { Parent::hide(n); }
   2.999 -    void unHide(const Node& n) const { Parent::unHide(n); }
  2.1000 -    bool hidden(const Node& n) const { return Parent::hidden(n); }
  2.1001 +    void status(const Node& n, bool v) const { Parent::status(n, v); }
  2.1002 +    bool status(const Node& n) const { return Parent::status(n); }
  2.1003 +    void disable(const Node& n) const { Parent::status(n, false); }
  2.1004 +    void enable(const Node& n) const { Parent::status(n, true); }
  2.1005  
  2.1006    };
  2.1007  
  2.1008  
  2.1009 -  /// \brief Just gives back a FilterNodes adaptor
  2.1010 +  /// \brief Returns a read-only FilterNodes adaptor
  2.1011    ///
  2.1012 -  /// Just gives back a FilterNodes adaptor
  2.1013 -  template<typename Digraph, typename NodeFilterMap>
  2.1014 -  FilterNodes<const Digraph, NodeFilterMap>
  2.1015 -  filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
  2.1016 -    return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
  2.1017 +  /// This function just returns a read-only \ref FilterNodes adaptor.
  2.1018 +  /// \ingroup graph_adaptors
  2.1019 +  /// \relates FilterNodes
  2.1020 +  template<typename GR, typename NF>
  2.1021 +  FilterNodes<const GR, NF>
  2.1022 +  filterNodes(const GR& graph, NF& node_filter_map) {
  2.1023 +    return FilterNodes<const GR, NF>(graph, node_filter_map);
  2.1024    }
  2.1025  
  2.1026 -  template<typename Digraph, typename NodeFilterMap>
  2.1027 -  FilterNodes<const Digraph, const NodeFilterMap>
  2.1028 -  filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
  2.1029 -    return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
  2.1030 +  template<typename GR, typename NF>
  2.1031 +  FilterNodes<const GR, const NF>
  2.1032 +  filterNodes(const GR& graph, const NF& node_filter_map) {
  2.1033 +    return FilterNodes<const GR, const NF>(graph, node_filter_map);
  2.1034    }
  2.1035  
  2.1036    /// \ingroup graph_adaptors
  2.1037    ///
  2.1038 -  /// \brief An adaptor for hiding arcs from a digraph.
  2.1039 +  /// \brief Adaptor class for hiding arcs in a digraph.
  2.1040    ///
  2.1041 -  /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must
  2.1042 -  /// be specified, which defines the filters for arcs. Just the
  2.1043 -  /// unfiltered arcs are shown in the subdigraph. The FilterArcs is
  2.1044 -  /// conform to the \ref concepts::Digraph "Digraph concept".
  2.1045 +  /// FilterArcs adaptor can be used for hiding arcs in a digraph.
  2.1046 +  /// A \c bool arc map must be specified, which defines the filter for
  2.1047 +  /// the arcs. Only the arcs with \c true filter value are shown in the
  2.1048 +  /// subdigraph. This adaptor conforms to the \ref concepts::Digraph
  2.1049 +  /// "Digraph" concept.
  2.1050    ///
  2.1051 -  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
  2.1052 -  /// "Digraph concept". The type can be specified to be const.
  2.1053 -  /// \tparam _ArcFilterMap A bool valued arc map of the the adapted
  2.1054 -  /// graph.
  2.1055 -  template<typename _Digraph, typename _ArcFilterMap>
  2.1056 +  /// The adapted digraph can also be modified through this adaptor
  2.1057 +  /// by adding or removing nodes or arcs, unless the \c GR template
  2.1058 +  /// parameter is set to be \c const.
  2.1059 +  ///
  2.1060 +  /// \tparam GR The type of the adapted digraph.
  2.1061 +  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
  2.1062 +  /// It can also be specified to be \c const.
  2.1063 +  /// \tparam AF The type of the arc filter map.
  2.1064 +  /// It must be a \c bool (or convertible) arc map of the
  2.1065 +  /// adapted digraph. The default type is
  2.1066 +  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>".
  2.1067 +  ///
  2.1068 +  /// \note The \c Node and \c Arc types of this adaptor and the adapted
  2.1069 +  /// digraph are convertible to each other.
  2.1070 +#ifdef DOXYGEN
  2.1071 +  template<typename GR,
  2.1072 +           typename AF>
  2.1073 +  class FilterArcs {
  2.1074 +#else
  2.1075 +  template<typename GR,
  2.1076 +           typename AF = typename GR::template ArcMap<bool> >
  2.1077    class FilterArcs :
  2.1078 -    public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
  2.1079 -                      _ArcFilterMap, false> {
  2.1080 +    public DigraphAdaptorExtender<
  2.1081 +      SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> > {
  2.1082 +#endif
  2.1083    public:
  2.1084 -    typedef _Digraph Digraph;
  2.1085 -    typedef _ArcFilterMap ArcFilterMap;
  2.1086 -
  2.1087 -    typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
  2.1088 -                       ArcFilterMap, false> Parent;
  2.1089 +    /// The type of the adapted digraph.
  2.1090 +    typedef GR Digraph;
  2.1091 +    /// The type of the arc filter map.
  2.1092 +    typedef AF ArcFilterMap;
  2.1093 +
  2.1094 +    typedef DigraphAdaptorExtender<
  2.1095 +      SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> >
  2.1096 +      Parent;
  2.1097  
  2.1098      typedef typename Parent::Arc Arc;
  2.1099  
  2.1100 @@ -1530,8 +1656,8 @@
  2.1101  
  2.1102      /// \brief Constructor
  2.1103      ///
  2.1104 -    /// Creates a FilterArcs adaptor for the given graph with
  2.1105 -    /// given arc map filter.
  2.1106 +    /// Creates a subdigraph for the given digraph with the given arc
  2.1107 +    /// filter map.
  2.1108      FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
  2.1109        : Parent(), const_true_map(true) {
  2.1110        Parent::setDigraph(digraph);
  2.1111 @@ -1539,66 +1665,98 @@
  2.1112        Parent::setArcFilterMap(arc_filter);
  2.1113      }
  2.1114  
  2.1115 -    /// \brief Hides the arc of the graph
  2.1116 +    /// \brief Sets the status of the given arc
  2.1117      ///
  2.1118 -    /// This function hides \c a in the graph, i.e. the iteration
  2.1119 -    /// jumps over it. This is done by simply setting the value of \c a
  2.1120 -    /// to be false in the corresponding arc map.
  2.1121 -    void hide(const Arc& a) const { Parent::hide(a); }
  2.1122 -
  2.1123 -    /// \brief Unhides the arc of the graph
  2.1124 +    /// This function sets the status of the given arc.
  2.1125 +    /// It is done by simply setting the assigned value of \c a
  2.1126 +    /// to \c v in the arc filter map.
  2.1127 +    void status(const Arc& a, bool v) const { Parent::status(a, v); }
  2.1128 +
  2.1129 +    /// \brief Returns the status of the given arc
  2.1130      ///
  2.1131 -    /// The value of \c a is set to be true in the arc-map which stores
  2.1132 -    /// hide information. If \c a was hidden previuosly, then it is shown
  2.1133 -    /// again
  2.1134 -    void unHide(const Arc& a) const { Parent::unHide(a); }
  2.1135 -
  2.1136 -    /// \brief Returns true if \c a is hidden.
  2.1137 +    /// This function returns the status of the given arc.
  2.1138 +    /// It is \c true if the given arc is enabled (i.e. not hidden).
  2.1139 +    bool status(const Arc& a) const { return Parent::status(a); }
  2.1140 +
  2.1141 +    /// \brief Disables the given arc
  2.1142      ///
  2.1143 -    /// Returns true if \c a is hidden.
  2.1144 +    /// This function disables the given arc in the subdigraph,
  2.1145 +    /// so the iteration jumps over it.
  2.1146 +    /// It is the same as \ref status() "status(a, false)".
  2.1147 +    void disable(const Arc& a) const { Parent::status(a, false); }
  2.1148 +
  2.1149 +    /// \brief Enables the given arc
  2.1150      ///
  2.1151 -    bool hidden(const Arc& a) const { return Parent::hidden(a); }
  2.1152 +    /// This function enables the given arc in the subdigraph.
  2.1153 +    /// It is the same as \ref status() "status(a, true)".
  2.1154 +    void enable(const Arc& a) const { Parent::status(a, true); }
  2.1155  
  2.1156    };
  2.1157  
  2.1158 -  /// \brief Just gives back an FilterArcs adaptor
  2.1159 +  /// \brief Returns a read-only FilterArcs adaptor
  2.1160    ///
  2.1161 -  /// Just gives back an FilterArcs adaptor
  2.1162 -  template<typename Digraph, typename ArcFilterMap>
  2.1163 -  FilterArcs<const Digraph, ArcFilterMap>
  2.1164 -  filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
  2.1165 -    return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
  2.1166 +  /// This function just returns a read-only \ref FilterArcs adaptor.
  2.1167 +  /// \ingroup graph_adaptors
  2.1168 +  /// \relates FilterArcs
  2.1169 +  template<typename GR, typename AF>
  2.1170 +  FilterArcs<const GR, AF>
  2.1171 +  filterArcs(const GR& digraph, AF& arc_filter_map) {
  2.1172 +    return FilterArcs<const GR, AF>(digraph, arc_filter_map);
  2.1173    }
  2.1174  
  2.1175 -  template<typename Digraph, typename ArcFilterMap>
  2.1176 -  FilterArcs<const Digraph, const ArcFilterMap>
  2.1177 -  filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
  2.1178 -    return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
  2.1179 +  template<typename GR, typename AF>
  2.1180 +  FilterArcs<const GR, const AF>
  2.1181 +  filterArcs(const GR& digraph, const AF& arc_filter_map) {
  2.1182 +    return FilterArcs<const GR, const AF>(digraph, arc_filter_map);
  2.1183    }
  2.1184  
  2.1185    /// \ingroup graph_adaptors
  2.1186    ///
  2.1187 -  /// \brief An adaptor for hiding edges from a graph.
  2.1188 +  /// \brief Adaptor class for hiding edges in a graph.
  2.1189    ///
  2.1190 -  /// FilterEdges adaptor hides edges in a digraph. A bool edge map must
  2.1191 -  /// be specified, which defines the filters for edges. Just the
  2.1192 -  /// unfiltered edges are shown in the subdigraph. The FilterEdges is
  2.1193 -  /// conform to the \ref concepts::Graph "Graph concept".
  2.1194 +  /// FilterEdges adaptor can be used for hiding edges in a graph.
  2.1195 +  /// A \c bool edge map must be specified, which defines the filter for
  2.1196 +  /// the edges. Only the edges with \c true filter value are shown in the
  2.1197 +  /// subgraph. This adaptor conforms to the \ref concepts::Graph
  2.1198 +  /// "Graph" concept.
  2.1199    ///
  2.1200 -  /// \tparam _Graph It must be conform to the \ref concepts::Graph
  2.1201 -  /// "Graph concept". The type can be specified to be const.
  2.1202 -  /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted
  2.1203 -  /// graph.
  2.1204 -  template<typename _Graph, typename _EdgeFilterMap>
  2.1205 +  /// The adapted graph can also be modified through this adaptor
  2.1206 +  /// by adding or removing nodes or edges, unless the \c GR template
  2.1207 +  /// parameter is set to be \c const.
  2.1208 +  ///
  2.1209 +  /// \tparam GR The type of the adapted graph.
  2.1210 +  /// It must conform to the \ref concepts::Graph "Graph" concept.
  2.1211 +  /// It can also be specified to be \c const.
  2.1212 +  /// \tparam EF The type of the edge filter map.
  2.1213 +  /// It must be a \c bool (or convertible) edge map of the
  2.1214 +  /// adapted graph. The default type is
  2.1215 +  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
  2.1216 +  ///
  2.1217 +  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
  2.1218 +  /// adapted graph are convertible to each other.
  2.1219 +#ifdef DOXYGEN
  2.1220 +  template<typename GR,
  2.1221 +           typename EF>
  2.1222 +  class FilterEdges {
  2.1223 +#else
  2.1224 +  template<typename GR,
  2.1225 +           typename EF = typename GR::template EdgeMap<bool> >
  2.1226    class FilterEdges :
  2.1227 -    public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
  2.1228 -                    _EdgeFilterMap, false> {
  2.1229 +    public GraphAdaptorExtender<
  2.1230 +      SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> > {
  2.1231 +#endif
  2.1232    public:
  2.1233 -    typedef _Graph Graph;
  2.1234 -    typedef _EdgeFilterMap EdgeFilterMap;
  2.1235 -    typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,
  2.1236 -                     EdgeFilterMap, false> Parent;
  2.1237 +    /// The type of the adapted graph.
  2.1238 +    typedef GR Graph;
  2.1239 +    /// The type of the edge filter map.
  2.1240 +    typedef EF EdgeFilterMap;
  2.1241 +
  2.1242 +    typedef GraphAdaptorExtender<
  2.1243 +      SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> >
  2.1244 +      Parent;
  2.1245 +
  2.1246      typedef typename Parent::Edge Edge;
  2.1247 +
  2.1248    protected:
  2.1249      ConstMap<typename Graph::Node, bool> const_true_map;
  2.1250  
  2.1251 @@ -1610,52 +1768,61 @@
  2.1252  
  2.1253      /// \brief Constructor
  2.1254      ///
  2.1255 -    /// Creates a FilterEdges adaptor for the given graph with
  2.1256 -    /// given edge map filters.
  2.1257 -    FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :
  2.1258 +    /// Creates a subgraph for the given graph with the given edge
  2.1259 +    /// filter map.
  2.1260 +    FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) :
  2.1261        Parent(), const_true_map(true) {
  2.1262 -      Parent::setGraph(_graph);
  2.1263 +      Parent::setGraph(graph);
  2.1264        Parent::setNodeFilterMap(const_true_map);
  2.1265        Parent::setEdgeFilterMap(edge_filter_map);
  2.1266      }
  2.1267  
  2.1268 -    /// \brief Hides the edge of the graph
  2.1269 +    /// \brief Sets the status of the given edge
  2.1270      ///
  2.1271 -    /// This function hides \c e in the graph, i.e. the iteration
  2.1272 -    /// jumps over it. This is done by simply setting the value of \c e
  2.1273 -    /// to be false in the corresponding edge-map.
  2.1274 -    void hide(const Edge& e) const { Parent::hide(e); }
  2.1275 -
  2.1276 -    /// \brief Unhides the edge of the graph
  2.1277 +    /// This function sets the status of the given edge.
  2.1278 +    /// It is done by simply setting the assigned value of \c e
  2.1279 +    /// to \c v in the edge filter map.
  2.1280 +    void status(const Edge& e, bool v) const { Parent::status(e, v); }
  2.1281 +
  2.1282 +    /// \brief Returns the status of the given edge
  2.1283      ///
  2.1284 -    /// The value of \c e is set to be true in the edge-map which stores
  2.1285 -    /// hide information. If \c e was hidden previuosly, then it is shown
  2.1286 -    /// again
  2.1287 -    void unHide(const Edge& e) const { Parent::unHide(e); }
  2.1288 -
  2.1289 -    /// \brief Returns true if \c e is hidden.
  2.1290 +    /// This function returns the status of the given edge.
  2.1291 +    /// It is \c true if the given edge is enabled (i.e. not hidden).
  2.1292 +    bool status(const Edge& e) const { return Parent::status(e); }
  2.1293 +
  2.1294 +    /// \brief Disables the given edge
  2.1295      ///
  2.1296 -    /// Returns true if \c e is hidden.
  2.1297 +    /// This function disables the given edge in the subgraph,
  2.1298 +    /// so the iteration jumps over it.
  2.1299 +    /// It is the same as \ref status() "status(e, false)".
  2.1300 +    void disable(const Edge& e) const { Parent::status(e, false); }
  2.1301 +
  2.1302 +    /// \brief Enables the given edge
  2.1303      ///
  2.1304 -    bool hidden(const Edge& e) const { return Parent::hidden(e); }
  2.1305 +    /// This function enables the given edge in the subgraph.
  2.1306 +    /// It is the same as \ref status() "status(e, true)".
  2.1307 +    void enable(const Edge& e) const { Parent::status(e, true); }
  2.1308  
  2.1309    };
  2.1310  
  2.1311 -  /// \brief Just gives back a FilterEdges adaptor
  2.1312 +  /// \brief Returns a read-only FilterEdges adaptor
  2.1313    ///
  2.1314 -  /// Just gives back a FilterEdges adaptor
  2.1315 -  template<typename Graph, typename EdgeFilterMap>
  2.1316 -  FilterEdges<const Graph, EdgeFilterMap>
  2.1317 -  filterEdges(const Graph& graph, EdgeFilterMap& efm) {
  2.1318 -    return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);
  2.1319 +  /// This function just returns a read-only \ref FilterEdges adaptor.
  2.1320 +  /// \ingroup graph_adaptors
  2.1321 +  /// \relates FilterEdges
  2.1322 +  template<typename GR, typename EF>
  2.1323 +  FilterEdges<const GR, EF>
  2.1324 +  filterEdges(const GR& graph, EF& edge_filter_map) {
  2.1325 +    return FilterEdges<const GR, EF>(graph, edge_filter_map);
  2.1326    }
  2.1327  
  2.1328 -  template<typename Graph, typename EdgeFilterMap>
  2.1329 -  FilterEdges<const Graph, const EdgeFilterMap>
  2.1330 -  filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
  2.1331 -    return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);
  2.1332 +  template<typename GR, typename EF>
  2.1333 +  FilterEdges<const GR, const EF>
  2.1334 +  filterEdges(const GR& graph, const EF& edge_filter_map) {
  2.1335 +    return FilterEdges<const GR, const EF>(graph, edge_filter_map);
  2.1336    }
  2.1337  
  2.1338 +
  2.1339    template <typename _Digraph>
  2.1340    class UndirectorBase {
  2.1341    public:
  2.1342 @@ -1695,8 +1862,6 @@
  2.1343        }
  2.1344      };
  2.1345  
  2.1346 -
  2.1347 -
  2.1348      void first(Node& n) const {
  2.1349        _digraph->first(n);
  2.1350      }
  2.1351 @@ -1845,12 +2010,15 @@
  2.1352      void clear() { _digraph->clear(); }
  2.1353  
  2.1354      typedef NodeNumTagIndicator<Digraph> NodeNumTag;
  2.1355 -    int nodeNum() const { return 2 * _digraph->arcNum(); }
  2.1356 -    typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
  2.1357 +    int nodeNum() const { return _digraph->nodeNum(); }
  2.1358 +
  2.1359 +    typedef ArcNumTagIndicator<Digraph> ArcNumTag;
  2.1360      int arcNum() const { return 2 * _digraph->arcNum(); }
  2.1361 +
  2.1362 +    typedef ArcNumTag EdgeNumTag;
  2.1363      int edgeNum() const { return _digraph->arcNum(); }
  2.1364  
  2.1365 -    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
  2.1366 +    typedef FindArcTagIndicator<Digraph> FindArcTag;
  2.1367      Arc findArc(Node s, Node t, Arc p = INVALID) const {
  2.1368        if (p == INVALID) {
  2.1369          Edge arc = _digraph->findArc(s, t);
  2.1370 @@ -1869,6 +2037,7 @@
  2.1371        return INVALID;
  2.1372      }
  2.1373  
  2.1374 +    typedef FindArcTag FindEdgeTag;
  2.1375      Edge findEdge(Node s, Node t, Edge p = INVALID) const {
  2.1376        if (s != t) {
  2.1377          if (p == INVALID) {
  2.1378 @@ -1876,7 +2045,7 @@
  2.1379            if (arc != INVALID) return arc;
  2.1380            arc = _digraph->findArc(t, s);
  2.1381            if (arc != INVALID) return arc;
  2.1382 -        } else if (_digraph->s(p) == s) {
  2.1383 +        } else if (_digraph->source(p) == s) {
  2.1384            Edge arc = _digraph->findArc(s, t, p);
  2.1385            if (arc != INVALID) return arc;
  2.1386            arc = _digraph->findArc(t, s);
  2.1387 @@ -1905,6 +2074,10 @@
  2.1388  
  2.1389        typedef _Value Value;
  2.1390        typedef Arc Key;
  2.1391 +      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
  2.1392 +      typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;
  2.1393 +      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;
  2.1394 +      typedef typename MapTraits<MapImpl>::ReturnValue Reference;
  2.1395  
  2.1396        ArcMapBase(const Adaptor& adaptor) :
  2.1397          _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
  2.1398 @@ -1920,8 +2093,7 @@
  2.1399          }
  2.1400        }
  2.1401  
  2.1402 -      typename MapTraits<MapImpl>::ConstReturnValue
  2.1403 -      operator[](const Arc& a) const {
  2.1404 +      ConstReturnValue operator[](const Arc& a) const {
  2.1405          if (direction(a)) {
  2.1406            return _forward[a];
  2.1407          } else {
  2.1408 @@ -1929,8 +2101,7 @@
  2.1409          }
  2.1410        }
  2.1411  
  2.1412 -      typename MapTraits<MapImpl>::ReturnValue
  2.1413 -      operator[](const Arc& a) {
  2.1414 +      ReturnValue operator[](const Arc& a) {
  2.1415          if (direction(a)) {
  2.1416            return _forward[a];
  2.1417          } else {
  2.1418 @@ -1980,7 +2151,7 @@
  2.1419        typedef _Value Value;
  2.1420        typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
  2.1421  
  2.1422 -      ArcMap(const Adaptor& adaptor)
  2.1423 +      explicit ArcMap(const Adaptor& adaptor)
  2.1424          : Parent(adaptor) {}
  2.1425  
  2.1426        ArcMap(const Adaptor& adaptor, const Value& value)
  2.1427 @@ -2027,6 +2198,9 @@
  2.1428      typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
  2.1429      NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
  2.1430  
  2.1431 +    typedef typename ItemSetTraits<Digraph, Edge>::ItemNotifier EdgeNotifier;
  2.1432 +    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
  2.1433 +
  2.1434    protected:
  2.1435  
  2.1436      UndirectorBase() : _digraph(0) {}
  2.1437 @@ -2041,59 +2215,76 @@
  2.1438  
  2.1439    /// \ingroup graph_adaptors
  2.1440    ///
  2.1441 -  /// \brief Undirect the graph
  2.1442 +  /// \brief Adaptor class for viewing a digraph as an undirected graph.
  2.1443    ///
  2.1444 -  /// This adaptor makes an undirected graph from a directed
  2.1445 -  /// graph. All arcs of the underlying digraph will be showed in the
  2.1446 -  /// adaptor as an edge. The Orienter adaptor is conform to the \ref
  2.1447 -  /// concepts::Graph "Graph concept".
  2.1448 +  /// Undirector adaptor can be used for viewing a digraph as an undirected
  2.1449 +  /// graph. All arcs of the underlying digraph are showed in the
  2.1450 +  /// adaptor as an edge (and also as a pair of arcs, of course).
  2.1451 +  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
  2.1452    ///
  2.1453 -  /// \tparam _Digraph It must be conform to the \ref
  2.1454 -  /// concepts::Digraph "Digraph concept". The type can be specified
  2.1455 -  /// to const.
  2.1456 -  template<typename _Digraph>
  2.1457 -  class Undirector
  2.1458 -    : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
  2.1459 +  /// The adapted digraph can also be modified through this adaptor
  2.1460 +  /// by adding or removing nodes or edges, unless the \c GR template
  2.1461 +  /// parameter is set to be \c const.
  2.1462 +  ///
  2.1463 +  /// \tparam GR The type of the adapted digraph.
  2.1464 +  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
  2.1465 +  /// It can also be specified to be \c const.
  2.1466 +  ///
  2.1467 +  /// \note The \c Node type of this adaptor and the adapted digraph are
  2.1468 +  /// convertible to each other, moreover the \c Edge type of the adaptor
  2.1469 +  /// and the \c Arc type of the adapted digraph are also convertible to
  2.1470 +  /// each other.
  2.1471 +  /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
  2.1472 +  /// of the adapted digraph.)
  2.1473 +  template<typename GR>
  2.1474 +#ifdef DOXYGEN
  2.1475 +  class Undirector {
  2.1476 +#else
  2.1477 +  class Undirector :
  2.1478 +    public GraphAdaptorExtender<UndirectorBase<GR> > {
  2.1479 +#endif
  2.1480    public:
  2.1481 -    typedef _Digraph Digraph;
  2.1482 -    typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
  2.1483 +    /// The type of the adapted digraph.
  2.1484 +    typedef GR Digraph;
  2.1485 +    typedef GraphAdaptorExtender<UndirectorBase<GR> > Parent;
  2.1486    protected:
  2.1487      Undirector() { }
  2.1488    public:
  2.1489  
  2.1490      /// \brief Constructor
  2.1491      ///
  2.1492 -    /// Creates a undirected graph from the given digraph
  2.1493 -    Undirector(_Digraph& digraph) {
  2.1494 +    /// Creates an undirected graph from the given digraph.
  2.1495 +    Undirector(Digraph& digraph) {
  2.1496        setDigraph(digraph);
  2.1497      }
  2.1498  
  2.1499 -    /// \brief ArcMap combined from two original ArcMap
  2.1500 +    /// \brief Arc map combined from two original arc maps
  2.1501      ///
  2.1502 -    /// This class adapts two original digraph ArcMap to
  2.1503 -    /// get an arc map on the undirected graph.
  2.1504 -    template <typename _ForwardMap, typename _BackwardMap>
  2.1505 +    /// This map adaptor class adapts two arc maps of the underlying
  2.1506 +    /// digraph to get an arc map of the undirected graph.
  2.1507 +    /// Its value type is inherited from the first arc map type
  2.1508 +    /// (\c %ForwardMap).
  2.1509 +    template <typename ForwardMap, typename BackwardMap>
  2.1510      class CombinedArcMap {
  2.1511      public:
  2.1512  
  2.1513 -      typedef _ForwardMap ForwardMap;
  2.1514 -      typedef _BackwardMap BackwardMap;
  2.1515 +      /// The key type of the map
  2.1516 +      typedef typename Parent::Arc Key;
  2.1517 +      /// The value type of the map
  2.1518 +      typedef typename ForwardMap::Value Value;
  2.1519  
  2.1520        typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
  2.1521  
  2.1522 -      typedef typename ForwardMap::Value Value;
  2.1523 -      typedef typename Parent::Arc Key;
  2.1524 -
  2.1525 -      /// \brief Constructor
  2.1526 -      ///
  2.1527 +      typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
  2.1528 +      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;
  2.1529 +      typedef typename MapTraits<ForwardMap>::ReturnValue Reference;
  2.1530 +      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
  2.1531 +
  2.1532        /// Constructor
  2.1533        CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
  2.1534          : _forward(&forward), _backward(&backward) {}
  2.1535  
  2.1536 -
  2.1537 -      /// \brief Sets the value associated with a key.
  2.1538 -      ///
  2.1539 -      /// Sets the value associated with a key.
  2.1540 +      /// Sets the value associated with the given key.
  2.1541        void set(const Key& e, const Value& a) {
  2.1542          if (Parent::direction(e)) {
  2.1543            _forward->set(e, a);
  2.1544 @@ -2102,11 +2293,8 @@
  2.1545          }
  2.1546        }
  2.1547  
  2.1548 -      /// \brief Returns the value associated with a key.
  2.1549 -      ///
  2.1550 -      /// Returns the value associated with a key.
  2.1551 -      typename MapTraits<ForwardMap>::ConstReturnValue
  2.1552 -      operator[](const Key& e) const {
  2.1553 +      /// Returns the value associated with the given key.
  2.1554 +      ConstReturnValue operator[](const Key& e) const {
  2.1555          if (Parent::direction(e)) {
  2.1556            return (*_forward)[e];
  2.1557          } else {
  2.1558 @@ -2114,11 +2302,8 @@
  2.1559          }
  2.1560        }
  2.1561  
  2.1562 -      /// \brief Returns the value associated with a key.
  2.1563 -      ///
  2.1564 -      /// Returns the value associated with a key.
  2.1565 -      typename MapTraits<ForwardMap>::ReturnValue
  2.1566 -      operator[](const Key& e) {
  2.1567 +      /// Returns a reference to the value associated with the given key.
  2.1568 +      ReturnValue operator[](const Key& e) {
  2.1569          if (Parent::direction(e)) {
  2.1570            return (*_forward)[e];
  2.1571          } else {
  2.1572 @@ -2133,9 +2318,9 @@
  2.1573  
  2.1574      };
  2.1575  
  2.1576 -    /// \brief Just gives back a combined arc map
  2.1577 +    /// \brief Returns a combined arc map
  2.1578      ///
  2.1579 -    /// Just gives back a combined arc map
  2.1580 +    /// This function just returns a combined arc map.
  2.1581      template <typename ForwardMap, typename BackwardMap>
  2.1582      static CombinedArcMap<ForwardMap, BackwardMap>
  2.1583      combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
  2.1584 @@ -2165,15 +2350,17 @@
  2.1585  
  2.1586    };
  2.1587  
  2.1588 -  /// \brief Just gives back an undirected view of the given digraph
  2.1589 +  /// \brief Returns a read-only Undirector adaptor
  2.1590    ///
  2.1591 -  /// Just gives back an undirected view of the given digraph
  2.1592 -  template<typename Digraph>
  2.1593 -  Undirector<const Digraph>
  2.1594 -  undirector(const Digraph& digraph) {
  2.1595 -    return Undirector<const Digraph>(digraph);
  2.1596 +  /// This function just returns a read-only \ref Undirector adaptor.
  2.1597 +  /// \ingroup graph_adaptors
  2.1598 +  /// \relates Undirector
  2.1599 +  template<typename GR>
  2.1600 +  Undirector<const GR> undirector(const GR& digraph) {
  2.1601 +    return Undirector<const GR>(digraph);
  2.1602    }
  2.1603  
  2.1604 +
  2.1605    template <typename _Graph, typename _DirectionMap>
  2.1606    class OrienterBase {
  2.1607    public:
  2.1608 @@ -2191,12 +2378,12 @@
  2.1609      void first(Node& i) const { _graph->first(i); }
  2.1610      void first(Arc& i) const { _graph->first(i); }
  2.1611      void firstIn(Arc& i, const Node& n) const {
  2.1612 -      bool d;
  2.1613 +      bool d = true;
  2.1614        _graph->firstInc(i, d, n);
  2.1615        while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
  2.1616      }
  2.1617      void firstOut(Arc& i, const Node& n ) const {
  2.1618 -      bool d;
  2.1619 +      bool d = true;
  2.1620        _graph->firstInc(i, d, n);
  2.1621        while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
  2.1622      }
  2.1623 @@ -2224,24 +2411,15 @@
  2.1624      typedef NodeNumTagIndicator<Graph> NodeNumTag;
  2.1625      int nodeNum() const { return _graph->nodeNum(); }
  2.1626  
  2.1627 -    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
  2.1628 +    typedef EdgeNumTagIndicator<Graph> ArcNumTag;
  2.1629      int arcNum() const { return _graph->edgeNum(); }
  2.1630  
  2.1631 -    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
  2.1632 +    typedef FindEdgeTagIndicator<Graph> FindArcTag;
  2.1633      Arc findArc(const Node& u, const Node& v,
  2.1634 -                const Arc& prev = INVALID) {
  2.1635 -      Arc arc = prev;
  2.1636 -      bool d = arc == INVALID ? true : (*_direction)[arc];
  2.1637 -      if (d) {
  2.1638 +                const Arc& prev = INVALID) const {
  2.1639 +      Arc arc = _graph->findEdge(u, v, prev);
  2.1640 +      while (arc != INVALID && source(arc) != u) {
  2.1641          arc = _graph->findEdge(u, v, arc);
  2.1642 -        while (arc != INVALID && !(*_direction)[arc]) {
  2.1643 -          _graph->findEdge(u, v, arc);
  2.1644 -        }
  2.1645 -        if (arc != INVALID) return arc;
  2.1646 -      }
  2.1647 -      _graph->findEdge(v, u, arc);
  2.1648 -      while (arc != INVALID && (*_direction)[arc]) {
  2.1649 -        _graph->findEdge(u, v, arc);
  2.1650        }
  2.1651        return arc;
  2.1652      }
  2.1653 @@ -2251,8 +2429,8 @@
  2.1654      }
  2.1655  
  2.1656      Arc addArc(const Node& u, const Node& v) {
  2.1657 -      Arc arc = _graph->addArc(u, v);
  2.1658 -      _direction->set(arc, _graph->source(arc) == u);
  2.1659 +      Arc arc = _graph->addEdge(u, v);
  2.1660 +      _direction->set(arc, _graph->u(arc) == u);
  2.1661        return arc;
  2.1662      }
  2.1663  
  2.1664 @@ -2343,78 +2521,98 @@
  2.1665  
  2.1666    /// \ingroup graph_adaptors
  2.1667    ///
  2.1668 -  /// \brief Orients the edges of the graph to get a digraph
  2.1669 +  /// \brief Adaptor class for orienting the edges of a graph to get a digraph
  2.1670    ///
  2.1671 -  /// This adaptor orients each edge in the undirected graph. The
  2.1672 -  /// direction of the arcs stored in an edge node map.  The arcs can
  2.1673 -  /// be easily reverted by the \c reverseArc() member function in the
  2.1674 -  /// adaptor. The Orienter adaptor is conform to the \ref
  2.1675 -  /// concepts::Digraph "Digraph concept".
  2.1676 +  /// Orienter adaptor can be used for orienting the edges of a graph to
  2.1677 +  /// get a digraph. A \c bool edge map of the underlying graph must be
  2.1678 +  /// specified, which define the direction of the arcs in the adaptor.
  2.1679 +  /// The arcs can be easily reversed by the \c reverseArc() member function
  2.1680 +  /// of the adaptor.
  2.1681 +  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
  2.1682    ///
  2.1683 -  /// \tparam _Graph It must be conform to the \ref concepts::Graph
  2.1684 -  /// "Graph concept". The type can be specified to be const.
  2.1685 -  /// \tparam _DirectionMap A bool valued edge map of the the adapted
  2.1686 -  /// graph.
  2.1687 +  /// The adapted graph can also be modified through this adaptor
  2.1688 +  /// by adding or removing nodes or arcs, unless the \c GR template
  2.1689 +  /// parameter is set to be \c const.
  2.1690    ///
  2.1691 -  /// \sa orienter
  2.1692 -  template<typename _Graph,
  2.1693 -           typename DirectionMap = typename _Graph::template EdgeMap<bool> >
  2.1694 +  /// \tparam GR The type of the adapted graph.
  2.1695 +  /// It must conform to the \ref concepts::Graph "Graph" concept.
  2.1696 +  /// It can also be specified to be \c const.
  2.1697 +  /// \tparam DM The type of the direction map.
  2.1698 +  /// It must be a \c bool (or convertible) edge map of the
  2.1699 +  /// adapted graph. The default type is
  2.1700 +  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
  2.1701 +  ///
  2.1702 +  /// \note The \c Node type of this adaptor and the adapted graph are
  2.1703 +  /// convertible to each other, moreover the \c Arc type of the adaptor
  2.1704 +  /// and the \c Edge type of the adapted graph are also convertible to
  2.1705 +  /// each other.
  2.1706 +#ifdef DOXYGEN
  2.1707 +  template<typename GR,
  2.1708 +           typename DM>
  2.1709 +  class Orienter {
  2.1710 +#else
  2.1711 +  template<typename GR,
  2.1712 +           typename DM = typename GR::template EdgeMap<bool> >
  2.1713    class Orienter :
  2.1714 -    public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {
  2.1715 +    public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
  2.1716 +#endif
  2.1717    public:
  2.1718 -    typedef _Graph Graph;
  2.1719 -    typedef DigraphAdaptorExtender<
  2.1720 -      OrienterBase<_Graph, DirectionMap> > Parent;
  2.1721 +
  2.1722 +    /// The type of the adapted graph.
  2.1723 +    typedef GR Graph;
  2.1724 +    /// The type of the direction edge map.
  2.1725 +    typedef DM DirectionMap;
  2.1726 +
  2.1727 +    typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
  2.1728      typedef typename Parent::Arc Arc;
  2.1729    protected:
  2.1730      Orienter() { }
  2.1731    public:
  2.1732  
  2.1733 -    /// \brief Constructor of the adaptor
  2.1734 +    /// \brief Constructor
  2.1735      ///
  2.1736 -    /// Constructor of the adaptor
  2.1737 +    /// Constructor of the adaptor.
  2.1738      Orienter(Graph& graph, DirectionMap& direction) {
  2.1739        setGraph(graph);
  2.1740        setDirectionMap(direction);
  2.1741      }
  2.1742  
  2.1743 -    /// \brief Reverse arc
  2.1744 +    /// \brief Reverses the given arc
  2.1745      ///
  2.1746 -    /// It reverse the given arc. It simply negate the direction in the map.
  2.1747 +    /// This function reverses the given arc.
  2.1748 +    /// It is done by simply negate the assigned value of \c a
  2.1749 +    /// in the direction map.
  2.1750      void reverseArc(const Arc& a) {
  2.1751        Parent::reverseArc(a);
  2.1752      }
  2.1753    };
  2.1754  
  2.1755 -  /// \brief Just gives back a Orienter
  2.1756 +  /// \brief Returns a read-only Orienter adaptor
  2.1757    ///
  2.1758 -  /// Just gives back a Orienter
  2.1759 -  template<typename Graph, typename DirectionMap>
  2.1760 -  Orienter<const Graph, DirectionMap>
  2.1761 -  orienter(const Graph& graph, DirectionMap& dm) {
  2.1762 -    return Orienter<const Graph, DirectionMap>(graph, dm);
  2.1763 +  /// This function just returns a read-only \ref Orienter adaptor.
  2.1764 +  /// \ingroup graph_adaptors
  2.1765 +  /// \relates Orienter
  2.1766 +  template<typename GR, typename DM>
  2.1767 +  Orienter<const GR, DM>
  2.1768 +  orienter(const GR& graph, DM& direction_map) {
  2.1769 +    return Orienter<const GR, DM>(graph, direction_map);
  2.1770    }
  2.1771  
  2.1772 -  template<typename Graph, typename DirectionMap>
  2.1773 -  Orienter<const Graph, const DirectionMap>
  2.1774 -  orienter(const Graph& graph, const DirectionMap& dm) {
  2.1775 -    return Orienter<const Graph, const DirectionMap>(graph, dm);
  2.1776 +  template<typename GR, typename DM>
  2.1777 +  Orienter<const GR, const DM>
  2.1778 +  orienter(const GR& graph, const DM& direction_map) {
  2.1779 +    return Orienter<const GR, const DM>(graph, direction_map);
  2.1780    }
  2.1781  
  2.1782    namespace _adaptor_bits {
  2.1783  
  2.1784 -    template<typename _Digraph,
  2.1785 -             typename _CapacityMap = typename _Digraph::template ArcMap<int>,
  2.1786 -             typename _FlowMap = _CapacityMap,
  2.1787 -             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
  2.1788 +    template<typename Digraph,
  2.1789 +             typename CapacityMap,
  2.1790 +             typename FlowMap,
  2.1791 +             typename Tolerance>
  2.1792      class ResForwardFilter {
  2.1793      public:
  2.1794  
  2.1795 -      typedef _Digraph Digraph;
  2.1796 -      typedef _CapacityMap CapacityMap;
  2.1797 -      typedef _FlowMap FlowMap;
  2.1798 -      typedef _Tolerance Tolerance;
  2.1799 -
  2.1800        typedef typename Digraph::Arc Key;
  2.1801        typedef bool Value;
  2.1802  
  2.1803 @@ -2434,18 +2632,13 @@
  2.1804        }
  2.1805      };
  2.1806  
  2.1807 -    template<typename _Digraph,
  2.1808 -             typename _CapacityMap = typename _Digraph::template ArcMap<int>,
  2.1809 -             typename _FlowMap = _CapacityMap,
  2.1810 -             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
  2.1811 +    template<typename Digraph,
  2.1812 +             typename CapacityMap,
  2.1813 +             typename FlowMap,
  2.1814 +             typename Tolerance>
  2.1815      class ResBackwardFilter {
  2.1816      public:
  2.1817  
  2.1818 -      typedef _Digraph Digraph;
  2.1819 -      typedef _CapacityMap CapacityMap;
  2.1820 -      typedef _FlowMap FlowMap;
  2.1821 -      typedef _Tolerance Tolerance;
  2.1822 -
  2.1823        typedef typename Digraph::Arc Key;
  2.1824        typedef bool Value;
  2.1825  
  2.1826 @@ -2470,50 +2663,71 @@
  2.1827  
  2.1828    /// \ingroup graph_adaptors
  2.1829    ///
  2.1830 -  /// \brief An adaptor for composing the residual graph for directed
  2.1831 +  /// \brief Adaptor class for composing the residual digraph for directed
  2.1832    /// flow and circulation problems.
  2.1833    ///
  2.1834 -  /// An adaptor for composing the residual graph for directed flow and
  2.1835 -  /// circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph
  2.1836 -  /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
  2.1837 -  /// be functions on the arc-set.
  2.1838 +  /// Residual can be used for composing the \e residual digraph for directed
  2.1839 +  /// flow and circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
  2.1840 +  /// and let \f$ F \f$ be a number type. Let \f$ flow, cap: A\to F \f$ be
  2.1841 +  /// functions on the arcs.
  2.1842 +  /// This adaptor implements a digraph structure with node set \f$ V \f$
  2.1843 +  /// and arc set \f$ A_{forward}\cup A_{backward} \f$,
  2.1844 +  /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and
  2.1845 +  /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so
  2.1846 +  /// called residual digraph.
  2.1847 +  /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,
  2.1848 +  /// multiplicities are counted, i.e. the adaptor has exactly
  2.1849 +  /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel
  2.1850 +  /// arcs).
  2.1851 +  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
  2.1852    ///
  2.1853 -  /// Then Residual implements the digraph structure with
  2.1854 -  /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$,
  2.1855 -  /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
  2.1856 -  /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
  2.1857 -  /// called residual graph.  When we take the union
  2.1858 -  /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,
  2.1859 -  /// i.e.  if an arc is in both \f$ A_{forward} \f$ and
  2.1860 -  /// \f$ A_{backward} \f$, then in the adaptor it appears in both
  2.1861 -  /// orientation.
  2.1862 +  /// \tparam GR The type of the adapted digraph.
  2.1863 +  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
  2.1864 +  /// It is implicitly \c const.
  2.1865 +  /// \tparam CM The type of the capacity map.
  2.1866 +  /// It must be an arc map of some numerical type, which defines
  2.1867 +  /// the capacities in the flow problem. It is implicitly \c const.
  2.1868 +  /// The default type is
  2.1869 +  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
  2.1870 +  /// \tparam FM The type of the flow map.
  2.1871 +  /// It must be an arc map of some numerical type, which defines
  2.1872 +  /// the flow values in the flow problem. The default type is \c CM.
  2.1873 +  /// \tparam TL The tolerance type for handling inexact computation.
  2.1874 +  /// The default tolerance type depends on the value type of the
  2.1875 +  /// capacity map.
  2.1876    ///
  2.1877 -  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
  2.1878 -  /// "Digraph concept". The type is implicitly const.
  2.1879 -  /// \tparam _CapacityMap An arc map of some numeric type, it defines
  2.1880 -  /// the capacities in the flow problem. The map is implicitly const.
  2.1881 -  /// \tparam _FlowMap An arc map of some numeric type, it defines
  2.1882 -  /// the capacities in the flow problem.
  2.1883 -  /// \tparam _Tolerance Handler for inexact computation.
  2.1884 -  template<typename _Digraph,
  2.1885 -           typename _CapacityMap = typename _Digraph::template ArcMap<int>,
  2.1886 -           typename _FlowMap = _CapacityMap,
  2.1887 -           typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
  2.1888 +  /// \note This adaptor is implemented using Undirector and FilterArcs
  2.1889 +  /// adaptors.
  2.1890 +  ///
  2.1891 +  /// \note The \c Node type of this adaptor and the adapted digraph are
  2.1892 +  /// convertible to each other, moreover the \c Arc type of the adaptor
  2.1893 +  /// is convertible to the \c Arc type of the adapted digraph.
  2.1894 +#ifdef DOXYGEN
  2.1895 +  template<typename GR, typename CM, typename FM, typename TL>
  2.1896 +  class Residual
  2.1897 +#else
  2.1898 +  template<typename GR,
  2.1899 +           typename CM = typename GR::template ArcMap<int>,
  2.1900 +           typename FM = CM,
  2.1901 +           typename TL = Tolerance<typename CM::Value> >
  2.1902    class Residual :
  2.1903      public FilterArcs<
  2.1904 -    Undirector<const _Digraph>,
  2.1905 -    typename Undirector<const _Digraph>::template CombinedArcMap<
  2.1906 -      _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,
  2.1907 -                                      _FlowMap, _Tolerance>,
  2.1908 -      _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
  2.1909 -                                       _FlowMap, _Tolerance> > >
  2.1910 +      Undirector<const GR>,
  2.1911 +      typename Undirector<const GR>::template CombinedArcMap<
  2.1912 +        _adaptor_bits::ResForwardFilter<const GR, CM, FM, TL>,
  2.1913 +        _adaptor_bits::ResBackwardFilter<const GR, CM, FM, TL> > >
  2.1914 +#endif
  2.1915    {
  2.1916    public:
  2.1917  
  2.1918 -    typedef _Digraph Digraph;
  2.1919 -    typedef _CapacityMap CapacityMap;
  2.1920 -    typedef _FlowMap FlowMap;
  2.1921 -    typedef _Tolerance Tolerance;
  2.1922 +    /// The type of the underlying digraph.
  2.1923 +    typedef GR Digraph;
  2.1924 +    /// The type of the capacity map.
  2.1925 +    typedef CM CapacityMap;
  2.1926 +    /// The type of the flow map.
  2.1927 +    typedef FM FlowMap;
  2.1928 +    /// The tolerance type.
  2.1929 +    typedef TL Tolerance;
  2.1930  
  2.1931      typedef typename CapacityMap::Value Value;
  2.1932      typedef Residual Adaptor;
  2.1933 @@ -2529,7 +2743,7 @@
  2.1934                                               FlowMap, Tolerance> BackwardFilter;
  2.1935  
  2.1936      typedef typename Undirected::
  2.1937 -    template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
  2.1938 +      template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
  2.1939  
  2.1940      typedef FilterArcs<Undirected, ArcFilter> Parent;
  2.1941  
  2.1942 @@ -2543,10 +2757,10 @@
  2.1943  
  2.1944    public:
  2.1945  
  2.1946 -    /// \brief Constructor of the residual digraph.
  2.1947 +    /// \brief Constructor
  2.1948      ///
  2.1949 -    /// Constructor of the residual graph. The parameters are the digraph,
  2.1950 -    /// the flow map, the capacity map and a tolerance object.
  2.1951 +    /// Constructor of the residual digraph adaptor. The parameters are the
  2.1952 +    /// digraph, the capacity map, the flow map, and a tolerance object.
  2.1953      Residual(const Digraph& digraph, const CapacityMap& capacity,
  2.1954               FlowMap& flow, const Tolerance& tolerance = Tolerance())
  2.1955        : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
  2.1956 @@ -2560,9 +2774,9 @@
  2.1957  
  2.1958      typedef typename Parent::Arc Arc;
  2.1959  
  2.1960 -    /// \brief Gives back the residual capacity of the arc.
  2.1961 +    /// \brief Returns the residual capacity of the given arc.
  2.1962      ///
  2.1963 -    /// Gives back the residual capacity of the arc.
  2.1964 +    /// Returns the residual capacity of the given arc.
  2.1965      Value residualCapacity(const Arc& a) const {
  2.1966        if (Undirected::direction(a)) {
  2.1967          return (*_capacity)[a] - (*_flow)[a];
  2.1968 @@ -2571,11 +2785,11 @@
  2.1969        }
  2.1970      }
  2.1971  
  2.1972 -    /// \brief Augment on the given arc in the residual graph.
  2.1973 +    /// \brief Augments on the given arc in the residual digraph.
  2.1974      ///
  2.1975 -    /// Augment on the given arc in the residual graph. It increase
  2.1976 -    /// or decrease the flow on the original arc depend on the direction
  2.1977 -    /// of the residual arc.
  2.1978 +    /// Augments on the given arc in the residual digraph. It increases
  2.1979 +    /// or decreases the flow value on the original arc according to the
  2.1980 +    /// direction of the residual arc.
  2.1981      void augment(const Arc& a, const Value& v) const {
  2.1982        if (Undirected::direction(a)) {
  2.1983          _flow->set(a, (*_flow)[a] + v);
  2.1984 @@ -2584,59 +2798,84 @@
  2.1985        }
  2.1986      }
  2.1987  
  2.1988 -    /// \brief Returns the direction of the arc.
  2.1989 +    /// \brief Returns \c true if the given residual arc is a forward arc.
  2.1990      ///
  2.1991 -    /// Returns true when the arc is same oriented as the original arc.
  2.1992 +    /// Returns \c true if the given residual arc has the same orientation
  2.1993 +    /// as the original arc, i.e. it is a so called forward arc.
  2.1994      static bool forward(const Arc& a) {
  2.1995        return Undirected::direction(a);
  2.1996      }
  2.1997  
  2.1998 -    /// \brief Returns the direction of the arc.
  2.1999 +    /// \brief Returns \c true if the given residual arc is a backward arc.
  2.2000      ///
  2.2001 -    /// Returns true when the arc is opposite oriented as the original arc.
  2.2002 +    /// Returns \c true if the given residual arc has the opposite orientation
  2.2003 +    /// than the original arc, i.e. it is a so called backward arc.
  2.2004      static bool backward(const Arc& a) {
  2.2005        return !Undirected::direction(a);
  2.2006      }
  2.2007  
  2.2008 -    /// \brief Gives back the forward oriented residual arc.
  2.2009 +    /// \brief Returns the forward oriented residual arc.
  2.2010      ///
  2.2011 -    /// Gives back the forward oriented residual arc.
  2.2012 +    /// Returns the forward oriented residual arc related to the given
  2.2013 +    /// arc of the underlying digraph.
  2.2014      static Arc forward(const typename Digraph::Arc& a) {
  2.2015        return Undirected::direct(a, true);
  2.2016      }
  2.2017  
  2.2018 -    /// \brief Gives back the backward oriented residual arc.
  2.2019 +    /// \brief Returns the backward oriented residual arc.
  2.2020      ///
  2.2021 -    /// Gives back the backward oriented residual arc.
  2.2022 +    /// Returns the backward oriented residual arc related to the given
  2.2023 +    /// arc of the underlying digraph.
  2.2024      static Arc backward(const typename Digraph::Arc& a) {
  2.2025        return Undirected::direct(a, false);
  2.2026      }
  2.2027  
  2.2028      /// \brief Residual capacity map.
  2.2029      ///
  2.2030 -    /// In generic residual graph the residual capacity can be obtained
  2.2031 -    /// as a map.
  2.2032 +    /// This map adaptor class can be used for obtaining the residual
  2.2033 +    /// capacities as an arc map of the residual digraph.
  2.2034 +    /// Its value type is inherited from the capacity map.
  2.2035      class ResidualCapacity {
  2.2036      protected:
  2.2037        const Adaptor* _adaptor;
  2.2038      public:
  2.2039 -      /// The Key type
  2.2040 +      /// The key type of the map
  2.2041        typedef Arc Key;
  2.2042 -      /// The Value type
  2.2043 -      typedef typename _CapacityMap::Value Value;
  2.2044 +      /// The value type of the map
  2.2045 +      typedef typename CapacityMap::Value Value;
  2.2046  
  2.2047        /// Constructor
  2.2048        ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
  2.2049  
  2.2050 -      /// \e
  2.2051 +      /// Returns the value associated with the given residual arc
  2.2052        Value operator[](const Arc& a) const {
  2.2053          return _adaptor->residualCapacity(a);
  2.2054        }
  2.2055  
  2.2056      };
  2.2057  
  2.2058 +    /// \brief Returns a residual capacity map
  2.2059 +    ///
  2.2060 +    /// This function just returns a residual capacity map.
  2.2061 +    ResidualCapacity residualCapacity() const {
  2.2062 +      return ResidualCapacity(*this);
  2.2063 +    }
  2.2064 +
  2.2065    };
  2.2066  
  2.2067 +  /// \brief Returns a (read-only) Residual adaptor
  2.2068 +  ///
  2.2069 +  /// This function just returns a (read-only) \ref Residual adaptor.
  2.2070 +  /// \ingroup graph_adaptors
  2.2071 +  /// \relates Residual
  2.2072 +  template<typename GR, typename CM, typename FM>
  2.2073 +  Residual<GR, CM, FM> residual(const GR& digraph,
  2.2074 +                                const CM& capacity_map,
  2.2075 +                                FM& flow_map) {
  2.2076 +    return Residual<GR, CM, FM> (digraph, capacity_map, flow_map);
  2.2077 +  }
  2.2078 +
  2.2079 +
  2.2080    template <typename _Digraph>
  2.2081    class SplitNodesBase {
  2.2082    public:
  2.2083 @@ -2884,30 +3123,26 @@
  2.2084      }
  2.2085  
  2.2086      typedef True NodeNumTag;
  2.2087 -
  2.2088      int nodeNum() const {
  2.2089        return  2 * countNodes(*_digraph);
  2.2090      }
  2.2091  
  2.2092 -    typedef True EdgeNumTag;
  2.2093 +    typedef True ArcNumTag;
  2.2094      int arcNum() const {
  2.2095        return countArcs(*_digraph) + countNodes(*_digraph);
  2.2096      }
  2.2097  
  2.2098 -    typedef True FindEdgeTag;
  2.2099 +    typedef True FindArcTag;
  2.2100      Arc findArc(const Node& u, const Node& v,
  2.2101                  const Arc& prev = INVALID) const {
  2.2102 -      if (inNode(u)) {
  2.2103 -        if (outNode(v)) {
  2.2104 -          if (static_cast<const DigraphNode&>(u) ==
  2.2105 -              static_cast<const DigraphNode&>(v) && prev == INVALID) {
  2.2106 -            return Arc(u);
  2.2107 -          }
  2.2108 +      if (inNode(u) && outNode(v)) {
  2.2109 +        if (static_cast<const DigraphNode&>(u) ==
  2.2110 +            static_cast<const DigraphNode&>(v) && prev == INVALID) {
  2.2111 +          return Arc(u);
  2.2112          }
  2.2113 -      } else {
  2.2114 -        if (inNode(v)) {
  2.2115 -          return Arc(::lemon::findArc(*_digraph, u, v, prev));
  2.2116 -        }
  2.2117 +      }
  2.2118 +      else if (outNode(u) && inNode(v)) {
  2.2119 +        return Arc(::lemon::findArc(*_digraph, u, v, prev));
  2.2120        }
  2.2121        return INVALID;
  2.2122      }
  2.2123 @@ -2921,6 +3156,11 @@
  2.2124      public:
  2.2125        typedef Node Key;
  2.2126        typedef _Value Value;
  2.2127 +      typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
  2.2128 +      typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
  2.2129 +      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;
  2.2130 +      typedef typename MapTraits<NodeImpl>::ReturnValue Reference;
  2.2131 +      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
  2.2132  
  2.2133        NodeMapBase(const Adaptor& adaptor)
  2.2134          : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
  2.2135 @@ -2933,14 +3173,12 @@
  2.2136          else {_out_map.set(key, val); }
  2.2137        }
  2.2138  
  2.2139 -      typename MapTraits<NodeImpl>::ReturnValue
  2.2140 -      operator[](const Node& key) {
  2.2141 +      ReturnValue operator[](const Node& key) {
  2.2142          if (Adaptor::inNode(key)) { return _in_map[key]; }
  2.2143          else { return _out_map[key]; }
  2.2144        }
  2.2145  
  2.2146 -      typename MapTraits<NodeImpl>::ConstReturnValue
  2.2147 -      operator[](const Node& key) const {
  2.2148 +      ConstReturnValue operator[](const Node& key) const {
  2.2149          if (Adaptor::inNode(key)) { return _in_map[key]; }
  2.2150          else { return _out_map[key]; }
  2.2151        }
  2.2152 @@ -2957,6 +3195,11 @@
  2.2153      public:
  2.2154        typedef Arc Key;
  2.2155        typedef _Value Value;
  2.2156 +      typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
  2.2157 +      typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
  2.2158 +      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;
  2.2159 +      typedef typename MapTraits<ArcImpl>::ReturnValue Reference;
  2.2160 +      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
  2.2161  
  2.2162        ArcMapBase(const Adaptor& adaptor)
  2.2163          : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
  2.2164 @@ -2972,8 +3215,7 @@
  2.2165          }
  2.2166        }
  2.2167  
  2.2168 -      typename MapTraits<ArcImpl>::ReturnValue
  2.2169 -      operator[](const Arc& key) {
  2.2170 +      ReturnValue operator[](const Arc& key) {
  2.2171          if (Adaptor::origArc(key)) {
  2.2172            return _arc_map[key._item.first()];
  2.2173          } else {
  2.2174 @@ -2981,8 +3223,7 @@
  2.2175          }
  2.2176        }
  2.2177  
  2.2178 -      typename MapTraits<ArcImpl>::ConstReturnValue
  2.2179 -      operator[](const Arc& key) const {
  2.2180 +      ConstReturnValue operator[](const Arc& key) const {
  2.2181          if (Adaptor::origArc(key)) {
  2.2182            return _arc_map[key._item.first()];
  2.2183          } else {
  2.2184 @@ -3063,31 +3304,41 @@
  2.2185  
  2.2186    /// \ingroup graph_adaptors
  2.2187    ///
  2.2188 -  /// \brief Split the nodes of a directed graph
  2.2189 +  /// \brief Adaptor class for splitting the nodes of a digraph.
  2.2190    ///
  2.2191 -  /// The SplitNodes adaptor splits each node into an in-node and an
  2.2192 -  /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in
  2.2193 -  /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node
  2.2194 -  /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the
  2.2195 -  /// original digraph the new target of the arc will be \f$ u_{in} \f$
  2.2196 -  /// and similarly the source of the original \f$ (u, v) \f$ arc
  2.2197 -  /// will be \f$ u_{out} \f$.  The adaptor will add for each node in
  2.2198 -  /// the original digraph an additional arc which connects
  2.2199 -  /// \f$ (u_{in}, u_{out}) \f$.
  2.2200 +  /// SplitNodes adaptor can be used for splitting each node into an
  2.2201 +  /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor
  2.2202 +  /// replaces each node \f$ u \f$ in the digraph with two nodes,
  2.2203 +  /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.
  2.2204 +  /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the
  2.2205 +  /// new target of the arc will be \f$ u_{in} \f$ and similarly the
  2.2206 +  /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.
  2.2207 +  /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$
  2.2208 +  /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.
  2.2209    ///
  2.2210 -  /// The aim of this class is to run algorithm with node costs if the
  2.2211 -  /// algorithm can use directly just arc costs. In this case we should use
  2.2212 -  /// a \c SplitNodes and set the node cost of the graph to the
  2.2213 -  /// bind arc in the adapted graph.
  2.2214 +  /// The aim of this class is running an algorithm with respect to node
  2.2215 +  /// costs or capacities if the algorithm considers only arc costs or
  2.2216 +  /// capacities directly.
  2.2217 +  /// In this case you can use \c SplitNodes adaptor, and set the node
  2.2218 +  /// costs/capacities of the original digraph to the \e bind \e arcs
  2.2219 +  /// in the adaptor.
  2.2220    ///
  2.2221 -  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
  2.2222 -  /// "Digraph concept". The type can be specified to be const.
  2.2223 -  template <typename _Digraph>
  2.2224 +  /// \tparam GR The type of the adapted digraph.
  2.2225 +  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
  2.2226 +  /// It is implicitly \c const.
  2.2227 +  ///
  2.2228 +  /// \note The \c Node type of this adaptor is converible to the \c Node
  2.2229 +  /// type of the adapted digraph.
  2.2230 +  template <typename GR>
  2.2231 +#ifdef DOXYGEN
  2.2232 +  class SplitNodes {
  2.2233 +#else
  2.2234    class SplitNodes
  2.2235 -    : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > {
  2.2236 +    : public DigraphAdaptorExtender<SplitNodesBase<const GR> > {
  2.2237 +#endif
  2.2238    public:
  2.2239 -    typedef _Digraph Digraph;
  2.2240 -    typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent;
  2.2241 +    typedef GR Digraph;
  2.2242 +    typedef DigraphAdaptorExtender<SplitNodesBase<const GR> > Parent;
  2.2243  
  2.2244      typedef typename Digraph::Node DigraphNode;
  2.2245      typedef typename Digraph::Arc DigraphArc;
  2.2246 @@ -3095,89 +3346,110 @@
  2.2247      typedef typename Parent::Node Node;
  2.2248      typedef typename Parent::Arc Arc;
  2.2249  
  2.2250 -    /// \brief Constructor of the adaptor.
  2.2251 +    /// \brief Constructor
  2.2252      ///
  2.2253      /// Constructor of the adaptor.
  2.2254 -    SplitNodes(Digraph& g) {
  2.2255 +    SplitNodes(const Digraph& g) {
  2.2256        Parent::setDigraph(g);
  2.2257      }
  2.2258  
  2.2259 -    /// \brief Returns true when the node is in-node.
  2.2260 +    /// \brief Returns \c true if the given node is an in-node.
  2.2261      ///
  2.2262 -    /// Returns true when the node is in-node.
  2.2263 +    /// Returns \c true if the given node is an in-node.
  2.2264      static bool inNode(const Node& n) {
  2.2265        return Parent::inNode(n);
  2.2266      }
  2.2267  
  2.2268 -    /// \brief Returns true when the node is out-node.
  2.2269 +    /// \brief Returns \c true if the given node is an out-node.
  2.2270      ///
  2.2271 -    /// Returns true when the node is out-node.
  2.2272 +    /// Returns \c true if the given node is an out-node.
  2.2273      static bool outNode(const Node& n) {
  2.2274        return Parent::outNode(n);
  2.2275      }
  2.2276  
  2.2277 -    /// \brief Returns true when the arc is arc in the original digraph.
  2.2278 +    /// \brief Returns \c true if the given arc is an original arc.
  2.2279      ///
  2.2280 -    /// Returns true when the arc is arc in the original digraph.
  2.2281 +    /// Returns \c true if the given arc is one of the arcs in the
  2.2282 +    /// original digraph.
  2.2283      static bool origArc(const Arc& a) {
  2.2284        return Parent::origArc(a);
  2.2285      }
  2.2286  
  2.2287 -    /// \brief Returns true when the arc binds an in-node and an out-node.
  2.2288 +    /// \brief Returns \c true if the given arc is a bind arc.
  2.2289      ///
  2.2290 -    /// Returns true when the arc binds an in-node and an out-node.
  2.2291 +    /// Returns \c true if the given arc is a bind arc, i.e. it connects
  2.2292 +    /// an in-node and an out-node.
  2.2293      static bool bindArc(const Arc& a) {
  2.2294        return Parent::bindArc(a);
  2.2295      }
  2.2296  
  2.2297 -    /// \brief Gives back the in-node created from the \c node.
  2.2298 +    /// \brief Returns the in-node created from the given original node.
  2.2299      ///
  2.2300 -    /// Gives back the in-node created from the \c node.
  2.2301 +    /// Returns the in-node created from the given original node.
  2.2302      static Node inNode(const DigraphNode& n) {
  2.2303        return Parent::inNode(n);
  2.2304      }
  2.2305  
  2.2306 -    /// \brief Gives back the out-node created from the \c node.
  2.2307 +    /// \brief Returns the out-node created from the given original node.
  2.2308      ///
  2.2309 -    /// Gives back the out-node created from the \c node.
  2.2310 +    /// Returns the out-node created from the given original node.
  2.2311      static Node outNode(const DigraphNode& n) {
  2.2312        return Parent::outNode(n);
  2.2313      }
  2.2314  
  2.2315 -    /// \brief Gives back the arc binds the two part of the node.
  2.2316 +    /// \brief Returns the bind arc that corresponds to the given
  2.2317 +    /// original node.
  2.2318      ///
  2.2319 -    /// Gives back the arc binds the two part of the node.
  2.2320 +    /// Returns the bind arc in the adaptor that corresponds to the given
  2.2321 +    /// original node, i.e. the arc connecting the in-node and out-node
  2.2322 +    /// of \c n.
  2.2323      static Arc arc(const DigraphNode& n) {
  2.2324        return Parent::arc(n);
  2.2325      }
  2.2326  
  2.2327 -    /// \brief Gives back the arc of the original arc.
  2.2328 +    /// \brief Returns the arc that corresponds to the given original arc.
  2.2329      ///
  2.2330 -    /// Gives back the arc of the original arc.
  2.2331 +    /// Returns the arc in the adaptor that corresponds to the given
  2.2332 +    /// original arc.
  2.2333      static Arc arc(const DigraphArc& a) {
  2.2334        return Parent::arc(a);
  2.2335      }
  2.2336  
  2.2337 -    /// \brief NodeMap combined from two original NodeMap
  2.2338 +    /// \brief Node map combined from two original node maps
  2.2339      ///
  2.2340 -    /// This class adapt two of the original digraph NodeMap to
  2.2341 -    /// get a node map on the adapted digraph.
  2.2342 +    /// This map adaptor class adapts two node maps of the original digraph
  2.2343 +    /// to get a node map of the split digraph.
  2.2344 +    /// Its value type is inherited from the first node map type
  2.2345 +    /// (\c InNodeMap).
  2.2346      template <typename InNodeMap, typename OutNodeMap>
  2.2347      class CombinedNodeMap {
  2.2348      public:
  2.2349  
  2.2350 +      /// The key type of the map
  2.2351        typedef Node Key;
  2.2352 +      /// The value type of the map
  2.2353        typedef typename InNodeMap::Value Value;
  2.2354  
  2.2355 -      /// \brief Constructor
  2.2356 -      ///
  2.2357 -      /// Constructor.
  2.2358 +      typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
  2.2359 +      typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
  2.2360 +      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
  2.2361 +      typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
  2.2362 +      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
  2.2363 +
  2.2364 +      /// Constructor
  2.2365        CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
  2.2366          : _in_map(in_map), _out_map(out_map) {}
  2.2367  
  2.2368 -      /// \brief The subscript operator.
  2.2369 -      ///
  2.2370 -      /// The subscript operator.
  2.2371 +      /// Returns the value associated with the given key.
  2.2372 +      Value operator[](const Key& key) const {
  2.2373 +        if (Parent::inNode(key)) {
  2.2374 +          return _in_map[key];
  2.2375 +        } else {
  2.2376 +          return _out_map[key];
  2.2377 +        }
  2.2378 +      }
  2.2379 +
  2.2380 +      /// Returns a reference to the value associated with the given key.
  2.2381        Value& operator[](const Key& key) {
  2.2382          if (Parent::inNode(key)) {
  2.2383            return _in_map[key];
  2.2384 @@ -3186,20 +3458,7 @@
  2.2385          }
  2.2386        }
  2.2387  
  2.2388 -      /// \brief The const subscript operator.
  2.2389 -      ///
  2.2390 -      /// The const subscript operator.
  2.2391 -      Value operator[](const Key& key) const {
  2.2392 -        if (Parent::inNode(key)) {
  2.2393 -          return _in_map[key];
  2.2394 -        } else {
  2.2395 -          return _out_map[key];
  2.2396 -        }
  2.2397 -      }
  2.2398 -
  2.2399 -      /// \brief The setter function of the map.
  2.2400 -      ///
  2.2401 -      /// The setter function of the map.
  2.2402 +      /// Sets the value associated with the given key.
  2.2403        void set(const Key& key, const Value& value) {
  2.2404          if (Parent::inNode(key)) {
  2.2405            _in_map.set(key, value);
  2.2406 @@ -3216,9 +3475,9 @@
  2.2407      };
  2.2408  
  2.2409  
  2.2410 -    /// \brief Just gives back a combined node map
  2.2411 +    /// \brief Returns a combined node map
  2.2412      ///
  2.2413 -    /// Just gives back a combined node map
  2.2414 +    /// This function just returns a combined node map.
  2.2415      template <typename InNodeMap, typename OutNodeMap>
  2.2416      static CombinedNodeMap<InNodeMap, OutNodeMap>
  2.2417      combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
  2.2418 @@ -3244,26 +3503,51 @@
  2.2419          const OutNodeMap>(in_map, out_map);
  2.2420      }
  2.2421  
  2.2422 -    /// \brief ArcMap combined from an original ArcMap and a NodeMap
  2.2423 +    /// \brief Arc map combined from an arc map and a node map of the
  2.2424 +    /// original digraph.
  2.2425      ///
  2.2426 -    /// This class adapt an original ArcMap and a NodeMap to get an
  2.2427 -    /// arc map on the adapted digraph
  2.2428 -    template <typename DigraphArcMap, typename DigraphNodeMap>
  2.2429 +    /// This map adaptor class adapts an arc map and a node map of the
  2.2430 +    /// original digraph to get an arc map of the split digraph.
  2.2431 +    /// Its value type is inherited from the original arc map type
  2.2432 +    /// (\c ArcMap).
  2.2433 +    template <typename ArcMap, typename NodeMap>
  2.2434      class CombinedArcMap {
  2.2435      public:
  2.2436  
  2.2437 +      /// The key type of the map
  2.2438        typedef Arc Key;
  2.2439 -      typedef typename DigraphArcMap::Value Value;
  2.2440 -
  2.2441 -      /// \brief Constructor
  2.2442 -      ///
  2.2443 -      /// Constructor.
  2.2444 -      CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
  2.2445 +      /// The value type of the map
  2.2446 +      typedef typename ArcMap::Value Value;
  2.2447 +
  2.2448 +      typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag;
  2.2449 +      typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue;
  2.2450 +      typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue;
  2.2451 +      typedef typename MapTraits<ArcMap>::ReturnValue Reference;
  2.2452 +      typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference;
  2.2453 +
  2.2454 +      /// Constructor
  2.2455 +      CombinedArcMap(ArcMap& arc_map, NodeMap& node_map)
  2.2456          : _arc_map(arc_map), _node_map(node_map) {}
  2.2457  
  2.2458 -      /// \brief The subscript operator.
  2.2459 -      ///
  2.2460 -      /// The subscript operator.
  2.2461 +      /// Returns the value associated with the given key.
  2.2462 +      Value operator[](const Key& arc) const {
  2.2463 +        if (Parent::origArc(arc)) {
  2.2464 +          return _arc_map[arc];
  2.2465 +        } else {
  2.2466 +          return _node_map[arc];
  2.2467 +        }
  2.2468 +      }
  2.2469 +
  2.2470 +      /// Returns a reference to the value associated with the given key.
  2.2471 +      Value& operator[](const Key& arc) {
  2.2472 +        if (Parent::origArc(arc)) {
  2.2473 +          return _arc_map[arc];
  2.2474 +        } else {
  2.2475 +          return _node_map[arc];
  2.2476 +        }
  2.2477 +      }
  2.2478 +
  2.2479 +      /// Sets the value associated with the given key.
  2.2480        void set(const Arc& arc, const Value& val) {
  2.2481          if (Parent::origArc(arc)) {
  2.2482            _arc_map.set(arc, val);
  2.2483 @@ -3272,76 +3556,51 @@
  2.2484          }
  2.2485        }
  2.2486  
  2.2487 -      /// \brief The const subscript operator.
  2.2488 -      ///
  2.2489 -      /// The const subscript operator.
  2.2490 -      Value operator[](const Key& arc) const {
  2.2491 -        if (Parent::origArc(arc)) {
  2.2492 -          return _arc_map[arc];
  2.2493 -        } else {
  2.2494 -          return _node_map[arc];
  2.2495 -        }
  2.2496 -      }
  2.2497 -
  2.2498 -      /// \brief The const subscript operator.
  2.2499 -      ///
  2.2500 -      /// The const subscript operator.
  2.2501 -      Value& operator[](const Key& arc) {
  2.2502 -        if (Parent::origArc(arc)) {
  2.2503 -          return _arc_map[arc];
  2.2504 -        } else {
  2.2505 -          return _node_map[arc];
  2.2506 -        }
  2.2507 -      }
  2.2508 -
  2.2509      private:
  2.2510 -      DigraphArcMap& _arc_map;
  2.2511 -      DigraphNodeMap& _node_map;
  2.2512 +      ArcMap& _arc_map;
  2.2513 +      NodeMap& _node_map;
  2.2514      };
  2.2515  
  2.2516 -    /// \brief Just gives back a combined arc map
  2.2517 +    /// \brief Returns a combined arc map
  2.2518      ///
  2.2519 -    /// Just gives back a combined arc map
  2.2520 -    template <typename DigraphArcMap, typename DigraphNodeMap>
  2.2521 -    static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
  2.2522 -    combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
  2.2523 -      return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
  2.2524 +    /// This function just returns a combined arc map.
  2.2525 +    template <typename ArcMap, typename NodeMap>
  2.2526 +    static CombinedArcMap<ArcMap, NodeMap>
  2.2527 +    combinedArcMap(ArcMap& arc_map, NodeMap& node_map) {
  2.2528 +      return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map);
  2.2529      }
  2.2530  
  2.2531 -    template <typename DigraphArcMap, typename DigraphNodeMap>
  2.2532 -    static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
  2.2533 -    combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
  2.2534 -      return CombinedArcMap<const DigraphArcMap,
  2.2535 -        DigraphNodeMap>(arc_map, node_map);
  2.2536 +    template <typename ArcMap, typename NodeMap>
  2.2537 +    static CombinedArcMap<const ArcMap, NodeMap>
  2.2538 +    combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) {
  2.2539 +      return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map);
  2.2540      }
  2.2541  
  2.2542 -    template <typename DigraphArcMap, typename DigraphNodeMap>
  2.2543 -    static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
  2.2544 -    combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
  2.2545 -      return CombinedArcMap<DigraphArcMap,
  2.2546 -        const DigraphNodeMap>(arc_map, node_map);
  2.2547 +    template <typename ArcMap, typename NodeMap>
  2.2548 +    static CombinedArcMap<ArcMap, const NodeMap>
  2.2549 +    combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) {
  2.2550 +      return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map);
  2.2551      }
  2.2552  
  2.2553 -    template <typename DigraphArcMap, typename DigraphNodeMap>
  2.2554 -    static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
  2.2555 -    combinedArcMap(const DigraphArcMap& arc_map,
  2.2556 -                   const DigraphNodeMap& node_map) {
  2.2557 -      return CombinedArcMap<const DigraphArcMap,
  2.2558 -        const DigraphNodeMap>(arc_map, node_map);
  2.2559 +    template <typename ArcMap, typename NodeMap>
  2.2560 +    static CombinedArcMap<const ArcMap, const NodeMap>
  2.2561 +    combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) {
  2.2562 +      return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map);
  2.2563      }
  2.2564  
  2.2565    };
  2.2566  
  2.2567 -  /// \brief Just gives back a node splitter
  2.2568 +  /// \brief Returns a (read-only) SplitNodes adaptor
  2.2569    ///
  2.2570 -  /// Just gives back a node splitter
  2.2571 -  template<typename Digraph>
  2.2572 -  SplitNodes<Digraph>
  2.2573 -  splitNodes(const Digraph& digraph) {
  2.2574 -    return SplitNodes<Digraph>(digraph);
  2.2575 +  /// This function just returns a (read-only) \ref SplitNodes adaptor.
  2.2576 +  /// \ingroup graph_adaptors
  2.2577 +  /// \relates SplitNodes
  2.2578 +  template<typename GR>
  2.2579 +  SplitNodes<GR>
  2.2580 +  splitNodes(const GR& digraph) {
  2.2581 +    return SplitNodes<GR>(digraph);
  2.2582    }
  2.2583  
  2.2584 -
  2.2585  } //namespace lemon
  2.2586  
  2.2587  #endif //LEMON_ADAPTORS_H
     3.1 --- a/lemon/bits/graph_adaptor_extender.h	Thu Jan 08 17:19:26 2009 +0000
     3.2 +++ b/lemon/bits/graph_adaptor_extender.h	Sun Jan 11 15:09:53 2009 +0000
     3.3 @@ -173,10 +173,6 @@
     3.4  
     3.5    };
     3.6  
     3.7 -
     3.8 -  /// \ingroup digraphbits
     3.9 -  ///
    3.10 -  /// \brief Extender for the GraphAdaptors
    3.11    template <typename _Graph>
    3.12    class GraphAdaptorExtender : public _Graph {
    3.13    public: