1.1 --- a/lemon/bfs.h Mon Jul 14 15:40:24 2008 +0100
1.2 +++ b/lemon/bfs.h Sun Aug 03 13:34:57 2008 +0200
1.3 @@ -21,7 +21,7 @@
1.4
1.5 ///\ingroup search
1.6 ///\file
1.7 -///\brief Bfs algorithm.
1.8 +///\brief BFS algorithm.
1.9
1.10 #include <lemon/list_graph.h>
1.11 #include <lemon/graph_utils.h>
1.12 @@ -32,8 +32,6 @@
1.13
1.14 namespace lemon {
1.15
1.16 -
1.17 -
1.18 ///Default traits class of Bfs class.
1.19
1.20 ///Default traits class of Bfs class.
1.21 @@ -41,73 +39,75 @@
1.22 template<class GR>
1.23 struct BfsDefaultTraits
1.24 {
1.25 - ///The digraph type the algorithm runs on.
1.26 + ///The type of the digraph the algorithm runs on.
1.27 typedef GR Digraph;
1.28 - ///\brief The type of the map that stores the last
1.29 +
1.30 + ///\brief The type of the map that stores the predecessor
1.31 ///arcs of the shortest paths.
1.32 ///
1.33 - ///The type of the map that stores the last
1.34 + ///The type of the map that stores the predecessor
1.35 ///arcs of the shortest paths.
1.36 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.37 - ///
1.38 - typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
1.39 - ///Instantiates a PredMap.
1.40 + typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.41 + ///Instantiates a \ref PredMap.
1.42
1.43 ///This function instantiates a \ref PredMap.
1.44 - ///\param G is the digraph, to which we would like to define the PredMap.
1.45 + ///\param g is the digraph, to which we would like to define the
1.46 + ///\ref PredMap.
1.47 ///\todo The digraph alone may be insufficient to initialize
1.48 - static PredMap *createPredMap(const GR &G)
1.49 + static PredMap *createPredMap(const Digraph &g)
1.50 {
1.51 - return new PredMap(G);
1.52 + return new PredMap(g);
1.53 }
1.54 +
1.55 ///The type of the map that indicates which nodes are processed.
1.56
1.57 ///The type of the map that indicates which nodes are processed.
1.58 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.59 - ///\todo named parameter to set this type, function to read and write.
1.60 + ///By default it is a NullMap.
1.61 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.62 - ///Instantiates a ProcessedMap.
1.63 + ///Instantiates a \ref ProcessedMap.
1.64
1.65 ///This function instantiates a \ref ProcessedMap.
1.66 ///\param g is the digraph, to which
1.67 ///we would like to define the \ref ProcessedMap
1.68 #ifdef DOXYGEN
1.69 - static ProcessedMap *createProcessedMap(const GR &g)
1.70 + static ProcessedMap *createProcessedMap(const Digraph &g)
1.71 #else
1.72 - static ProcessedMap *createProcessedMap(const GR &)
1.73 + static ProcessedMap *createProcessedMap(const Digraph &)
1.74 #endif
1.75 {
1.76 return new ProcessedMap();
1.77 }
1.78 +
1.79 ///The type of the map that indicates which nodes are reached.
1.80
1.81 ///The type of the map that indicates which nodes are reached.
1.82 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.83 - ///\todo named parameter to set this type, function to read and write.
1.84 + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.85 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.86 - ///Instantiates a ReachedMap.
1.87 + ///Instantiates a \ref ReachedMap.
1.88
1.89 ///This function instantiates a \ref ReachedMap.
1.90 - ///\param G is the digraph, to which
1.91 + ///\param g is the digraph, to which
1.92 ///we would like to define the \ref ReachedMap.
1.93 - static ReachedMap *createReachedMap(const GR &G)
1.94 + static ReachedMap *createReachedMap(const Digraph &g)
1.95 {
1.96 - return new ReachedMap(G);
1.97 + return new ReachedMap(g);
1.98 }
1.99 - ///The type of the map that stores the dists of the nodes.
1.100
1.101 - ///The type of the map that stores the dists of the nodes.
1.102 + ///The type of the map that stores the distances of the nodes.
1.103 +
1.104 + ///The type of the map that stores the distances of the nodes.
1.105 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.106 - ///
1.107 typedef typename Digraph::template NodeMap<int> DistMap;
1.108 - ///Instantiates a DistMap.
1.109 + ///Instantiates a \ref DistMap.
1.110
1.111 ///This function instantiates a \ref DistMap.
1.112 - ///\param G is the digraph, to which we would like to define
1.113 - ///the \ref DistMap
1.114 - static DistMap *createDistMap(const GR &G)
1.115 + ///\param g is the digraph, to which we would like to define the
1.116 + ///\ref DistMap.
1.117 + static DistMap *createDistMap(const Digraph &g)
1.118 {
1.119 - return new DistMap(G);
1.120 + return new DistMap(g);
1.121 }
1.122 };
1.123
1.124 @@ -116,15 +116,18 @@
1.125 ///\ingroup search
1.126 ///This class provides an efficient implementation of the %BFS algorithm.
1.127 ///
1.128 - ///\tparam GR The digraph type the algorithm runs on. The default value is
1.129 - ///\ref ListDigraph. The value of GR is not used directly by Bfs, it
1.130 - ///is only passed to \ref BfsDefaultTraits.
1.131 + ///There is also a \ref bfs() "function type interface" for the BFS
1.132 + ///algorithm, which is convenient in the simplier cases and it can be
1.133 + ///used easier.
1.134 + ///
1.135 + ///\tparam GR The type of the digraph the algorithm runs on.
1.136 + ///The default value is \ref ListDigraph. The value of GR is not used
1.137 + ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
1.138 ///\tparam TR Traits class to set various data types used by the algorithm.
1.139 ///The default traits class is
1.140 ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
1.141 ///See \ref BfsDefaultTraits for the documentation of
1.142 ///a Bfs traits class.
1.143 -
1.144 #ifdef DOXYGEN
1.145 template <typename GR,
1.146 typename TR>
1.147 @@ -134,12 +137,10 @@
1.148 #endif
1.149 class Bfs {
1.150 public:
1.151 - /**
1.152 - * \brief \ref Exception for uninitialized parameters.
1.153 - *
1.154 - * This error represents problems in the initialization
1.155 - * of the parameters of the algorithms.
1.156 - */
1.157 + ///\ref Exception for uninitialized parameters.
1.158 +
1.159 + ///This error represents problems in the initialization of the
1.160 + ///parameters of the algorithm.
1.161 class UninitializedParameter : public lemon::UninitializedParameter {
1.162 public:
1.163 virtual const char* what() const throw() {
1.164 @@ -147,19 +148,24 @@
1.165 }
1.166 };
1.167
1.168 - typedef TR Traits;
1.169 - ///The type of the underlying digraph.
1.170 + ///The type of the digraph the algorithm runs on.
1.171 typedef typename TR::Digraph Digraph;
1.172
1.173 - ///\brief The type of the map that stores the last
1.174 - ///arcs of the shortest paths.
1.175 + ///\brief The type of the map that stores the predecessor arcs of the
1.176 + ///shortest paths.
1.177 typedef typename TR::PredMap PredMap;
1.178 - ///The type of the map indicating which nodes are reached.
1.179 + ///The type of the map that stores the distances of the nodes.
1.180 + typedef typename TR::DistMap DistMap;
1.181 + ///The type of the map that indicates which nodes are reached.
1.182 typedef typename TR::ReachedMap ReachedMap;
1.183 - ///The type of the map indicating which nodes are processed.
1.184 + ///The type of the map that indicates which nodes are processed.
1.185 typedef typename TR::ProcessedMap ProcessedMap;
1.186 - ///The type of the map that stores the dists of the nodes.
1.187 - typedef typename TR::DistMap DistMap;
1.188 + ///The type of the paths.
1.189 + typedef PredMapPath<Digraph, PredMap> Path;
1.190 +
1.191 + ///The traits class.
1.192 + typedef TR Traits;
1.193 +
1.194 private:
1.195
1.196 typedef typename Digraph::Node Node;
1.197 @@ -167,23 +173,23 @@
1.198 typedef typename Digraph::Arc Arc;
1.199 typedef typename Digraph::OutArcIt OutArcIt;
1.200
1.201 - /// Pointer to the underlying digraph.
1.202 + //Pointer to the underlying digraph.
1.203 const Digraph *G;
1.204 - ///Pointer to the map of predecessors arcs.
1.205 + //Pointer to the map of predecessor arcs.
1.206 PredMap *_pred;
1.207 - ///Indicates if \ref _pred is locally allocated (\c true) or not.
1.208 + //Indicates if _pred is locally allocated (true) or not.
1.209 bool local_pred;
1.210 - ///Pointer to the map of distances.
1.211 + //Pointer to the map of distances.
1.212 DistMap *_dist;
1.213 - ///Indicates if \ref _dist is locally allocated (\c true) or not.
1.214 + //Indicates if _dist is locally allocated (true) or not.
1.215 bool local_dist;
1.216 - ///Pointer to the map of reached status of the nodes.
1.217 + //Pointer to the map of reached status of the nodes.
1.218 ReachedMap *_reached;
1.219 - ///Indicates if \ref _reached is locally allocated (\c true) or not.
1.220 + //Indicates if _reached is locally allocated (true) or not.
1.221 bool local_reached;
1.222 - ///Pointer to the map of processed status of the nodes.
1.223 + //Pointer to the map of processed status of the nodes.
1.224 ProcessedMap *_processed;
1.225 - ///Indicates if \ref _processed is locally allocated (\c true) or not.
1.226 + //Indicates if _processed is locally allocated (true) or not.
1.227 bool local_processed;
1.228
1.229 std::vector<typename Digraph::Node> _queue;
1.230 @@ -191,7 +197,6 @@
1.231 int _curr_dist;
1.232
1.233 ///Creates the maps if necessary.
1.234 -
1.235 ///\todo Better memory allocation (instead of new).
1.236 void create_maps()
1.237 {
1.238 @@ -234,10 +239,10 @@
1.239 }
1.240 };
1.241 ///\brief \ref named-templ-param "Named parameter" for setting
1.242 - ///PredMap type
1.243 + ///\ref PredMap type.
1.244 ///
1.245 - ///\ref named-templ-param "Named parameter" for setting PredMap type
1.246 - ///
1.247 + ///\ref named-templ-param "Named parameter" for setting
1.248 + ///\ref PredMap type.
1.249 template <class T>
1.250 struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
1.251 typedef Bfs< Digraph, DefPredMapTraits<T> > Create;
1.252 @@ -252,10 +257,10 @@
1.253 }
1.254 };
1.255 ///\brief \ref named-templ-param "Named parameter" for setting
1.256 - ///DistMap type
1.257 + ///\ref DistMap type.
1.258 ///
1.259 - ///\ref named-templ-param "Named parameter" for setting DistMap type
1.260 - ///
1.261 + ///\ref named-templ-param "Named parameter" for setting
1.262 + ///\ref DistMap type.
1.263 template <class T>
1.264 struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
1.265 typedef Bfs< Digraph, DefDistMapTraits<T> > Create;
1.266 @@ -270,10 +275,10 @@
1.267 }
1.268 };
1.269 ///\brief \ref named-templ-param "Named parameter" for setting
1.270 - ///ReachedMap type
1.271 + ///\ref ReachedMap type.
1.272 ///
1.273 - ///\ref named-templ-param "Named parameter" for setting ReachedMap type
1.274 - ///
1.275 + ///\ref named-templ-param "Named parameter" for setting
1.276 + ///\ref ReachedMap type.
1.277 template <class T>
1.278 struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
1.279 typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;
1.280 @@ -288,10 +293,10 @@
1.281 }
1.282 };
1.283 ///\brief \ref named-templ-param "Named parameter" for setting
1.284 - ///ProcessedMap type
1.285 + ///\ref ProcessedMap type.
1.286 ///
1.287 - ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.288 - ///
1.289 + ///\ref named-templ-param "Named parameter" for setting
1.290 + ///\ref ProcessedMap type.
1.291 template <class T>
1.292 struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {
1.293 typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;
1.294 @@ -299,16 +304,16 @@
1.295
1.296 struct DefDigraphProcessedMapTraits : public Traits {
1.297 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
1.298 - static ProcessedMap *createProcessedMap(const Digraph &G)
1.299 + static ProcessedMap *createProcessedMap(const Digraph &g)
1.300 {
1.301 - return new ProcessedMap(G);
1.302 + return new ProcessedMap(g);
1.303 }
1.304 };
1.305 - ///\brief \ref named-templ-param "Named parameter"
1.306 - ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
1.307 + ///\brief \ref named-templ-param "Named parameter" for setting
1.308 + ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.309 ///
1.310 - ///\ref named-templ-param "Named parameter"
1.311 - ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
1.312 + ///\ref named-templ-param "Named parameter" for setting
1.313 + ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.314 ///If you don't set it explicitly, it will be automatically allocated.
1.315 template <class T>
1.316 struct DefProcessedMapToBeDefaultMap :
1.317 @@ -322,10 +327,10 @@
1.318
1.319 ///Constructor.
1.320
1.321 - ///\param _G the digraph the algorithm will run on.
1.322 - ///
1.323 - Bfs(const Digraph& _G) :
1.324 - G(&_G),
1.325 + ///Constructor.
1.326 + ///\param g The digraph the algorithm runs on.
1.327 + Bfs(const Digraph &g) :
1.328 + G(&g),
1.329 _pred(NULL), local_pred(false),
1.330 _dist(NULL), local_dist(false),
1.331 _reached(NULL), local_reached(false),
1.332 @@ -341,9 +346,9 @@
1.333 if(local_processed) delete _processed;
1.334 }
1.335
1.336 - ///Sets the map storing the predecessor arcs.
1.337 + ///Sets the map that stores the predecessor arcs.
1.338
1.339 - ///Sets the map storing the predecessor arcs.
1.340 + ///Sets the map that stores the predecessor arcs.
1.341 ///If you don't use this function before calling \ref run(),
1.342 ///it will allocate one. The destructor deallocates this
1.343 ///automatically allocated map, of course.
1.344 @@ -358,9 +363,9 @@
1.345 return *this;
1.346 }
1.347
1.348 - ///Sets the map indicating the reached nodes.
1.349 + ///Sets the map that indicates which nodes are reached.
1.350
1.351 - ///Sets the map indicating the reached nodes.
1.352 + ///Sets the map that indicates which nodes are reached.
1.353 ///If you don't use this function before calling \ref run(),
1.354 ///it will allocate one. The destructor deallocates this
1.355 ///automatically allocated map, of course.
1.356 @@ -375,9 +380,9 @@
1.357 return *this;
1.358 }
1.359
1.360 - ///Sets the map indicating the processed nodes.
1.361 + ///Sets the map that indicates which nodes are processed.
1.362
1.363 - ///Sets the map indicating the processed nodes.
1.364 + ///Sets the map that indicates which nodes are processed.
1.365 ///If you don't use this function before calling \ref run(),
1.366 ///it will allocate one. The destructor deallocates this
1.367 ///automatically allocated map, of course.
1.368 @@ -392,9 +397,10 @@
1.369 return *this;
1.370 }
1.371
1.372 - ///Sets the map storing the distances calculated by the algorithm.
1.373 + ///Sets the map that stores the distances of the nodes.
1.374
1.375 - ///Sets the map storing the distances calculated by the algorithm.
1.376 + ///Sets the map that stores the distances of the nodes calculated by
1.377 + ///the algorithm.
1.378 ///If you don't use this function before calling \ref run(),
1.379 ///it will allocate one. The destructor deallocates this
1.380 ///automatically allocated map, of course.
1.381 @@ -410,20 +416,21 @@
1.382 }
1.383
1.384 public:
1.385 +
1.386 ///\name Execution control
1.387 ///The simplest way to execute the algorithm is to use
1.388 - ///one of the member functions called \c run(...).
1.389 + ///one of the member functions called \ref lemon::Bfs::run() "run()".
1.390 ///\n
1.391 - ///If you need more control on the execution,
1.392 - ///first you must call \ref init(), then you can add several source nodes
1.393 - ///with \ref addSource().
1.394 - ///Finally \ref start() will perform the actual path
1.395 - ///computation.
1.396 + ///If you need more control on the execution, first you must call
1.397 + ///\ref lemon::Bfs::init() "init()", then you can add several source
1.398 + ///nodes with \ref lemon::Bfs::addSource() "addSource()".
1.399 + ///Finally \ref lemon::Bfs::start() "start()" will perform the
1.400 + ///actual path computation.
1.401
1.402 ///@{
1.403
1.404 - ///\brief Initializes the internal data structures.
1.405 - ///
1.406 + ///Initializes the internal data structures.
1.407 +
1.408 ///Initializes the internal data structures.
1.409 ///
1.410 void init()
1.411 @@ -461,7 +468,7 @@
1.412 ///
1.413 ///\return The processed node.
1.414 ///
1.415 - ///\warning The queue must not be empty!
1.416 + ///\pre The queue must not be empty.
1.417 Node processNextNode()
1.418 {
1.419 if(_queue_tail==_queue_next_dist) {
1.420 @@ -483,16 +490,17 @@
1.421
1.422 ///Processes the next node.
1.423
1.424 - ///Processes the next node. And checks that the given target node
1.425 + ///Processes the next node and checks if the given target node
1.426 ///is reached. If the target node is reachable from the processed
1.427 - ///node then the reached parameter will be set true. The reached
1.428 - ///parameter should be initially false.
1.429 + ///node, then the \c reach parameter will be set to \c true.
1.430 ///
1.431 ///\param target The target node.
1.432 - ///\retval reach Indicates that the target node is reached.
1.433 + ///\retval reach Indicates if the target node is reached.
1.434 + ///It should be initially \c false.
1.435 + ///
1.436 ///\return The processed node.
1.437 ///
1.438 - ///\warning The queue must not be empty!
1.439 + ///\pre The queue must not be empty.
1.440 Node processNextNode(Node target, bool& reach)
1.441 {
1.442 if(_queue_tail==_queue_next_dist) {
1.443 @@ -515,16 +523,19 @@
1.444
1.445 ///Processes the next node.
1.446
1.447 - ///Processes the next node. And checks that at least one of
1.448 - ///reached node has true value in the \c nm node map. If one node
1.449 - ///with true value is reachable from the processed node then the
1.450 - ///rnode parameter will be set to the first of such nodes.
1.451 + ///Processes the next node and checks if at least one of reached
1.452 + ///nodes has \c true value in the \c nm node map. If one node
1.453 + ///with \c true value is reachable from the processed node, then the
1.454 + ///\c rnode parameter will be set to the first of such nodes.
1.455 ///
1.456 - ///\param nm The node map of possible targets.
1.457 + ///\param nm A \c bool (or convertible) node map that indicates the
1.458 + ///possible targets.
1.459 ///\retval rnode The reached target node.
1.460 + ///It should be initially \c INVALID.
1.461 + ///
1.462 ///\return The processed node.
1.463 ///
1.464 - ///\warning The queue must not be empty!
1.465 + ///\pre The queue must not be empty.
1.466 template<class NM>
1.467 Node processNextNode(const NM& nm, Node& rnode)
1.468 {
1.469 @@ -546,58 +557,73 @@
1.470 return n;
1.471 }
1.472
1.473 - ///Next node to be processed.
1.474 + ///The next node to be processed.
1.475
1.476 - ///Next node to be processed.
1.477 - ///
1.478 - ///\return The next node to be processed or INVALID if the queue is
1.479 - /// empty.
1.480 - Node nextNode()
1.481 + ///Returns the next node to be processed or \c INVALID if the queue
1.482 + ///is empty.
1.483 + Node nextNode() const
1.484 {
1.485 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
1.486 }
1.487
1.488 ///\brief Returns \c false if there are nodes
1.489 - ///to be processed in the queue
1.490 + ///to be processed.
1.491 ///
1.492 ///Returns \c false if there are nodes
1.493 - ///to be processed in the queue
1.494 - bool emptyQueue() { return _queue_tail==_queue_head; }
1.495 + ///to be processed in the queue.
1.496 + bool emptyQueue() const { return _queue_tail==_queue_head; }
1.497 +
1.498 ///Returns the number of the nodes to be processed.
1.499
1.500 ///Returns the number of the nodes to be processed in the queue.
1.501 - int queueSize() { return _queue_head-_queue_tail; }
1.502 + int queueSize() const { return _queue_head-_queue_tail; }
1.503
1.504 ///Executes the algorithm.
1.505
1.506 ///Executes the algorithm.
1.507 ///
1.508 - ///\pre init() must be called and at least one node should be added
1.509 - ///with addSource() before using this function.
1.510 + ///This method runs the %BFS algorithm from the root node(s)
1.511 + ///in order to compute the shortest path to each node.
1.512 ///
1.513 - ///This method runs the %BFS algorithm from the root node(s)
1.514 - ///in order to
1.515 - ///compute the
1.516 - ///shortest path to each node. The algorithm computes
1.517 - ///- The shortest path tree.
1.518 - ///- The distance of each node from the root(s).
1.519 + ///The algorithm computes
1.520 + ///- the shortest path tree (forest),
1.521 + ///- the distance of each node from the root(s).
1.522 + ///
1.523 + ///\pre init() must be called and at least one root node should be
1.524 + ///added with addSource() before using this function.
1.525 + ///
1.526 + ///\note <tt>b.start()</tt> is just a shortcut of the following code.
1.527 + ///\code
1.528 + /// while ( !b.emptyQueue() ) {
1.529 + /// b.processNextNode();
1.530 + /// }
1.531 + ///\endcode
1.532 void start()
1.533 {
1.534 while ( !emptyQueue() ) processNextNode();
1.535 }
1.536
1.537 - ///Executes the algorithm until \c dest is reached.
1.538 + ///Executes the algorithm until the given target node is reached.
1.539
1.540 - ///Executes the algorithm until \c dest is reached.
1.541 - ///
1.542 - ///\pre init() must be called and at least one node should be added
1.543 - ///with addSource() before using this function.
1.544 + ///Executes the algorithm until the given target node is reached.
1.545 ///
1.546 ///This method runs the %BFS algorithm from the root node(s)
1.547 ///in order to compute the shortest path to \c dest.
1.548 + ///
1.549 ///The algorithm computes
1.550 - ///- The shortest path to \c dest.
1.551 - ///- The distance of \c dest from the root(s).
1.552 + ///- the shortest path to \c dest,
1.553 + ///- the distance of \c dest from the root(s).
1.554 + ///
1.555 + ///\pre init() must be called and at least one root node should be
1.556 + ///added with addSource() before using this function.
1.557 + ///
1.558 + ///\note <tt>b.start(t)</tt> is just a shortcut of the following code.
1.559 + ///\code
1.560 + /// bool reach = false;
1.561 + /// while ( !b.emptyQueue() && !reach ) {
1.562 + /// b.processNextNode(t, reach);
1.563 + /// }
1.564 + ///\endcode
1.565 void start(Node dest)
1.566 {
1.567 bool reach = false;
1.568 @@ -608,17 +634,29 @@
1.569
1.570 ///Executes the algorithm until a condition is met.
1.571 ///
1.572 - ///\pre init() must be called and at least one node should be added
1.573 - ///with addSource() before using this function.
1.574 + ///This method runs the %BFS algorithm from the root node(s) in
1.575 + ///order to compute the shortest path to a node \c v with
1.576 + /// <tt>nm[v]</tt> true, if such a node can be found.
1.577 ///
1.578 - ///\param nm must be a bool (or convertible) node map. The
1.579 - ///algorithm will stop when it reaches a node \c v with
1.580 - /// <tt>nm[v]</tt> true.
1.581 + ///\param nm A \c bool (or convertible) node map. The algorithm
1.582 + ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
1.583 ///
1.584 ///\return The reached node \c v with <tt>nm[v]</tt> true or
1.585 ///\c INVALID if no such node was found.
1.586 - template<class NM>
1.587 - Node start(const NM &nm)
1.588 + ///
1.589 + ///\pre init() must be called and at least one root node should be
1.590 + ///added with addSource() before using this function.
1.591 + ///
1.592 + ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
1.593 + ///\code
1.594 + /// Node rnode = INVALID;
1.595 + /// while ( !b.emptyQueue() && rnode == INVALID ) {
1.596 + /// b.processNextNode(nm, rnode);
1.597 + /// }
1.598 + /// return rnode;
1.599 + ///\endcode
1.600 + template<class NodeBoolMap>
1.601 + Node start(const NodeBoolMap &nm)
1.602 {
1.603 Node rnode = INVALID;
1.604 while ( !emptyQueue() && rnode == INVALID ) {
1.605 @@ -627,16 +665,16 @@
1.606 return rnode;
1.607 }
1.608
1.609 - ///Runs %BFS algorithm from node \c s.
1.610 + ///Runs the algorithm from the given node.
1.611
1.612 - ///This method runs the %BFS algorithm from a root node \c s
1.613 - ///in order to
1.614 - ///compute the
1.615 - ///shortest path to each node. The algorithm computes
1.616 - ///- The shortest path tree.
1.617 - ///- The distance of each node from the root.
1.618 + ///This method runs the %BFS algorithm from node \c s
1.619 + ///in order to compute the shortest path to each node.
1.620 ///
1.621 - ///\note b.run(s) is just a shortcut of the following code.
1.622 + ///The algorithm computes
1.623 + ///- the shortest path tree,
1.624 + ///- the distance of each node from the root.
1.625 + ///
1.626 + ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
1.627 ///\code
1.628 /// b.init();
1.629 /// b.addSource(s);
1.630 @@ -650,12 +688,14 @@
1.631
1.632 ///Finds the shortest path between \c s and \c t.
1.633
1.634 - ///Finds the shortest path between \c s and \c t.
1.635 + ///This method runs the %BFS algorithm from node \c s
1.636 + ///in order to compute the shortest path to \c t.
1.637 ///
1.638 - ///\return The length of the shortest s---t path if there exists one,
1.639 - ///0 otherwise.
1.640 - ///\note Apart from the return value, b.run(s) is
1.641 - ///just a shortcut of the following code.
1.642 + ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
1.643 + ///if \c t is reachable form \c s, \c 0 otherwise.
1.644 + ///
1.645 + ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
1.646 + ///shortcut of the following code.
1.647 ///\code
1.648 /// b.init();
1.649 /// b.addSource(s);
1.650 @@ -668,116 +708,152 @@
1.651 return reached(t) ? _curr_dist : 0;
1.652 }
1.653
1.654 + ///Runs the algorithm to visit all nodes in the digraph.
1.655 +
1.656 + ///This method runs the %BFS algorithm in order to
1.657 + ///compute the shortest path to each node.
1.658 + ///
1.659 + ///The algorithm computes
1.660 + ///- the shortest path tree (forest),
1.661 + ///- the distance of each node from the root(s).
1.662 + ///
1.663 + ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
1.664 + ///\code
1.665 + /// b.init();
1.666 + /// for (NodeIt n(gr); n != INVALID; ++n) {
1.667 + /// if (!b.reached(n)) {
1.668 + /// b.addSource(n);
1.669 + /// b.start();
1.670 + /// }
1.671 + /// }
1.672 + ///\endcode
1.673 + void run() {
1.674 + init();
1.675 + for (NodeIt n(*G); n != INVALID; ++n) {
1.676 + if (!reached(n)) {
1.677 + addSource(n);
1.678 + start();
1.679 + }
1.680 + }
1.681 + }
1.682 +
1.683 ///@}
1.684
1.685 ///\name Query Functions
1.686 ///The result of the %BFS algorithm can be obtained using these
1.687 ///functions.\n
1.688 - ///Before the use of these functions,
1.689 - ///either run() or start() must be calleb.
1.690 + ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
1.691 + ///"start()" must be called before using them.
1.692
1.693 ///@{
1.694
1.695 - typedef PredMapPath<Digraph, PredMap> Path;
1.696 + ///The shortest path to a node.
1.697
1.698 - ///Gives back the shortest path.
1.699 -
1.700 - ///Gives back the shortest path.
1.701 - ///\pre The \c t should be reachable from the source.
1.702 - Path path(Node t)
1.703 - {
1.704 - return Path(*G, *_pred, t);
1.705 - }
1.706 + ///Returns the shortest path to a node.
1.707 + ///
1.708 + ///\warning \c t should be reachable from the root(s).
1.709 + ///
1.710 + ///\pre Either \ref run() or \ref start() must be called before
1.711 + ///using this function.
1.712 + Path path(Node t) const { return Path(*G, *_pred, t); }
1.713
1.714 ///The distance of a node from the root(s).
1.715
1.716 ///Returns the distance of a node from the root(s).
1.717 - ///\pre \ref run() must be called before using this function.
1.718 - ///\warning If node \c v in unreachable from the root(s) the return value
1.719 - ///of this function is undefined.
1.720 + ///
1.721 + ///\warning If node \c v is not reachable from the root(s), then
1.722 + ///the return value of this function is undefined.
1.723 + ///
1.724 + ///\pre Either \ref run() or \ref start() must be called before
1.725 + ///using this function.
1.726 int dist(Node v) const { return (*_dist)[v]; }
1.727
1.728 - ///Returns the 'previous arc' of the shortest path tree.
1.729 + ///Returns the 'previous arc' of the shortest path tree for a node.
1.730
1.731 - ///For a node \c v it returns the 'previous arc'
1.732 - ///of the shortest path tree,
1.733 - ///i.e. it returns the last arc of a shortest path from the root(s) to \c
1.734 - ///v. It is \ref INVALID
1.735 - ///if \c v is unreachable from the root(s) or \c v is a root. The
1.736 - ///shortest path tree used here is equal to the shortest path tree used in
1.737 - ///\ref predNode().
1.738 - ///\pre Either \ref run() or \ref start() must be called before using
1.739 - ///this function.
1.740 + ///This function returns the 'previous arc' of the shortest path
1.741 + ///tree for the node \c v, i.e. it returns the last arc of a
1.742 + ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
1.743 + ///is not reachable from the root(s) or if \c v is a root.
1.744 + ///
1.745 + ///The shortest path tree used here is equal to the shortest path
1.746 + ///tree used in \ref predNode().
1.747 + ///
1.748 + ///\pre Either \ref run() or \ref start() must be called before
1.749 + ///using this function.
1.750 Arc predArc(Node v) const { return (*_pred)[v];}
1.751
1.752 - ///Returns the 'previous node' of the shortest path tree.
1.753 + ///Returns the 'previous node' of the shortest path tree for a node.
1.754
1.755 - ///For a node \c v it returns the 'previous node'
1.756 - ///of the shortest path tree,
1.757 - ///i.e. it returns the last but one node from a shortest path from the
1.758 - ///root(a) to \c /v.
1.759 - ///It is INVALID if \c v is unreachable from the root(s) or
1.760 - ///if \c v itself a root.
1.761 + ///This function returns the 'previous node' of the shortest path
1.762 + ///tree for the node \c v, i.e. it returns the last but one node
1.763 + ///from a shortest path from the root(s) to \c v. It is \c INVALID
1.764 + ///if \c v is not reachable from the root(s) or if \c v is a root.
1.765 + ///
1.766 ///The shortest path tree used here is equal to the shortest path
1.767 ///tree used in \ref predArc().
1.768 + ///
1.769 ///\pre Either \ref run() or \ref start() must be called before
1.770 ///using this function.
1.771 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.772 G->source((*_pred)[v]); }
1.773
1.774 - ///Returns a reference to the NodeMap of distances.
1.775 -
1.776 - ///Returns a reference to the NodeMap of distances.
1.777 - ///\pre Either \ref run() or \ref init() must
1.778 - ///be called before using this function.
1.779 + ///\brief Returns a const reference to the node map that stores the
1.780 + /// distances of the nodes.
1.781 + ///
1.782 + ///Returns a const reference to the node map that stores the distances
1.783 + ///of the nodes calculated by the algorithm.
1.784 + ///
1.785 + ///\pre Either \ref run() or \ref init()
1.786 + ///must be called before using this function.
1.787 const DistMap &distMap() const { return *_dist;}
1.788
1.789 - ///Returns a reference to the shortest path tree map.
1.790 -
1.791 - ///Returns a reference to the NodeMap of the arcs of the
1.792 - ///shortest path tree.
1.793 + ///\brief Returns a const reference to the node map that stores the
1.794 + ///predecessor arcs.
1.795 + ///
1.796 + ///Returns a const reference to the node map that stores the predecessor
1.797 + ///arcs, which form the shortest path tree.
1.798 + ///
1.799 ///\pre Either \ref run() or \ref init()
1.800 ///must be called before using this function.
1.801 const PredMap &predMap() const { return *_pred;}
1.802
1.803 - ///Checks if a node is reachable from the root.
1.804 + ///Checks if a node is reachable from the root(s).
1.805
1.806 - ///Returns \c true if \c v is reachable from the root.
1.807 - ///\warning The source nodes are indicated as unreached.
1.808 + ///Returns \c true if \c v is reachable from the root(s).
1.809 ///\pre Either \ref run() or \ref start()
1.810 ///must be called before using this function.
1.811 - ///
1.812 - bool reached(Node v) { return (*_reached)[v]; }
1.813 + bool reached(Node v) const { return (*_reached)[v]; }
1.814
1.815 ///@}
1.816 };
1.817
1.818 - ///Default traits class of Bfs function.
1.819 + ///Default traits class of bfs() function.
1.820
1.821 - ///Default traits class of Bfs function.
1.822 + ///Default traits class of bfs() function.
1.823 ///\tparam GR Digraph type.
1.824 template<class GR>
1.825 struct BfsWizardDefaultTraits
1.826 {
1.827 - ///The digraph type the algorithm runs on.
1.828 + ///The type of the digraph the algorithm runs on.
1.829 typedef GR Digraph;
1.830 - ///\brief The type of the map that stores the last
1.831 +
1.832 + ///\brief The type of the map that stores the predecessor
1.833 ///arcs of the shortest paths.
1.834 ///
1.835 - ///The type of the map that stores the last
1.836 + ///The type of the map that stores the predecessor
1.837 ///arcs of the shortest paths.
1.838 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.839 - ///
1.840 - typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
1.841 - ///Instantiates a PredMap.
1.842 + typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
1.843 + ///Instantiates a \ref PredMap.
1.844
1.845 ///This function instantiates a \ref PredMap.
1.846 - ///\param g is the digraph, to which we would like to define the PredMap.
1.847 + ///\param g is the digraph, to which we would like to define the
1.848 + ///\ref PredMap.
1.849 ///\todo The digraph alone may be insufficient to initialize
1.850 #ifdef DOXYGEN
1.851 - static PredMap *createPredMap(const GR &g)
1.852 + static PredMap *createPredMap(const Digraph &g)
1.853 #else
1.854 - static PredMap *createPredMap(const GR &)
1.855 + static PredMap *createPredMap(const Digraph &)
1.856 #endif
1.857 {
1.858 return new PredMap();
1.859 @@ -787,63 +863,63 @@
1.860
1.861 ///The type of the map that indicates which nodes are processed.
1.862 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.863 - ///\todo named parameter to set this type, function to read and write.
1.864 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.865 - ///Instantiates a ProcessedMap.
1.866 + ///Instantiates a \ref ProcessedMap.
1.867
1.868 ///This function instantiates a \ref ProcessedMap.
1.869 ///\param g is the digraph, to which
1.870 - ///we would like to define the \ref ProcessedMap
1.871 + ///we would like to define the \ref ProcessedMap.
1.872 #ifdef DOXYGEN
1.873 - static ProcessedMap *createProcessedMap(const GR &g)
1.874 + static ProcessedMap *createProcessedMap(const Digraph &g)
1.875 #else
1.876 - static ProcessedMap *createProcessedMap(const GR &)
1.877 + static ProcessedMap *createProcessedMap(const Digraph &)
1.878 #endif
1.879 {
1.880 return new ProcessedMap();
1.881 }
1.882 +
1.883 ///The type of the map that indicates which nodes are reached.
1.884
1.885 ///The type of the map that indicates which nodes are reached.
1.886 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.887 - ///\todo named parameter to set this type, function to read and write.
1.888 + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.889 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.890 - ///Instantiates a ReachedMap.
1.891 + ///Instantiates a \ref ReachedMap.
1.892
1.893 ///This function instantiates a \ref ReachedMap.
1.894 - ///\param G is the digraph, to which
1.895 + ///\param g is the digraph, to which
1.896 ///we would like to define the \ref ReachedMap.
1.897 - static ReachedMap *createReachedMap(const GR &G)
1.898 + static ReachedMap *createReachedMap(const Digraph &g)
1.899 {
1.900 - return new ReachedMap(G);
1.901 + return new ReachedMap(g);
1.902 }
1.903 - ///The type of the map that stores the dists of the nodes.
1.904
1.905 - ///The type of the map that stores the dists of the nodes.
1.906 + ///The type of the map that stores the distances of the nodes.
1.907 +
1.908 + ///The type of the map that stores the distances of the nodes.
1.909 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.910 ///
1.911 typedef NullMap<typename Digraph::Node,int> DistMap;
1.912 - ///Instantiates a DistMap.
1.913 + ///Instantiates a \ref DistMap.
1.914
1.915 ///This function instantiates a \ref DistMap.
1.916 ///\param g is the digraph, to which we would like to define
1.917 ///the \ref DistMap
1.918 #ifdef DOXYGEN
1.919 - static DistMap *createDistMap(const GR &g)
1.920 + static DistMap *createDistMap(const Digraph &g)
1.921 #else
1.922 - static DistMap *createDistMap(const GR &)
1.923 + static DistMap *createDistMap(const Digraph &)
1.924 #endif
1.925 {
1.926 return new DistMap();
1.927 }
1.928 };
1.929
1.930 - /// Default traits used by \ref BfsWizard
1.931 + /// Default traits class used by \ref BfsWizard
1.932
1.933 /// To make it easier to use Bfs algorithm
1.934 - ///we have created a wizard class.
1.935 + /// we have created a wizard class.
1.936 /// This \ref BfsWizard class needs default traits,
1.937 - ///as well as the \ref Bfs class.
1.938 + /// as well as the \ref Bfs class.
1.939 /// The \ref BfsWizardBase is a class to be the default traits of the
1.940 /// \ref BfsWizard class.
1.941 template<class GR>
1.942 @@ -852,20 +928,20 @@
1.943
1.944 typedef BfsWizardDefaultTraits<GR> Base;
1.945 protected:
1.946 - /// Type of the nodes in the digraph.
1.947 + //The type of the nodes in the digraph.
1.948 typedef typename Base::Digraph::Node Node;
1.949
1.950 - /// Pointer to the underlying digraph.
1.951 + //Pointer to the digraph the algorithm runs on.
1.952 void *_g;
1.953 - ///Pointer to the map of reached nodes.
1.954 + //Pointer to the map of reached nodes.
1.955 void *_reached;
1.956 - ///Pointer to the map of processed nodes.
1.957 + //Pointer to the map of processed nodes.
1.958 void *_processed;
1.959 - ///Pointer to the map of predecessors arcs.
1.960 + //Pointer to the map of predecessors arcs.
1.961 void *_pred;
1.962 - ///Pointer to the map of distances.
1.963 + //Pointer to the map of distances.
1.964 void *_dist;
1.965 - ///Pointer to the source node.
1.966 + //Pointer to the source node.
1.967 Node _source;
1.968
1.969 public:
1.970 @@ -874,26 +950,28 @@
1.971 /// This constructor does not require parameters, therefore it initiates
1.972 /// all of the attributes to default values (0, INVALID).
1.973 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
1.974 - _dist(0), _source(INVALID) {}
1.975 + _dist(0), _source(INVALID) {}
1.976
1.977 /// Constructor.
1.978
1.979 /// This constructor requires some parameters,
1.980 /// listed in the parameters list.
1.981 /// Others are initiated to 0.
1.982 - /// \param g is the initial value of \ref _g
1.983 - /// \param s is the initial value of \ref _source
1.984 + /// \param g The digraph the algorithm runs on.
1.985 + /// \param s The source node.
1.986 BfsWizardBase(const GR &g, Node s=INVALID) :
1.987 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1.988 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
1.989
1.990 };
1.991
1.992 - /// A class to make the usage of Bfs algorithm easier
1.993 + /// Auxiliary class for the function type interface of BFS algorithm.
1.994
1.995 - /// This class is created to make it easier to use Bfs algorithm.
1.996 - /// It uses the functions and features of the plain \ref Bfs,
1.997 - /// but it is much simpler to use it.
1.998 + /// This auxiliary class is created to implement the function type
1.999 + /// interface of \ref Bfs algorithm. It uses the functions and features
1.1000 + /// of the plain \ref Bfs, but it is much simpler to use it.
1.1001 + /// It should only be used through the \ref bfs() function, which makes
1.1002 + /// it easier to use the algorithm.
1.1003 ///
1.1004 /// Simplicity means that the way to change the types defined
1.1005 /// in the traits class is based on functions that returns the new class
1.1006 @@ -902,41 +980,37 @@
1.1007 /// the new class with the modified type comes from
1.1008 /// the original class by using the ::
1.1009 /// operator. In the case of \ref BfsWizard only
1.1010 - /// a function have to be called and it will
1.1011 + /// a function have to be called, and it will
1.1012 /// return the needed class.
1.1013 ///
1.1014 - /// It does not have own \ref run method. When its \ref run method is called
1.1015 - /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
1.1016 - /// method of it.
1.1017 + /// It does not have own \ref run() method. When its \ref run() method
1.1018 + /// is called, it initiates a plain \ref Bfs object, and calls the
1.1019 + /// \ref Bfs::run() method of it.
1.1020 template<class TR>
1.1021 class BfsWizard : public TR
1.1022 {
1.1023 typedef TR Base;
1.1024
1.1025 - ///The type of the underlying digraph.
1.1026 + ///The type of the digraph the algorithm runs on.
1.1027 typedef typename TR::Digraph Digraph;
1.1028 - //\e
1.1029 +
1.1030 typedef typename Digraph::Node Node;
1.1031 - //\e
1.1032 typedef typename Digraph::NodeIt NodeIt;
1.1033 - //\e
1.1034 typedef typename Digraph::Arc Arc;
1.1035 - //\e
1.1036 typedef typename Digraph::OutArcIt OutArcIt;
1.1037
1.1038 - ///\brief The type of the map that stores
1.1039 - ///the reached nodes
1.1040 - typedef typename TR::ReachedMap ReachedMap;
1.1041 - ///\brief The type of the map that stores
1.1042 - ///the processed nodes
1.1043 - typedef typename TR::ProcessedMap ProcessedMap;
1.1044 - ///\brief The type of the map that stores the last
1.1045 + ///\brief The type of the map that stores the predecessor
1.1046 ///arcs of the shortest paths.
1.1047 typedef typename TR::PredMap PredMap;
1.1048 - ///The type of the map that stores the dists of the nodes.
1.1049 + ///\brief The type of the map that stores the distances of the nodes.
1.1050 typedef typename TR::DistMap DistMap;
1.1051 + ///\brief The type of the map that indicates which nodes are reached.
1.1052 + typedef typename TR::ReachedMap ReachedMap;
1.1053 + ///\brief The type of the map that indicates which nodes are processed.
1.1054 + typedef typename TR::ProcessedMap ProcessedMap;
1.1055
1.1056 public:
1.1057 +
1.1058 /// Constructor.
1.1059 BfsWizard() : TR() {}
1.1060
1.1061 @@ -952,10 +1026,10 @@
1.1062
1.1063 ~BfsWizard() {}
1.1064
1.1065 - ///Runs Bfs algorithm from a given node.
1.1066 + ///Runs BFS algorithm from a source node.
1.1067
1.1068 - ///Runs Bfs algorithm from a given node.
1.1069 - ///The node can be given by the \ref source function.
1.1070 + ///Runs BFS algorithm from a source node.
1.1071 + ///The node can be given with the \ref source() function.
1.1072 void run()
1.1073 {
1.1074 if(Base::_source==INVALID) throw UninitializedParameter();
1.1075 @@ -971,9 +1045,9 @@
1.1076 alg.run(Base::_source);
1.1077 }
1.1078
1.1079 - ///Runs Bfs algorithm from the given node.
1.1080 + ///Runs BFS algorithm from the given node.
1.1081
1.1082 - ///Runs Bfs algorithm from the given node.
1.1083 + ///Runs BFS algorithm from the given node.
1.1084 ///\param s is the given source.
1.1085 void run(Node s)
1.1086 {
1.1087 @@ -981,89 +1055,6 @@
1.1088 run();
1.1089 }
1.1090
1.1091 - template<class T>
1.1092 - struct DefPredMapBase : public Base {
1.1093 - typedef T PredMap;
1.1094 - static PredMap *createPredMap(const Digraph &) { return 0; };
1.1095 - DefPredMapBase(const TR &b) : TR(b) {}
1.1096 - };
1.1097 -
1.1098 - ///\brief \ref named-templ-param "Named parameter"
1.1099 - ///function for setting PredMap
1.1100 - ///
1.1101 - /// \ref named-templ-param "Named parameter"
1.1102 - ///function for setting PredMap
1.1103 - ///
1.1104 - template<class T>
1.1105 - BfsWizard<DefPredMapBase<T> > predMap(const T &t)
1.1106 - {
1.1107 - Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1108 - return BfsWizard<DefPredMapBase<T> >(*this);
1.1109 - }
1.1110 -
1.1111 -
1.1112 - template<class T>
1.1113 - struct DefReachedMapBase : public Base {
1.1114 - typedef T ReachedMap;
1.1115 - static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1.1116 - DefReachedMapBase(const TR &b) : TR(b) {}
1.1117 - };
1.1118 -
1.1119 - ///\brief \ref named-templ-param "Named parameter"
1.1120 - ///function for setting ReachedMap
1.1121 - ///
1.1122 - /// \ref named-templ-param "Named parameter"
1.1123 - ///function for setting ReachedMap
1.1124 - ///
1.1125 - template<class T>
1.1126 - BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1.1127 - {
1.1128 - Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1129 - return BfsWizard<DefReachedMapBase<T> >(*this);
1.1130 - }
1.1131 -
1.1132 -
1.1133 - template<class T>
1.1134 - struct DefProcessedMapBase : public Base {
1.1135 - typedef T ProcessedMap;
1.1136 - static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.1137 - DefProcessedMapBase(const TR &b) : TR(b) {}
1.1138 - };
1.1139 -
1.1140 - ///\brief \ref named-templ-param "Named parameter"
1.1141 - ///function for setting ProcessedMap
1.1142 - ///
1.1143 - /// \ref named-templ-param "Named parameter"
1.1144 - ///function for setting ProcessedMap
1.1145 - ///
1.1146 - template<class T>
1.1147 - BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1.1148 - {
1.1149 - Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1150 - return BfsWizard<DefProcessedMapBase<T> >(*this);
1.1151 - }
1.1152 -
1.1153 -
1.1154 - template<class T>
1.1155 - struct DefDistMapBase : public Base {
1.1156 - typedef T DistMap;
1.1157 - static DistMap *createDistMap(const Digraph &) { return 0; };
1.1158 - DefDistMapBase(const TR &b) : TR(b) {}
1.1159 - };
1.1160 -
1.1161 - ///\brief \ref named-templ-param "Named parameter"
1.1162 - ///function for setting DistMap type
1.1163 - ///
1.1164 - /// \ref named-templ-param "Named parameter"
1.1165 - ///function for setting DistMap type
1.1166 - ///
1.1167 - template<class T>
1.1168 - BfsWizard<DefDistMapBase<T> > distMap(const T &t)
1.1169 - {
1.1170 - Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1171 - return BfsWizard<DefDistMapBase<T> >(*this);
1.1172 - }
1.1173 -
1.1174 /// Sets the source node, from which the Bfs algorithm runs.
1.1175
1.1176 /// Sets the source node, from which the Bfs algorithm runs.
1.1177 @@ -1074,6 +1065,78 @@
1.1178 return *this;
1.1179 }
1.1180
1.1181 + template<class T>
1.1182 + struct DefPredMapBase : public Base {
1.1183 + typedef T PredMap;
1.1184 + static PredMap *createPredMap(const Digraph &) { return 0; };
1.1185 + DefPredMapBase(const TR &b) : TR(b) {}
1.1186 + };
1.1187 + ///\brief \ref named-templ-param "Named parameter"
1.1188 + ///for setting \ref PredMap object.
1.1189 + ///
1.1190 + /// \ref named-templ-param "Named parameter"
1.1191 + ///for setting \ref PredMap object.
1.1192 + template<class T>
1.1193 + BfsWizard<DefPredMapBase<T> > predMap(const T &t)
1.1194 + {
1.1195 + Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1196 + return BfsWizard<DefPredMapBase<T> >(*this);
1.1197 + }
1.1198 +
1.1199 + template<class T>
1.1200 + struct DefReachedMapBase : public Base {
1.1201 + typedef T ReachedMap;
1.1202 + static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1.1203 + DefReachedMapBase(const TR &b) : TR(b) {}
1.1204 + };
1.1205 + ///\brief \ref named-templ-param "Named parameter"
1.1206 + ///for setting \ref ReachedMap object.
1.1207 + ///
1.1208 + /// \ref named-templ-param "Named parameter"
1.1209 + ///for setting \ref ReachedMap object.
1.1210 + template<class T>
1.1211 + BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1.1212 + {
1.1213 + Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1214 + return BfsWizard<DefReachedMapBase<T> >(*this);
1.1215 + }
1.1216 +
1.1217 + template<class T>
1.1218 + struct DefProcessedMapBase : public Base {
1.1219 + typedef T ProcessedMap;
1.1220 + static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.1221 + DefProcessedMapBase(const TR &b) : TR(b) {}
1.1222 + };
1.1223 + ///\brief \ref named-templ-param "Named parameter"
1.1224 + ///for setting \ref ProcessedMap object.
1.1225 + ///
1.1226 + /// \ref named-templ-param "Named parameter"
1.1227 + ///for setting \ref ProcessedMap object.
1.1228 + template<class T>
1.1229 + BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1.1230 + {
1.1231 + Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1232 + return BfsWizard<DefProcessedMapBase<T> >(*this);
1.1233 + }
1.1234 +
1.1235 + template<class T>
1.1236 + struct DefDistMapBase : public Base {
1.1237 + typedef T DistMap;
1.1238 + static DistMap *createDistMap(const Digraph &) { return 0; };
1.1239 + DefDistMapBase(const TR &b) : TR(b) {}
1.1240 + };
1.1241 + ///\brief \ref named-templ-param "Named parameter"
1.1242 + ///for setting \ref DistMap object.
1.1243 + ///
1.1244 + /// \ref named-templ-param "Named parameter"
1.1245 + ///for setting \ref DistMap object.
1.1246 + template<class T>
1.1247 + BfsWizard<DefDistMapBase<T> > distMap(const T &t)
1.1248 + {
1.1249 + Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1250 + return BfsWizard<DefDistMapBase<T> >(*this);
1.1251 + }
1.1252 +
1.1253 };
1.1254
1.1255 ///Function type interface for Bfs algorithm.
1.1256 @@ -1101,38 +1164,38 @@
1.1257 }
1.1258
1.1259 #ifdef DOXYGEN
1.1260 - /// \brief Visitor class for bfs.
1.1261 + /// \brief Visitor class for BFS.
1.1262 ///
1.1263 /// This class defines the interface of the BfsVisit events, and
1.1264 - /// it could be the base of a real Visitor class.
1.1265 + /// it could be the base of a real visitor class.
1.1266 template <typename _Digraph>
1.1267 struct BfsVisitor {
1.1268 typedef _Digraph Digraph;
1.1269 typedef typename Digraph::Arc Arc;
1.1270 typedef typename Digraph::Node Node;
1.1271 - /// \brief Called when the arc reach a node.
1.1272 + /// \brief Called for the source node(s) of the BFS.
1.1273 ///
1.1274 - /// It is called when the bfs find an arc which target is not
1.1275 - /// reached yet.
1.1276 + /// This function is called for the source node(s) of the BFS.
1.1277 + void start(const Node& node) {}
1.1278 + /// \brief Called when a node is reached first time.
1.1279 + ///
1.1280 + /// This function is called when a node is reached first time.
1.1281 + void reach(const Node& node) {}
1.1282 + /// \brief Called when a node is processed.
1.1283 + ///
1.1284 + /// This function is called when a node is processed.
1.1285 + void process(const Node& node) {}
1.1286 + /// \brief Called when an arc reaches a new node.
1.1287 + ///
1.1288 + /// This function is called when the BFS finds an arc whose target node
1.1289 + /// is not reached yet.
1.1290 void discover(const Arc& arc) {}
1.1291 - /// \brief Called when the node reached first time.
1.1292 - ///
1.1293 - /// It is Called when the node reached first time.
1.1294 - void reach(const Node& node) {}
1.1295 - /// \brief Called when the arc examined but target of the arc
1.1296 + /// \brief Called when an arc is examined but its target node is
1.1297 /// already discovered.
1.1298 ///
1.1299 - /// It called when the arc examined but the target of the arc
1.1300 + /// This function is called when an arc is examined but its target node is
1.1301 /// already discovered.
1.1302 void examine(const Arc& arc) {}
1.1303 - /// \brief Called for the source node of the bfs.
1.1304 - ///
1.1305 - /// It is called for the source node of the bfs.
1.1306 - void start(const Node& node) {}
1.1307 - /// \brief Called when the node processed.
1.1308 - ///
1.1309 - /// It is Called when the node processed.
1.1310 - void process(const Node& node) {}
1.1311 };
1.1312 #else
1.1313 template <typename _Digraph>
1.1314 @@ -1140,22 +1203,22 @@
1.1315 typedef _Digraph Digraph;
1.1316 typedef typename Digraph::Arc Arc;
1.1317 typedef typename Digraph::Node Node;
1.1318 + void start(const Node&) {}
1.1319 + void reach(const Node&) {}
1.1320 + void process(const Node&) {}
1.1321 void discover(const Arc&) {}
1.1322 - void reach(const Node&) {}
1.1323 void examine(const Arc&) {}
1.1324 - void start(const Node&) {}
1.1325 - void process(const Node&) {}
1.1326
1.1327 template <typename _Visitor>
1.1328 struct Constraints {
1.1329 void constraints() {
1.1330 Arc arc;
1.1331 Node node;
1.1332 + visitor.start(node);
1.1333 + visitor.reach(node);
1.1334 + visitor.process(node);
1.1335 visitor.discover(arc);
1.1336 - visitor.reach(node);
1.1337 visitor.examine(arc);
1.1338 - visitor.start(node);
1.1339 - visitor.process(node);
1.1340 }
1.1341 _Visitor& visitor;
1.1342 };
1.1343 @@ -1165,21 +1228,20 @@
1.1344 /// \brief Default traits class of BfsVisit class.
1.1345 ///
1.1346 /// Default traits class of BfsVisit class.
1.1347 - /// \tparam _Digraph Digraph type.
1.1348 + /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.1349 template<class _Digraph>
1.1350 struct BfsVisitDefaultTraits {
1.1351
1.1352 - /// \brief The digraph type the algorithm runs on.
1.1353 + /// \brief The type of the digraph the algorithm runs on.
1.1354 typedef _Digraph Digraph;
1.1355
1.1356 /// \brief The type of the map that indicates which nodes are reached.
1.1357 ///
1.1358 /// The type of the map that indicates which nodes are reached.
1.1359 - /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.1360 - /// \todo named parameter to set this type, function to read and write.
1.1361 + /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.1362 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.1363
1.1364 - /// \brief Instantiates a ReachedMap.
1.1365 + /// \brief Instantiates a \ref ReachedMap.
1.1366 ///
1.1367 /// This function instantiates a \ref ReachedMap.
1.1368 /// \param digraph is the digraph, to which
1.1369 @@ -1192,28 +1254,28 @@
1.1370
1.1371 /// \ingroup search
1.1372 ///
1.1373 - /// \brief %BFS Visit algorithm class.
1.1374 + /// \brief %BFS algorithm class with visitor interface.
1.1375 ///
1.1376 /// This class provides an efficient implementation of the %BFS algorithm
1.1377 /// with visitor interface.
1.1378 ///
1.1379 /// The %BfsVisit class provides an alternative interface to the Bfs
1.1380 /// class. It works with callback mechanism, the BfsVisit object calls
1.1381 - /// on every bfs event the \c Visitor class member functions.
1.1382 + /// the member functions of the \c Visitor class on every BFS event.
1.1383 ///
1.1384 - /// \tparam _Digraph The digraph type the algorithm runs on.
1.1385 + /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.1386 /// The default value is
1.1387 - /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it
1.1388 - /// is only passed to \ref BfsDefaultTraits.
1.1389 - /// \tparam _Visitor The Visitor object for the algorithm. The
1.1390 - /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which
1.1391 - /// does not observe the Bfs events. If you want to observe the bfs
1.1392 - /// events you should implement your own Visitor class.
1.1393 + /// \ref ListDigraph. The value of _Digraph is not used directly by
1.1394 + /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
1.1395 + /// \tparam _Visitor The Visitor type that is used by the algorithm.
1.1396 + /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
1.1397 + /// does not observe the BFS events. If you want to observe the BFS
1.1398 + /// events, you should implement your own visitor class.
1.1399 /// \tparam _Traits Traits class to set various data types used by the
1.1400 /// algorithm. The default traits class is
1.1401 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
1.1402 /// See \ref BfsVisitDefaultTraits for the documentation of
1.1403 - /// a Bfs visit traits class.
1.1404 + /// a BFS visit traits class.
1.1405 #ifdef DOXYGEN
1.1406 template <typename _Digraph, typename _Visitor, typename _Traits>
1.1407 #else
1.1408 @@ -1227,7 +1289,7 @@
1.1409 /// \brief \ref Exception for uninitialized parameters.
1.1410 ///
1.1411 /// This error represents problems in the initialization
1.1412 - /// of the parameters of the algorithms.
1.1413 + /// of the parameters of the algorithm.
1.1414 class UninitializedParameter : public lemon::UninitializedParameter {
1.1415 public:
1.1416 virtual const char* what() const throw()
1.1417 @@ -1236,13 +1298,16 @@
1.1418 }
1.1419 };
1.1420
1.1421 + ///The traits class.
1.1422 typedef _Traits Traits;
1.1423
1.1424 + ///The type of the digraph the algorithm runs on.
1.1425 typedef typename Traits::Digraph Digraph;
1.1426
1.1427 + ///The visitor type used by the algorithm.
1.1428 typedef _Visitor Visitor;
1.1429
1.1430 - ///The type of the map indicating which nodes are reached.
1.1431 + ///The type of the map that indicates which nodes are reached.
1.1432 typedef typename Traits::ReachedMap ReachedMap;
1.1433
1.1434 private:
1.1435 @@ -1252,21 +1317,20 @@
1.1436 typedef typename Digraph::Arc Arc;
1.1437 typedef typename Digraph::OutArcIt OutArcIt;
1.1438
1.1439 - /// Pointer to the underlying digraph.
1.1440 + //Pointer to the underlying digraph.
1.1441 const Digraph *_digraph;
1.1442 - /// Pointer to the visitor object.
1.1443 + //Pointer to the visitor object.
1.1444 Visitor *_visitor;
1.1445 - ///Pointer to the map of reached status of the nodes.
1.1446 + //Pointer to the map of reached status of the nodes.
1.1447 ReachedMap *_reached;
1.1448 - ///Indicates if \ref _reached is locally allocated (\c true) or not.
1.1449 + //Indicates if _reached is locally allocated (true) or not.
1.1450 bool local_reached;
1.1451
1.1452 std::vector<typename Digraph::Node> _list;
1.1453 int _list_front, _list_back;
1.1454
1.1455 - /// \brief Creates the maps if necessary.
1.1456 - ///
1.1457 - /// Creates the maps if necessary.
1.1458 + ///Creates the maps if necessary.
1.1459 + ///\todo Better memory allocation (instead of new).
1.1460 void create_maps() {
1.1461 if(!_reached) {
1.1462 local_reached = true;
1.1463 @@ -1293,9 +1357,9 @@
1.1464 }
1.1465 };
1.1466 /// \brief \ref named-templ-param "Named parameter" for setting
1.1467 - /// ReachedMap type
1.1468 + /// ReachedMap type.
1.1469 ///
1.1470 - /// \ref named-templ-param "Named parameter" for setting ReachedMap type
1.1471 + /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
1.1472 template <class T>
1.1473 struct DefReachedMap : public BfsVisit< Digraph, Visitor,
1.1474 DefReachedMapTraits<T> > {
1.1475 @@ -1309,25 +1373,22 @@
1.1476 ///
1.1477 /// Constructor.
1.1478 ///
1.1479 - /// \param digraph the digraph the algorithm will run on.
1.1480 - /// \param visitor The visitor of the algorithm.
1.1481 - ///
1.1482 + /// \param digraph The digraph the algorithm runs on.
1.1483 + /// \param visitor The visitor object of the algorithm.
1.1484 BfsVisit(const Digraph& digraph, Visitor& visitor)
1.1485 : _digraph(&digraph), _visitor(&visitor),
1.1486 _reached(0), local_reached(false) {}
1.1487
1.1488 /// \brief Destructor.
1.1489 - ///
1.1490 - /// Destructor.
1.1491 ~BfsVisit() {
1.1492 if(local_reached) delete _reached;
1.1493 }
1.1494
1.1495 - /// \brief Sets the map indicating if a node is reached.
1.1496 + /// \brief Sets the map that indicates which nodes are reached.
1.1497 ///
1.1498 - /// Sets the map indicating if a node is reached.
1.1499 + /// Sets the map that indicates which nodes are reached.
1.1500 /// If you don't use this function before calling \ref run(),
1.1501 - /// it will allocate one. The destuctor deallocates this
1.1502 + /// it will allocate one. The destructor deallocates this
1.1503 /// automatically allocated map, of course.
1.1504 /// \return <tt> (*this) </tt>
1.1505 BfsVisit &reachedMap(ReachedMap &m) {
1.1506 @@ -1340,21 +1401,23 @@
1.1507 }
1.1508
1.1509 public:
1.1510 +
1.1511 /// \name Execution control
1.1512 /// The simplest way to execute the algorithm is to use
1.1513 - /// one of the member functions called \c run(...).
1.1514 + /// one of the member functions called \ref lemon::BfsVisit::run()
1.1515 + /// "run()".
1.1516 /// \n
1.1517 - /// If you need more control on the execution,
1.1518 - /// first you must call \ref init(), then you can adda source node
1.1519 - /// with \ref addSource().
1.1520 - /// Finally \ref start() will perform the actual path
1.1521 - /// computation.
1.1522 + /// If you need more control on the execution, first you must call
1.1523 + /// \ref lemon::BfsVisit::init() "init()", then you can add several
1.1524 + /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
1.1525 + /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
1.1526 + /// actual path computation.
1.1527
1.1528 /// @{
1.1529 +
1.1530 /// \brief Initializes the internal data structures.
1.1531 ///
1.1532 /// Initializes the internal data structures.
1.1533 - ///
1.1534 void init() {
1.1535 create_maps();
1.1536 _list.resize(countNodes(*_digraph));
1.1537 @@ -1382,7 +1445,7 @@
1.1538 ///
1.1539 /// \return The processed node.
1.1540 ///
1.1541 - /// \pre The queue must not be empty!
1.1542 + /// \pre The queue must not be empty.
1.1543 Node processNextNode() {
1.1544 Node n = _list[++_list_front];
1.1545 _visitor->process(n);
1.1546 @@ -1403,16 +1466,17 @@
1.1547
1.1548 /// \brief Processes the next node.
1.1549 ///
1.1550 - /// Processes the next node. And checks that the given target node
1.1551 + /// Processes the next node and checks if the given target node
1.1552 /// is reached. If the target node is reachable from the processed
1.1553 - /// node then the reached parameter will be set true. The reached
1.1554 - /// parameter should be initially false.
1.1555 + /// node, then the \c reach parameter will be set to \c true.
1.1556 ///
1.1557 /// \param target The target node.
1.1558 - /// \retval reach Indicates that the target node is reached.
1.1559 + /// \retval reach Indicates if the target node is reached.
1.1560 + /// It should be initially \c false.
1.1561 + ///
1.1562 /// \return The processed node.
1.1563 ///
1.1564 - /// \warning The queue must not be empty!
1.1565 + /// \pre The queue must not be empty.
1.1566 Node processNextNode(Node target, bool& reach) {
1.1567 Node n = _list[++_list_front];
1.1568 _visitor->process(n);
1.1569 @@ -1434,16 +1498,19 @@
1.1570
1.1571 /// \brief Processes the next node.
1.1572 ///
1.1573 - /// Processes the next node. And checks that at least one of
1.1574 - /// reached node has true value in the \c nm node map. If one node
1.1575 - /// with true value is reachable from the processed node then the
1.1576 - /// rnode parameter will be set to the first of such nodes.
1.1577 + /// Processes the next node and checks if at least one of reached
1.1578 + /// nodes has \c true value in the \c nm node map. If one node
1.1579 + /// with \c true value is reachable from the processed node, then the
1.1580 + /// \c rnode parameter will be set to the first of such nodes.
1.1581 ///
1.1582 - /// \param nm The node map of possible targets.
1.1583 + /// \param nm A \c bool (or convertible) node map that indicates the
1.1584 + /// possible targets.
1.1585 /// \retval rnode The reached target node.
1.1586 + /// It should be initially \c INVALID.
1.1587 + ///
1.1588 /// \return The processed node.
1.1589 ///
1.1590 - /// \warning The queue must not be empty!
1.1591 + /// \pre The queue must not be empty.
1.1592 template <typename NM>
1.1593 Node processNextNode(const NM& nm, Node& rnode) {
1.1594 Node n = _list[++_list_front];
1.1595 @@ -1464,44 +1531,71 @@
1.1596 return n;
1.1597 }
1.1598
1.1599 - /// \brief Next node to be processed.
1.1600 + /// \brief The next node to be processed.
1.1601 ///
1.1602 - /// Next node to be processed.
1.1603 - ///
1.1604 - /// \return The next node to be processed or INVALID if the stack is
1.1605 - /// empty.
1.1606 - Node nextNode() {
1.1607 + /// Returns the next node to be processed or \c INVALID if the queue
1.1608 + /// is empty.
1.1609 + Node nextNode() const {
1.1610 return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
1.1611 }
1.1612
1.1613 /// \brief Returns \c false if there are nodes
1.1614 - /// to be processed in the queue
1.1615 + /// to be processed.
1.1616 ///
1.1617 /// Returns \c false if there are nodes
1.1618 - /// to be processed in the queue
1.1619 - bool emptyQueue() { return _list_front == _list_back; }
1.1620 + /// to be processed in the queue.
1.1621 + bool emptyQueue() const { return _list_front == _list_back; }
1.1622
1.1623 /// \brief Returns the number of the nodes to be processed.
1.1624 ///
1.1625 /// Returns the number of the nodes to be processed in the queue.
1.1626 - int queueSize() { return _list_back - _list_front; }
1.1627 + int queueSize() const { return _list_back - _list_front; }
1.1628
1.1629 /// \brief Executes the algorithm.
1.1630 ///
1.1631 /// Executes the algorithm.
1.1632 ///
1.1633 - /// \pre init() must be called and at least one node should be added
1.1634 + /// This method runs the %BFS algorithm from the root node(s)
1.1635 + /// in order to compute the shortest path to each node.
1.1636 + ///
1.1637 + /// The algorithm computes
1.1638 + /// - the shortest path tree (forest),
1.1639 + /// - the distance of each node from the root(s).
1.1640 + ///
1.1641 + /// \pre init() must be called and at least one root node should be added
1.1642 /// with addSource() before using this function.
1.1643 + ///
1.1644 + /// \note <tt>b.start()</tt> is just a shortcut of the following code.
1.1645 + /// \code
1.1646 + /// while ( !b.emptyQueue() ) {
1.1647 + /// b.processNextNode();
1.1648 + /// }
1.1649 + /// \endcode
1.1650 void start() {
1.1651 while ( !emptyQueue() ) processNextNode();
1.1652 }
1.1653
1.1654 - /// \brief Executes the algorithm until \c dest is reached.
1.1655 + /// \brief Executes the algorithm until the given target node is reached.
1.1656 ///
1.1657 - /// Executes the algorithm until \c dest is reached.
1.1658 + /// Executes the algorithm until the given target node is reached.
1.1659 ///
1.1660 - /// \pre init() must be called and at least one node should be added
1.1661 - /// with addSource() before using this function.
1.1662 + /// This method runs the %BFS algorithm from the root node(s)
1.1663 + /// in order to compute the shortest path to \c dest.
1.1664 + ///
1.1665 + /// The algorithm computes
1.1666 + /// - the shortest path to \c dest,
1.1667 + /// - the distance of \c dest from the root(s).
1.1668 + ///
1.1669 + /// \pre init() must be called and at least one root node should be
1.1670 + /// added with addSource() before using this function.
1.1671 + ///
1.1672 + /// \note <tt>b.start(t)</tt> is just a shortcut of the following code.
1.1673 + /// \code
1.1674 + /// bool reach = false;
1.1675 + /// while ( !b.emptyQueue() && !reach ) {
1.1676 + /// b.processNextNode(t, reach);
1.1677 + /// }
1.1678 + /// \endcode
1.1679 void start(Node dest) {
1.1680 bool reach = false;
1.1681 while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
1.1682 @@ -1511,15 +1605,28 @@
1.1683 ///
1.1684 /// Executes the algorithm until a condition is met.
1.1685 ///
1.1686 - /// \pre init() must be called and at least one node should be added
1.1687 - /// with addSource() before using this function.
1.1688 + /// This method runs the %BFS algorithm from the root node(s) in
1.1689 + /// order to compute the shortest path to a node \c v with
1.1690 + /// <tt>nm[v]</tt> true, if such a node can be found.
1.1691 ///
1.1692 - ///\param nm must be a bool (or convertible) node map. The
1.1693 - ///algorithm will stop when it reaches a node \c v with
1.1694 + /// \param nm must be a bool (or convertible) node map. The
1.1695 + /// algorithm will stop when it reaches a node \c v with
1.1696 /// <tt>nm[v]</tt> true.
1.1697 ///
1.1698 - ///\return The reached node \c v with <tt>nm[v]</tt> true or
1.1699 - ///\c INVALID if no such node was found.
1.1700 + /// \return The reached node \c v with <tt>nm[v]</tt> true or
1.1701 + /// \c INVALID if no such node was found.
1.1702 + ///
1.1703 + /// \pre init() must be called and at least one root node should be
1.1704 + /// added with addSource() before using this function.
1.1705 + ///
1.1706 + /// \note <tt>b.start(nm)</tt> is just a shortcut of the following code.
1.1707 + /// \code
1.1708 + /// Node rnode = INVALID;
1.1709 + /// while ( !b.emptyQueue() && rnode == INVALID ) {
1.1710 + /// b.processNextNode(nm, rnode);
1.1711 + /// }
1.1712 + /// return rnode;
1.1713 + /// \endcode
1.1714 template <typename NM>
1.1715 Node start(const NM &nm) {
1.1716 Node rnode = INVALID;
1.1717 @@ -1529,10 +1636,16 @@
1.1718 return rnode;
1.1719 }
1.1720
1.1721 - /// \brief Runs %BFSVisit algorithm from node \c s.
1.1722 + /// \brief Runs the algorithm from the given node.
1.1723 ///
1.1724 - /// This method runs the %BFS algorithm from a root node \c s.
1.1725 - /// \note b.run(s) is just a shortcut of the following code.
1.1726 + /// This method runs the %BFS algorithm from node \c s
1.1727 + /// in order to compute the shortest path to each node.
1.1728 + ///
1.1729 + /// The algorithm computes
1.1730 + /// - the shortest path tree,
1.1731 + /// - the distance of each node from the root.
1.1732 + ///
1.1733 + /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
1.1734 ///\code
1.1735 /// b.init();
1.1736 /// b.addSource(s);
1.1737 @@ -1544,19 +1657,21 @@
1.1738 start();
1.1739 }
1.1740
1.1741 - /// \brief Runs %BFSVisit algorithm to visit all nodes in the digraph.
1.1742 + /// \brief Runs the algorithm to visit all nodes in the digraph.
1.1743 ///
1.1744 /// This method runs the %BFS algorithm in order to
1.1745 - /// compute the %BFS path to each node. The algorithm computes
1.1746 - /// - The %BFS tree.
1.1747 - /// - The distance of each node from the root in the %BFS tree.
1.1748 + /// compute the shortest path to each node.
1.1749 ///
1.1750 - ///\note b.run() is just a shortcut of the following code.
1.1751 + /// The algorithm computes
1.1752 + /// - the shortest path tree (forest),
1.1753 + /// - the distance of each node from the root(s).
1.1754 + ///
1.1755 + /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
1.1756 ///\code
1.1757 /// b.init();
1.1758 - /// for (NodeIt it(digraph); it != INVALID; ++it) {
1.1759 - /// if (!b.reached(it)) {
1.1760 - /// b.addSource(it);
1.1761 + /// for (NodeIt n(gr); n != INVALID; ++n) {
1.1762 + /// if (!b.reached(n)) {
1.1763 + /// b.addSource(n);
1.1764 /// b.start();
1.1765 /// }
1.1766 /// }
1.1767 @@ -1570,27 +1685,28 @@
1.1768 }
1.1769 }
1.1770 }
1.1771 +
1.1772 ///@}
1.1773
1.1774 /// \name Query Functions
1.1775 /// The result of the %BFS algorithm can be obtained using these
1.1776 /// functions.\n
1.1777 - /// Before the use of these functions,
1.1778 - /// either run() or start() must be called.
1.1779 + /// Either \ref lemon::BfsVisit::run() "run()" or
1.1780 + /// \ref lemon::BfsVisit::start() "start()" must be called before
1.1781 + /// using them.
1.1782 ///@{
1.1783
1.1784 - /// \brief Checks if a node is reachable from the root.
1.1785 + /// \brief Checks if a node is reachable from the root(s).
1.1786 ///
1.1787 /// Returns \c true if \c v is reachable from the root(s).
1.1788 - /// \warning The source nodes are inditated as unreachable.
1.1789 /// \pre Either \ref run() or \ref start()
1.1790 /// must be called before using this function.
1.1791 - ///
1.1792 bool reached(Node v) { return (*_reached)[v]; }
1.1793 +
1.1794 ///@}
1.1795 +
1.1796 };
1.1797
1.1798 } //END OF NAMESPACE LEMON
1.1799
1.1800 #endif
1.1801 -