lemon/bfs.h
changeset 719 ba79e8d64448
parent 716 f47b6c94577e
parent 713 4ac30454f1c1
child 786 e20173729589
child 787 c2230649a493
     1.1 --- a/lemon/bfs.h	Thu Aug 20 20:34:30 2009 +0200
     1.2 +++ b/lemon/bfs.h	Fri Sep 25 09:33:09 2009 +0200
     1.3 @@ -47,7 +47,7 @@
     1.4      ///
     1.5      ///The type of the map that stores the predecessor
     1.6      ///arcs of the shortest paths.
     1.7 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     1.8 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     1.9      typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    1.10      ///Instantiates a \c PredMap.
    1.11  
    1.12 @@ -62,7 +62,8 @@
    1.13      ///The type of the map that indicates which nodes are processed.
    1.14  
    1.15      ///The type of the map that indicates which nodes are processed.
    1.16 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.17 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    1.18 +    ///By default it is a NullMap.
    1.19      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    1.20      ///Instantiates a \c ProcessedMap.
    1.21  
    1.22 @@ -81,7 +82,7 @@
    1.23      ///The type of the map that indicates which nodes are reached.
    1.24  
    1.25      ///The type of the map that indicates which nodes are reached.
    1.26 -    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    1.27 +    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    1.28      typedef typename Digraph::template NodeMap<bool> ReachedMap;
    1.29      ///Instantiates a \c ReachedMap.
    1.30  
    1.31 @@ -96,7 +97,7 @@
    1.32      ///The type of the map that stores the distances of the nodes.
    1.33  
    1.34      ///The type of the map that stores the distances of the nodes.
    1.35 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.36 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    1.37      typedef typename Digraph::template NodeMap<int> DistMap;
    1.38      ///Instantiates a \c DistMap.
    1.39  
    1.40 @@ -225,7 +226,7 @@
    1.41      ///
    1.42      ///\ref named-templ-param "Named parameter" for setting
    1.43      ///\c PredMap type.
    1.44 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.45 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    1.46      template <class T>
    1.47      struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
    1.48        typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
    1.49 @@ -245,7 +246,7 @@
    1.50      ///
    1.51      ///\ref named-templ-param "Named parameter" for setting
    1.52      ///\c DistMap type.
    1.53 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.54 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    1.55      template <class T>
    1.56      struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
    1.57        typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
    1.58 @@ -265,7 +266,7 @@
    1.59      ///
    1.60      ///\ref named-templ-param "Named parameter" for setting
    1.61      ///\c ReachedMap type.
    1.62 -    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    1.63 +    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    1.64      template <class T>
    1.65      struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
    1.66        typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
    1.67 @@ -285,7 +286,7 @@
    1.68      ///
    1.69      ///\ref named-templ-param "Named parameter" for setting
    1.70      ///\c ProcessedMap type.
    1.71 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.72 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    1.73      template <class T>
    1.74      struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
    1.75        typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
    1.76 @@ -413,8 +414,8 @@
    1.77      ///\name Execution Control
    1.78      ///The simplest way to execute the BFS algorithm is to use one of the
    1.79      ///member functions called \ref run(Node) "run()".\n
    1.80 -    ///If you need more control on the execution, first you have to call
    1.81 -    ///\ref init(), then you can add several source nodes with
    1.82 +    ///If you need better control on the execution, you have to call
    1.83 +    ///\ref init() first, then you can add several source nodes with
    1.84      ///\ref addSource(). Finally the actual path computation can be
    1.85      ///performed with one of the \ref start() functions.
    1.86  
    1.87 @@ -737,9 +738,9 @@
    1.88  
    1.89      ///@{
    1.90  
    1.91 -    ///The shortest path to a node.
    1.92 +    ///The shortest path to the given node.
    1.93  
    1.94 -    ///Returns the shortest path to a node.
    1.95 +    ///Returns the shortest path to the given node from the root(s).
    1.96      ///
    1.97      ///\warning \c t should be reached from the root(s).
    1.98      ///
    1.99 @@ -747,9 +748,9 @@
   1.100      ///must be called before using this function.
   1.101      Path path(Node t) const { return Path(*G, *_pred, t); }
   1.102  
   1.103 -    ///The distance of a node from the root(s).
   1.104 +    ///The distance of the given node from the root(s).
   1.105  
   1.106 -    ///Returns the distance of a node from the root(s).
   1.107 +    ///Returns the distance of the given node from the root(s).
   1.108      ///
   1.109      ///\warning If node \c v is not reached from the root(s), then
   1.110      ///the return value of this function is undefined.
   1.111 @@ -758,29 +759,31 @@
   1.112      ///must be called before using this function.
   1.113      int dist(Node v) const { return (*_dist)[v]; }
   1.114  
   1.115 -    ///Returns the 'previous arc' of the shortest path tree for a node.
   1.116 -
   1.117 +    ///\brief Returns the 'previous arc' of the shortest path tree for
   1.118 +    ///the given node.
   1.119 +    ///
   1.120      ///This function returns the 'previous arc' of the shortest path
   1.121      ///tree for the node \c v, i.e. it returns the last arc of a
   1.122      ///shortest path from a root to \c v. It is \c INVALID if \c v
   1.123      ///is not reached from the root(s) or if \c v is a root.
   1.124      ///
   1.125      ///The shortest path tree used here is equal to the shortest path
   1.126 -    ///tree used in \ref predNode().
   1.127 +    ///tree used in \ref predNode() and \ref predMap().
   1.128      ///
   1.129      ///\pre Either \ref run(Node) "run()" or \ref init()
   1.130      ///must be called before using this function.
   1.131      Arc predArc(Node v) const { return (*_pred)[v];}
   1.132  
   1.133 -    ///Returns the 'previous node' of the shortest path tree for a node.
   1.134 -
   1.135 +    ///\brief Returns the 'previous node' of the shortest path tree for
   1.136 +    ///the given node.
   1.137 +    ///
   1.138      ///This function returns the 'previous node' of the shortest path
   1.139      ///tree for the node \c v, i.e. it returns the last but one node
   1.140 -    ///from a shortest path from a root to \c v. It is \c INVALID
   1.141 +    ///of a shortest path from a root to \c v. It is \c INVALID
   1.142      ///if \c v is not reached from the root(s) or if \c v is a root.
   1.143      ///
   1.144      ///The shortest path tree used here is equal to the shortest path
   1.145 -    ///tree used in \ref predArc().
   1.146 +    ///tree used in \ref predArc() and \ref predMap().
   1.147      ///
   1.148      ///\pre Either \ref run(Node) "run()" or \ref init()
   1.149      ///must be called before using this function.
   1.150 @@ -801,13 +804,13 @@
   1.151      ///predecessor arcs.
   1.152      ///
   1.153      ///Returns a const reference to the node map that stores the predecessor
   1.154 -    ///arcs, which form the shortest path tree.
   1.155 +    ///arcs, which form the shortest path tree (forest).
   1.156      ///
   1.157      ///\pre Either \ref run(Node) "run()" or \ref init()
   1.158      ///must be called before using this function.
   1.159      const PredMap &predMap() const { return *_pred;}
   1.160  
   1.161 -    ///Checks if a node is reached from the root(s).
   1.162 +    ///Checks if the given node is reached from the root(s).
   1.163  
   1.164      ///Returns \c true if \c v is reached from the root(s).
   1.165      ///
   1.166 @@ -833,7 +836,7 @@
   1.167      ///
   1.168      ///The type of the map that stores the predecessor
   1.169      ///arcs of the shortest paths.
   1.170 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.171 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   1.172      typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   1.173      ///Instantiates a PredMap.
   1.174  
   1.175 @@ -848,7 +851,7 @@
   1.176      ///The type of the map that indicates which nodes are processed.
   1.177  
   1.178      ///The type of the map that indicates which nodes are processed.
   1.179 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.180 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   1.181      ///By default it is a NullMap.
   1.182      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   1.183      ///Instantiates a ProcessedMap.
   1.184 @@ -868,7 +871,7 @@
   1.185      ///The type of the map that indicates which nodes are reached.
   1.186  
   1.187      ///The type of the map that indicates which nodes are reached.
   1.188 -    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   1.189 +    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   1.190      typedef typename Digraph::template NodeMap<bool> ReachedMap;
   1.191      ///Instantiates a ReachedMap.
   1.192  
   1.193 @@ -883,7 +886,7 @@
   1.194      ///The type of the map that stores the distances of the nodes.
   1.195  
   1.196      ///The type of the map that stores the distances of the nodes.
   1.197 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.198 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   1.199      typedef typename Digraph::template NodeMap<int> DistMap;
   1.200      ///Instantiates a DistMap.
   1.201  
   1.202 @@ -898,18 +901,14 @@
   1.203      ///The type of the shortest paths.
   1.204  
   1.205      ///The type of the shortest paths.
   1.206 -    ///It must meet the \ref concepts::Path "Path" concept.
   1.207 +    ///It must conform to the \ref concepts::Path "Path" concept.
   1.208      typedef lemon::Path<Digraph> Path;
   1.209    };
   1.210  
   1.211    /// Default traits class used by BfsWizard
   1.212  
   1.213 -  /// To make it easier to use Bfs algorithm
   1.214 -  /// we have created a wizard class.
   1.215 -  /// This \ref BfsWizard class needs default traits,
   1.216 -  /// as well as the \ref Bfs class.
   1.217 -  /// The \ref BfsWizardBase is a class to be the default traits of the
   1.218 -  /// \ref BfsWizard class.
   1.219 +  /// Default traits class used by BfsWizard.
   1.220 +  /// \tparam GR The type of the digraph.
   1.221    template<class GR>
   1.222    class BfsWizardBase : public BfsWizardDefaultTraits<GR>
   1.223    {
   1.224 @@ -937,7 +936,7 @@
   1.225      public:
   1.226      /// Constructor.
   1.227  
   1.228 -    /// This constructor does not require parameters, therefore it initiates
   1.229 +    /// This constructor does not require parameters, it initiates
   1.230      /// all of the attributes to \c 0.
   1.231      BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
   1.232                        _dist(0), _path(0), _di(0) {}
   1.233 @@ -967,7 +966,6 @@
   1.234    {
   1.235      typedef TR Base;
   1.236  
   1.237 -    ///The type of the digraph the algorithm runs on.
   1.238      typedef typename TR::Digraph Digraph;
   1.239  
   1.240      typedef typename Digraph::Node Node;
   1.241 @@ -975,16 +973,10 @@
   1.242      typedef typename Digraph::Arc Arc;
   1.243      typedef typename Digraph::OutArcIt OutArcIt;
   1.244  
   1.245 -    ///\brief The type of the map that stores the predecessor
   1.246 -    ///arcs of the shortest paths.
   1.247      typedef typename TR::PredMap PredMap;
   1.248 -    ///\brief The type of the map that stores the distances of the nodes.
   1.249      typedef typename TR::DistMap DistMap;
   1.250 -    ///\brief The type of the map that indicates which nodes are reached.
   1.251      typedef typename TR::ReachedMap ReachedMap;
   1.252 -    ///\brief The type of the map that indicates which nodes are processed.
   1.253      typedef typename TR::ProcessedMap ProcessedMap;
   1.254 -    ///The type of the shortest paths
   1.255      typedef typename TR::Path Path;
   1.256  
   1.257    public:
   1.258 @@ -1067,11 +1059,12 @@
   1.259        static PredMap *createPredMap(const Digraph &) { return 0; };
   1.260        SetPredMapBase(const TR &b) : TR(b) {}
   1.261      };
   1.262 -    ///\brief \ref named-func-param "Named parameter"
   1.263 -    ///for setting PredMap object.
   1.264 +
   1.265 +    ///\brief \ref named-templ-param "Named parameter" for setting
   1.266 +    ///the predecessor map.
   1.267      ///
   1.268 -    ///\ref named-func-param "Named parameter"
   1.269 -    ///for setting PredMap object.
   1.270 +    ///\ref named-templ-param "Named parameter" function for setting
   1.271 +    ///the map that stores the predecessor arcs of the nodes.
   1.272      template<class T>
   1.273      BfsWizard<SetPredMapBase<T> > predMap(const T &t)
   1.274      {
   1.275 @@ -1085,11 +1078,12 @@
   1.276        static ReachedMap *createReachedMap(const Digraph &) { return 0; };
   1.277        SetReachedMapBase(const TR &b) : TR(b) {}
   1.278      };
   1.279 -    ///\brief \ref named-func-param "Named parameter"
   1.280 -    ///for setting ReachedMap object.
   1.281 +
   1.282 +    ///\brief \ref named-templ-param "Named parameter" for setting
   1.283 +    ///the reached map.
   1.284      ///
   1.285 -    /// \ref named-func-param "Named parameter"
   1.286 -    ///for setting ReachedMap object.
   1.287 +    ///\ref named-templ-param "Named parameter" function for setting
   1.288 +    ///the map that indicates which nodes are reached.
   1.289      template<class T>
   1.290      BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
   1.291      {
   1.292 @@ -1103,11 +1097,13 @@
   1.293        static DistMap *createDistMap(const Digraph &) { return 0; };
   1.294        SetDistMapBase(const TR &b) : TR(b) {}
   1.295      };
   1.296 -    ///\brief \ref named-func-param "Named parameter"
   1.297 -    ///for setting DistMap object.
   1.298 +
   1.299 +    ///\brief \ref named-templ-param "Named parameter" for setting
   1.300 +    ///the distance map.
   1.301      ///
   1.302 -    /// \ref named-func-param "Named parameter"
   1.303 -    ///for setting DistMap object.
   1.304 +    ///\ref named-templ-param "Named parameter" function for setting
   1.305 +    ///the map that stores the distances of the nodes calculated
   1.306 +    ///by the algorithm.
   1.307      template<class T>
   1.308      BfsWizard<SetDistMapBase<T> > distMap(const T &t)
   1.309      {
   1.310 @@ -1121,11 +1117,12 @@
   1.311        static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
   1.312        SetProcessedMapBase(const TR &b) : TR(b) {}
   1.313      };
   1.314 -    ///\brief \ref named-func-param "Named parameter"
   1.315 -    ///for setting ProcessedMap object.
   1.316 +
   1.317 +    ///\brief \ref named-func-param "Named parameter" for setting
   1.318 +    ///the processed map.
   1.319      ///
   1.320 -    /// \ref named-func-param "Named parameter"
   1.321 -    ///for setting ProcessedMap object.
   1.322 +    ///\ref named-templ-param "Named parameter" function for setting
   1.323 +    ///the map that indicates which nodes are processed.
   1.324      template<class T>
   1.325      BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
   1.326      {
   1.327 @@ -1264,7 +1261,7 @@
   1.328      /// \brief The type of the map that indicates which nodes are reached.
   1.329      ///
   1.330      /// The type of the map that indicates which nodes are reached.
   1.331 -    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   1.332 +    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   1.333      typedef typename Digraph::template NodeMap<bool> ReachedMap;
   1.334  
   1.335      /// \brief Instantiates a ReachedMap.
   1.336 @@ -1425,8 +1422,8 @@
   1.337      /// \name Execution Control
   1.338      /// The simplest way to execute the BFS algorithm is to use one of the
   1.339      /// member functions called \ref run(Node) "run()".\n
   1.340 -    /// If you need more control on the execution, first you have to call
   1.341 -    /// \ref init(), then you can add several source nodes with
   1.342 +    /// If you need better control on the execution, you have to call
   1.343 +    /// \ref init() first, then you can add several source nodes with
   1.344      /// \ref addSource(). Finally the actual path computation can be
   1.345      /// performed with one of the \ref start() functions.
   1.346  
   1.347 @@ -1735,7 +1732,7 @@
   1.348  
   1.349      ///@{
   1.350  
   1.351 -    /// \brief Checks if a node is reached from the root(s).
   1.352 +    /// \brief Checks if the given node is reached from the root(s).
   1.353      ///
   1.354      /// Returns \c true if \c v is reached from the root(s).
   1.355      ///