COIN-OR::LEMON - Graph Library

Changeset 455:5a1e9fdcfd3a in lemon-1.2


Ignore:
Timestamp:
01/11/09 16:09:53 (15 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
456:aff6888e71c9, 463:a2fd8b8d0b30
Parents:
445:75a5df083951 (diff), 454:f599fa651202 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge

Files:
5 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r440 r455  
    6363
    6464/**
    65 @defgroup graph_adaptors Adaptor Classes for graphs
     65@defgroup graph_adaptors Adaptor Classes for Graphs
    6666@ingroup graphs
    67 \brief This group contains several adaptor classes for digraphs and graphs
     67\brief Adaptor classes for digraphs and graphs
     68
     69This group contains several useful adaptor classes for digraphs and graphs.
    6870
    6971The main parts of LEMON are the different graph structures, generic
    70 graph algorithms, graph concepts which couple these, and graph
     72graph algorithms, graph concepts, which couple them, and graph
    7173adaptors. While the previous notions are more or less clear, the
    7274latter one needs further explanation. Graph adaptors are graph classes
     
    7476
    7577A short example makes this much clearer.  Suppose that we have an
    76 instance \c g of a directed graph type say ListDigraph and an algorithm
     78instance \c g of a directed graph type, say ListDigraph and an algorithm
    7779\code
    7880template <typename Digraph>
     
    8284(in time or in memory usage) to copy \c g with the reversed
    8385arcs.  In this case, an adaptor class is used, which (according
    84 to LEMON digraph concepts) works as a digraph.  The adaptor uses the
    85 original digraph structure and digraph operations when methods of the
    86 reversed oriented graph are called.  This means that the adaptor have
    87 minor memory usage, and do not perform sophisticated algorithmic
     86to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
     87The adaptor uses the original digraph structure and digraph operations when
     88methods of the reversed oriented graph are called.  This means that the adaptor
     89have minor memory usage, and do not perform sophisticated algorithmic
    8890actions.  The purpose of it is to give a tool for the cases when a
    8991graph have to be used in a specific alteration.  If this alteration is
    90 obtained by a usual construction like filtering the arc-set or
     92obtained by a usual construction like filtering the node or the arc set or
    9193considering a new orientation, then an adaptor is worthwhile to use.
    9294To come back to the reverse oriented graph, in this situation
     
    9799\code
    98100ListDigraph g;
    99 ReverseDigraph<ListGraph> rg(g);
     101ReverseDigraph<ListDigraph> rg(g);
    100102int result = algorithm(rg);
    101103\endcode
    102 After running the algorithm, the original graph \c g is untouched.
    103 This techniques gives rise to an elegant code, and based on stable
     104During running the algorithm, the original digraph \c g is untouched.
     105This techniques give rise to an elegant code, and based on stable
    104106graph adaptors, complex algorithms can be implemented easily.
    105107
    106 In flow, circulation and bipartite matching problems, the residual
     108In flow, circulation and matching problems, the residual
    107109graph is of particular importance. Combining an adaptor implementing
    108 this, shortest path algorithms and minimum mean cycle algorithms,
     110this with shortest path algorithms or minimum mean cycle algorithms,
    109111a range of weighted and cardinality optimization algorithms can be
    110112obtained. For other examples, the interested user is referred to the
     
    113115The behavior of graph adaptors can be very different. Some of them keep
    114116capabilities of the original graph while in other cases this would be
    115 meaningless. This means that the concepts that they are models of depend
    116 on the graph adaptor, and the wrapped graph(s).
    117 If an arc of \c rg is deleted, this is carried out by deleting the
    118 corresponding arc of \c g, thus the adaptor modifies the original graph.
    119 
    120 But for a residual graph, this operation has no sense.
     117meaningless. This means that the concepts that they meet depend
     118on the graph adaptor, and the wrapped graph.
     119For example, if an arc of a reversed digraph is deleted, this is carried
     120out by deleting the corresponding arc of the original digraph, thus the
     121adaptor modifies the original digraph.
     122However in case of a residual digraph, this operation has no sense.
     123
    121124Let us stand one more example here to simplify your work.
    122 RevGraphAdaptor has constructor
     125ReverseDigraph has constructor
    123126\code
    124127ReverseDigraph(Digraph& digraph);
    125128\endcode
    126 This means that in a situation, when a <tt>const ListDigraph&</tt>
     129This means that in a situation, when a <tt>const %ListDigraph&</tt>
    127130reference to a graph is given, then it have to be instantiated with
    128 <tt>Digraph=const ListDigraph</tt>.
     131<tt>Digraph=const %ListDigraph</tt>.
    129132\code
    130133int algorithm1(const ListDigraph& g) {
    131   RevGraphAdaptor<const ListDigraph> rg(g);
     134  ReverseDigraph<const ListDigraph> rg(g);
    132135  return algorithm2(rg);
    133136}
  • doc/groups.dox

    r451 r455  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/adaptors.h

    r440 r455  
    2222/// \ingroup graph_adaptors
    2323/// \file
    24 /// \brief Several graph adaptors
     24/// \brief Adaptor classes for digraphs and graphs
    2525///
    2626/// This file contains several useful adaptors for digraphs and graphs.
     
    7171    int nodeNum() const { return _digraph->nodeNum(); }
    7272
    73     typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
     73    typedef ArcNumTagIndicator<Digraph> ArcNumTag;
    7474    int arcNum() const { return _digraph->arcNum(); }
    7575
    76     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
    77     Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
     76    typedef FindArcTagIndicator<Digraph> FindArcTag;
     77    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {
    7878      return _digraph->findArc(u, v, prev);
    7979    }
     
    8282    Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
    8383
    84     void erase(const Node& n) const { _digraph->erase(n); }
    85     void erase(const Arc& a) const { _digraph->erase(a); }
    86 
    87     void clear() const { _digraph->clear(); }
     84    void erase(const Node& n) { _digraph->erase(n); }
     85    void erase(const Arc& a) { _digraph->erase(a); }
     86
     87    void clear() { _digraph->clear(); }
    8888
    8989    int id(const Node& n) const { return _digraph->id(n); }
     
    199199    int nodeNum() const { return _graph->nodeNum(); }
    200200
     201    typedef ArcNumTagIndicator<Graph> ArcNumTag;
     202    int arcNum() const { return _graph->arcNum(); }
     203
    201204    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
    202     int arcNum() const { return _graph->arcNum(); }
    203205    int edgeNum() const { return _graph->edgeNum(); }
    204206
     207    typedef FindArcTagIndicator<Graph> FindArcTag;
     208    Arc findArc(const Node& u, const Node& v,
     209                const Arc& prev = INVALID) const {
     210      return _graph->findArc(u, v, prev);
     211    }
     212
    205213    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
    206     Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
    207       return _graph->findArc(u, v, prev);
    208     }
    209     Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
     214    Edge findEdge(const Node& u, const Node& v,
     215                  const Edge& prev = INVALID) const {
    210216      return _graph->findEdge(u, v, prev);
    211217    }
     
    331337    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
    332338
    333     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
     339    typedef FindArcTagIndicator<Digraph> FindArcTag;
    334340    Arc findArc(const Node& u, const Node& v,
    335                 const Arc& prev = INVALID) {
     341                const Arc& prev = INVALID) const {
    336342      return Parent::findArc(v, u, prev);
    337343    }
     
    341347  /// \ingroup graph_adaptors
    342348  ///
    343   /// \brief A digraph adaptor which reverses the orientation of the arcs.
    344   ///
    345   /// ReverseDigraph reverses the arcs in the adapted digraph. The
    346   /// SubDigraph is conform to the \ref concepts::Digraph
    347   /// "Digraph concept".
    348   ///
    349   /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
    350   /// "Digraph concept". The type can be specified to be const.
    351   template<typename _Digraph>
     349  /// \brief Adaptor class for reversing the orientation of the arcs in
     350  /// a digraph.
     351  ///
     352  /// ReverseDigraph can be used for reversing the arcs in a digraph.
     353  /// It conforms to the \ref concepts::Digraph "Digraph" concept.
     354  ///
     355  /// The adapted digraph can also be modified through this adaptor
     356  /// by adding or removing nodes or arcs, unless the \c GR template
     357  /// parameter is set to be \c const.
     358  ///
     359  /// \tparam GR The type of the adapted digraph.
     360  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     361  /// It can also be specified to be \c const.
     362  ///
     363  /// \note The \c Node and \c Arc types of this adaptor and the adapted
     364  /// digraph are convertible to each other.
     365  template<typename GR>
     366#ifdef DOXYGEN
     367  class ReverseDigraph {
     368#else
    352369  class ReverseDigraph :
    353     public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
    354   public:
    355     typedef _Digraph Digraph;
    356     typedef DigraphAdaptorExtender<
    357       ReverseDigraphBase<_Digraph> > Parent;
     370    public DigraphAdaptorExtender<ReverseDigraphBase<GR> > {
     371#endif
     372  public:
     373    /// The type of the adapted digraph.
     374    typedef GR Digraph;
     375    typedef DigraphAdaptorExtender<ReverseDigraphBase<GR> > Parent;
    358376  protected:
    359377    ReverseDigraph() { }
     
    362380    /// \brief Constructor
    363381    ///
    364     /// Creates a reverse digraph adaptor for the given digraph
     382    /// Creates a reverse digraph adaptor for the given digraph.
    365383    explicit ReverseDigraph(Digraph& digraph) {
    366384      Parent::setDigraph(digraph);
     
    368386  };
    369387
    370   /// \brief Just gives back a reverse digraph adaptor
    371   ///
    372   /// Just gives back a reverse digraph adaptor
    373   template<typename Digraph>
    374   ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
    375     return ReverseDigraph<const Digraph>(digraph);
     388  /// \brief Returns a read-only ReverseDigraph adaptor
     389  ///
     390  /// This function just returns a read-only \ref ReverseDigraph adaptor.
     391  /// \ingroup graph_adaptors
     392  /// \relates ReverseDigraph
     393  template<typename GR>
     394  ReverseDigraph<const GR> reverseDigraph(const GR& digraph) {
     395    return ReverseDigraph<const GR>(digraph);
    376396  }
     397
    377398
    378399  template <typename _Digraph, typename _NodeFilterMap,
     
    458479    }
    459480
    460     void hide(const Node& n) const { _node_filter->set(n, false); }
    461     void hide(const Arc& a) const { _arc_filter->set(a, false); }
    462 
    463     void unHide(const Node& n) const { _node_filter->set(n, true); }
    464     void unHide(const Arc& a) const { _arc_filter->set(a, true); }
    465 
    466     bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
    467     bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
     481    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
     482    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
     483
     484    bool status(const Node& n) const { return (*_node_filter)[n]; }
     485    bool status(const Arc& a) const { return (*_arc_filter)[a]; }
    468486
    469487    typedef False NodeNumTag;
    470     typedef False EdgeNumTag;
    471 
    472     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
     488    typedef False ArcNumTag;
     489
     490    typedef FindArcTagIndicator<Digraph> FindArcTag;
    473491    Arc findArc(const Node& source, const Node& target,
    474                 const Arc& prev = INVALID) {
     492                const Arc& prev = INVALID) const {
    475493      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
    476494        return INVALID;
     
    601619    }
    602620
    603     void hide(const Node& n) const { _node_filter->set(n, false); }
    604     void hide(const Arc& e) const { _arc_filter->set(e, false); }
    605 
    606     void unHide(const Node& n) const { _node_filter->set(n, true); }
    607     void unHide(const Arc& e) const { _arc_filter->set(e, true); }
    608 
    609     bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
    610     bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
     621    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
     622    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
     623
     624    bool status(const Node& n) const { return (*_node_filter)[n]; }
     625    bool status(const Arc& a) const { return (*_arc_filter)[a]; }
    611626
    612627    typedef False NodeNumTag;
    613     typedef False EdgeNumTag;
    614 
    615     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
     628    typedef False ArcNumTag;
     629
     630    typedef FindArcTagIndicator<Digraph> FindArcTag;
    616631    Arc findArc(const Node& source, const Node& target,
    617                 const Arc& prev = INVALID) {
     632                const Arc& prev = INVALID) const {
    618633      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
    619634        return INVALID;
     
    680695  /// \ingroup graph_adaptors
    681696  ///
    682   /// \brief An adaptor for hiding nodes and arcs in a digraph
    683   ///
    684   /// SubDigraph hides nodes and arcs in a digraph. A bool node map
    685   /// and a bool arc map must be specified, which define the filters
    686   /// for nodes and arcs. Just the nodes and arcs with true value are
    687   /// shown in the subdigraph. The SubDigraph is conform to the \ref
    688   /// concepts::Digraph "Digraph concept". If the \c _checked parameter
    689   /// is true, then the arcs incident to filtered nodes are also
    690   /// filtered out.
    691   ///
    692   /// \tparam _Digraph It must be conform to the \ref
    693   /// concepts::Digraph "Digraph concept". The type can be specified
    694   /// to const.
    695   /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph.
    696   /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph.
    697   /// \tparam _checked If the parameter is false then the arc filtering
    698   /// is not checked with respect to node filter. Otherwise, each arc
    699   /// is automatically filtered, which is incident to a filtered node.
     697  /// \brief Adaptor class for hiding nodes and arcs in a digraph
     698  ///
     699  /// SubDigraph can be used for hiding nodes and arcs in a digraph.
     700  /// A \c bool node map and a \c bool arc map must be specified, which
     701  /// define the filters for nodes and arcs.
     702  /// Only the nodes and arcs with \c true filter value are
     703  /// shown in the subdigraph. The arcs that are incident to hidden
     704  /// nodes are also filtered out.
     705  /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept.
     706  ///
     707  /// The adapted digraph can also be modified through this adaptor
     708  /// by adding or removing nodes or arcs, unless the \c GR template
     709  /// parameter is set to be \c const.
     710  ///
     711  /// \tparam GR The type of the adapted digraph.
     712  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     713  /// It can also be specified to be \c const.
     714  /// \tparam NF The type of the node filter map.
     715  /// It must be a \c bool (or convertible) node map of the
     716  /// adapted digraph. The default type is
     717  /// \ref concepts::Digraph::NodeMap "GR::NodeMap<bool>".
     718  /// \tparam AF The type of the arc filter map.
     719  /// It must be \c bool (or convertible) arc map of the
     720  /// adapted digraph. The default type is
     721  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>".
     722  ///
     723  /// \note The \c Node and \c Arc types of this adaptor and the adapted
     724  /// digraph are convertible to each other.
    700725  ///
    701726  /// \see FilterNodes
    702727  /// \see FilterArcs
    703   template<typename _Digraph,
    704            typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
    705            typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
    706            bool _checked = true>
    707   class SubDigraph
    708     : public DigraphAdaptorExtender<
    709       SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
    710   public:
    711     typedef _Digraph Digraph;
    712     typedef _NodeFilterMap NodeFilterMap;
    713     typedef _ArcFilterMap ArcFilterMap;
    714 
    715     typedef DigraphAdaptorExtender<
    716       SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >
    717     Parent;
     728#ifdef DOXYGEN
     729  template<typename GR, typename NF, typename AF>
     730  class SubDigraph {
     731#else
     732  template<typename GR,
     733           typename NF = typename GR::template NodeMap<bool>,
     734           typename AF = typename GR::template ArcMap<bool> >
     735  class SubDigraph :
     736    public DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> > {
     737#endif
     738  public:
     739    /// The type of the adapted digraph.
     740    typedef GR Digraph;
     741    /// The type of the node filter map.
     742    typedef NF NodeFilterMap;
     743    /// The type of the arc filter map.
     744    typedef AF ArcFilterMap;
     745
     746    typedef DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> >
     747      Parent;
    718748
    719749    typedef typename Parent::Node Node;
     
    726756    /// \brief Constructor
    727757    ///
    728     /// Creates a subdigraph for the given digraph with
    729     /// given node and arc map filters.
     758    /// Creates a subdigraph for the given digraph with the
     759    /// given node and arc filter maps.
    730760    SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
    731761               ArcFilterMap& arc_filter) {
     
    735765    }
    736766
    737     /// \brief Hides the node of the graph
    738     ///
    739     /// This function hides \c n in the digraph, i.e. the iteration
    740     /// jumps over it. This is done by simply setting the value of \c n
    741     /// to be false in the corresponding node-map.
    742     void hide(const Node& n) const { Parent::hide(n); }
    743 
    744     /// \brief Hides the arc of the graph
    745     ///
    746     /// This function hides \c a in the digraph, i.e. the iteration
    747     /// jumps over it. This is done by simply setting the value of \c a
    748     /// to be false in the corresponding arc-map.
    749     void hide(const Arc& a) const { Parent::hide(a); }
    750 
    751     /// \brief Unhides the node of the graph
    752     ///
    753     /// The value of \c n is set to be true in the node-map which stores
    754     /// hide information. If \c n was hidden previuosly, then it is shown
    755     /// again
    756     void unHide(const Node& n) const { Parent::unHide(n); }
    757 
    758     /// \brief Unhides the arc of the graph
    759     ///
    760     /// The value of \c a is set to be true in the arc-map which stores
    761     /// hide information. If \c a was hidden previuosly, then it is shown
    762     /// again
    763     void unHide(const Arc& a) const { Parent::unHide(a); }
    764 
    765     /// \brief Returns true if \c n is hidden.
    766     ///
    767     /// Returns true if \c n is hidden.
    768     ///
    769     bool hidden(const Node& n) const { return Parent::hidden(n); }
    770 
    771     /// \brief Returns true if \c a is hidden.
    772     ///
    773     /// Returns true if \c a is hidden.
    774     ///
    775     bool hidden(const Arc& a) const { return Parent::hidden(a); }
     767    /// \brief Sets the status of the given node
     768    ///
     769    /// This function sets the status of the given node.
     770    /// It is done by simply setting the assigned value of \c n
     771    /// to \c v in the node filter map.
     772    void status(const Node& n, bool v) const { Parent::status(n, v); }
     773
     774    /// \brief Sets the status of the given arc
     775    ///
     776    /// This function sets the status of the given arc.
     777    /// It is done by simply setting the assigned value of \c a
     778    /// to \c v in the arc filter map.
     779    void status(const Arc& a, bool v) const { Parent::status(a, v); }
     780
     781    /// \brief Returns the status of the given node
     782    ///
     783    /// This function returns the status of the given node.
     784    /// It is \c true if the given node is enabled (i.e. not hidden).
     785    bool status(const Node& n) const { return Parent::status(n); }
     786
     787    /// \brief Returns the status of the given arc
     788    ///
     789    /// This function returns the status of the given arc.
     790    /// It is \c true if the given arc is enabled (i.e. not hidden).
     791    bool status(const Arc& a) const { return Parent::status(a); }
     792
     793    /// \brief Disables the given node
     794    ///
     795    /// This function disables the given node in the subdigraph,
     796    /// so the iteration jumps over it.
     797    /// It is the same as \ref status() "status(n, false)".
     798    void disable(const Node& n) const { Parent::status(n, false); }
     799
     800    /// \brief Disables the given arc
     801    ///
     802    /// This function disables the given arc in the subdigraph,
     803    /// so the iteration jumps over it.
     804    /// It is the same as \ref status() "status(a, false)".
     805    void disable(const Arc& a) const { Parent::status(a, false); }
     806
     807    /// \brief Enables the given node
     808    ///
     809    /// This function enables the given node in the subdigraph.
     810    /// It is the same as \ref status() "status(n, true)".
     811    void enable(const Node& n) const { Parent::status(n, true); }
     812
     813    /// \brief Enables the given arc
     814    ///
     815    /// This function enables the given arc in the subdigraph.
     816    /// It is the same as \ref status() "status(a, true)".
     817    void enable(const Arc& a) const { Parent::status(a, true); }
    776818
    777819  };
    778820
    779   /// \brief Just gives back a subdigraph
    780   ///
    781   /// Just gives back a subdigraph
    782   template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
    783   SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
    784   subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
    785     return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
    786       (digraph, nfm, afm);
     821  /// \brief Returns a read-only SubDigraph adaptor
     822  ///
     823  /// This function just returns a read-only \ref SubDigraph adaptor.
     824  /// \ingroup graph_adaptors
     825  /// \relates SubDigraph
     826  template<typename GR, typename NF, typename AF>
     827  SubDigraph<const GR, NF, AF>
     828  subDigraph(const GR& digraph,
     829             NF& node_filter_map, AF& arc_filter_map) {
     830    return SubDigraph<const GR, NF, AF>
     831      (digraph, node_filter_map, arc_filter_map);
    787832  }
    788833
    789   template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
    790   SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
    791   subDigraph(const Digraph& digraph,
    792              const NodeFilterMap& nfm, ArcFilterMap& afm) {
    793     return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
    794       (digraph, nfm, afm);
     834  template<typename GR, typename NF, typename AF>
     835  SubDigraph<const GR, const NF, AF>
     836  subDigraph(const GR& digraph,
     837             const NF& node_filter_map, AF& arc_filter_map) {
     838    return SubDigraph<const GR, const NF, AF>
     839      (digraph, node_filter_map, arc_filter_map);
    795840  }
    796841
    797   template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
    798   SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
    799   subDigraph(const Digraph& digraph,
    800              NodeFilterMap& nfm, const ArcFilterMap& afm) {
    801     return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
    802       (digraph, nfm, afm);
     842  template<typename GR, typename NF, typename AF>
     843  SubDigraph<const GR, NF, const AF>
     844  subDigraph(const GR& digraph,
     845             NF& node_filter_map, const AF& arc_filter_map) {
     846    return SubDigraph<const GR, NF, const AF>
     847      (digraph, node_filter_map, arc_filter_map);
    803848  }
    804849
    805   template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
    806   SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>
    807   subDigraph(const Digraph& digraph,
    808              const NodeFilterMap& nfm, const ArcFilterMap& afm) {
    809     return SubDigraph<const Digraph, const NodeFilterMap,
    810       const ArcFilterMap>(digraph, nfm, afm);
     850  template<typename GR, typename NF, typename AF>
     851  SubDigraph<const GR, const NF, const AF>
     852  subDigraph(const GR& digraph,
     853             const NF& node_filter_map, const AF& arc_filter_map) {
     854    return SubDigraph<const GR, const NF, const AF>
     855      (digraph, node_filter_map, arc_filter_map);
    811856  }
    812857
    813858
    814   template <typename _Graph, typename NodeFilterMap,
    815             typename EdgeFilterMap, bool _checked = true>
     859  template <typename _Graph, typename _NodeFilterMap,
     860            typename _EdgeFilterMap, bool _checked = true>
    816861  class SubGraphBase : public GraphAdaptorBase<_Graph> {
    817862  public:
    818863    typedef _Graph Graph;
     864    typedef _NodeFilterMap NodeFilterMap;
     865    typedef _EdgeFilterMap EdgeFilterMap;
     866
    819867    typedef SubGraphBase Adaptor;
    820868    typedef GraphAdaptorBase<_Graph> Parent;
     
    926974    }
    927975
    928     void hide(const Node& n) const { _node_filter_map->set(n, false); }
    929     void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
    930 
    931     void unHide(const Node& n) const { _node_filter_map->set(n, true); }
    932     void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
    933 
    934     bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
    935     bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
     976    void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
     977    void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
     978
     979    bool status(const Node& n) const { return (*_node_filter_map)[n]; }
     980    bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
    936981
    937982    typedef False NodeNumTag;
     983    typedef False ArcNumTag;
    938984    typedef False EdgeNumTag;
    939985
    940     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
     986    typedef FindArcTagIndicator<Graph> FindArcTag;
    941987    Arc findArc(const Node& u, const Node& v,
    942                 const Arc& prev = INVALID) {
     988                const Arc& prev = INVALID) const {
    943989      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
    944990        return INVALID;
     
    950996      return arc;
    951997    }
     998
     999    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
    9521000    Edge findEdge(const Node& u, const Node& v,
    953                   const Edge& prev = INVALID) {
     1001                  const Edge& prev = INVALID) const {
    9541002      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
    9551003        return INVALID;
     
    10401088  };
    10411089
    1042   template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
    1043   class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
     1090  template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>
     1091  class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false>
    10441092    : public GraphAdaptorBase<_Graph> {
    10451093  public:
    10461094    typedef _Graph Graph;
     1095    typedef _NodeFilterMap NodeFilterMap;
     1096    typedef _EdgeFilterMap EdgeFilterMap;
     1097
    10471098    typedef SubGraphBase Adaptor;
    10481099    typedef GraphAdaptorBase<_Graph> Parent;
     
    11221173    }
    11231174
    1124     void hide(const Node& n) const { _node_filter_map->set(n, false); }
    1125     void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
    1126 
    1127     void unHide(const Node& n) const { _node_filter_map->set(n, true); }
    1128     void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
    1129 
    1130     bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
    1131     bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
     1175    void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
     1176    void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
     1177
     1178    bool status(const Node& n) const { return (*_node_filter_map)[n]; }
     1179    bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
    11321180
    11331181    typedef False NodeNumTag;
     1182    typedef False ArcNumTag;
    11341183    typedef False EdgeNumTag;
    11351184
    1136     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
     1185    typedef FindArcTagIndicator<Graph> FindArcTag;
    11371186    Arc findArc(const Node& u, const Node& v,
    1138                 const Arc& prev = INVALID) {
     1187                const Arc& prev = INVALID) const {
    11391188      Arc arc = Parent::findArc(u, v, prev);
    11401189      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
     
    11431192      return arc;
    11441193    }
     1194
     1195    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
    11451196    Edge findEdge(const Node& u, const Node& v,
    1146                   const Edge& prev = INVALID) {
     1197                  const Edge& prev = INVALID) const {
    11471198      Edge edge = Parent::findEdge(u, v, prev);
    11481199      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
     
    12321283  /// \ingroup graph_adaptors
    12331284  ///
    1234   /// \brief A graph adaptor for hiding nodes and edges in an
    1235   /// undirected graph.
    1236   ///
    1237   /// SubGraph hides nodes and edges in a graph. A bool node map and a
    1238   /// bool edge map must be specified, which define the filters for
    1239   /// nodes and edges. Just the nodes and edges with true value are
    1240   /// shown in the subgraph. The SubGraph is conform to the \ref
    1241   /// concepts::Graph "Graph concept". If the \c _checked parameter is
    1242   /// true, then the edges incident to filtered nodes are also
    1243   /// filtered out.
    1244   ///
    1245   /// \tparam _Graph It must be conform to the \ref
    1246   /// concepts::Graph "Graph concept". The type can be specified
    1247   /// to const.
    1248   /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
    1249   /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph.
    1250   /// \tparam _checked If the parameter is false then the edge filtering
    1251   /// is not checked with respect to node filter. Otherwise, each edge
    1252   /// is automatically filtered, which is incident to a filtered node.
     1285  /// \brief Adaptor class for hiding nodes and edges in an undirected
     1286  /// graph.
     1287  ///
     1288  /// SubGraph can be used for hiding nodes and edges in a graph.
     1289  /// A \c bool node map and a \c bool edge map must be specified, which
     1290  /// define the filters for nodes and edges.
     1291  /// Only the nodes and edges with \c true filter value are
     1292  /// shown in the subgraph. The edges that are incident to hidden
     1293  /// nodes are also filtered out.
     1294  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
     1295  ///
     1296  /// The adapted graph can also be modified through this adaptor
     1297  /// by adding or removing nodes or edges, unless the \c GR template
     1298  /// parameter is set to be \c const.
     1299  ///
     1300  /// \tparam GR The type of the adapted graph.
     1301  /// It must conform to the \ref concepts::Graph "Graph" concept.
     1302  /// It can also be specified to be \c const.
     1303  /// \tparam NF The type of the node filter map.
     1304  /// It must be a \c bool (or convertible) node map of the
     1305  /// adapted graph. The default type is
     1306  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
     1307  /// \tparam EF The type of the edge filter map.
     1308  /// It must be a \c bool (or convertible) edge map of the
     1309  /// adapted graph. The default type is
     1310  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
     1311  ///
     1312  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
     1313  /// adapted graph are convertible to each other.
    12531314  ///
    12541315  /// \see FilterNodes
    12551316  /// \see FilterEdges
    1256   template<typename _Graph, typename NodeFilterMap,
    1257            typename EdgeFilterMap, bool _checked = true>
    1258   class SubGraph
    1259     : public GraphAdaptorExtender<
    1260       SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {
    1261   public:
    1262     typedef _Graph Graph;
    1263     typedef GraphAdaptorExtender<
    1264       SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
     1317#ifdef DOXYGEN
     1318  template<typename GR, typename NF, typename EF>
     1319  class SubGraph {
     1320#else
     1321  template<typename GR,
     1322           typename NF = typename GR::template NodeMap<bool>,
     1323           typename EF = typename GR::template EdgeMap<bool> >
     1324  class SubGraph :
     1325    public GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> > {
     1326#endif
     1327  public:
     1328    /// The type of the adapted graph.
     1329    typedef GR Graph;
     1330    /// The type of the node filter map.
     1331    typedef NF NodeFilterMap;
     1332    /// The type of the edge filter map.
     1333    typedef EF EdgeFilterMap;
     1334
     1335    typedef GraphAdaptorExtender< SubGraphBase<GR, NF, EF, true> >
     1336      Parent;
    12651337
    12661338    typedef typename Parent::Node Node;
     
    12731345    /// \brief Constructor
    12741346    ///
    1275     /// Creates a subgraph for the given graph with given node and
    1276     /// edge map filters.
    1277     SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,
     1347    /// Creates a subgraph for the given graph with the given node
     1348    /// and edge filter maps.
     1349    SubGraph(Graph& graph, NodeFilterMap& node_filter_map,
    12781350             EdgeFilterMap& edge_filter_map) {
    1279       setGraph(_graph);
     1351      setGraph(graph);
    12801352      setNodeFilterMap(node_filter_map);
    12811353      setEdgeFilterMap(edge_filter_map);
    12821354    }
    12831355
    1284     /// \brief Hides the node of the graph
    1285     ///
    1286     /// This function hides \c n in the graph, i.e. the iteration
    1287     /// jumps over it. This is done by simply setting the value of \c n
    1288     /// to be false in the corresponding node-map.
    1289     void hide(const Node& n) const { Parent::hide(n); }
    1290 
    1291     /// \brief Hides the edge of the graph
    1292     ///
    1293     /// This function hides \c e in the graph, i.e. the iteration
    1294     /// jumps over it. This is done by simply setting the value of \c e
    1295     /// to be false in the corresponding edge-map.
    1296     void hide(const Edge& e) const { Parent::hide(e); }
    1297 
    1298     /// \brief Unhides the node of the graph
    1299     ///
    1300     /// The value of \c n is set to be true in the node-map which stores
    1301     /// hide information. If \c n was hidden previuosly, then it is shown
    1302     /// again
    1303     void unHide(const Node& n) const { Parent::unHide(n); }
    1304 
    1305     /// \brief Unhides the edge of the graph
    1306     ///
    1307     /// The value of \c e is set to be true in the edge-map which stores
    1308     /// hide information. If \c e was hidden previuosly, then it is shown
    1309     /// again
    1310     void unHide(const Edge& e) const { Parent::unHide(e); }
    1311 
    1312     /// \brief Returns true if \c n is hidden.
    1313     ///
    1314     /// Returns true if \c n is hidden.
    1315     ///
    1316     bool hidden(const Node& n) const { return Parent::hidden(n); }
    1317 
    1318     /// \brief Returns true if \c e is hidden.
    1319     ///
    1320     /// Returns true if \c e is hidden.
    1321     ///
    1322     bool hidden(const Edge& e) const { return Parent::hidden(e); }
     1356    /// \brief Sets the status of the given node
     1357    ///
     1358    /// This function sets the status of the given node.
     1359    /// It is done by simply setting the assigned value of \c n
     1360    /// to \c v in the node filter map.
     1361    void status(const Node& n, bool v) const { Parent::status(n, v); }
     1362
     1363    /// \brief Sets the status of the given edge
     1364    ///
     1365    /// This function sets the status of the given edge.
     1366    /// It is done by simply setting the assigned value of \c e
     1367    /// to \c v in the edge filter map.
     1368    void status(const Edge& e, bool v) const { Parent::status(e, v); }
     1369
     1370    /// \brief Returns the status of the given node
     1371    ///
     1372    /// This function returns the status of the given node.
     1373    /// It is \c true if the given node is enabled (i.e. not hidden).
     1374    bool status(const Node& n) const { return Parent::status(n); }
     1375
     1376    /// \brief Returns the status of the given edge
     1377    ///
     1378    /// This function returns the status of the given edge.
     1379    /// It is \c true if the given edge is enabled (i.e. not hidden).
     1380    bool status(const Edge& e) const { return Parent::status(e); }
     1381
     1382    /// \brief Disables the given node
     1383    ///
     1384    /// This function disables the given node in the subdigraph,
     1385    /// so the iteration jumps over it.
     1386    /// It is the same as \ref status() "status(n, false)".
     1387    void disable(const Node& n) const { Parent::status(n, false); }
     1388
     1389    /// \brief Disables the given edge
     1390    ///
     1391    /// This function disables the given edge in the subgraph,
     1392    /// so the iteration jumps over it.
     1393    /// It is the same as \ref status() "status(e, false)".
     1394    void disable(const Edge& e) const { Parent::status(e, false); }
     1395
     1396    /// \brief Enables the given node
     1397    ///
     1398    /// This function enables the given node in the subdigraph.
     1399    /// It is the same as \ref status() "status(n, true)".
     1400    void enable(const Node& n) const { Parent::status(n, true); }
     1401
     1402    /// \brief Enables the given edge
     1403    ///
     1404    /// This function enables the given edge in the subgraph.
     1405    /// It is the same as \ref status() "status(e, true)".
     1406    void enable(const Edge& e) const { Parent::status(e, true); }
     1407
    13231408  };
    13241409
    1325   /// \brief Just gives back a subgraph
    1326   ///
    1327   /// Just gives back a subgraph
    1328   template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
    1329   SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
    1330   subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
    1331     return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);
     1410  /// \brief Returns a read-only SubGraph adaptor
     1411  ///
     1412  /// This function just returns a read-only \ref SubGraph adaptor.
     1413  /// \ingroup graph_adaptors
     1414  /// \relates SubGraph
     1415  template<typename GR, typename NF, typename EF>
     1416  SubGraph<const GR, NF, EF>
     1417  subGraph(const GR& graph,
     1418           NF& node_filter_map, EF& edge_filter_map) {
     1419    return SubGraph<const GR, NF, EF>
     1420      (graph, node_filter_map, edge_filter_map);
    13321421  }
    13331422
    1334   template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
    1335   SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
    1336   subGraph(const Graph& graph,
    1337            const NodeFilterMap& nfm, ArcFilterMap& efm) {
    1338     return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
    1339       (graph, nfm, efm);
     1423  template<typename GR, typename NF, typename EF>
     1424  SubGraph<const GR, const NF, EF>
     1425  subGraph(const GR& graph,
     1426           const NF& node_filter_map, EF& edge_filter_map) {
     1427    return SubGraph<const GR, const NF, EF>
     1428      (graph, node_filter_map, edge_filter_map);
    13401429  }
    13411430
    1342   template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
    1343   SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
    1344   subGraph(const Graph& graph,
    1345            NodeFilterMap& nfm, const ArcFilterMap& efm) {
    1346     return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
    1347       (graph, nfm, efm);
     1431  template<typename GR, typename NF, typename EF>
     1432  SubGraph<const GR, NF, const EF>
     1433  subGraph(const GR& graph,
     1434           NF& node_filter_map, const EF& edge_filter_map) {
     1435    return SubGraph<const GR, NF, const EF>
     1436      (graph, node_filter_map, edge_filter_map);
    13481437  }
    13491438
    1350   template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
    1351   SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
    1352   subGraph(const Graph& graph,
    1353            const NodeFilterMap& nfm, const ArcFilterMap& efm) {
    1354     return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
    1355       (graph, nfm, efm);
     1439  template<typename GR, typename NF, typename EF>
     1440  SubGraph<const GR, const NF, const EF>
     1441  subGraph(const GR& graph,
     1442           const NF& node_filter_map, const EF& edge_filter_map) {
     1443    return SubGraph<const GR, const NF, const EF>
     1444      (graph, node_filter_map, edge_filter_map);
    13561445  }
    13571446
     1447
    13581448  /// \ingroup graph_adaptors
    13591449  ///
    1360   /// \brief An adaptor for hiding nodes from a digraph or a graph.
    1361   ///
    1362   /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool
    1363   /// node map must be specified, which defines the filters for
    1364   /// nodes. Just the unfiltered nodes and the arcs or edges incident
    1365   /// to unfiltered nodes are shown in the subdigraph or subgraph. The
    1366   /// FilterNodes is conform to the \ref concepts::Digraph
    1367   /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending
    1368   /// on the \c _Digraph template parameter. If the \c _checked
    1369   /// parameter is true, then the arc or edges incident to filtered nodes
    1370   /// are also filtered out.
    1371   ///
    1372   /// \tparam _Digraph It must be conform to the \ref
    1373   /// concepts::Digraph "Digraph concept" or \ref concepts::Graph
    1374   /// "Graph concept". The type can be specified to be const.
    1375   /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
    1376   /// \tparam _checked If the parameter is false then the arc or edge
    1377   /// filtering is not checked with respect to node filter. In this
    1378   /// case just isolated nodes can be filtered out from the
    1379   /// graph.
     1450  /// \brief Adaptor class for hiding nodes in a digraph or a graph.
     1451  ///
     1452  /// FilterNodes adaptor can be used for hiding nodes in a digraph or a
     1453  /// graph. A \c bool node map must be specified, which defines the filter
     1454  /// for the nodes. Only the nodes with \c true filter value and the
     1455  /// arcs/edges incident to nodes both with \c true filter value are shown
     1456  /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph
     1457  /// "Digraph" concept or the \ref concepts::Graph "Graph" concept
     1458  /// depending on the \c GR template parameter.
     1459  ///
     1460  /// The adapted (di)graph can also be modified through this adaptor
     1461  /// by adding or removing nodes or arcs/edges, unless the \c GR template
     1462  /// parameter is set to be \c const.
     1463  ///
     1464  /// \tparam GR The type of the adapted digraph or graph.
     1465  /// It must conform to the \ref concepts::Digraph "Digraph" concept
     1466  /// or the \ref concepts::Graph "Graph" concept.
     1467  /// It can also be specified to be \c const.
     1468  /// \tparam NF The type of the node filter map.
     1469  /// It must be a \c bool (or convertible) node map of the
     1470  /// adapted (di)graph. The default type is
     1471  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
     1472  ///
     1473  /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the
     1474  /// adapted (di)graph are convertible to each other.
    13801475#ifdef DOXYGEN
    1381   template<typename _Digraph,
    1382            typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
    1383            bool _checked = true>
     1476  template<typename GR, typename NF>
     1477  class FilterNodes {
    13841478#else
    1385   template<typename _Digraph,
    1386            typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
    1387            bool _checked = true,
     1479  template<typename GR,
     1480           typename NF = typename GR::template NodeMap<bool>,
    13881481           typename Enable = void>
     1482  class FilterNodes :
     1483    public DigraphAdaptorExtender<
     1484      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> > {
    13891485#endif
    1390   class FilterNodes
    1391     : public SubDigraph<_Digraph, _NodeFilterMap,
    1392                         ConstMap<typename _Digraph::Arc, bool>, _checked> {
    1393   public:
    1394 
    1395     typedef _Digraph Digraph;
    1396     typedef _NodeFilterMap NodeFilterMap;
    1397 
    1398     typedef SubDigraph<Digraph, NodeFilterMap,
    1399                        ConstMap<typename Digraph::Arc, bool>, _checked>
    1400     Parent;
     1486  public:
     1487
     1488    typedef GR Digraph;
     1489    typedef NF NodeFilterMap;
     1490
     1491    typedef DigraphAdaptorExtender<
     1492      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> >
     1493      Parent;
    14011494
    14021495    typedef typename Parent::Node Node;
     
    14131506    /// \brief Constructor
    14141507    ///
    1415     /// Creates an adaptor for the given digraph or graph with
     1508    /// Creates a subgraph for the given digraph or graph with the
    14161509    /// given node filter map.
    1417     FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :
    1418       Parent(), const_true_map(true) {
    1419       Parent::setDigraph(_digraph);
     1510    FilterNodes(GR& graph, NodeFilterMap& node_filter) :
     1511      Parent(), const_true_map(true)
     1512    {
     1513      Parent::setDigraph(graph);
    14201514      Parent::setNodeFilterMap(node_filter);
    14211515      Parent::setArcFilterMap(const_true_map);
    14221516    }
    14231517
    1424     /// \brief Hides the node of the graph
    1425     ///
    1426     /// This function hides \c n in the digraph or graph, i.e. the iteration
    1427     /// jumps over it. This is done by simply setting the value of \c n
    1428     /// to be false in the corresponding node map.
    1429     void hide(const Node& n) const { Parent::hide(n); }
    1430 
    1431     /// \brief Unhides the node of the graph
    1432     ///
    1433     /// The value of \c n is set to be true in the node-map which stores
    1434     /// hide information. If \c n was hidden previuosly, then it is shown
    1435     /// again
    1436     void unHide(const Node& n) const { Parent::unHide(n); }
    1437 
    1438     /// \brief Returns true if \c n is hidden.
    1439     ///
    1440     /// Returns true if \c n is hidden.
    1441     ///
    1442     bool hidden(const Node& n) const { return Parent::hidden(n); }
     1518    /// \brief Sets the status of the given node
     1519    ///
     1520    /// This function sets the status of the given node.
     1521    /// It is done by simply setting the assigned value of \c n
     1522    /// to \c v in the node filter map.
     1523    void status(const Node& n, bool v) const { Parent::status(n, v); }
     1524
     1525    /// \brief Returns the status of the given node
     1526    ///
     1527    /// This function returns the status of the given node.
     1528    /// It is \c true if the given node is enabled (i.e. not hidden).
     1529    bool status(const Node& n) const { return Parent::status(n); }
     1530
     1531    /// \brief Disables the given node
     1532    ///
     1533    /// This function disables the given node, so the iteration
     1534    /// jumps over it.
     1535    /// It is the same as \ref status() "status(n, false)".
     1536    void disable(const Node& n) const { Parent::status(n, false); }
     1537
     1538    /// \brief Enables the given node
     1539    ///
     1540    /// This function enables the given node.
     1541    /// It is the same as \ref status() "status(n, true)".
     1542    void enable(const Node& n) const { Parent::status(n, true); }
    14431543
    14441544  };
    14451545
    1446   template<typename _Graph, typename _NodeFilterMap, bool _checked>
    1447   class FilterNodes<_Graph, _NodeFilterMap, _checked,
    1448                     typename enable_if<UndirectedTagIndicator<_Graph> >::type>
    1449     : public SubGraph<_Graph, _NodeFilterMap,
    1450                       ConstMap<typename _Graph::Edge, bool>, _checked> {
    1451   public:
    1452     typedef _Graph Graph;
    1453     typedef _NodeFilterMap NodeFilterMap;
    1454     typedef SubGraph<Graph, NodeFilterMap,
    1455                      ConstMap<typename Graph::Edge, bool> > Parent;
     1546  template<typename GR, typename NF>
     1547  class FilterNodes<GR, NF,
     1548                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
     1549    public GraphAdaptorExtender<
     1550      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> > {
     1551
     1552  public:
     1553    typedef GR Graph;
     1554    typedef NF NodeFilterMap;
     1555    typedef GraphAdaptorExtender<
     1556      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> >
     1557      Parent;
    14561558
    14571559    typedef typename Parent::Node Node;
     
    14721574    }
    14731575
    1474     void hide(const Node& n) const { Parent::hide(n); }
    1475     void unHide(const Node& n) const { Parent::unHide(n); }
    1476     bool hidden(const Node& n) const { return Parent::hidden(n); }
     1576    void status(const Node& n, bool v) const { Parent::status(n, v); }
     1577    bool status(const Node& n) const { return Parent::status(n); }
     1578    void disable(const Node& n) const { Parent::status(n, false); }
     1579    void enable(const Node& n) const { Parent::status(n, true); }
    14771580
    14781581  };
    14791582
    14801583
    1481   /// \brief Just gives back a FilterNodes adaptor
    1482   ///
    1483   /// Just gives back a FilterNodes adaptor
    1484   template<typename Digraph, typename NodeFilterMap>
    1485   FilterNodes<const Digraph, NodeFilterMap>
    1486   filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
    1487     return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
     1584  /// \brief Returns a read-only FilterNodes adaptor
     1585  ///
     1586  /// This function just returns a read-only \ref FilterNodes adaptor.
     1587  /// \ingroup graph_adaptors
     1588  /// \relates FilterNodes
     1589  template<typename GR, typename NF>
     1590  FilterNodes<const GR, NF>
     1591  filterNodes(const GR& graph, NF& node_filter_map) {
     1592    return FilterNodes<const GR, NF>(graph, node_filter_map);
    14881593  }
    14891594
    1490   template<typename Digraph, typename NodeFilterMap>
    1491   FilterNodes<const Digraph, const NodeFilterMap>
    1492   filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
    1493     return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
     1595  template<typename GR, typename NF>
     1596  FilterNodes<const GR, const NF>
     1597  filterNodes(const GR& graph, const NF& node_filter_map) {
     1598    return FilterNodes<const GR, const NF>(graph, node_filter_map);
    14941599  }
    14951600
    14961601  /// \ingroup graph_adaptors
    14971602  ///
    1498   /// \brief An adaptor for hiding arcs from a digraph.
    1499   ///
    1500   /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must
    1501   /// be specified, which defines the filters for arcs. Just the
    1502   /// unfiltered arcs are shown in the subdigraph. The FilterArcs is
    1503   /// conform to the \ref concepts::Digraph "Digraph concept".
    1504   ///
    1505   /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
    1506   /// "Digraph concept". The type can be specified to be const.
    1507   /// \tparam _ArcFilterMap A bool valued arc map of the the adapted
    1508   /// graph.
    1509   template<typename _Digraph, typename _ArcFilterMap>
     1603  /// \brief Adaptor class for hiding arcs in a digraph.
     1604  ///
     1605  /// FilterArcs adaptor can be used for hiding arcs in a digraph.
     1606  /// A \c bool arc map must be specified, which defines the filter for
     1607  /// the arcs. Only the arcs with \c true filter value are shown in the
     1608  /// subdigraph. This adaptor conforms to the \ref concepts::Digraph
     1609  /// "Digraph" concept.
     1610  ///
     1611  /// The adapted digraph can also be modified through this adaptor
     1612  /// by adding or removing nodes or arcs, unless the \c GR template
     1613  /// parameter is set to be \c const.
     1614  ///
     1615  /// \tparam GR The type of the adapted digraph.
     1616  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     1617  /// It can also be specified to be \c const.
     1618  /// \tparam AF The type of the arc filter map.
     1619  /// It must be a \c bool (or convertible) arc map of the
     1620  /// adapted digraph. The default type is
     1621  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>".
     1622  ///
     1623  /// \note The \c Node and \c Arc types of this adaptor and the adapted
     1624  /// digraph are convertible to each other.
     1625#ifdef DOXYGEN
     1626  template<typename GR,
     1627           typename AF>
     1628  class FilterArcs {
     1629#else
     1630  template<typename GR,
     1631           typename AF = typename GR::template ArcMap<bool> >
    15101632  class FilterArcs :
    1511     public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
    1512                       _ArcFilterMap, false> {
    1513   public:
    1514     typedef _Digraph Digraph;
    1515     typedef _ArcFilterMap ArcFilterMap;
    1516 
    1517     typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
    1518                        ArcFilterMap, false> Parent;
     1633    public DigraphAdaptorExtender<
     1634      SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> > {
     1635#endif
     1636  public:
     1637    /// The type of the adapted digraph.
     1638    typedef GR Digraph;
     1639    /// The type of the arc filter map.
     1640    typedef AF ArcFilterMap;
     1641
     1642    typedef DigraphAdaptorExtender<
     1643      SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> >
     1644      Parent;
    15191645
    15201646    typedef typename Parent::Arc Arc;
     
    15311657    /// \brief Constructor
    15321658    ///
    1533     /// Creates a FilterArcs adaptor for the given graph with
    1534     /// given arc map filter.
     1659    /// Creates a subdigraph for the given digraph with the given arc
     1660    /// filter map.
    15351661    FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
    15361662      : Parent(), const_true_map(true) {
     
    15401666    }
    15411667
    1542     /// \brief Hides the arc of the graph
    1543     ///
    1544     /// This function hides \c a in the graph, i.e. the iteration
    1545     /// jumps over it. This is done by simply setting the value of \c a
    1546     /// to be false in the corresponding arc map.
    1547     void hide(const Arc& a) const { Parent::hide(a); }
    1548 
    1549     /// \brief Unhides the arc of the graph
    1550     ///
    1551     /// The value of \c a is set to be true in the arc-map which stores
    1552     /// hide information. If \c a was hidden previuosly, then it is shown
    1553     /// again
    1554     void unHide(const Arc& a) const { Parent::unHide(a); }
    1555 
    1556     /// \brief Returns true if \c a is hidden.
    1557     ///
    1558     /// Returns true if \c a is hidden.
    1559     ///
    1560     bool hidden(const Arc& a) const { return Parent::hidden(a); }
     1668    /// \brief Sets the status of the given arc
     1669    ///
     1670    /// This function sets the status of the given arc.
     1671    /// It is done by simply setting the assigned value of \c a
     1672    /// to \c v in the arc filter map.
     1673    void status(const Arc& a, bool v) const { Parent::status(a, v); }
     1674
     1675    /// \brief Returns the status of the given arc
     1676    ///
     1677    /// This function returns the status of the given arc.
     1678    /// It is \c true if the given arc is enabled (i.e. not hidden).
     1679    bool status(const Arc& a) const { return Parent::status(a); }
     1680
     1681    /// \brief Disables the given arc
     1682    ///
     1683    /// This function disables the given arc in the subdigraph,
     1684    /// so the iteration jumps over it.
     1685    /// It is the same as \ref status() "status(a, false)".
     1686    void disable(const Arc& a) const { Parent::status(a, false); }
     1687
     1688    /// \brief Enables the given arc
     1689    ///
     1690    /// This function enables the given arc in the subdigraph.
     1691    /// It is the same as \ref status() "status(a, true)".
     1692    void enable(const Arc& a) const { Parent::status(a, true); }
    15611693
    15621694  };
    15631695
    1564   /// \brief Just gives back an FilterArcs adaptor
    1565   ///
    1566   /// Just gives back an FilterArcs adaptor
    1567   template<typename Digraph, typename ArcFilterMap>
    1568   FilterArcs<const Digraph, ArcFilterMap>
    1569   filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
    1570     return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
     1696  /// \brief Returns a read-only FilterArcs adaptor
     1697  ///
     1698  /// This function just returns a read-only \ref FilterArcs adaptor.
     1699  /// \ingroup graph_adaptors
     1700  /// \relates FilterArcs
     1701  template<typename GR, typename AF>
     1702  FilterArcs<const GR, AF>
     1703  filterArcs(const GR& digraph, AF& arc_filter_map) {
     1704    return FilterArcs<const GR, AF>(digraph, arc_filter_map);
    15711705  }
    15721706
    1573   template<typename Digraph, typename ArcFilterMap>
    1574   FilterArcs<const Digraph, const ArcFilterMap>
    1575   filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
    1576     return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
     1707  template<typename GR, typename AF>
     1708  FilterArcs<const GR, const AF>
     1709  filterArcs(const GR& digraph, const AF& arc_filter_map) {
     1710    return FilterArcs<const GR, const AF>(digraph, arc_filter_map);
    15771711  }
    15781712
    15791713  /// \ingroup graph_adaptors
    15801714  ///
    1581   /// \brief An adaptor for hiding edges from a graph.
    1582   ///
    1583   /// FilterEdges adaptor hides edges in a digraph. A bool edge map must
    1584   /// be specified, which defines the filters for edges. Just the
    1585   /// unfiltered edges are shown in the subdigraph. The FilterEdges is
    1586   /// conform to the \ref concepts::Graph "Graph concept".
    1587   ///
    1588   /// \tparam _Graph It must be conform to the \ref concepts::Graph
    1589   /// "Graph concept". The type can be specified to be const.
    1590   /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted
    1591   /// graph.
    1592   template<typename _Graph, typename _EdgeFilterMap>
     1715  /// \brief Adaptor class for hiding edges in a graph.
     1716  ///
     1717  /// FilterEdges adaptor can be used for hiding edges in a graph.
     1718  /// A \c bool edge map must be specified, which defines the filter for
     1719  /// the edges. Only the edges with \c true filter value are shown in the
     1720  /// subgraph. This adaptor conforms to the \ref concepts::Graph
     1721  /// "Graph" concept.
     1722  ///
     1723  /// The adapted graph can also be modified through this adaptor
     1724  /// by adding or removing nodes or edges, unless the \c GR template
     1725  /// parameter is set to be \c const.
     1726  ///
     1727  /// \tparam GR The type of the adapted graph.
     1728  /// It must conform to the \ref concepts::Graph "Graph" concept.
     1729  /// It can also be specified to be \c const.
     1730  /// \tparam EF The type of the edge filter map.
     1731  /// It must be a \c bool (or convertible) edge map of the
     1732  /// adapted graph. The default type is
     1733  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
     1734  ///
     1735  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
     1736  /// adapted graph are convertible to each other.
     1737#ifdef DOXYGEN
     1738  template<typename GR,
     1739           typename EF>
     1740  class FilterEdges {
     1741#else
     1742  template<typename GR,
     1743           typename EF = typename GR::template EdgeMap<bool> >
    15931744  class FilterEdges :
    1594     public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
    1595                     _EdgeFilterMap, false> {
    1596   public:
    1597     typedef _Graph Graph;
    1598     typedef _EdgeFilterMap EdgeFilterMap;
    1599     typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,
    1600                      EdgeFilterMap, false> Parent;
     1745    public GraphAdaptorExtender<
     1746      SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> > {
     1747#endif
     1748  public:
     1749    /// The type of the adapted graph.
     1750    typedef GR Graph;
     1751    /// The type of the edge filter map.
     1752    typedef EF EdgeFilterMap;
     1753
     1754    typedef GraphAdaptorExtender<
     1755      SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> >
     1756      Parent;
     1757
    16011758    typedef typename Parent::Edge Edge;
     1759
    16021760  protected:
    16031761    ConstMap<typename Graph::Node, bool> const_true_map;
     
    16111769    /// \brief Constructor
    16121770    ///
    1613     /// Creates a FilterEdges adaptor for the given graph with
    1614     /// given edge map filters.
    1615     FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :
     1771    /// Creates a subgraph for the given graph with the given edge
     1772    /// filter map.
     1773    FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) :
    16161774      Parent(), const_true_map(true) {
    1617       Parent::setGraph(_graph);
     1775      Parent::setGraph(graph);
    16181776      Parent::setNodeFilterMap(const_true_map);
    16191777      Parent::setEdgeFilterMap(edge_filter_map);
    16201778    }
    16211779
    1622     /// \brief Hides the edge of the graph
    1623     ///
    1624     /// This function hides \c e in the graph, i.e. the iteration
    1625     /// jumps over it. This is done by simply setting the value of \c e
    1626     /// to be false in the corresponding edge-map.
    1627     void hide(const Edge& e) const { Parent::hide(e); }
    1628 
    1629     /// \brief Unhides the edge of the graph
    1630     ///
    1631     /// The value of \c e is set to be true in the edge-map which stores
    1632     /// hide information. If \c e was hidden previuosly, then it is shown
    1633     /// again
    1634     void unHide(const Edge& e) const { Parent::unHide(e); }
    1635 
    1636     /// \brief Returns true if \c e is hidden.
    1637     ///
    1638     /// Returns true if \c e is hidden.
    1639     ///
    1640     bool hidden(const Edge& e) const { return Parent::hidden(e); }
     1780    /// \brief Sets the status of the given edge
     1781    ///
     1782    /// This function sets the status of the given edge.
     1783    /// It is done by simply setting the assigned value of \c e
     1784    /// to \c v in the edge filter map.
     1785    void status(const Edge& e, bool v) const { Parent::status(e, v); }
     1786
     1787    /// \brief Returns the status of the given edge
     1788    ///
     1789    /// This function returns the status of the given edge.
     1790    /// It is \c true if the given edge is enabled (i.e. not hidden).
     1791    bool status(const Edge& e) const { return Parent::status(e); }
     1792
     1793    /// \brief Disables the given edge
     1794    ///
     1795    /// This function disables the given edge in the subgraph,
     1796    /// so the iteration jumps over it.
     1797    /// It is the same as \ref status() "status(e, false)".
     1798    void disable(const Edge& e) const { Parent::status(e, false); }
     1799
     1800    /// \brief Enables the given edge
     1801    ///
     1802    /// This function enables the given edge in the subgraph.
     1803    /// It is the same as \ref status() "status(e, true)".
     1804    void enable(const Edge& e) const { Parent::status(e, true); }
    16411805
    16421806  };
    16431807
    1644   /// \brief Just gives back a FilterEdges adaptor
    1645   ///
    1646   /// Just gives back a FilterEdges adaptor
    1647   template<typename Graph, typename EdgeFilterMap>
    1648   FilterEdges<const Graph, EdgeFilterMap>
    1649   filterEdges(const Graph& graph, EdgeFilterMap& efm) {
    1650     return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);
     1808  /// \brief Returns a read-only FilterEdges adaptor
     1809  ///
     1810  /// This function just returns a read-only \ref FilterEdges adaptor.
     1811  /// \ingroup graph_adaptors
     1812  /// \relates FilterEdges
     1813  template<typename GR, typename EF>
     1814  FilterEdges<const GR, EF>
     1815  filterEdges(const GR& graph, EF& edge_filter_map) {
     1816    return FilterEdges<const GR, EF>(graph, edge_filter_map);
    16511817  }
    16521818
    1653   template<typename Graph, typename EdgeFilterMap>
    1654   FilterEdges<const Graph, const EdgeFilterMap>
    1655   filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
    1656     return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);
     1819  template<typename GR, typename EF>
     1820  FilterEdges<const GR, const EF>
     1821  filterEdges(const GR& graph, const EF& edge_filter_map) {
     1822    return FilterEdges<const GR, const EF>(graph, edge_filter_map);
    16571823  }
     1824
    16581825
    16591826  template <typename _Digraph>
     
    16951862      }
    16961863    };
    1697 
    1698 
    16991864
    17001865    void first(Node& n) const {
     
    18462011
    18472012    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
    1848     int nodeNum() const { return 2 * _digraph->arcNum(); }
    1849     typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
     2013    int nodeNum() const { return _digraph->nodeNum(); }
     2014
     2015    typedef ArcNumTagIndicator<Digraph> ArcNumTag;
    18502016    int arcNum() const { return 2 * _digraph->arcNum(); }
     2017
     2018    typedef ArcNumTag EdgeNumTag;
    18512019    int edgeNum() const { return _digraph->arcNum(); }
    18522020
    1853     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
     2021    typedef FindArcTagIndicator<Digraph> FindArcTag;
    18542022    Arc findArc(Node s, Node t, Arc p = INVALID) const {
    18552023      if (p == INVALID) {
     
    18702038    }
    18712039
     2040    typedef FindArcTag FindEdgeTag;
    18722041    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
    18732042      if (s != t) {
     
    18772046          arc = _digraph->findArc(t, s);
    18782047          if (arc != INVALID) return arc;
    1879         } else if (_digraph->s(p) == s) {
     2048        } else if (_digraph->source(p) == s) {
    18802049          Edge arc = _digraph->findArc(s, t, p);
    18812050          if (arc != INVALID) return arc;
     
    19062075      typedef _Value Value;
    19072076      typedef Arc Key;
     2077      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
     2078      typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;
     2079      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;
     2080      typedef typename MapTraits<MapImpl>::ReturnValue Reference;
    19082081
    19092082      ArcMapBase(const Adaptor& adaptor) :
     
    19212094      }
    19222095
    1923       typename MapTraits<MapImpl>::ConstReturnValue
    1924       operator[](const Arc& a) const {
     2096      ConstReturnValue operator[](const Arc& a) const {
    19252097        if (direction(a)) {
    19262098          return _forward[a];
     
    19302102      }
    19312103
    1932       typename MapTraits<MapImpl>::ReturnValue
    1933       operator[](const Arc& a) {
     2104      ReturnValue operator[](const Arc& a) {
    19342105        if (direction(a)) {
    19352106          return _forward[a];
     
    19812152      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
    19822153
    1983       ArcMap(const Adaptor& adaptor)
     2154      explicit ArcMap(const Adaptor& adaptor)
    19842155        : Parent(adaptor) {}
    19852156
     
    20282199    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
    20292200
     2201    typedef typename ItemSetTraits<Digraph, Edge>::ItemNotifier EdgeNotifier;
     2202    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
     2203
    20302204  protected:
    20312205
     
    20422216  /// \ingroup graph_adaptors
    20432217  ///
    2044   /// \brief Undirect the graph
    2045   ///
    2046   /// This adaptor makes an undirected graph from a directed
    2047   /// graph. All arcs of the underlying digraph will be showed in the
    2048   /// adaptor as an edge. The Orienter adaptor is conform to the \ref
    2049   /// concepts::Graph "Graph concept".
    2050   ///
    2051   /// \tparam _Digraph It must be conform to the \ref
    2052   /// concepts::Digraph "Digraph concept". The type can be specified
    2053   /// to const.
    2054   template<typename _Digraph>
    2055   class Undirector
    2056     : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
    2057   public:
    2058     typedef _Digraph Digraph;
    2059     typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
     2218  /// \brief Adaptor class for viewing a digraph as an undirected graph.
     2219  ///
     2220  /// Undirector adaptor can be used for viewing a digraph as an undirected
     2221  /// graph. All arcs of the underlying digraph are showed in the
     2222  /// adaptor as an edge (and also as a pair of arcs, of course).
     2223  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
     2224  ///
     2225  /// The adapted digraph can also be modified through this adaptor
     2226  /// by adding or removing nodes or edges, unless the \c GR template
     2227  /// parameter is set to be \c const.
     2228  ///
     2229  /// \tparam GR The type of the adapted digraph.
     2230  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     2231  /// It can also be specified to be \c const.
     2232  ///
     2233  /// \note The \c Node type of this adaptor and the adapted digraph are
     2234  /// convertible to each other, moreover the \c Edge type of the adaptor
     2235  /// and the \c Arc type of the adapted digraph are also convertible to
     2236  /// each other.
     2237  /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
     2238  /// of the adapted digraph.)
     2239  template<typename GR>
     2240#ifdef DOXYGEN
     2241  class Undirector {
     2242#else
     2243  class Undirector :
     2244    public GraphAdaptorExtender<UndirectorBase<GR> > {
     2245#endif
     2246  public:
     2247    /// The type of the adapted digraph.
     2248    typedef GR Digraph;
     2249    typedef GraphAdaptorExtender<UndirectorBase<GR> > Parent;
    20602250  protected:
    20612251    Undirector() { }
     
    20642254    /// \brief Constructor
    20652255    ///
    2066     /// Creates a undirected graph from the given digraph
    2067     Undirector(_Digraph& digraph) {
     2256    /// Creates an undirected graph from the given digraph.
     2257    Undirector(Digraph& digraph) {
    20682258      setDigraph(digraph);
    20692259    }
    20702260
    2071     /// \brief ArcMap combined from two original ArcMap
    2072     ///
    2073     /// This class adapts two original digraph ArcMap to
    2074     /// get an arc map on the undirected graph.
    2075     template <typename _ForwardMap, typename _BackwardMap>
     2261    /// \brief Arc map combined from two original arc maps
     2262    ///
     2263    /// This map adaptor class adapts two arc maps of the underlying
     2264    /// digraph to get an arc map of the undirected graph.
     2265    /// Its value type is inherited from the first arc map type
     2266    /// (\c %ForwardMap).
     2267    template <typename ForwardMap, typename BackwardMap>
    20762268    class CombinedArcMap {
    20772269    public:
    20782270
    2079       typedef _ForwardMap ForwardMap;
    2080       typedef _BackwardMap BackwardMap;
     2271      /// The key type of the map
     2272      typedef typename Parent::Arc Key;
     2273      /// The value type of the map
     2274      typedef typename ForwardMap::Value Value;
    20812275
    20822276      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
    20832277
    2084       typedef typename ForwardMap::Value Value;
    2085       typedef typename Parent::Arc Key;
    2086 
    2087       /// \brief Constructor
    2088       ///
     2278      typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
     2279      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;
     2280      typedef typename MapTraits<ForwardMap>::ReturnValue Reference;
     2281      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
     2282
    20892283      /// Constructor
    20902284      CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
    20912285        : _forward(&forward), _backward(&backward) {}
    20922286
    2093 
    2094       /// \brief Sets the value associated with a key.
    2095       ///
    2096       /// Sets the value associated with a key.
     2287      /// Sets the value associated with the given key.
    20972288      void set(const Key& e, const Value& a) {
    20982289        if (Parent::direction(e)) {
     
    21032294      }
    21042295
    2105       /// \brief Returns the value associated with a key.
    2106       ///
    2107       /// Returns the value associated with a key.
    2108       typename MapTraits<ForwardMap>::ConstReturnValue
    2109       operator[](const Key& e) const {
     2296      /// Returns the value associated with the given key.
     2297      ConstReturnValue operator[](const Key& e) const {
    21102298        if (Parent::direction(e)) {
    21112299          return (*_forward)[e];
     
    21152303      }
    21162304
    2117       /// \brief Returns the value associated with a key.
    2118       ///
    2119       /// Returns the value associated with a key.
    2120       typename MapTraits<ForwardMap>::ReturnValue
    2121       operator[](const Key& e) {
     2305      /// Returns a reference to the value associated with the given key.
     2306      ReturnValue operator[](const Key& e) {
    21222307        if (Parent::direction(e)) {
    21232308          return (*_forward)[e];
     
    21342319    };
    21352320
    2136     /// \brief Just gives back a combined arc map
    2137     ///
    2138     /// Just gives back a combined arc map
     2321    /// \brief Returns a combined arc map
     2322    ///
     2323    /// This function just returns a combined arc map.
    21392324    template <typename ForwardMap, typename BackwardMap>
    21402325    static CombinedArcMap<ForwardMap, BackwardMap>
     
    21662351  };
    21672352
    2168   /// \brief Just gives back an undirected view of the given digraph
    2169   ///
    2170   /// Just gives back an undirected view of the given digraph
    2171   template<typename Digraph>
    2172   Undirector<const Digraph>
    2173   undirector(const Digraph& digraph) {
    2174     return Undirector<const Digraph>(digraph);
     2353  /// \brief Returns a read-only Undirector adaptor
     2354  ///
     2355  /// This function just returns a read-only \ref Undirector adaptor.
     2356  /// \ingroup graph_adaptors
     2357  /// \relates Undirector
     2358  template<typename GR>
     2359  Undirector<const GR> undirector(const GR& digraph) {
     2360    return Undirector<const GR>(digraph);
    21752361  }
     2362
    21762363
    21772364  template <typename _Graph, typename _DirectionMap>
     
    21922379    void first(Arc& i) const { _graph->first(i); }
    21932380    void firstIn(Arc& i, const Node& n) const {
    2194       bool d;
     2381      bool d = true;
    21952382      _graph->firstInc(i, d, n);
    21962383      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
    21972384    }
    21982385    void firstOut(Arc& i, const Node& n ) const {
    2199       bool d;
     2386      bool d = true;
    22002387      _graph->firstInc(i, d, n);
    22012388      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
     
    22252412    int nodeNum() const { return _graph->nodeNum(); }
    22262413
    2227     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
     2414    typedef EdgeNumTagIndicator<Graph> ArcNumTag;
    22282415    int arcNum() const { return _graph->edgeNum(); }
    22292416
    2230     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
     2417    typedef FindEdgeTagIndicator<Graph> FindArcTag;
    22312418    Arc findArc(const Node& u, const Node& v,
    2232                 const Arc& prev = INVALID) {
    2233       Arc arc = prev;
    2234       bool d = arc == INVALID ? true : (*_direction)[arc];
    2235       if (d) {
     2419                const Arc& prev = INVALID) const {
     2420      Arc arc = _graph->findEdge(u, v, prev);
     2421      while (arc != INVALID && source(arc) != u) {
    22362422        arc = _graph->findEdge(u, v, arc);
    2237         while (arc != INVALID && !(*_direction)[arc]) {
    2238           _graph->findEdge(u, v, arc);
    2239         }
    2240         if (arc != INVALID) return arc;
    2241       }
    2242       _graph->findEdge(v, u, arc);
    2243       while (arc != INVALID && (*_direction)[arc]) {
    2244         _graph->findEdge(u, v, arc);
    22452423      }
    22462424      return arc;
     
    22522430
    22532431    Arc addArc(const Node& u, const Node& v) {
    2254       Arc arc = _graph->addArc(u, v);
    2255       _direction->set(arc, _graph->source(arc) == u);
     2432      Arc arc = _graph->addEdge(u, v);
     2433      _direction->set(arc, _graph->u(arc) == u);
    22562434      return arc;
    22572435    }
     
    23442522  /// \ingroup graph_adaptors
    23452523  ///
    2346   /// \brief Orients the edges of the graph to get a digraph
    2347   ///
    2348   /// This adaptor orients each edge in the undirected graph. The
    2349   /// direction of the arcs stored in an edge node map.  The arcs can
    2350   /// be easily reverted by the \c reverseArc() member function in the
    2351   /// adaptor. The Orienter adaptor is conform to the \ref
    2352   /// concepts::Digraph "Digraph concept".
    2353   ///
    2354   /// \tparam _Graph It must be conform to the \ref concepts::Graph
    2355   /// "Graph concept". The type can be specified to be const.
    2356   /// \tparam _DirectionMap A bool valued edge map of the the adapted
    2357   /// graph.
    2358   ///
    2359   /// \sa orienter
    2360   template<typename _Graph,
    2361            typename DirectionMap = typename _Graph::template EdgeMap<bool> >
     2524  /// \brief Adaptor class for orienting the edges of a graph to get a digraph
     2525  ///
     2526  /// Orienter adaptor can be used for orienting the edges of a graph to
     2527  /// get a digraph. A \c bool edge map of the underlying graph must be
     2528  /// specified, which define the direction of the arcs in the adaptor.
     2529  /// The arcs can be easily reversed by the \c reverseArc() member function
     2530  /// of the adaptor.
     2531  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
     2532  ///
     2533  /// The adapted graph can also be modified through this adaptor
     2534  /// by adding or removing nodes or arcs, unless the \c GR template
     2535  /// parameter is set to be \c const.
     2536  ///
     2537  /// \tparam GR The type of the adapted graph.
     2538  /// It must conform to the \ref concepts::Graph "Graph" concept.
     2539  /// It can also be specified to be \c const.
     2540  /// \tparam DM The type of the direction map.
     2541  /// It must be a \c bool (or convertible) edge map of the
     2542  /// adapted graph. The default type is
     2543  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
     2544  ///
     2545  /// \note The \c Node type of this adaptor and the adapted graph are
     2546  /// convertible to each other, moreover the \c Arc type of the adaptor
     2547  /// and the \c Edge type of the adapted graph are also convertible to
     2548  /// each other.
     2549#ifdef DOXYGEN
     2550  template<typename GR,
     2551           typename DM>
     2552  class Orienter {
     2553#else
     2554  template<typename GR,
     2555           typename DM = typename GR::template EdgeMap<bool> >
    23622556  class Orienter :
    2363     public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {
    2364   public:
    2365     typedef _Graph Graph;
    2366     typedef DigraphAdaptorExtender<
    2367       OrienterBase<_Graph, DirectionMap> > Parent;
     2557    public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
     2558#endif
     2559  public:
     2560
     2561    /// The type of the adapted graph.
     2562    typedef GR Graph;
     2563    /// The type of the direction edge map.
     2564    typedef DM DirectionMap;
     2565
     2566    typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
    23682567    typedef typename Parent::Arc Arc;
    23692568  protected:
     
    23712570  public:
    23722571
    2373     /// \brief Constructor of the adaptor
    2374     ///
    2375     /// Constructor of the adaptor
     2572    /// \brief Constructor
     2573    ///
     2574    /// Constructor of the adaptor.
    23762575    Orienter(Graph& graph, DirectionMap& direction) {
    23772576      setGraph(graph);
     
    23792578    }
    23802579
    2381     /// \brief Reverse arc
    2382     ///
    2383     /// It reverse the given arc. It simply negate the direction in the map.
     2580    /// \brief Reverses the given arc
     2581    ///
     2582    /// This function reverses the given arc.
     2583    /// It is done by simply negate the assigned value of \c a
     2584    /// in the direction map.
    23842585    void reverseArc(const Arc& a) {
    23852586      Parent::reverseArc(a);
     
    23872588  };
    23882589
    2389   /// \brief Just gives back a Orienter
    2390   ///
    2391   /// Just gives back a Orienter
    2392   template<typename Graph, typename DirectionMap>
    2393   Orienter<const Graph, DirectionMap>
    2394   orienter(const Graph& graph, DirectionMap& dm) {
    2395     return Orienter<const Graph, DirectionMap>(graph, dm);
     2590  /// \brief Returns a read-only Orienter adaptor
     2591  ///
     2592  /// This function just returns a read-only \ref Orienter adaptor.
     2593  /// \ingroup graph_adaptors
     2594  /// \relates Orienter
     2595  template<typename GR, typename DM>
     2596  Orienter<const GR, DM>
     2597  orienter(const GR& graph, DM& direction_map) {
     2598    return Orienter<const GR, DM>(graph, direction_map);
    23962599  }
    23972600
    2398   template<typename Graph, typename DirectionMap>
    2399   Orienter<const Graph, const DirectionMap>
    2400   orienter(const Graph& graph, const DirectionMap& dm) {
    2401     return Orienter<const Graph, const DirectionMap>(graph, dm);
     2601  template<typename GR, typename DM>
     2602  Orienter<const GR, const DM>
     2603  orienter(const GR& graph, const DM& direction_map) {
     2604    return Orienter<const GR, const DM>(graph, direction_map);
    24022605  }
    24032606
    24042607  namespace _adaptor_bits {
    24052608
    2406     template<typename _Digraph,
    2407              typename _CapacityMap = typename _Digraph::template ArcMap<int>,
    2408              typename _FlowMap = _CapacityMap,
    2409              typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
     2609    template<typename Digraph,
     2610             typename CapacityMap,
     2611             typename FlowMap,
     2612             typename Tolerance>
    24102613    class ResForwardFilter {
    24112614    public:
    2412 
    2413       typedef _Digraph Digraph;
    2414       typedef _CapacityMap CapacityMap;
    2415       typedef _FlowMap FlowMap;
    2416       typedef _Tolerance Tolerance;
    24172615
    24182616      typedef typename Digraph::Arc Key;
     
    24352633    };
    24362634
    2437     template<typename _Digraph,
    2438              typename _CapacityMap = typename _Digraph::template ArcMap<int>,
    2439              typename _FlowMap = _CapacityMap,
    2440              typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
     2635    template<typename Digraph,
     2636             typename CapacityMap,
     2637             typename FlowMap,
     2638             typename Tolerance>
    24412639    class ResBackwardFilter {
    24422640    public:
    2443 
    2444       typedef _Digraph Digraph;
    2445       typedef _CapacityMap CapacityMap;
    2446       typedef _FlowMap FlowMap;
    2447       typedef _Tolerance Tolerance;
    24482641
    24492642      typedef typename Digraph::Arc Key;
     
    24712664  /// \ingroup graph_adaptors
    24722665  ///
    2473   /// \brief An adaptor for composing the residual graph for directed
     2666  /// \brief Adaptor class for composing the residual digraph for directed
    24742667  /// flow and circulation problems.
    24752668  ///
    2476   /// An adaptor for composing the residual graph for directed flow and
    2477   /// circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph
    2478   /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
    2479   /// be functions on the arc-set.
    2480   ///
    2481   /// Then Residual implements the digraph structure with
    2482   /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$,
    2483   /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
    2484   /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
    2485   /// called residual graph.  When we take the union
    2486   /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,
    2487   /// i.e.  if an arc is in both \f$ A_{forward} \f$ and
    2488   /// \f$ A_{backward} \f$, then in the adaptor it appears in both
    2489   /// orientation.
    2490   ///
    2491   /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
    2492   /// "Digraph concept". The type is implicitly const.
    2493   /// \tparam _CapacityMap An arc map of some numeric type, it defines
    2494   /// the capacities in the flow problem. The map is implicitly const.
    2495   /// \tparam _FlowMap An arc map of some numeric type, it defines
    2496   /// the capacities in the flow problem.
    2497   /// \tparam _Tolerance Handler for inexact computation.
    2498   template<typename _Digraph,
    2499            typename _CapacityMap = typename _Digraph::template ArcMap<int>,
    2500            typename _FlowMap = _CapacityMap,
    2501            typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
     2669  /// Residual can be used for composing the \e residual digraph for directed
     2670  /// flow and circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
     2671  /// and let \f$ F \f$ be a number type. Let \f$ flow, cap: A\to F \f$ be
     2672  /// functions on the arcs.
     2673  /// This adaptor implements a digraph structure with node set \f$ V \f$
     2674  /// and arc set \f$ A_{forward}\cup A_{backward} \f$,
     2675  /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and
     2676  /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so
     2677  /// called residual digraph.
     2678  /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,
     2679  /// multiplicities are counted, i.e. the adaptor has exactly
     2680  /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel
     2681  /// arcs).
     2682  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
     2683  ///
     2684  /// \tparam GR The type of the adapted digraph.
     2685  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     2686  /// It is implicitly \c const.
     2687  /// \tparam CM The type of the capacity map.
     2688  /// It must be an arc map of some numerical type, which defines
     2689  /// the capacities in the flow problem. It is implicitly \c const.
     2690  /// The default type is
     2691  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
     2692  /// \tparam FM The type of the flow map.
     2693  /// It must be an arc map of some numerical type, which defines
     2694  /// the flow values in the flow problem. The default type is \c CM.
     2695  /// \tparam TL The tolerance type for handling inexact computation.
     2696  /// The default tolerance type depends on the value type of the
     2697  /// capacity map.
     2698  ///
     2699  /// \note This adaptor is implemented using Undirector and FilterArcs
     2700  /// adaptors.
     2701  ///
     2702  /// \note The \c Node type of this adaptor and the adapted digraph are
     2703  /// convertible to each other, moreover the \c Arc type of the adaptor
     2704  /// is convertible to the \c Arc type of the adapted digraph.
     2705#ifdef DOXYGEN
     2706  template<typename GR, typename CM, typename FM, typename TL>
     2707  class Residual
     2708#else
     2709  template<typename GR,
     2710           typename CM = typename GR::template ArcMap<int>,
     2711           typename FM = CM,
     2712           typename TL = Tolerance<typename CM::Value> >
    25022713  class Residual :
    25032714    public FilterArcs<
    2504     Undirector<const _Digraph>,
    2505     typename Undirector<const _Digraph>::template CombinedArcMap<
    2506       _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,
    2507                                       _FlowMap, _Tolerance>,
    2508       _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
    2509                                        _FlowMap, _Tolerance> > >
     2715      Undirector<const GR>,
     2716      typename Undirector<const GR>::template CombinedArcMap<
     2717        _adaptor_bits::ResForwardFilter<const GR, CM, FM, TL>,
     2718        _adaptor_bits::ResBackwardFilter<const GR, CM, FM, TL> > >
     2719#endif
    25102720  {
    25112721  public:
    25122722
    2513     typedef _Digraph Digraph;
    2514     typedef _CapacityMap CapacityMap;
    2515     typedef _FlowMap FlowMap;
    2516     typedef _Tolerance Tolerance;
     2723    /// The type of the underlying digraph.
     2724    typedef GR Digraph;
     2725    /// The type of the capacity map.
     2726    typedef CM CapacityMap;
     2727    /// The type of the flow map.
     2728    typedef FM FlowMap;
     2729    /// The tolerance type.
     2730    typedef TL Tolerance;
    25172731
    25182732    typedef typename CapacityMap::Value Value;
     
    25302744
    25312745    typedef typename Undirected::
    2532     template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
     2746      template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
    25332747
    25342748    typedef FilterArcs<Undirected, ArcFilter> Parent;
     
    25442758  public:
    25452759
    2546     /// \brief Constructor of the residual digraph.
    2547     ///
    2548     /// Constructor of the residual graph. The parameters are the digraph,
    2549     /// the flow map, the capacity map and a tolerance object.
     2760    /// \brief Constructor
     2761    ///
     2762    /// Constructor of the residual digraph adaptor. The parameters are the
     2763    /// digraph, the capacity map, the flow map, and a tolerance object.
    25502764    Residual(const Digraph& digraph, const CapacityMap& capacity,
    25512765             FlowMap& flow, const Tolerance& tolerance = Tolerance())
     
    25612775    typedef typename Parent::Arc Arc;
    25622776
    2563     /// \brief Gives back the residual capacity of the arc.
    2564     ///
    2565     /// Gives back the residual capacity of the arc.
     2777    /// \brief Returns the residual capacity of the given arc.
     2778    ///
     2779    /// Returns the residual capacity of the given arc.
    25662780    Value residualCapacity(const Arc& a) const {
    25672781      if (Undirected::direction(a)) {
     
    25722786    }
    25732787
    2574     /// \brief Augment on the given arc in the residual graph.
    2575     ///
    2576     /// Augment on the given arc in the residual graph. It increase
    2577     /// or decrease the flow on the original arc depend on the direction
    2578     /// of the residual arc.
     2788    /// \brief Augments on the given arc in the residual digraph.
     2789    ///
     2790    /// Augments on the given arc in the residual digraph. It increases
     2791    /// or decreases the flow value on the original arc according to the
     2792    /// direction of the residual arc.
    25792793    void augment(const Arc& a, const Value& v) const {
    25802794      if (Undirected::direction(a)) {
     
    25852799    }
    25862800
    2587     /// \brief Returns the direction of the arc.
    2588     ///
    2589     /// Returns true when the arc is same oriented as the original arc.
     2801    /// \brief Returns \c true if the given residual arc is a forward arc.
     2802    ///
     2803    /// Returns \c true if the given residual arc has the same orientation
     2804    /// as the original arc, i.e. it is a so called forward arc.
    25902805    static bool forward(const Arc& a) {
    25912806      return Undirected::direction(a);
    25922807    }
    25932808
    2594     /// \brief Returns the direction of the arc.
    2595     ///
    2596     /// Returns true when the arc is opposite oriented as the original arc.
     2809    /// \brief Returns \c true if the given residual arc is a backward arc.
     2810    ///
     2811    /// Returns \c true if the given residual arc has the opposite orientation
     2812    /// than the original arc, i.e. it is a so called backward arc.
    25972813    static bool backward(const Arc& a) {
    25982814      return !Undirected::direction(a);
    25992815    }
    26002816
    2601     /// \brief Gives back the forward oriented residual arc.
    2602     ///
    2603     /// Gives back the forward oriented residual arc.
     2817    /// \brief Returns the forward oriented residual arc.
     2818    ///
     2819    /// Returns the forward oriented residual arc related to the given
     2820    /// arc of the underlying digraph.
    26042821    static Arc forward(const typename Digraph::Arc& a) {
    26052822      return Undirected::direct(a, true);
    26062823    }
    26072824
    2608     /// \brief Gives back the backward oriented residual arc.
    2609     ///
    2610     /// Gives back the backward oriented residual arc.
     2825    /// \brief Returns the backward oriented residual arc.
     2826    ///
     2827    /// Returns the backward oriented residual arc related to the given
     2828    /// arc of the underlying digraph.
    26112829    static Arc backward(const typename Digraph::Arc& a) {
    26122830      return Undirected::direct(a, false);
     
    26152833    /// \brief Residual capacity map.
    26162834    ///
    2617     /// In generic residual graph the residual capacity can be obtained
    2618     /// as a map.
     2835    /// This map adaptor class can be used for obtaining the residual
     2836    /// capacities as an arc map of the residual digraph.
     2837    /// Its value type is inherited from the capacity map.
    26192838    class ResidualCapacity {
    26202839    protected:
    26212840      const Adaptor* _adaptor;
    26222841    public:
    2623       /// The Key type
     2842      /// The key type of the map
    26242843      typedef Arc Key;
    2625       /// The Value type
    2626       typedef typename _CapacityMap::Value Value;
     2844      /// The value type of the map
     2845      typedef typename CapacityMap::Value Value;
    26272846
    26282847      /// Constructor
    26292848      ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
    26302849
    2631       /// \e
     2850      /// Returns the value associated with the given residual arc
    26322851      Value operator[](const Arc& a) const {
    26332852        return _adaptor->residualCapacity(a);
     
    26362855    };
    26372856
     2857    /// \brief Returns a residual capacity map
     2858    ///
     2859    /// This function just returns a residual capacity map.
     2860    ResidualCapacity residualCapacity() const {
     2861      return ResidualCapacity(*this);
     2862    }
     2863
    26382864  };
     2865
     2866  /// \brief Returns a (read-only) Residual adaptor
     2867  ///
     2868  /// This function just returns a (read-only) \ref Residual adaptor.
     2869  /// \ingroup graph_adaptors
     2870  /// \relates Residual
     2871  template<typename GR, typename CM, typename FM>
     2872  Residual<GR, CM, FM> residual(const GR& digraph,
     2873                                const CM& capacity_map,
     2874                                FM& flow_map) {
     2875    return Residual<GR, CM, FM> (digraph, capacity_map, flow_map);
     2876  }
     2877
    26392878
    26402879  template <typename _Digraph>
     
    28853124
    28863125    typedef True NodeNumTag;
    2887 
    28883126    int nodeNum() const {
    28893127      return  2 * countNodes(*_digraph);
    28903128    }
    28913129
    2892     typedef True EdgeNumTag;
     3130    typedef True ArcNumTag;
    28933131    int arcNum() const {
    28943132      return countArcs(*_digraph) + countNodes(*_digraph);
    28953133    }
    28963134
    2897     typedef True FindEdgeTag;
     3135    typedef True FindArcTag;
    28983136    Arc findArc(const Node& u, const Node& v,
    28993137                const Arc& prev = INVALID) const {
    2900       if (inNode(u)) {
    2901         if (outNode(v)) {
    2902           if (static_cast<const DigraphNode&>(u) ==
    2903               static_cast<const DigraphNode&>(v) && prev == INVALID) {
    2904             return Arc(u);
    2905           }
     3138      if (inNode(u) && outNode(v)) {
     3139        if (static_cast<const DigraphNode&>(u) ==
     3140            static_cast<const DigraphNode&>(v) && prev == INVALID) {
     3141          return Arc(u);
    29063142        }
    2907       } else {
    2908         if (inNode(v)) {
    2909           return Arc(::lemon::findArc(*_digraph, u, v, prev));
    2910         }
     3143      }
     3144      else if (outNode(u) && inNode(v)) {
     3145        return Arc(::lemon::findArc(*_digraph, u, v, prev));
    29113146      }
    29123147      return INVALID;
     
    29223157      typedef Node Key;
    29233158      typedef _Value Value;
     3159      typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
     3160      typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
     3161      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;
     3162      typedef typename MapTraits<NodeImpl>::ReturnValue Reference;
     3163      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
    29243164
    29253165      NodeMapBase(const Adaptor& adaptor)
     
    29343174      }
    29353175
    2936       typename MapTraits<NodeImpl>::ReturnValue
    2937       operator[](const Node& key) {
     3176      ReturnValue operator[](const Node& key) {
    29383177        if (Adaptor::inNode(key)) { return _in_map[key]; }
    29393178        else { return _out_map[key]; }
    29403179      }
    29413180
    2942       typename MapTraits<NodeImpl>::ConstReturnValue
    2943       operator[](const Node& key) const {
     3181      ConstReturnValue operator[](const Node& key) const {
    29443182        if (Adaptor::inNode(key)) { return _in_map[key]; }
    29453183        else { return _out_map[key]; }
     
    29583196      typedef Arc Key;
    29593197      typedef _Value Value;
     3198      typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
     3199      typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
     3200      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;
     3201      typedef typename MapTraits<ArcImpl>::ReturnValue Reference;
     3202      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
    29603203
    29613204      ArcMapBase(const Adaptor& adaptor)
     
    29733216      }
    29743217
    2975       typename MapTraits<ArcImpl>::ReturnValue
    2976       operator[](const Arc& key) {
     3218      ReturnValue operator[](const Arc& key) {
    29773219        if (Adaptor::origArc(key)) {
    29783220          return _arc_map[key._item.first()];
     
    29823224      }
    29833225
    2984       typename MapTraits<ArcImpl>::ConstReturnValue
    2985       operator[](const Arc& key) const {
     3226      ConstReturnValue operator[](const Arc& key) const {
    29863227        if (Adaptor::origArc(key)) {
    29873228          return _arc_map[key._item.first()];
     
    30643305  /// \ingroup graph_adaptors
    30653306  ///
    3066   /// \brief Split the nodes of a directed graph
    3067   ///
    3068   /// The SplitNodes adaptor splits each node into an in-node and an
    3069   /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in
    3070   /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node
    3071   /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the
    3072   /// original digraph the new target of the arc will be \f$ u_{in} \f$
    3073   /// and similarly the source of the original \f$ (u, v) \f$ arc
    3074   /// will be \f$ u_{out} \f$.  The adaptor will add for each node in
    3075   /// the original digraph an additional arc which connects
    3076   /// \f$ (u_{in}, u_{out}) \f$.
    3077   ///
    3078   /// The aim of this class is to run algorithm with node costs if the
    3079   /// algorithm can use directly just arc costs. In this case we should use
    3080   /// a \c SplitNodes and set the node cost of the graph to the
    3081   /// bind arc in the adapted graph.
    3082   ///
    3083   /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
    3084   /// "Digraph concept". The type can be specified to be const.
    3085   template <typename _Digraph>
     3307  /// \brief Adaptor class for splitting the nodes of a digraph.
     3308  ///
     3309  /// SplitNodes adaptor can be used for splitting each node into an
     3310  /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor
     3311  /// replaces each node \f$ u \f$ in the digraph with two nodes,
     3312  /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.
     3313  /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the
     3314  /// new target of the arc will be \f$ u_{in} \f$ and similarly the
     3315  /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.
     3316  /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$
     3317  /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.
     3318  ///
     3319  /// The aim of this class is running an algorithm with respect to node
     3320  /// costs or capacities if the algorithm considers only arc costs or
     3321  /// capacities directly.
     3322  /// In this case you can use \c SplitNodes adaptor, and set the node
     3323  /// costs/capacities of the original digraph to the \e bind \e arcs
     3324  /// in the adaptor.
     3325  ///
     3326  /// \tparam GR The type of the adapted digraph.
     3327  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     3328  /// It is implicitly \c const.
     3329  ///
     3330  /// \note The \c Node type of this adaptor is converible to the \c Node
     3331  /// type of the adapted digraph.
     3332  template <typename GR>
     3333#ifdef DOXYGEN
     3334  class SplitNodes {
     3335#else
    30863336  class SplitNodes
    3087     : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > {
    3088   public:
    3089     typedef _Digraph Digraph;
    3090     typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent;
     3337    : public DigraphAdaptorExtender<SplitNodesBase<const GR> > {
     3338#endif
     3339  public:
     3340    typedef GR Digraph;
     3341    typedef DigraphAdaptorExtender<SplitNodesBase<const GR> > Parent;
    30913342
    30923343    typedef typename Digraph::Node DigraphNode;
     
    30963347    typedef typename Parent::Arc Arc;
    30973348
    3098     /// \brief Constructor of the adaptor.
     3349    /// \brief Constructor
    30993350    ///
    31003351    /// Constructor of the adaptor.
    3101     SplitNodes(Digraph& g) {
     3352    SplitNodes(const Digraph& g) {
    31023353      Parent::setDigraph(g);
    31033354    }
    31043355
    3105     /// \brief Returns true when the node is in-node.
    3106     ///
    3107     /// Returns true when the node is in-node.
     3356    /// \brief Returns \c true if the given node is an in-node.
     3357    ///
     3358    /// Returns \c true if the given node is an in-node.
    31083359    static bool inNode(const Node& n) {
    31093360      return Parent::inNode(n);
    31103361    }
    31113362
    3112     /// \brief Returns true when the node is out-node.
    3113     ///
    3114     /// Returns true when the node is out-node.
     3363    /// \brief Returns \c true if the given node is an out-node.
     3364    ///
     3365    /// Returns \c true if the given node is an out-node.
    31153366    static bool outNode(const Node& n) {
    31163367      return Parent::outNode(n);
    31173368    }
    31183369
    3119     /// \brief Returns true when the arc is arc in the original digraph.
    3120     ///
    3121     /// Returns true when the arc is arc in the original digraph.
     3370    /// \brief Returns \c true if the given arc is an original arc.
     3371    ///
     3372    /// Returns \c true if the given arc is one of the arcs in the
     3373    /// original digraph.
    31223374    static bool origArc(const Arc& a) {
    31233375      return Parent::origArc(a);
    31243376    }
    31253377
    3126     /// \brief Returns true when the arc binds an in-node and an out-node.
    3127     ///
    3128     /// Returns true when the arc binds an in-node and an out-node.
     3378    /// \brief Returns \c true if the given arc is a bind arc.
     3379    ///
     3380    /// Returns \c true if the given arc is a bind arc, i.e. it connects
     3381    /// an in-node and an out-node.
    31293382    static bool bindArc(const Arc& a) {
    31303383      return Parent::bindArc(a);
    31313384    }
    31323385
    3133     /// \brief Gives back the in-node created from the \c node.
    3134     ///
    3135     /// Gives back the in-node created from the \c node.
     3386    /// \brief Returns the in-node created from the given original node.
     3387    ///
     3388    /// Returns the in-node created from the given original node.
    31363389    static Node inNode(const DigraphNode& n) {
    31373390      return Parent::inNode(n);
    31383391    }
    31393392
    3140     /// \brief Gives back the out-node created from the \c node.
    3141     ///
    3142     /// Gives back the out-node created from the \c node.
     3393    /// \brief Returns the out-node created from the given original node.
     3394    ///
     3395    /// Returns the out-node created from the given original node.
    31433396    static Node outNode(const DigraphNode& n) {
    31443397      return Parent::outNode(n);
    31453398    }
    31463399
    3147     /// \brief Gives back the arc binds the two part of the node.
    3148     ///
    3149     /// Gives back the arc binds the two part of the node.
     3400    /// \brief Returns the bind arc that corresponds to the given
     3401    /// original node.
     3402    ///
     3403    /// Returns the bind arc in the adaptor that corresponds to the given
     3404    /// original node, i.e. the arc connecting the in-node and out-node
     3405    /// of \c n.
    31503406    static Arc arc(const DigraphNode& n) {
    31513407      return Parent::arc(n);
    31523408    }
    31533409
    3154     /// \brief Gives back the arc of the original arc.
    3155     ///
    3156     /// Gives back the arc of the original arc.
     3410    /// \brief Returns the arc that corresponds to the given original arc.
     3411    ///
     3412    /// Returns the arc in the adaptor that corresponds to the given
     3413    /// original arc.
    31573414    static Arc arc(const DigraphArc& a) {
    31583415      return Parent::arc(a);
    31593416    }
    31603417
    3161     /// \brief NodeMap combined from two original NodeMap
    3162     ///
    3163     /// This class adapt two of the original digraph NodeMap to
    3164     /// get a node map on the adapted digraph.
     3418    /// \brief Node map combined from two original node maps
     3419    ///
     3420    /// This map adaptor class adapts two node maps of the original digraph
     3421    /// to get a node map of the split digraph.
     3422    /// Its value type is inherited from the first node map type
     3423    /// (\c InNodeMap).
    31653424    template <typename InNodeMap, typename OutNodeMap>
    31663425    class CombinedNodeMap {
    31673426    public:
    31683427
     3428      /// The key type of the map
    31693429      typedef Node Key;
     3430      /// The value type of the map
    31703431      typedef typename InNodeMap::Value Value;
    31713432
    3172       /// \brief Constructor
    3173       ///
    3174       /// Constructor.
     3433      typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
     3434      typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
     3435      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
     3436      typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
     3437      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
     3438
     3439      /// Constructor
    31753440      CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
    31763441        : _in_map(in_map), _out_map(out_map) {}
    31773442
    3178       /// \brief The subscript operator.
    3179       ///
    3180       /// The subscript operator.
     3443      /// Returns the value associated with the given key.
     3444      Value operator[](const Key& key) const {
     3445        if (Parent::inNode(key)) {
     3446          return _in_map[key];
     3447        } else {
     3448          return _out_map[key];
     3449        }
     3450      }
     3451
     3452      /// Returns a reference to the value associated with the given key.
    31813453      Value& operator[](const Key& key) {
    31823454        if (Parent::inNode(key)) {
     
    31873459      }
    31883460
    3189       /// \brief The const subscript operator.
    3190       ///
    3191       /// The const subscript operator.
    3192       Value operator[](const Key& key) const {
    3193         if (Parent::inNode(key)) {
    3194           return _in_map[key];
    3195         } else {
    3196           return _out_map[key];
    3197         }
    3198       }
    3199 
    3200       /// \brief The setter function of the map.
    3201       ///
    3202       /// The setter function of the map.
     3461      /// Sets the value associated with the given key.
    32033462      void set(const Key& key, const Value& value) {
    32043463        if (Parent::inNode(key)) {
     
    32173476
    32183477
    3219     /// \brief Just gives back a combined node map
    3220     ///
    3221     /// Just gives back a combined node map
     3478    /// \brief Returns a combined node map
     3479    ///
     3480    /// This function just returns a combined node map.
    32223481    template <typename InNodeMap, typename OutNodeMap>
    32233482    static CombinedNodeMap<InNodeMap, OutNodeMap>
     
    32453504    }
    32463505
    3247     /// \brief ArcMap combined from an original ArcMap and a NodeMap
    3248     ///
    3249     /// This class adapt an original ArcMap and a NodeMap to get an
    3250     /// arc map on the adapted digraph
    3251     template <typename DigraphArcMap, typename DigraphNodeMap>
     3506    /// \brief Arc map combined from an arc map and a node map of the
     3507    /// original digraph.
     3508    ///
     3509    /// This map adaptor class adapts an arc map and a node map of the
     3510    /// original digraph to get an arc map of the split digraph.
     3511    /// Its value type is inherited from the original arc map type
     3512    /// (\c ArcMap).
     3513    template <typename ArcMap, typename NodeMap>
    32523514    class CombinedArcMap {
    32533515    public:
    32543516
     3517      /// The key type of the map
    32553518      typedef Arc Key;
    3256       typedef typename DigraphArcMap::Value Value;
    3257 
    3258       /// \brief Constructor
    3259       ///
    3260       /// Constructor.
    3261       CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
     3519      /// The value type of the map
     3520      typedef typename ArcMap::Value Value;
     3521
     3522      typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag;
     3523      typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue;
     3524      typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue;
     3525      typedef typename MapTraits<ArcMap>::ReturnValue Reference;
     3526      typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference;
     3527
     3528      /// Constructor
     3529      CombinedArcMap(ArcMap& arc_map, NodeMap& node_map)
    32623530        : _arc_map(arc_map), _node_map(node_map) {}
    32633531
    3264       /// \brief The subscript operator.
    3265       ///
    3266       /// The subscript operator.
     3532      /// Returns the value associated with the given key.
     3533      Value operator[](const Key& arc) const {
     3534        if (Parent::origArc(arc)) {
     3535          return _arc_map[arc];
     3536        } else {
     3537          return _node_map[arc];
     3538        }
     3539      }
     3540
     3541      /// Returns a reference to the value associated with the given key.
     3542      Value& operator[](const Key& arc) {
     3543        if (Parent::origArc(arc)) {
     3544          return _arc_map[arc];
     3545        } else {
     3546          return _node_map[arc];
     3547        }
     3548      }
     3549
     3550      /// Sets the value associated with the given key.
    32673551      void set(const Arc& arc, const Value& val) {
    32683552        if (Parent::origArc(arc)) {
     
    32733557      }
    32743558
    3275       /// \brief The const subscript operator.
    3276       ///
    3277       /// The const subscript operator.
    3278       Value operator[](const Key& arc) const {
    3279         if (Parent::origArc(arc)) {
    3280           return _arc_map[arc];
    3281         } else {
    3282           return _node_map[arc];
    3283         }
    3284       }
    3285 
    3286       /// \brief The const subscript operator.
    3287       ///
    3288       /// The const subscript operator.
    3289       Value& operator[](const Key& arc) {
    3290         if (Parent::origArc(arc)) {
    3291           return _arc_map[arc];
    3292         } else {
    3293           return _node_map[arc];
    3294         }
    3295       }
    3296 
    32973559    private:
    3298       DigraphArcMap& _arc_map;
    3299       DigraphNodeMap& _node_map;
     3560      ArcMap& _arc_map;
     3561      NodeMap& _node_map;
    33003562    };
    33013563
    3302     /// \brief Just gives back a combined arc map
    3303     ///
    3304     /// Just gives back a combined arc map
    3305     template <typename DigraphArcMap, typename DigraphNodeMap>
    3306     static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
    3307     combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
    3308       return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
    3309     }
    3310 
    3311     template <typename DigraphArcMap, typename DigraphNodeMap>
    3312     static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
    3313     combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
    3314       return CombinedArcMap<const DigraphArcMap,
    3315         DigraphNodeMap>(arc_map, node_map);
    3316     }
    3317 
    3318     template <typename DigraphArcMap, typename DigraphNodeMap>
    3319     static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
    3320     combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
    3321       return CombinedArcMap<DigraphArcMap,
    3322         const DigraphNodeMap>(arc_map, node_map);
    3323     }
    3324 
    3325     template <typename DigraphArcMap, typename DigraphNodeMap>
    3326     static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
    3327     combinedArcMap(const DigraphArcMap& arc_map,
    3328                    const DigraphNodeMap& node_map) {
    3329       return CombinedArcMap<const DigraphArcMap,
    3330         const DigraphNodeMap>(arc_map, node_map);
     3564    /// \brief Returns a combined arc map
     3565    ///
     3566    /// This function just returns a combined arc map.
     3567    template <typename ArcMap, typename NodeMap>
     3568    static CombinedArcMap<ArcMap, NodeMap>
     3569    combinedArcMap(ArcMap& arc_map, NodeMap& node_map) {
     3570      return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map);
     3571    }
     3572
     3573    template <typename ArcMap, typename NodeMap>
     3574    static CombinedArcMap<const ArcMap, NodeMap>
     3575    combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) {
     3576      return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map);
     3577    }
     3578
     3579    template <typename ArcMap, typename NodeMap>
     3580    static CombinedArcMap<ArcMap, const NodeMap>
     3581    combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) {
     3582      return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map);
     3583    }
     3584
     3585    template <typename ArcMap, typename NodeMap>
     3586    static CombinedArcMap<const ArcMap, const NodeMap>
     3587    combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) {
     3588      return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map);
    33313589    }
    33323590
    33333591  };
    33343592
    3335   /// \brief Just gives back a node splitter
    3336   ///
    3337   /// Just gives back a node splitter
    3338   template<typename Digraph>
    3339   SplitNodes<Digraph>
    3340   splitNodes(const Digraph& digraph) {
    3341     return SplitNodes<Digraph>(digraph);
     3593  /// \brief Returns a (read-only) SplitNodes adaptor
     3594  ///
     3595  /// This function just returns a (read-only) \ref SplitNodes adaptor.
     3596  /// \ingroup graph_adaptors
     3597  /// \relates SplitNodes
     3598  template<typename GR>
     3599  SplitNodes<GR>
     3600  splitNodes(const GR& digraph) {
     3601    return SplitNodes<GR>(digraph);
    33423602  }
    33433603
    3344 
    33453604} //namespace lemon
    33463605
  • lemon/bits/graph_adaptor_extender.h

    r440 r455  
    174174  };
    175175
    176 
    177   /// \ingroup digraphbits
    178   ///
    179   /// \brief Extender for the GraphAdaptors
    180176  template <typename _Graph>
    181177  class GraphAdaptorExtender : public _Graph {
  • lemon/bits/graph_adaptor_extender.h

    r453 r455  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
Note: See TracChangeset for help on using the changeset viewer.