COIN-OR::LEMON - Graph Library

Changeset 455:5a1e9fdcfd3a in lemon-1.2 for lemon


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

Location:
lemon
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • 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.