1.1 --- a/lemon/bfs.h Sun Nov 30 09:39:34 2008 +0000
1.2 +++ b/lemon/bfs.h Sun Nov 30 19:17:51 2008 +0100
1.3 @@ -51,7 +51,7 @@
1.4 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.5 ///Instantiates a PredMap.
1.6
1.7 - ///This function instantiates a PredMap.
1.8 + ///This function instantiates a PredMap.
1.9 ///\param g is the digraph, to which we would like to define the
1.10 ///PredMap.
1.11 static PredMap *createPredMap(const Digraph &g)
1.12 @@ -80,7 +80,8 @@
1.13
1.14 ///The type of the map that indicates which nodes are reached.
1.15
1.16 - ///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.17 + ///The type of the map that indicates which nodes are reached.
1.18 + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.19 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.20 ///Instantiates a ReachedMap.
1.21
1.22 @@ -118,13 +119,7 @@
1.23 ///used easier.
1.24 ///
1.25 ///\tparam GR The type of the digraph the algorithm runs on.
1.26 - ///The default value is \ref ListDigraph. The value of GR is not used
1.27 - ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
1.28 - ///\tparam TR Traits class to set various data types used by the algorithm.
1.29 - ///The default traits class is
1.30 - ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
1.31 - ///See \ref BfsDefaultTraits for the documentation of
1.32 - ///a Bfs traits class.
1.33 + ///The default type is \ref ListDigraph.
1.34 #ifdef DOXYGEN
1.35 template <typename GR,
1.36 typename TR>
1.37 @@ -150,7 +145,7 @@
1.38 ///The type of the paths.
1.39 typedef PredMapPath<Digraph, PredMap> Path;
1.40
1.41 - ///The traits class.
1.42 + ///The \ref BfsDefaultTraits "traits class" of the algorithm.
1.43 typedef TR Traits;
1.44
1.45 private:
1.46 @@ -212,7 +207,7 @@
1.47
1.48 typedef Bfs Create;
1.49
1.50 - ///\name Named template parameters
1.51 + ///\name Named Template Parameters
1.52
1.53 ///@{
1.54
1.55 @@ -230,6 +225,7 @@
1.56 ///
1.57 ///\ref named-templ-param "Named parameter" for setting
1.58 ///PredMap type.
1.59 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.60 template <class T>
1.61 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
1.62 typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
1.63 @@ -249,6 +245,7 @@
1.64 ///
1.65 ///\ref named-templ-param "Named parameter" for setting
1.66 ///DistMap type.
1.67 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.68 template <class T>
1.69 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
1.70 typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
1.71 @@ -268,6 +265,7 @@
1.72 ///
1.73 ///\ref named-templ-param "Named parameter" for setting
1.74 ///ReachedMap type.
1.75 + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.76 template <class T>
1.77 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
1.78 typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
1.79 @@ -287,6 +285,7 @@
1.80 ///
1.81 ///\ref named-templ-param "Named parameter" for setting
1.82 ///ProcessedMap type.
1.83 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.84 template <class T>
1.85 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
1.86 typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
1.87 @@ -339,9 +338,10 @@
1.88 ///Sets the map that stores the predecessor arcs.
1.89
1.90 ///Sets the map that stores the predecessor arcs.
1.91 - ///If you don't use this function before calling \ref run(),
1.92 - ///it will allocate one. The destructor deallocates this
1.93 - ///automatically allocated map, of course.
1.94 + ///If you don't use this function before calling \ref run(Node) "run()"
1.95 + ///or \ref init(), an instance will be allocated automatically.
1.96 + ///The destructor deallocates this automatically allocated map,
1.97 + ///of course.
1.98 ///\return <tt> (*this) </tt>
1.99 Bfs &predMap(PredMap &m)
1.100 {
1.101 @@ -356,9 +356,10 @@
1.102 ///Sets the map that indicates which nodes are reached.
1.103
1.104 ///Sets the map that indicates which nodes are reached.
1.105 - ///If you don't use this function before calling \ref run(),
1.106 - ///it will allocate one. The destructor deallocates this
1.107 - ///automatically allocated map, of course.
1.108 + ///If you don't use this function before calling \ref run(Node) "run()"
1.109 + ///or \ref init(), an instance will be allocated automatically.
1.110 + ///The destructor deallocates this automatically allocated map,
1.111 + ///of course.
1.112 ///\return <tt> (*this) </tt>
1.113 Bfs &reachedMap(ReachedMap &m)
1.114 {
1.115 @@ -373,9 +374,10 @@
1.116 ///Sets the map that indicates which nodes are processed.
1.117
1.118 ///Sets the map that indicates which nodes are processed.
1.119 - ///If you don't use this function before calling \ref run(),
1.120 - ///it will allocate one. The destructor deallocates this
1.121 - ///automatically allocated map, of course.
1.122 + ///If you don't use this function before calling \ref run(Node) "run()"
1.123 + ///or \ref init(), an instance will be allocated automatically.
1.124 + ///The destructor deallocates this automatically allocated map,
1.125 + ///of course.
1.126 ///\return <tt> (*this) </tt>
1.127 Bfs &processedMap(ProcessedMap &m)
1.128 {
1.129 @@ -391,9 +393,10 @@
1.130
1.131 ///Sets the map that stores the distances of the nodes calculated by
1.132 ///the algorithm.
1.133 - ///If you don't use this function before calling \ref run(),
1.134 - ///it will allocate one. The destructor deallocates this
1.135 - ///automatically allocated map, of course.
1.136 + ///If you don't use this function before calling \ref run(Node) "run()"
1.137 + ///or \ref init(), an instance will be allocated automatically.
1.138 + ///The destructor deallocates this automatically allocated map,
1.139 + ///of course.
1.140 ///\return <tt> (*this) </tt>
1.141 Bfs &distMap(DistMap &m)
1.142 {
1.143 @@ -407,22 +410,19 @@
1.144
1.145 public:
1.146
1.147 - ///\name Execution control
1.148 - ///The simplest way to execute the algorithm is to use
1.149 - ///one of the member functions called \ref lemon::Bfs::run() "run()".
1.150 - ///\n
1.151 - ///If you need more control on the execution, first you must call
1.152 - ///\ref lemon::Bfs::init() "init()", then you can add several source
1.153 - ///nodes with \ref lemon::Bfs::addSource() "addSource()".
1.154 - ///Finally \ref lemon::Bfs::start() "start()" will perform the
1.155 - ///actual path computation.
1.156 + ///\name Execution Control
1.157 + ///The simplest way to execute the BFS algorithm is to use one of the
1.158 + ///member functions called \ref run(Node) "run()".\n
1.159 + ///If you need more control on the execution, first you have to call
1.160 + ///\ref init(), then you can add several source nodes with
1.161 + ///\ref addSource(). Finally the actual path computation can be
1.162 + ///performed with one of the \ref start() functions.
1.163
1.164 ///@{
1.165
1.166 + ///\brief Initializes the internal data structures.
1.167 + ///
1.168 ///Initializes the internal data structures.
1.169 -
1.170 - ///Initializes the internal data structures.
1.171 - ///
1.172 void init()
1.173 {
1.174 create_maps();
1.175 @@ -556,16 +556,16 @@
1.176 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
1.177 }
1.178
1.179 - ///\brief Returns \c false if there are nodes
1.180 - ///to be processed.
1.181 - ///
1.182 - ///Returns \c false if there are nodes
1.183 - ///to be processed in the queue.
1.184 + ///Returns \c false if there are nodes to be processed.
1.185 +
1.186 + ///Returns \c false if there are nodes to be processed
1.187 + ///in the queue.
1.188 bool emptyQueue() const { return _queue_tail==_queue_head; }
1.189
1.190 ///Returns the number of the nodes to be processed.
1.191
1.192 - ///Returns the number of the nodes to be processed in the queue.
1.193 + ///Returns the number of the nodes to be processed
1.194 + ///in the queue.
1.195 int queueSize() const { return _queue_head-_queue_tail; }
1.196
1.197 ///Executes the algorithm.
1.198 @@ -730,10 +730,10 @@
1.199 ///@}
1.200
1.201 ///\name Query Functions
1.202 - ///The result of the %BFS algorithm can be obtained using these
1.203 + ///The results of the BFS algorithm can be obtained using these
1.204 ///functions.\n
1.205 - ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
1.206 - ///"start()" must be called before using them.
1.207 + ///Either \ref run(Node) "run()" or \ref start() should be called
1.208 + ///before using them.
1.209
1.210 ///@{
1.211
1.212 @@ -741,49 +741,49 @@
1.213
1.214 ///Returns the shortest path to a node.
1.215 ///
1.216 - ///\warning \c t should be reachable from the root(s).
1.217 + ///\warning \c t should be reached from the root(s).
1.218 ///
1.219 - ///\pre Either \ref run() or \ref start() must be called before
1.220 - ///using this function.
1.221 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.222 + ///must be called before using this function.
1.223 Path path(Node t) const { return Path(*G, *_pred, t); }
1.224
1.225 ///The distance of a node from the root(s).
1.226
1.227 ///Returns the distance of a node from the root(s).
1.228 ///
1.229 - ///\warning If node \c v is not reachable from the root(s), then
1.230 + ///\warning If node \c v is not reached from the root(s), then
1.231 ///the return value of this function is undefined.
1.232 ///
1.233 - ///\pre Either \ref run() or \ref start() must be called before
1.234 - ///using this function.
1.235 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.236 + ///must be called before using this function.
1.237 int dist(Node v) const { return (*_dist)[v]; }
1.238
1.239 ///Returns the 'previous arc' of the shortest path tree for a node.
1.240
1.241 ///This function returns the 'previous arc' of the shortest path
1.242 ///tree for the node \c v, i.e. it returns the last arc of a
1.243 - ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
1.244 - ///is not reachable from the root(s) or if \c v is a root.
1.245 + ///shortest path from a root to \c v. It is \c INVALID if \c v
1.246 + ///is not reached from the root(s) or if \c v is a root.
1.247 ///
1.248 ///The shortest path tree used here is equal to the shortest path
1.249 ///tree used in \ref predNode().
1.250 ///
1.251 - ///\pre Either \ref run() or \ref start() must be called before
1.252 - ///using this function.
1.253 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.254 + ///must be called before using this function.
1.255 Arc predArc(Node v) const { return (*_pred)[v];}
1.256
1.257 ///Returns the 'previous node' of the shortest path tree for a node.
1.258
1.259 ///This function returns the 'previous node' of the shortest path
1.260 ///tree for the node \c v, i.e. it returns the last but one node
1.261 - ///from a shortest path from the root(s) to \c v. It is \c INVALID
1.262 - ///if \c v is not reachable from the root(s) or if \c v is a root.
1.263 + ///from a shortest path from a root to \c v. It is \c INVALID
1.264 + ///if \c v is not reached from the root(s) or if \c v is a root.
1.265 ///
1.266 ///The shortest path tree used here is equal to the shortest path
1.267 ///tree used in \ref predArc().
1.268 ///
1.269 - ///\pre Either \ref run() or \ref start() must be called before
1.270 - ///using this function.
1.271 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.272 + ///must be called before using this function.
1.273 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.274 G->source((*_pred)[v]); }
1.275
1.276 @@ -793,7 +793,7 @@
1.277 ///Returns a const reference to the node map that stores the distances
1.278 ///of the nodes calculated by the algorithm.
1.279 ///
1.280 - ///\pre Either \ref run() or \ref init()
1.281 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.282 ///must be called before using this function.
1.283 const DistMap &distMap() const { return *_dist;}
1.284
1.285 @@ -803,14 +803,15 @@
1.286 ///Returns a const reference to the node map that stores the predecessor
1.287 ///arcs, which form the shortest path tree.
1.288 ///
1.289 - ///\pre Either \ref run() or \ref init()
1.290 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.291 ///must be called before using this function.
1.292 const PredMap &predMap() const { return *_pred;}
1.293
1.294 - ///Checks if a node is reachable from the root(s).
1.295 + ///Checks if a node is reached from the root(s).
1.296
1.297 - ///Returns \c true if \c v is reachable from the root(s).
1.298 - ///\pre Either \ref run() or \ref start()
1.299 + ///Returns \c true if \c v is reached from the root(s).
1.300 + ///
1.301 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.302 ///must be called before using this function.
1.303 bool reached(Node v) const { return (*_reached)[v]; }
1.304
1.305 @@ -956,8 +957,8 @@
1.306
1.307 /// This auxiliary class is created to implement the
1.308 /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
1.309 - /// It does not have own \ref run() method, it uses the functions
1.310 - /// and features of the plain \ref Bfs.
1.311 + /// It does not have own \ref run(Node) "run()" method, it uses the
1.312 + /// functions and features of the plain \ref Bfs.
1.313 ///
1.314 /// This class should only be used through the \ref bfs() function,
1.315 /// which makes it easier to use the algorithm.
1.316 @@ -1177,7 +1178,7 @@
1.317 /// // Compute shortest path from s to t
1.318 /// bool reached = bfs(g).path(p).dist(d).run(s,t);
1.319 ///\endcode
1.320 - ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1.321 + ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
1.322 ///to the end of the parameter list.
1.323 ///\sa BfsWizard
1.324 ///\sa Bfs
1.325 @@ -1363,7 +1364,7 @@
1.326
1.327 typedef BfsVisit Create;
1.328
1.329 - /// \name Named template parameters
1.330 + /// \name Named Template Parameters
1.331
1.332 ///@{
1.333 template <class T>
1.334 @@ -1405,9 +1406,10 @@
1.335 /// \brief Sets the map that indicates which nodes are reached.
1.336 ///
1.337 /// Sets the map that indicates which nodes are reached.
1.338 - /// If you don't use this function before calling \ref run(),
1.339 - /// it will allocate one. The destructor deallocates this
1.340 - /// automatically allocated map, of course.
1.341 + /// If you don't use this function before calling \ref run(Node) "run()"
1.342 + /// or \ref init(), an instance will be allocated automatically.
1.343 + /// The destructor deallocates this automatically allocated map,
1.344 + /// of course.
1.345 /// \return <tt> (*this) </tt>
1.346 BfsVisit &reachedMap(ReachedMap &m) {
1.347 if(local_reached) {
1.348 @@ -1420,16 +1422,13 @@
1.349
1.350 public:
1.351
1.352 - /// \name Execution control
1.353 - /// The simplest way to execute the algorithm is to use
1.354 - /// one of the member functions called \ref lemon::BfsVisit::run()
1.355 - /// "run()".
1.356 - /// \n
1.357 - /// If you need more control on the execution, first you must call
1.358 - /// \ref lemon::BfsVisit::init() "init()", then you can add several
1.359 - /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
1.360 - /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
1.361 - /// actual path computation.
1.362 + /// \name Execution Control
1.363 + /// The simplest way to execute the BFS algorithm is to use one of the
1.364 + /// member functions called \ref run(Node) "run()".\n
1.365 + /// If you need more control on the execution, first you have to call
1.366 + /// \ref init(), then you can add several source nodes with
1.367 + /// \ref addSource(). Finally the actual path computation can be
1.368 + /// performed with one of the \ref start() functions.
1.369
1.370 /// @{
1.371
1.372 @@ -1729,17 +1728,18 @@
1.373 ///@}
1.374
1.375 /// \name Query Functions
1.376 - /// The result of the %BFS algorithm can be obtained using these
1.377 + /// The results of the BFS algorithm can be obtained using these
1.378 /// functions.\n
1.379 - /// Either \ref lemon::BfsVisit::run() "run()" or
1.380 - /// \ref lemon::BfsVisit::start() "start()" must be called before
1.381 - /// using them.
1.382 + /// Either \ref run(Node) "run()" or \ref start() should be called
1.383 + /// before using them.
1.384 +
1.385 ///@{
1.386
1.387 - /// \brief Checks if a node is reachable from the root(s).
1.388 + /// \brief Checks if a node is reached from the root(s).
1.389 ///
1.390 - /// Returns \c true if \c v is reachable from the root(s).
1.391 - /// \pre Either \ref run() or \ref start()
1.392 + /// Returns \c true if \c v is reached from the root(s).
1.393 + ///
1.394 + /// \pre Either \ref run(Node) "run()" or \ref init()
1.395 /// must be called before using this function.
1.396 bool reached(Node v) { return (*_reached)[v]; }
1.397