1.1 --- a/lemon/bfs.h Fri Nov 13 12:33:33 2009 +0100
1.2 +++ b/lemon/bfs.h Thu Dec 10 17:05:35 2009 +0100
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2008
1.8 + * Copyright (C) 2003-2009
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -49,11 +49,11 @@
1.13 ///arcs of the shortest paths.
1.14 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.15 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.16 - ///Instantiates a PredMap.
1.17 + ///Instantiates a \c PredMap.
1.18
1.19 - ///This function instantiates a PredMap.
1.20 + ///This function instantiates a \ref PredMap.
1.21 ///\param g is the digraph, to which we would like to define the
1.22 - ///PredMap.
1.23 + ///\ref PredMap.
1.24 static PredMap *createPredMap(const Digraph &g)
1.25 {
1.26 return new PredMap(g);
1.27 @@ -64,11 +64,11 @@
1.28 ///The type of the map that indicates which nodes are processed.
1.29 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.30 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.31 - ///Instantiates a ProcessedMap.
1.32 + ///Instantiates a \c ProcessedMap.
1.33
1.34 - ///This function instantiates a ProcessedMap.
1.35 + ///This function instantiates a \ref ProcessedMap.
1.36 ///\param g is the digraph, to which
1.37 - ///we would like to define the ProcessedMap
1.38 + ///we would like to define the \ref ProcessedMap
1.39 #ifdef DOXYGEN
1.40 static ProcessedMap *createProcessedMap(const Digraph &g)
1.41 #else
1.42 @@ -83,11 +83,11 @@
1.43 ///The type of the map that indicates which nodes are reached.
1.44 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.45 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.46 - ///Instantiates a ReachedMap.
1.47 + ///Instantiates a \c ReachedMap.
1.48
1.49 - ///This function instantiates a ReachedMap.
1.50 + ///This function instantiates a \ref ReachedMap.
1.51 ///\param g is the digraph, to which
1.52 - ///we would like to define the ReachedMap.
1.53 + ///we would like to define the \ref ReachedMap.
1.54 static ReachedMap *createReachedMap(const Digraph &g)
1.55 {
1.56 return new ReachedMap(g);
1.57 @@ -98,11 +98,11 @@
1.58 ///The type of the map that stores the distances of the nodes.
1.59 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.60 typedef typename Digraph::template NodeMap<int> DistMap;
1.61 - ///Instantiates a DistMap.
1.62 + ///Instantiates a \c DistMap.
1.63
1.64 - ///This function instantiates a DistMap.
1.65 + ///This function instantiates a \ref DistMap.
1.66 ///\param g is the digraph, to which we would like to define the
1.67 - ///DistMap.
1.68 + ///\ref DistMap.
1.69 static DistMap *createDistMap(const Digraph &g)
1.70 {
1.71 return new DistMap(g);
1.72 @@ -119,13 +119,7 @@
1.73 ///used easier.
1.74 ///
1.75 ///\tparam GR The type of the digraph the algorithm runs on.
1.76 - ///The default value is \ref ListDigraph. The value of GR is not used
1.77 - ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
1.78 - ///\tparam TR Traits class to set various data types used by the algorithm.
1.79 - ///The default traits class is
1.80 - ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
1.81 - ///See \ref BfsDefaultTraits for the documentation of
1.82 - ///a Bfs traits class.
1.83 + ///The default type is \ref ListDigraph.
1.84 #ifdef DOXYGEN
1.85 template <typename GR,
1.86 typename TR>
1.87 @@ -151,7 +145,7 @@
1.88 ///The type of the paths.
1.89 typedef PredMapPath<Digraph, PredMap> Path;
1.90
1.91 - ///The traits class.
1.92 + ///The \ref BfsDefaultTraits "traits class" of the algorithm.
1.93 typedef TR Traits;
1.94
1.95 private:
1.96 @@ -213,7 +207,7 @@
1.97
1.98 typedef Bfs Create;
1.99
1.100 - ///\name Named template parameters
1.101 + ///\name Named Template Parameters
1.102
1.103 ///@{
1.104
1.105 @@ -227,10 +221,11 @@
1.106 }
1.107 };
1.108 ///\brief \ref named-templ-param "Named parameter" for setting
1.109 - ///PredMap type.
1.110 + ///\c PredMap type.
1.111 ///
1.112 ///\ref named-templ-param "Named parameter" for setting
1.113 - ///PredMap type.
1.114 + ///\c PredMap type.
1.115 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.116 template <class T>
1.117 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
1.118 typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
1.119 @@ -246,10 +241,11 @@
1.120 }
1.121 };
1.122 ///\brief \ref named-templ-param "Named parameter" for setting
1.123 - ///DistMap type.
1.124 + ///\c DistMap type.
1.125 ///
1.126 ///\ref named-templ-param "Named parameter" for setting
1.127 - ///DistMap type.
1.128 + ///\c DistMap type.
1.129 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.130 template <class T>
1.131 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
1.132 typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
1.133 @@ -265,10 +261,11 @@
1.134 }
1.135 };
1.136 ///\brief \ref named-templ-param "Named parameter" for setting
1.137 - ///ReachedMap type.
1.138 + ///\c ReachedMap type.
1.139 ///
1.140 ///\ref named-templ-param "Named parameter" for setting
1.141 - ///ReachedMap type.
1.142 + ///\c ReachedMap type.
1.143 + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.144 template <class T>
1.145 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
1.146 typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
1.147 @@ -284,10 +281,11 @@
1.148 }
1.149 };
1.150 ///\brief \ref named-templ-param "Named parameter" for setting
1.151 - ///ProcessedMap type.
1.152 + ///\c ProcessedMap type.
1.153 ///
1.154 ///\ref named-templ-param "Named parameter" for setting
1.155 - ///ProcessedMap type.
1.156 + ///\c ProcessedMap type.
1.157 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.158 template <class T>
1.159 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
1.160 typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
1.161 @@ -302,10 +300,10 @@
1.162 }
1.163 };
1.164 ///\brief \ref named-templ-param "Named parameter" for setting
1.165 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.166 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.167 ///
1.168 ///\ref named-templ-param "Named parameter" for setting
1.169 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.170 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.171 ///If you don't set it explicitly, it will be automatically allocated.
1.172 struct SetStandardProcessedMap :
1.173 public Bfs< Digraph, SetStandardProcessedMapTraits > {
1.174 @@ -340,9 +338,10 @@
1.175 ///Sets the map that stores the predecessor arcs.
1.176
1.177 ///Sets the map that stores the predecessor arcs.
1.178 - ///If you don't use this function before calling \ref run(),
1.179 - ///it will allocate one. The destructor deallocates this
1.180 - ///automatically allocated map, of course.
1.181 + ///If you don't use this function before calling \ref run(Node) "run()"
1.182 + ///or \ref init(), an instance will be allocated automatically.
1.183 + ///The destructor deallocates this automatically allocated map,
1.184 + ///of course.
1.185 ///\return <tt> (*this) </tt>
1.186 Bfs &predMap(PredMap &m)
1.187 {
1.188 @@ -357,9 +356,10 @@
1.189 ///Sets the map that indicates which nodes are reached.
1.190
1.191 ///Sets the map that indicates which nodes are reached.
1.192 - ///If you don't use this function before calling \ref run(),
1.193 - ///it will allocate one. The destructor deallocates this
1.194 - ///automatically allocated map, of course.
1.195 + ///If you don't use this function before calling \ref run(Node) "run()"
1.196 + ///or \ref init(), an instance will be allocated automatically.
1.197 + ///The destructor deallocates this automatically allocated map,
1.198 + ///of course.
1.199 ///\return <tt> (*this) </tt>
1.200 Bfs &reachedMap(ReachedMap &m)
1.201 {
1.202 @@ -374,9 +374,10 @@
1.203 ///Sets the map that indicates which nodes are processed.
1.204
1.205 ///Sets the map that indicates which nodes are processed.
1.206 - ///If you don't use this function before calling \ref run(),
1.207 - ///it will allocate one. The destructor deallocates this
1.208 - ///automatically allocated map, of course.
1.209 + ///If you don't use this function before calling \ref run(Node) "run()"
1.210 + ///or \ref init(), an instance will be allocated automatically.
1.211 + ///The destructor deallocates this automatically allocated map,
1.212 + ///of course.
1.213 ///\return <tt> (*this) </tt>
1.214 Bfs &processedMap(ProcessedMap &m)
1.215 {
1.216 @@ -392,9 +393,10 @@
1.217
1.218 ///Sets the map that stores the distances of the nodes calculated by
1.219 ///the algorithm.
1.220 - ///If you don't use this function before calling \ref run(),
1.221 - ///it will allocate one. The destructor deallocates this
1.222 - ///automatically allocated map, of course.
1.223 + ///If you don't use this function before calling \ref run(Node) "run()"
1.224 + ///or \ref init(), an instance will be allocated automatically.
1.225 + ///The destructor deallocates this automatically allocated map,
1.226 + ///of course.
1.227 ///\return <tt> (*this) </tt>
1.228 Bfs &distMap(DistMap &m)
1.229 {
1.230 @@ -408,22 +410,19 @@
1.231
1.232 public:
1.233
1.234 - ///\name Execution control
1.235 - ///The simplest way to execute the algorithm is to use
1.236 - ///one of the member functions called \ref lemon::Bfs::run() "run()".
1.237 - ///\n
1.238 - ///If you need more control on the execution, first you must call
1.239 - ///\ref lemon::Bfs::init() "init()", then you can add several source
1.240 - ///nodes with \ref lemon::Bfs::addSource() "addSource()".
1.241 - ///Finally \ref lemon::Bfs::start() "start()" will perform the
1.242 - ///actual path computation.
1.243 + ///\name Execution Control
1.244 + ///The simplest way to execute the BFS algorithm is to use one of the
1.245 + ///member functions called \ref run(Node) "run()".\n
1.246 + ///If you need more control on the execution, first you have to call
1.247 + ///\ref init(), then you can add several source nodes with
1.248 + ///\ref addSource(). Finally the actual path computation can be
1.249 + ///performed with one of the \ref start() functions.
1.250
1.251 ///@{
1.252
1.253 + ///\brief Initializes the internal data structures.
1.254 + ///
1.255 ///Initializes the internal data structures.
1.256 -
1.257 - ///Initializes the internal data structures.
1.258 - ///
1.259 void init()
1.260 {
1.261 create_maps();
1.262 @@ -557,16 +556,16 @@
1.263 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
1.264 }
1.265
1.266 - ///\brief Returns \c false if there are nodes
1.267 - ///to be processed.
1.268 - ///
1.269 - ///Returns \c false if there are nodes
1.270 - ///to be processed in the queue.
1.271 + ///Returns \c false if there are nodes to be processed.
1.272 +
1.273 + ///Returns \c false if there are nodes to be processed
1.274 + ///in the queue.
1.275 bool emptyQueue() const { return _queue_tail==_queue_head; }
1.276
1.277 ///Returns the number of the nodes to be processed.
1.278
1.279 - ///Returns the number of the nodes to be processed in the queue.
1.280 + ///Returns the number of the nodes to be processed
1.281 + ///in the queue.
1.282 int queueSize() const { return _queue_head-_queue_tail; }
1.283
1.284 ///Executes the algorithm.
1.285 @@ -731,10 +730,10 @@
1.286 ///@}
1.287
1.288 ///\name Query Functions
1.289 - ///The result of the %BFS algorithm can be obtained using these
1.290 + ///The results of the BFS algorithm can be obtained using these
1.291 ///functions.\n
1.292 - ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
1.293 - ///"start()" must be called before using them.
1.294 + ///Either \ref run(Node) "run()" or \ref start() should be called
1.295 + ///before using them.
1.296
1.297 ///@{
1.298
1.299 @@ -742,49 +741,49 @@
1.300
1.301 ///Returns the shortest path to a node.
1.302 ///
1.303 - ///\warning \c t should be reachable from the root(s).
1.304 + ///\warning \c t should be reached from the root(s).
1.305 ///
1.306 - ///\pre Either \ref run() or \ref start() must be called before
1.307 - ///using this function.
1.308 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.309 + ///must be called before using this function.
1.310 Path path(Node t) const { return Path(*G, *_pred, t); }
1.311
1.312 ///The distance of a node from the root(s).
1.313
1.314 ///Returns the distance of a node from the root(s).
1.315 ///
1.316 - ///\warning If node \c v is not reachable from the root(s), then
1.317 + ///\warning If node \c v is not reached from the root(s), then
1.318 ///the return value of this function is undefined.
1.319 ///
1.320 - ///\pre Either \ref run() or \ref start() must be called before
1.321 - ///using this function.
1.322 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.323 + ///must be called before using this function.
1.324 int dist(Node v) const { return (*_dist)[v]; }
1.325
1.326 ///Returns the 'previous arc' of the shortest path tree for a node.
1.327
1.328 ///This function returns the 'previous arc' of the shortest path
1.329 ///tree for the node \c v, i.e. it returns the last arc of a
1.330 - ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
1.331 - ///is not reachable from the root(s) or if \c v is a root.
1.332 + ///shortest path from a root to \c v. It is \c INVALID if \c v
1.333 + ///is not reached from the root(s) or if \c v is a root.
1.334 ///
1.335 ///The shortest path tree used here is equal to the shortest path
1.336 ///tree used in \ref predNode().
1.337 ///
1.338 - ///\pre Either \ref run() or \ref start() must be called before
1.339 - ///using this function.
1.340 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.341 + ///must be called before using this function.
1.342 Arc predArc(Node v) const { return (*_pred)[v];}
1.343
1.344 ///Returns the 'previous node' of the shortest path tree for a node.
1.345
1.346 ///This function returns the 'previous node' of the shortest path
1.347 ///tree for the node \c v, i.e. it returns the last but one node
1.348 - ///from a shortest path from the root(s) to \c v. It is \c INVALID
1.349 - ///if \c v is not reachable from the root(s) or if \c v is a root.
1.350 + ///from a shortest path from a root to \c v. It is \c INVALID
1.351 + ///if \c v is not reached from the root(s) or if \c v is a root.
1.352 ///
1.353 ///The shortest path tree used here is equal to the shortest path
1.354 ///tree used in \ref predArc().
1.355 ///
1.356 - ///\pre Either \ref run() or \ref start() must be called before
1.357 - ///using this function.
1.358 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.359 + ///must be called before using this function.
1.360 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.361 G->source((*_pred)[v]); }
1.362
1.363 @@ -794,7 +793,7 @@
1.364 ///Returns a const reference to the node map that stores the distances
1.365 ///of the nodes calculated by the algorithm.
1.366 ///
1.367 - ///\pre Either \ref run() or \ref init()
1.368 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.369 ///must be called before using this function.
1.370 const DistMap &distMap() const { return *_dist;}
1.371
1.372 @@ -804,14 +803,15 @@
1.373 ///Returns a const reference to the node map that stores the predecessor
1.374 ///arcs, which form the shortest path tree.
1.375 ///
1.376 - ///\pre Either \ref run() or \ref init()
1.377 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.378 ///must be called before using this function.
1.379 const PredMap &predMap() const { return *_pred;}
1.380
1.381 - ///Checks if a node is reachable from the root(s).
1.382 + ///Checks if a node is reached from the root(s).
1.383
1.384 - ///Returns \c true if \c v is reachable from the root(s).
1.385 - ///\pre Either \ref run() or \ref start()
1.386 + ///Returns \c true if \c v is reached from the root(s).
1.387 + ///
1.388 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.389 ///must be called before using this function.
1.390 bool reached(Node v) const { return (*_reached)[v]; }
1.391
1.392 @@ -957,8 +957,8 @@
1.393
1.394 /// This auxiliary class is created to implement the
1.395 /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
1.396 - /// It does not have own \ref run() method, it uses the functions
1.397 - /// and features of the plain \ref Bfs.
1.398 + /// It does not have own \ref run(Node) "run()" method, it uses the
1.399 + /// functions and features of the plain \ref Bfs.
1.400 ///
1.401 /// This class should only be used through the \ref bfs() function,
1.402 /// which makes it easier to use the algorithm.
1.403 @@ -1178,7 +1178,7 @@
1.404 /// // Compute shortest path from s to t
1.405 /// bool reached = bfs(g).path(p).dist(d).run(s,t);
1.406 ///\endcode
1.407 - ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1.408 + ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
1.409 ///to the end of the parameter list.
1.410 ///\sa BfsWizard
1.411 ///\sa Bfs
1.412 @@ -1194,9 +1194,9 @@
1.413 ///
1.414 /// This class defines the interface of the BfsVisit events, and
1.415 /// it could be the base of a real visitor class.
1.416 - template <typename _Digraph>
1.417 + template <typename GR>
1.418 struct BfsVisitor {
1.419 - typedef _Digraph Digraph;
1.420 + typedef GR Digraph;
1.421 typedef typename Digraph::Arc Arc;
1.422 typedef typename Digraph::Node Node;
1.423 /// \brief Called for the source node(s) of the BFS.
1.424 @@ -1224,9 +1224,9 @@
1.425 void examine(const Arc& arc) {}
1.426 };
1.427 #else
1.428 - template <typename _Digraph>
1.429 + template <typename GR>
1.430 struct BfsVisitor {
1.431 - typedef _Digraph Digraph;
1.432 + typedef GR Digraph;
1.433 typedef typename Digraph::Arc Arc;
1.434 typedef typename Digraph::Node Node;
1.435 void start(const Node&) {}
1.436 @@ -1254,12 +1254,12 @@
1.437 /// \brief Default traits class of BfsVisit class.
1.438 ///
1.439 /// Default traits class of BfsVisit class.
1.440 - /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.441 - template<class _Digraph>
1.442 + /// \tparam GR The type of the digraph the algorithm runs on.
1.443 + template<class GR>
1.444 struct BfsVisitDefaultTraits {
1.445
1.446 /// \brief The type of the digraph the algorithm runs on.
1.447 - typedef _Digraph Digraph;
1.448 + typedef GR Digraph;
1.449
1.450 /// \brief The type of the map that indicates which nodes are reached.
1.451 ///
1.452 @@ -1280,12 +1280,12 @@
1.453
1.454 /// \ingroup search
1.455 ///
1.456 - /// \brief %BFS algorithm class with visitor interface.
1.457 + /// \brief BFS algorithm class with visitor interface.
1.458 ///
1.459 - /// This class provides an efficient implementation of the %BFS algorithm
1.460 + /// This class provides an efficient implementation of the BFS algorithm
1.461 /// with visitor interface.
1.462 ///
1.463 - /// The %BfsVisit class provides an alternative interface to the Bfs
1.464 + /// The BfsVisit class provides an alternative interface to the Bfs
1.465 /// class. It works with callback mechanism, the BfsVisit object calls
1.466 /// the member functions of the \c Visitor class on every BFS event.
1.467 ///
1.468 @@ -1294,37 +1294,37 @@
1.469 /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
1.470 /// instead.
1.471 ///
1.472 - /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.473 - /// The default value is
1.474 - /// \ref ListDigraph. The value of _Digraph is not used directly by
1.475 - /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
1.476 - /// \tparam _Visitor The Visitor type that is used by the algorithm.
1.477 - /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
1.478 + /// \tparam GR The type of the digraph the algorithm runs on.
1.479 + /// The default type is \ref ListDigraph.
1.480 + /// The value of GR is not used directly by \ref BfsVisit,
1.481 + /// it is only passed to \ref BfsVisitDefaultTraits.
1.482 + /// \tparam VS The Visitor type that is used by the algorithm.
1.483 + /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
1.484 /// does not observe the BFS events. If you want to observe the BFS
1.485 /// events, you should implement your own visitor class.
1.486 - /// \tparam _Traits Traits class to set various data types used by the
1.487 + /// \tparam TR Traits class to set various data types used by the
1.488 /// algorithm. The default traits class is
1.489 - /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
1.490 + /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
1.491 /// See \ref BfsVisitDefaultTraits for the documentation of
1.492 /// a BFS visit traits class.
1.493 #ifdef DOXYGEN
1.494 - template <typename _Digraph, typename _Visitor, typename _Traits>
1.495 + template <typename GR, typename VS, typename TR>
1.496 #else
1.497 - template <typename _Digraph = ListDigraph,
1.498 - typename _Visitor = BfsVisitor<_Digraph>,
1.499 - typename _Traits = BfsVisitDefaultTraits<_Digraph> >
1.500 + template <typename GR = ListDigraph,
1.501 + typename VS = BfsVisitor<GR>,
1.502 + typename TR = BfsVisitDefaultTraits<GR> >
1.503 #endif
1.504 class BfsVisit {
1.505 public:
1.506
1.507 ///The traits class.
1.508 - typedef _Traits Traits;
1.509 + typedef TR Traits;
1.510
1.511 ///The type of the digraph the algorithm runs on.
1.512 typedef typename Traits::Digraph Digraph;
1.513
1.514 ///The visitor type used by the algorithm.
1.515 - typedef _Visitor Visitor;
1.516 + typedef VS Visitor;
1.517
1.518 ///The type of the map that indicates which nodes are reached.
1.519 typedef typename Traits::ReachedMap ReachedMap;
1.520 @@ -1364,7 +1364,7 @@
1.521
1.522 typedef BfsVisit Create;
1.523
1.524 - /// \name Named template parameters
1.525 + /// \name Named Template Parameters
1.526
1.527 ///@{
1.528 template <class T>
1.529 @@ -1406,9 +1406,10 @@
1.530 /// \brief Sets the map that indicates which nodes are reached.
1.531 ///
1.532 /// Sets the map that indicates which nodes are reached.
1.533 - /// If you don't use this function before calling \ref run(),
1.534 - /// it will allocate one. The destructor deallocates this
1.535 - /// automatically allocated map, of course.
1.536 + /// If you don't use this function before calling \ref run(Node) "run()"
1.537 + /// or \ref init(), an instance will be allocated automatically.
1.538 + /// The destructor deallocates this automatically allocated map,
1.539 + /// of course.
1.540 /// \return <tt> (*this) </tt>
1.541 BfsVisit &reachedMap(ReachedMap &m) {
1.542 if(local_reached) {
1.543 @@ -1421,16 +1422,13 @@
1.544
1.545 public:
1.546
1.547 - /// \name Execution control
1.548 - /// The simplest way to execute the algorithm is to use
1.549 - /// one of the member functions called \ref lemon::BfsVisit::run()
1.550 - /// "run()".
1.551 - /// \n
1.552 - /// If you need more control on the execution, first you must call
1.553 - /// \ref lemon::BfsVisit::init() "init()", then you can add several
1.554 - /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
1.555 - /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
1.556 - /// actual path computation.
1.557 + /// \name Execution Control
1.558 + /// The simplest way to execute the BFS algorithm is to use one of the
1.559 + /// member functions called \ref run(Node) "run()".\n
1.560 + /// If you need more control on the execution, first you have to call
1.561 + /// \ref init(), then you can add several source nodes with
1.562 + /// \ref addSource(). Finally the actual path computation can be
1.563 + /// performed with one of the \ref start() functions.
1.564
1.565 /// @{
1.566
1.567 @@ -1730,19 +1728,20 @@
1.568 ///@}
1.569
1.570 /// \name Query Functions
1.571 - /// The result of the %BFS algorithm can be obtained using these
1.572 + /// The results of the BFS algorithm can be obtained using these
1.573 /// functions.\n
1.574 - /// Either \ref lemon::BfsVisit::run() "run()" or
1.575 - /// \ref lemon::BfsVisit::start() "start()" must be called before
1.576 - /// using them.
1.577 + /// Either \ref run(Node) "run()" or \ref start() should be called
1.578 + /// before using them.
1.579 +
1.580 ///@{
1.581
1.582 - /// \brief Checks if a node is reachable from the root(s).
1.583 + /// \brief Checks if a node is reached from the root(s).
1.584 ///
1.585 - /// Returns \c true if \c v is reachable from the root(s).
1.586 - /// \pre Either \ref run() or \ref start()
1.587 + /// Returns \c true if \c v is reached from the root(s).
1.588 + ///
1.589 + /// \pre Either \ref run(Node) "run()" or \ref init()
1.590 /// must be called before using this function.
1.591 - bool reached(Node v) { return (*_reached)[v]; }
1.592 + bool reached(Node v) const { return (*_reached)[v]; }
1.593
1.594 ///@}
1.595