COIN-OR::LEMON - Graph Library

Changeset 964:7fdaa05a69a1 in lemon-1.2 for lemon/dfs.h


Ignore:
Timestamp:
09/13/12 11:56:19 (7 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
961:4bb9e72e1a41 (diff), 963:761fe0846f49 (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 #449 to branches >=1.2

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/dfs.h

    r942 r964  
    11941194      }
    11951195      _Visitor& visitor;
     1196      Constraints() {}
    11961197    };
    11971198  };
  • lemon/dfs.h

    r953 r964  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    4848    ///The type of the map that stores the predecessor
    4949    ///arcs of the %DFS paths.
    50     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    5252    ///Instantiates a \c PredMap.
     
    6363
    6464    ///The type of the map that indicates which nodes are processed.
    65     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     65    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     66    ///By default, it is a NullMap.
    6667    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6768    ///Instantiates a \c ProcessedMap.
     
    8283
    8384    ///The type of the map that indicates which nodes are reached.
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     85    ///It must conform to
     86    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8587    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8688    ///Instantiates a \c ReachedMap.
     
    9799
    98100    ///The type of the map that stores the distances of the nodes.
    99     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     101    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    100102    typedef typename Digraph::template NodeMap<int> DistMap;
    101103    ///Instantiates a \c DistMap.
     
    121123  ///\tparam GR The type of the digraph the algorithm runs on.
    122124  ///The default type is \ref ListDigraph.
     125  ///\tparam TR The traits class that defines various types used by the
     126  ///algorithm. By default, it is \ref DfsDefaultTraits
     127  ///"DfsDefaultTraits<GR>".
     128  ///In most cases, this parameter should not be set directly,
     129  ///consider to use the named template parameters instead.
    123130#ifdef DOXYGEN
    124131  template <typename GR,
     
    225232    ///\ref named-templ-param "Named parameter" for setting
    226233    ///\c PredMap type.
    227     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     234    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    228235    template <class T>
    229236    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
     
    245252    ///\ref named-templ-param "Named parameter" for setting
    246253    ///\c DistMap type.
    247     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     254    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    248255    template <class T>
    249256    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
     
    265272    ///\ref named-templ-param "Named parameter" for setting
    266273    ///\c ReachedMap type.
    267     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     274    ///It must conform to
     275    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    268276    template <class T>
    269277    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
     
    285293    ///\ref named-templ-param "Named parameter" for setting
    286294    ///\c ProcessedMap type.
    287     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     295    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    288296    template <class T>
    289297    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
     
    412420    ///The simplest way to execute the DFS algorithm is to use one of the
    413421    ///member functions called \ref run(Node) "run()".\n
    414     ///If you need more control on the execution, first you have to call
    415     ///\ref init(), then you can add a source node with \ref addSource()
     422    ///If you need better control on the execution, you have to call
     423    ///\ref init() first, then you can add a source node with \ref addSource()
    416424    ///and perform the actual computation with \ref start().
    417425    ///This procedure can be repeated if there are nodes that have not
     
    633641    ///Runs the algorithm to visit all nodes in the digraph.
    634642
    635     ///This method runs the %DFS algorithm in order to compute the
    636     ///%DFS path to each node.
    637     ///
    638     ///The algorithm computes
    639     ///- the %DFS tree (forest),
    640     ///- the distance of each node from the root(s) in the %DFS tree.
     643    ///This method runs the %DFS algorithm in order to visit all nodes
     644    ///in the digraph.
    641645    ///
    642646    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
     
    670674    ///@{
    671675
    672     ///The DFS path to a node.
    673 
    674     ///Returns the DFS path to a node.
     676    ///The DFS path to the given node.
     677
     678    ///Returns the DFS path to the given node from the root(s).
    675679    ///
    676680    ///\warning \c t should be reached from the root(s).
     
    680684    Path path(Node t) const { return Path(*G, *_pred, t); }
    681685
    682     ///The distance of a node from the root(s).
    683 
    684     ///Returns the distance of a node from the root(s).
     686    ///The distance of the given node from the root(s).
     687
     688    ///Returns the distance of the given node from the root(s).
    685689    ///
    686690    ///\warning If node \c v is not reached from the root(s), then
     
    691695    int dist(Node v) const { return (*_dist)[v]; }
    692696
    693     ///Returns the 'previous arc' of the %DFS tree for a node.
     697    ///Returns the 'previous arc' of the %DFS tree for the given node.
    694698
    695699    ///This function returns the 'previous arc' of the %DFS tree for the
     
    699703    ///
    700704    ///The %DFS tree used here is equal to the %DFS tree used in
    701     ///\ref predNode().
     705    ///\ref predNode() and \ref predMap().
    702706    ///
    703707    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    705709    Arc predArc(Node v) const { return (*_pred)[v];}
    706710
    707     ///Returns the 'previous node' of the %DFS tree.
     711    ///Returns the 'previous node' of the %DFS tree for the given node.
    708712
    709713    ///This function returns the 'previous node' of the %DFS
    710714    ///tree for the node \c v, i.e. it returns the last but one node
    711     ///from a %DFS path from a root to \c v. It is \c INVALID
     715    ///of a %DFS path from a root to \c v. It is \c INVALID
    712716    ///if \c v is not reached from the root(s) or if \c v is a root.
    713717    ///
    714718    ///The %DFS tree used here is equal to the %DFS tree used in
    715     ///\ref predArc().
     719    ///\ref predArc() and \ref predMap().
    716720    ///
    717721    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    734738    ///
    735739    ///Returns a const reference to the node map that stores the predecessor
    736     ///arcs, which form the DFS tree.
     740    ///arcs, which form the DFS tree (forest).
    737741    ///
    738742    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    740744    const PredMap &predMap() const { return *_pred;}
    741745
    742     ///Checks if a node is reached from the root(s).
     746    ///Checks if the given node. node is reached from the root(s).
    743747
    744748    ///Returns \c true if \c v is reached from the root(s).
     
    766770    ///The type of the map that stores the predecessor
    767771    ///arcs of the %DFS paths.
    768     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     772    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    769773    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    770774    ///Instantiates a PredMap.
     
    781785
    782786    ///The type of the map that indicates which nodes are processed.
    783     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    784     ///By default it is a NullMap.
     787    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     788    ///By default, it is a NullMap.
    785789    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    786790    ///Instantiates a ProcessedMap.
     
    801805
    802806    ///The type of the map that indicates which nodes are reached.
    803     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     807    ///It must conform to
     808    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    804809    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    805810    ///Instantiates a ReachedMap.
     
    816821
    817822    ///The type of the map that stores the distances of the nodes.
    818     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     823    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    819824    typedef typename Digraph::template NodeMap<int> DistMap;
    820825    ///Instantiates a DistMap.
     
    831836
    832837    ///The type of the DFS paths.
    833     ///It must meet the \ref concepts::Path "Path" concept.
     838    ///It must conform to the \ref concepts::Path "Path" concept.
    834839    typedef lemon::Path<Digraph> Path;
    835840  };
     
    837842  /// Default traits class used by DfsWizard
    838843
    839   /// To make it easier to use Dfs algorithm
    840   /// we have created a wizard class.
    841   /// This \ref DfsWizard class needs default traits,
    842   /// as well as the \ref Dfs class.
    843   /// The \ref DfsWizardBase is a class to be the default traits of the
    844   /// \ref DfsWizard class.
     844  /// Default traits class used by DfsWizard.
     845  /// \tparam GR The type of the digraph.
    845846  template<class GR>
    846847  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
     
    870871    /// Constructor.
    871872
    872     /// This constructor does not require parameters, therefore it initiates
     873    /// This constructor does not require parameters, it initiates
    873874    /// all of the attributes to \c 0.
    874875    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
     
    895896  /// This class should only be used through the \ref dfs() function,
    896897  /// which makes it easier to use the algorithm.
     898  ///
     899  /// \tparam TR The traits class that defines various types used by the
     900  /// algorithm.
    897901  template<class TR>
    898902  class DfsWizard : public TR
     
    900904    typedef TR Base;
    901905
    902     ///The type of the digraph the algorithm runs on.
    903906    typedef typename TR::Digraph Digraph;
    904907
     
    908911    typedef typename Digraph::OutArcIt OutArcIt;
    909912
    910     ///\brief The type of the map that stores the predecessor
    911     ///arcs of the DFS paths.
    912913    typedef typename TR::PredMap PredMap;
    913     ///\brief The type of the map that stores the distances of the nodes.
    914914    typedef typename TR::DistMap DistMap;
    915     ///\brief The type of the map that indicates which nodes are reached.
    916915    typedef typename TR::ReachedMap ReachedMap;
    917     ///\brief The type of the map that indicates which nodes are processed.
    918916    typedef typename TR::ProcessedMap ProcessedMap;
    919     ///The type of the DFS paths
    920917    typedef typename TR::Path Path;
    921918
     
    987984    ///Runs DFS algorithm to visit all nodes in the digraph.
    988985
    989     ///This method runs DFS algorithm in order to compute
    990     ///the DFS path to each node.
     986    ///This method runs DFS algorithm in order to visit all nodes
     987    ///in the digraph.
    991988    void run()
    992989    {
     
    1000997      SetPredMapBase(const TR &b) : TR(b) {}
    1001998    };
    1002     ///\brief \ref named-func-param "Named parameter"
    1003     ///for setting PredMap object.
    1004     ///
    1005     ///\ref named-func-param "Named parameter"
    1006     ///for setting PredMap object.
     999
     1000    ///\brief \ref named-templ-param "Named parameter" for setting
     1001    ///the predecessor map.
     1002    ///
     1003    ///\ref named-templ-param "Named parameter" function for setting
     1004    ///the map that stores the predecessor arcs of the nodes.
    10071005    template<class T>
    10081006    DfsWizard<SetPredMapBase<T> > predMap(const T &t)
     
    10181016      SetReachedMapBase(const TR &b) : TR(b) {}
    10191017    };
    1020     ///\brief \ref named-func-param "Named parameter"
    1021     ///for setting ReachedMap object.
    1022     ///
    1023     /// \ref named-func-param "Named parameter"
    1024     ///for setting ReachedMap object.
     1018
     1019    ///\brief \ref named-templ-param "Named parameter" for setting
     1020    ///the reached map.
     1021    ///
     1022    ///\ref named-templ-param "Named parameter" function for setting
     1023    ///the map that indicates which nodes are reached.
    10251024    template<class T>
    10261025    DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
     
    10361035      SetDistMapBase(const TR &b) : TR(b) {}
    10371036    };
    1038     ///\brief \ref named-func-param "Named parameter"
    1039     ///for setting DistMap object.
    1040     ///
    1041     /// \ref named-func-param "Named parameter"
    1042     ///for setting DistMap object.
     1037
     1038    ///\brief \ref named-templ-param "Named parameter" for setting
     1039    ///the distance map.
     1040    ///
     1041    ///\ref named-templ-param "Named parameter" function for setting
     1042    ///the map that stores the distances of the nodes calculated
     1043    ///by the algorithm.
    10431044    template<class T>
    10441045    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
     
    10541055      SetProcessedMapBase(const TR &b) : TR(b) {}
    10551056    };
    1056     ///\brief \ref named-func-param "Named parameter"
    1057     ///for setting ProcessedMap object.
    1058     ///
    1059     /// \ref named-func-param "Named parameter"
    1060     ///for setting ProcessedMap object.
     1057
     1058    ///\brief \ref named-func-param "Named parameter" for setting
     1059    ///the processed map.
     1060    ///
     1061    ///\ref named-templ-param "Named parameter" function for setting
     1062    ///the map that indicates which nodes are processed.
    10611063    template<class T>
    10621064    DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    12101212    ///
    12111213    /// The type of the map that indicates which nodes are reached.
    1212     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1214    /// It must conform to the
     1215    /// \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12131216    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12141217
     
    12481251  /// does not observe the DFS events. If you want to observe the DFS
    12491252  /// events, you should implement your own visitor class.
    1250   /// \tparam TR Traits class to set various data types used by the
    1251   /// algorithm. The default traits class is
    1252   /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
    1253   /// See \ref DfsVisitDefaultTraits for the documentation of
    1254   /// a DFS visit traits class.
     1253  /// \tparam TR The traits class that defines various types used by the
     1254  /// algorithm. By default, it is \ref DfsVisitDefaultTraits
     1255  /// "DfsVisitDefaultTraits<GR>".
     1256  /// In most cases, this parameter should not be set directly,
     1257  /// consider to use the named template parameters instead.
    12551258#ifdef DOXYGEN
    12561259  template <typename GR, typename VS, typename TR>
     
    13711374    /// The simplest way to execute the DFS algorithm is to use one of the
    13721375    /// member functions called \ref run(Node) "run()".\n
    1373     /// If you need more control on the execution, first you have to call
    1374     /// \ref init(), then you can add a source node with \ref addSource()
     1376    /// If you need better control on the execution, you have to call
     1377    /// \ref init() first, then you can add a source node with \ref addSource()
    13751378    /// and perform the actual computation with \ref start().
    13761379    /// This procedure can be repeated if there are nodes that have not
     
    15851588    /// \brief Runs the algorithm to visit all nodes in the digraph.
    15861589
    1587     /// This method runs the %DFS algorithm in order to
    1588     /// compute the %DFS path to each node.
    1589     ///
    1590     /// The algorithm computes
    1591     /// - the %DFS tree (forest),
    1592     /// - the distance of each node from the root(s) in the %DFS tree.
     1590    /// This method runs the %DFS algorithm in order to visit all nodes
     1591    /// in the digraph.
    15931592    ///
    15941593    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
     
    16221621    ///@{
    16231622
    1624     /// \brief Checks if a node is reached from the root(s).
     1623    /// \brief Checks if the given node is reached from the root(s).
    16251624    ///
    16261625    /// Returns \c true if \c v is reached from the root(s).
Note: See TracChangeset for help on using the changeset viewer.