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 -
2.1 --- a/lemon/dfs.h Mon Jul 14 15:40:24 2008 +0100
2.2 +++ b/lemon/dfs.h Sun Aug 03 13:34:57 2008 +0200
2.3 @@ -21,20 +21,18 @@
2.4
2.5 ///\ingroup search
2.6 ///\file
2.7 -///\brief Dfs algorithm.
2.8 +///\brief DFS algorithm.
2.9
2.10 #include <lemon/list_graph.h>
2.11 #include <lemon/graph_utils.h>
2.12 #include <lemon/bits/path_dump.h>
2.13 #include <lemon/bits/invalid.h>
2.14 #include <lemon/error.h>
2.15 +#include <lemon/assert.h>
2.16 #include <lemon/maps.h>
2.17
2.18 -#include <lemon/concept_check.h>
2.19 -
2.20 namespace lemon {
2.21
2.22 -
2.23 ///Default traits class of Dfs class.
2.24
2.25 ///Default traits class of Dfs class.
2.26 @@ -42,74 +40,75 @@
2.27 template<class GR>
2.28 struct DfsDefaultTraits
2.29 {
2.30 - ///The digraph type the algorithm runs on.
2.31 + ///The type of the digraph the algorithm runs on.
2.32 typedef GR Digraph;
2.33 - ///\brief The type of the map that stores the last
2.34 +
2.35 + ///\brief The type of the map that stores the predecessor
2.36 ///arcs of the %DFS paths.
2.37 ///
2.38 - ///The type of the map that stores the last
2.39 + ///The type of the map that stores the predecessor
2.40 ///arcs of the %DFS paths.
2.41 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
2.42 - ///
2.43 - typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
2.44 - ///Instantiates a PredMap.
2.45 + typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
2.46 + ///Instantiates a \ref PredMap.
2.47
2.48 ///This function instantiates a \ref PredMap.
2.49 - ///\param G is the digraph, to which we would like to define the PredMap.
2.50 + ///\param g is the digraph, to which we would like to define the
2.51 + ///\ref PredMap.
2.52 ///\todo The digraph alone may be insufficient to initialize
2.53 - static PredMap *createPredMap(const GR &G)
2.54 + static PredMap *createPredMap(const Digraph &g)
2.55 {
2.56 - return new PredMap(G);
2.57 + return new PredMap(g);
2.58 }
2.59
2.60 ///The type of the map that indicates which nodes are processed.
2.61
2.62 ///The type of the map that indicates which nodes are processed.
2.63 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
2.64 - ///\todo named parameter to set this type, function to read and write.
2.65 + ///By default it is a NullMap.
2.66 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
2.67 - ///Instantiates a ProcessedMap.
2.68 + ///Instantiates a \ref ProcessedMap.
2.69
2.70 ///This function instantiates a \ref ProcessedMap.
2.71 ///\param g is the digraph, to which
2.72 ///we would like to define the \ref ProcessedMap
2.73 #ifdef DOXYGEN
2.74 - static ProcessedMap *createProcessedMap(const GR &g)
2.75 + static ProcessedMap *createProcessedMap(const Digraph &g)
2.76 #else
2.77 - static ProcessedMap *createProcessedMap(const GR &)
2.78 + static ProcessedMap *createProcessedMap(const Digraph &)
2.79 #endif
2.80 {
2.81 return new ProcessedMap();
2.82 }
2.83 +
2.84 ///The type of the map that indicates which nodes are reached.
2.85
2.86 ///The type of the map that indicates which nodes are reached.
2.87 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
2.88 - ///\todo named parameter to set this type, function to read and write.
2.89 + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
2.90 typedef typename Digraph::template NodeMap<bool> ReachedMap;
2.91 - ///Instantiates a ReachedMap.
2.92 + ///Instantiates a \ref ReachedMap.
2.93
2.94 ///This function instantiates a \ref ReachedMap.
2.95 - ///\param G is the digraph, to which
2.96 + ///\param g is the digraph, to which
2.97 ///we would like to define the \ref ReachedMap.
2.98 - static ReachedMap *createReachedMap(const GR &G)
2.99 + static ReachedMap *createReachedMap(const Digraph &g)
2.100 {
2.101 - return new ReachedMap(G);
2.102 + return new ReachedMap(g);
2.103 }
2.104 - ///The type of the map that stores the dists of the nodes.
2.105
2.106 - ///The type of the map that stores the dists of the nodes.
2.107 + ///The type of the map that stores the distances of the nodes.
2.108 +
2.109 + ///The type of the map that stores the distances of the nodes.
2.110 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
2.111 - ///
2.112 typedef typename Digraph::template NodeMap<int> DistMap;
2.113 - ///Instantiates a DistMap.
2.114 + ///Instantiates a \ref DistMap.
2.115
2.116 ///This function instantiates a \ref DistMap.
2.117 - ///\param G is the digraph, to which we would like to define
2.118 - ///the \ref DistMap
2.119 - static DistMap *createDistMap(const GR &G)
2.120 + ///\param g is the digraph, to which we would like to define the
2.121 + ///\ref DistMap.
2.122 + static DistMap *createDistMap(const Digraph &g)
2.123 {
2.124 - return new DistMap(G);
2.125 + return new DistMap(g);
2.126 }
2.127 };
2.128
2.129 @@ -118,9 +117,13 @@
2.130 ///\ingroup search
2.131 ///This class provides an efficient implementation of the %DFS algorithm.
2.132 ///
2.133 - ///\tparam GR The digraph type the algorithm runs on. The default value is
2.134 - ///\ref ListDigraph. The value of GR is not used directly by Dfs, it
2.135 - ///is only passed to \ref DfsDefaultTraits.
2.136 + ///There is also a \ref dfs() "function type interface" for the DFS
2.137 + ///algorithm, which is convenient in the simplier cases and it can be
2.138 + ///used easier.
2.139 + ///
2.140 + ///\tparam GR The type of the digraph the algorithm runs on.
2.141 + ///The default value is \ref ListDigraph. The value of GR is not used
2.142 + ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
2.143 ///\tparam TR Traits class to set various data types used by the algorithm.
2.144 ///The default traits class is
2.145 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
2.146 @@ -135,12 +138,10 @@
2.147 #endif
2.148 class Dfs {
2.149 public:
2.150 - /**
2.151 - * \brief \ref Exception for uninitialized parameters.
2.152 - *
2.153 - * This error represents problems in the initialization
2.154 - * of the parameters of the algorithms.
2.155 - */
2.156 + ///\ref Exception for uninitialized parameters.
2.157 +
2.158 + ///This error represents problems in the initialization of the
2.159 + ///parameters of the algorithm.
2.160 class UninitializedParameter : public lemon::UninitializedParameter {
2.161 public:
2.162 virtual const char* what() const throw() {
2.163 @@ -148,52 +149,54 @@
2.164 }
2.165 };
2.166
2.167 + ///The type of the digraph the algorithm runs on.
2.168 + typedef typename TR::Digraph Digraph;
2.169 +
2.170 + ///\brief The type of the map that stores the predecessor arcs of the
2.171 + ///DFS paths.
2.172 + typedef typename TR::PredMap PredMap;
2.173 + ///The type of the map that stores the distances of the nodes.
2.174 + typedef typename TR::DistMap DistMap;
2.175 + ///The type of the map that indicates which nodes are reached.
2.176 + typedef typename TR::ReachedMap ReachedMap;
2.177 + ///The type of the map that indicates which nodes are processed.
2.178 + typedef typename TR::ProcessedMap ProcessedMap;
2.179 + ///The type of the paths.
2.180 + typedef PredMapPath<Digraph, PredMap> Path;
2.181 +
2.182 + ///The traits class.
2.183 typedef TR Traits;
2.184 - ///The type of the underlying digraph.
2.185 - typedef typename TR::Digraph Digraph;
2.186 - ///\e
2.187 +
2.188 + private:
2.189 +
2.190 typedef typename Digraph::Node Node;
2.191 - ///\e
2.192 typedef typename Digraph::NodeIt NodeIt;
2.193 - ///\e
2.194 typedef typename Digraph::Arc Arc;
2.195 - ///\e
2.196 typedef typename Digraph::OutArcIt OutArcIt;
2.197
2.198 - ///\brief The type of the map that stores the last
2.199 - ///arcs of the %DFS paths.
2.200 - typedef typename TR::PredMap PredMap;
2.201 - ///The type of the map indicating which nodes are reached.
2.202 - typedef typename TR::ReachedMap ReachedMap;
2.203 - ///The type of the map indicating which nodes are processed.
2.204 - typedef typename TR::ProcessedMap ProcessedMap;
2.205 - ///The type of the map that stores the dists of the nodes.
2.206 - typedef typename TR::DistMap DistMap;
2.207 - private:
2.208 - /// Pointer to the underlying digraph.
2.209 + //Pointer to the underlying digraph.
2.210 const Digraph *G;
2.211 - ///Pointer to the map of predecessors arcs.
2.212 + //Pointer to the map of predecessor arcs.
2.213 PredMap *_pred;
2.214 - ///Indicates if \ref _pred is locally allocated (\c true) or not.
2.215 + //Indicates if _pred is locally allocated (true) or not.
2.216 bool local_pred;
2.217 - ///Pointer to the map of distances.
2.218 + //Pointer to the map of distances.
2.219 DistMap *_dist;
2.220 - ///Indicates if \ref _dist is locally allocated (\c true) or not.
2.221 + //Indicates if _dist is locally allocated (true) or not.
2.222 bool local_dist;
2.223 - ///Pointer to the map of reached status of the nodes.
2.224 + //Pointer to the map of reached status of the nodes.
2.225 ReachedMap *_reached;
2.226 - ///Indicates if \ref _reached is locally allocated (\c true) or not.
2.227 + //Indicates if _reached is locally allocated (true) or not.
2.228 bool local_reached;
2.229 - ///Pointer to the map of processed status of the nodes.
2.230 + //Pointer to the map of processed status of the nodes.
2.231 ProcessedMap *_processed;
2.232 - ///Indicates if \ref _processed is locally allocated (\c true) or not.
2.233 + //Indicates if _processed is locally allocated (true) or not.
2.234 bool local_processed;
2.235
2.236 std::vector<typename Digraph::OutArcIt> _stack;
2.237 int _stack_head;
2.238
2.239 ///Creates the maps if necessary.
2.240 -
2.241 ///\todo Better memory allocation (instead of new).
2.242 void create_maps()
2.243 {
2.244 @@ -230,22 +233,21 @@
2.245 template <class T>
2.246 struct DefPredMapTraits : public Traits {
2.247 typedef T PredMap;
2.248 - static PredMap *createPredMap(const Digraph &G)
2.249 + static PredMap *createPredMap(const Digraph &)
2.250 {
2.251 throw UninitializedParameter();
2.252 }
2.253 };
2.254 ///\brief \ref named-templ-param "Named parameter" for setting
2.255 - ///PredMap type
2.256 + ///\ref PredMap type.
2.257 ///
2.258 - ///\ref named-templ-param "Named parameter" for setting PredMap type
2.259 - ///
2.260 + ///\ref named-templ-param "Named parameter" for setting
2.261 + ///\ref PredMap type.
2.262 template <class T>
2.263 struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
2.264 typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
2.265 };
2.266
2.267 -
2.268 template <class T>
2.269 struct DefDistMapTraits : public Traits {
2.270 typedef T DistMap;
2.271 @@ -255,12 +257,12 @@
2.272 }
2.273 };
2.274 ///\brief \ref named-templ-param "Named parameter" for setting
2.275 - ///DistMap type
2.276 + ///\ref DistMap type.
2.277 ///
2.278 - ///\ref named-templ-param "Named parameter" for setting DistMap
2.279 - ///type
2.280 + ///\ref named-templ-param "Named parameter" for setting
2.281 + ///\ref DistMap type.
2.282 template <class T>
2.283 - struct DefDistMap {
2.284 + struct DefDistMap : public Dfs< Digraph, DefDistMapTraits<T> > {
2.285 typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
2.286 };
2.287
2.288 @@ -273,10 +275,10 @@
2.289 }
2.290 };
2.291 ///\brief \ref named-templ-param "Named parameter" for setting
2.292 - ///ReachedMap type
2.293 + ///\ref ReachedMap type.
2.294 ///
2.295 - ///\ref named-templ-param "Named parameter" for setting ReachedMap type
2.296 - ///
2.297 + ///\ref named-templ-param "Named parameter" for setting
2.298 + ///\ref ReachedMap type.
2.299 template <class T>
2.300 struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > {
2.301 typedef Dfs< Digraph, DefReachedMapTraits<T> > Create;
2.302 @@ -291,10 +293,10 @@
2.303 }
2.304 };
2.305 ///\brief \ref named-templ-param "Named parameter" for setting
2.306 - ///ProcessedMap type
2.307 + ///\ref ProcessedMap type.
2.308 ///
2.309 - ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
2.310 - ///
2.311 + ///\ref named-templ-param "Named parameter" for setting
2.312 + ///\ref ProcessedMap type.
2.313 template <class T>
2.314 struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
2.315 typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create;
2.316 @@ -302,19 +304,19 @@
2.317
2.318 struct DefDigraphProcessedMapTraits : public Traits {
2.319 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
2.320 - static ProcessedMap *createProcessedMap(const Digraph &G)
2.321 + static ProcessedMap *createProcessedMap(const Digraph &g)
2.322 {
2.323 - return new ProcessedMap(G);
2.324 + return new ProcessedMap(g);
2.325 }
2.326 };
2.327 - ///\brief \ref named-templ-param "Named parameter"
2.328 - ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
2.329 + ///\brief \ref named-templ-param "Named parameter" for setting
2.330 + ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
2.331 ///
2.332 - ///\ref named-templ-param "Named parameter"
2.333 - ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
2.334 - ///If you don't set it explicitely, it will be automatically allocated.
2.335 + ///\ref named-templ-param "Named parameter" for setting
2.336 + ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
2.337 + ///If you don't set it explicitly, it will be automatically allocated.
2.338 template <class T>
2.339 - class DefProcessedMapToBeDefaultMap :
2.340 + struct DefProcessedMapToBeDefaultMap :
2.341 public Dfs< Digraph, DefDigraphProcessedMapTraits> {
2.342 typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
2.343 };
2.344 @@ -325,10 +327,10 @@
2.345
2.346 ///Constructor.
2.347
2.348 - ///\param _G the digraph the algorithm will run on.
2.349 - ///
2.350 - Dfs(const Digraph& _G) :
2.351 - G(&_G),
2.352 + ///Constructor.
2.353 + ///\param g The digraph the algorithm runs on.
2.354 + Dfs(const Digraph &g) :
2.355 + G(&g),
2.356 _pred(NULL), local_pred(false),
2.357 _dist(NULL), local_dist(false),
2.358 _reached(NULL), local_reached(false),
2.359 @@ -344,11 +346,11 @@
2.360 if(local_processed) delete _processed;
2.361 }
2.362
2.363 - ///Sets the map storing the predecessor arcs.
2.364 + ///Sets the map that stores the predecessor arcs.
2.365
2.366 - ///Sets the map storing the predecessor arcs.
2.367 + ///Sets the map that stores the predecessor arcs.
2.368 ///If you don't use this function before calling \ref run(),
2.369 - ///it will allocate one. The destuctor deallocates this
2.370 + ///it will allocate one. The destructor deallocates this
2.371 ///automatically allocated map, of course.
2.372 ///\return <tt> (*this) </tt>
2.373 Dfs &predMap(PredMap &m)
2.374 @@ -361,11 +363,46 @@
2.375 return *this;
2.376 }
2.377
2.378 - ///Sets the map storing the distances calculated by the algorithm.
2.379 + ///Sets the map that indicates which nodes are reached.
2.380
2.381 - ///Sets the map storing the distances calculated by the algorithm.
2.382 + ///Sets the map that indicates which nodes are reached.
2.383 ///If you don't use this function before calling \ref run(),
2.384 - ///it will allocate one. The destuctor deallocates this
2.385 + ///it will allocate one. The destructor deallocates this
2.386 + ///automatically allocated map, of course.
2.387 + ///\return <tt> (*this) </tt>
2.388 + Dfs &reachedMap(ReachedMap &m)
2.389 + {
2.390 + if(local_reached) {
2.391 + delete _reached;
2.392 + local_reached=false;
2.393 + }
2.394 + _reached = &m;
2.395 + return *this;
2.396 + }
2.397 +
2.398 + ///Sets the map that indicates which nodes are processed.
2.399 +
2.400 + ///Sets the map that indicates which nodes are processed.
2.401 + ///If you don't use this function before calling \ref run(),
2.402 + ///it will allocate one. The destructor deallocates this
2.403 + ///automatically allocated map, of course.
2.404 + ///\return <tt> (*this) </tt>
2.405 + Dfs &processedMap(ProcessedMap &m)
2.406 + {
2.407 + if(local_processed) {
2.408 + delete _processed;
2.409 + local_processed=false;
2.410 + }
2.411 + _processed = &m;
2.412 + return *this;
2.413 + }
2.414 +
2.415 + ///Sets the map that stores the distances of the nodes.
2.416 +
2.417 + ///Sets the map that stores the distances of the nodes calculated by
2.418 + ///the algorithm.
2.419 + ///If you don't use this function before calling \ref run(),
2.420 + ///it will allocate one. The destructor deallocates this
2.421 ///automatically allocated map, of course.
2.422 ///\return <tt> (*this) </tt>
2.423 Dfs &distMap(DistMap &m)
2.424 @@ -378,50 +415,17 @@
2.425 return *this;
2.426 }
2.427
2.428 - ///Sets the map indicating if a node is reached.
2.429 + public:
2.430
2.431 - ///Sets the map indicating if a node is reached.
2.432 - ///If you don't use this function before calling \ref run(),
2.433 - ///it will allocate one. The destuctor deallocates this
2.434 - ///automatically allocated map, of course.
2.435 - ///\return <tt> (*this) </tt>
2.436 - Dfs &reachedMap(ReachedMap &m)
2.437 - {
2.438 - if(local_reached) {
2.439 - delete _reached;
2.440 - local_reached=false;
2.441 - }
2.442 - _reached = &m;
2.443 - return *this;
2.444 - }
2.445 -
2.446 - ///Sets the map indicating if a node is processed.
2.447 -
2.448 - ///Sets the map indicating if a node is processed.
2.449 - ///If you don't use this function before calling \ref run(),
2.450 - ///it will allocate one. The destuctor deallocates this
2.451 - ///automatically allocated map, of course.
2.452 - ///\return <tt> (*this) </tt>
2.453 - Dfs &processedMap(ProcessedMap &m)
2.454 - {
2.455 - if(local_processed) {
2.456 - delete _processed;
2.457 - local_processed=false;
2.458 - }
2.459 - _processed = &m;
2.460 - return *this;
2.461 - }
2.462 -
2.463 - public:
2.464 ///\name Execution control
2.465 ///The simplest way to execute the algorithm is to use
2.466 - ///one of the member functions called \c run(...).
2.467 + ///one of the member functions called \ref lemon::Dfs::run() "run()".
2.468 ///\n
2.469 - ///If you need more control on the execution,
2.470 - ///first you must call \ref init(), then you can add a source node
2.471 - ///with \ref addSource().
2.472 - ///Finally \ref start() will perform the actual path
2.473 - ///computation.
2.474 + ///If you need more control on the execution, first you must call
2.475 + ///\ref lemon::Dfs::init() "init()", then you can add a source node
2.476 + ///with \ref lemon::Dfs::addSource() "addSource()".
2.477 + ///Finally \ref lemon::Dfs::start() "start()" will perform the
2.478 + ///actual path computation.
2.479
2.480 ///@{
2.481
2.482 @@ -436,7 +440,6 @@
2.483 _stack_head=-1;
2.484 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
2.485 _pred->set(u,INVALID);
2.486 - // _predNode->set(u,INVALID);
2.487 _reached->set(u,false);
2.488 _processed->set(u,false);
2.489 }
2.490 @@ -446,10 +449,14 @@
2.491
2.492 ///Adds a new source node to the set of nodes to be processed.
2.493 ///
2.494 - ///\warning dists are wrong (or at least strange)
2.495 - ///in case of multiple sources.
2.496 + ///\pre The stack must be empty. (Otherwise the algorithm gives
2.497 + ///false results.)
2.498 + ///
2.499 + ///\warning Distances will be wrong (or at least strange) in case of
2.500 + ///multiple sources.
2.501 void addSource(Node s)
2.502 {
2.503 + LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
2.504 if(!(*_reached)[s])
2.505 {
2.506 _reached->set(s,true);
2.507 @@ -472,7 +479,7 @@
2.508 ///
2.509 ///\return The processed arc.
2.510 ///
2.511 - ///\pre The stack must not be empty!
2.512 + ///\pre The stack must not be empty.
2.513 Arc processNextArc()
2.514 {
2.515 Node m;
2.516 @@ -498,61 +505,68 @@
2.517 }
2.518 return e;
2.519 }
2.520 +
2.521 ///Next arc to be processed.
2.522
2.523 ///Next arc to be processed.
2.524 ///
2.525 - ///\return The next arc to be processed or INVALID if the stack is
2.526 - /// empty.
2.527 - OutArcIt nextArc()
2.528 + ///\return The next arc to be processed or \c INVALID if the stack
2.529 + ///is empty.
2.530 + OutArcIt nextArc() const
2.531 {
2.532 return _stack_head>=0?_stack[_stack_head]:INVALID;
2.533 }
2.534
2.535 ///\brief Returns \c false if there are nodes
2.536 - ///to be processed in the queue
2.537 + ///to be processed.
2.538 ///
2.539 ///Returns \c false if there are nodes
2.540 - ///to be processed in the queue
2.541 - bool emptyQueue() { return _stack_head<0; }
2.542 + ///to be processed in the queue (stack).
2.543 + bool emptyQueue() const { return _stack_head<0; }
2.544 +
2.545 ///Returns the number of the nodes to be processed.
2.546
2.547 - ///Returns the number of the nodes to be processed in the queue.
2.548 - int queueSize() { return _stack_head+1; }
2.549 + ///Returns the number of the nodes to be processed in the queue (stack).
2.550 + int queueSize() const { return _stack_head+1; }
2.551
2.552 ///Executes the algorithm.
2.553
2.554 ///Executes the algorithm.
2.555 ///
2.556 - ///\pre init() must be called and at least one node should be added
2.557 - ///with addSource() before using this function.
2.558 + ///This method runs the %DFS algorithm from the root node
2.559 + ///in order to compute the DFS path to each node.
2.560 ///
2.561 - ///This method runs the %DFS algorithm from the root node(s)
2.562 - ///in order to
2.563 - ///compute the
2.564 - ///%DFS path to each node. The algorithm computes
2.565 - ///- The %DFS tree.
2.566 - ///- The distance of each node from the root(s) in the %DFS tree.
2.567 + /// The algorithm computes
2.568 + ///- the %DFS tree,
2.569 + ///- the distance of each node from the root in the %DFS tree.
2.570 ///
2.571 + ///\pre init() must be called and a root node should be
2.572 + ///added with addSource() before using this function.
2.573 + ///
2.574 + ///\note <tt>d.start()</tt> is just a shortcut of the following code.
2.575 + ///\code
2.576 + /// while ( !d.emptyQueue() ) {
2.577 + /// d.processNextArc();
2.578 + /// }
2.579 + ///\endcode
2.580 void start()
2.581 {
2.582 while ( !emptyQueue() ) processNextArc();
2.583 }
2.584
2.585 - ///Executes the algorithm until \c dest is reached.
2.586 + ///Executes the algorithm until the given target node is reached.
2.587
2.588 - ///Executes the algorithm until \c dest is reached.
2.589 + ///Executes the algorithm until the given target node is reached.
2.590 ///
2.591 - ///\pre init() must be called and at least one node should be added
2.592 - ///with addSource() before using this function.
2.593 + ///This method runs the %DFS algorithm from the root node
2.594 + ///in order to compute the DFS path to \c dest.
2.595 ///
2.596 - ///This method runs the %DFS algorithm from the root node(s)
2.597 - ///in order to
2.598 - ///compute the
2.599 - ///%DFS path to \c dest. The algorithm computes
2.600 - ///- The %DFS path to \c dest.
2.601 - ///- The distance of \c dest from the root(s) in the %DFS tree.
2.602 + ///The algorithm computes
2.603 + ///- the %DFS path to \c dest,
2.604 + ///- the distance of \c dest from the root in the %DFS tree.
2.605 ///
2.606 + ///\pre init() must be called and a root node should be
2.607 + ///added with addSource() before using this function.
2.608 void start(Node dest)
2.609 {
2.610 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
2.611 @@ -563,39 +577,86 @@
2.612
2.613 ///Executes the algorithm until a condition is met.
2.614 ///
2.615 - ///\pre init() must be called and at least one node should be added
2.616 - ///with addSource() before using this function.
2.617 + ///This method runs the %DFS algorithm from the root node
2.618 + ///until an arc \c a with <tt>am[a]</tt> true is found.
2.619 ///
2.620 - ///\param em must be a bool (or convertible) arc map. The algorithm
2.621 - ///will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
2.622 + ///\param am A \c bool (or convertible) arc map. The algorithm
2.623 + ///will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
2.624 ///
2.625 - ///\return The reached arc \c e with <tt>em[e]</tt> true or
2.626 + ///\return The reached arc \c a with <tt>am[a]</tt> true or
2.627 ///\c INVALID if no such arc was found.
2.628 ///
2.629 - ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
2.630 + ///\pre init() must be called and a root node should be
2.631 + ///added with addSource() before using this function.
2.632 + ///
2.633 + ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
2.634 ///not a node map.
2.635 - template<class EM>
2.636 - Arc start(const EM &em)
2.637 + template<class ArcBoolMap>
2.638 + Arc start(const ArcBoolMap &am)
2.639 {
2.640 - while ( !emptyQueue() && !em[_stack[_stack_head]] )
2.641 + while ( !emptyQueue() && !am[_stack[_stack_head]] )
2.642 processNextArc();
2.643 return emptyQueue() ? INVALID : _stack[_stack_head];
2.644 }
2.645
2.646 - ///Runs %DFS algorithm to visit all nodes in the digraph.
2.647 + ///Runs the algorithm from the given node.
2.648
2.649 - ///This method runs the %DFS algorithm in order to
2.650 - ///compute the
2.651 - ///%DFS path to each node. The algorithm computes
2.652 - ///- The %DFS tree.
2.653 - ///- The distance of each node from the root in the %DFS tree.
2.654 + ///This method runs the %DFS algorithm from node \c s
2.655 + ///in order to compute the DFS path to each node.
2.656 ///
2.657 - ///\note d.run() is just a shortcut of the following code.
2.658 + ///The algorithm computes
2.659 + ///- the %DFS tree,
2.660 + ///- the distance of each node from the root in the %DFS tree.
2.661 + ///
2.662 + ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
2.663 ///\code
2.664 /// d.init();
2.665 - /// for (NodeIt it(digraph); it != INVALID; ++it) {
2.666 - /// if (!d.reached(it)) {
2.667 - /// d.addSource(it);
2.668 + /// d.addSource(s);
2.669 + /// d.start();
2.670 + ///\endcode
2.671 + void run(Node s) {
2.672 + init();
2.673 + addSource(s);
2.674 + start();
2.675 + }
2.676 +
2.677 + ///Finds the %DFS path between \c s and \c t.
2.678 +
2.679 + ///This method runs the %DFS algorithm from node \c s
2.680 + ///in order to compute the DFS path to \c t.
2.681 + ///
2.682 + ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
2.683 + ///if \c t is reachable form \c s, \c 0 otherwise.
2.684 + ///
2.685 + ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
2.686 + ///just a shortcut of the following code.
2.687 + ///\code
2.688 + /// d.init();
2.689 + /// d.addSource(s);
2.690 + /// d.start(t);
2.691 + ///\endcode
2.692 + int run(Node s,Node t) {
2.693 + init();
2.694 + addSource(s);
2.695 + start(t);
2.696 + return reached(t)?_stack_head+1:0;
2.697 + }
2.698 +
2.699 + ///Runs the algorithm to visit all nodes in the digraph.
2.700 +
2.701 + ///This method runs the %DFS algorithm in order to compute the
2.702 + ///%DFS path to each node.
2.703 + ///
2.704 + ///The algorithm computes
2.705 + ///- the %DFS tree,
2.706 + ///- the distance of each node from the root in the %DFS tree.
2.707 + ///
2.708 + ///\note <tt>d.run()</tt> is just a shortcut of the following code.
2.709 + ///\code
2.710 + /// d.init();
2.711 + /// for (NodeIt n(digraph); n != INVALID; ++n) {
2.712 + /// if (!d.reached(n)) {
2.713 + /// d.addSource(n);
2.714 /// d.start();
2.715 /// }
2.716 /// }
2.717 @@ -610,157 +671,124 @@
2.718 }
2.719 }
2.720
2.721 - ///Runs %DFS algorithm from node \c s.
2.722 -
2.723 - ///This method runs the %DFS algorithm from a root node \c s
2.724 - ///in order to
2.725 - ///compute the
2.726 - ///%DFS path to each node. The algorithm computes
2.727 - ///- The %DFS tree.
2.728 - ///- The distance of each node from the root in the %DFS tree.
2.729 - ///
2.730 - ///\note d.run(s) is just a shortcut of the following code.
2.731 - ///\code
2.732 - /// d.init();
2.733 - /// d.addSource(s);
2.734 - /// d.start();
2.735 - ///\endcode
2.736 - void run(Node s) {
2.737 - init();
2.738 - addSource(s);
2.739 - start();
2.740 - }
2.741 -
2.742 - ///Finds the %DFS path between \c s and \c t.
2.743 -
2.744 - ///Finds the %DFS path between \c s and \c t.
2.745 - ///
2.746 - ///\return The length of the %DFS s---t path if there exists one,
2.747 - ///0 otherwise.
2.748 - ///\note Apart from the return value, d.run(s,t) is
2.749 - ///just a shortcut of the following code.
2.750 - ///\code
2.751 - /// d.init();
2.752 - /// d.addSource(s);
2.753 - /// d.start(t);
2.754 - ///\endcode
2.755 - int run(Node s,Node t) {
2.756 - init();
2.757 - addSource(s);
2.758 - start(t);
2.759 - return reached(t)?_stack_head+1:0;
2.760 - }
2.761 -
2.762 ///@}
2.763
2.764 ///\name Query Functions
2.765 ///The result of the %DFS algorithm can be obtained using these
2.766 ///functions.\n
2.767 - ///Before the use of these functions,
2.768 - ///either run() or start() must be called.
2.769 + ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
2.770 + ///"start()" must be called before using them.
2.771
2.772 ///@{
2.773
2.774 - typedef PredMapPath<Digraph, PredMap> Path;
2.775 + ///The DFS path to a node.
2.776
2.777 - ///Gives back the shortest path.
2.778 + ///Returns the DFS path to a node.
2.779 + ///
2.780 + ///\warning \c t should be reachable from the root.
2.781 + ///
2.782 + ///\pre Either \ref run() or \ref start() must be called before
2.783 + ///using this function.
2.784 + Path path(Node t) const { return Path(*G, *_pred, t); }
2.785
2.786 - ///Gives back the shortest path.
2.787 - ///\pre The \c t should be reachable from the source.
2.788 - Path path(Node t)
2.789 - {
2.790 - return Path(*G, *_pred, t);
2.791 - }
2.792 + ///The distance of a node from the root.
2.793
2.794 - ///The distance of a node from the root(s).
2.795 -
2.796 - ///Returns the distance of a node from the root(s).
2.797 - ///\pre \ref run() must be called before using this function.
2.798 - ///\warning If node \c v is unreachable from the root(s) then the return
2.799 - ///value of this funcion is undefined.
2.800 + ///Returns the distance of a node from the root.
2.801 + ///
2.802 + ///\warning If node \c v is not reachable from the root, then
2.803 + ///the return value of this function is undefined.
2.804 + ///
2.805 + ///\pre Either \ref run() or \ref start() must be called before
2.806 + ///using this function.
2.807 int dist(Node v) const { return (*_dist)[v]; }
2.808
2.809 - ///Returns the 'previous arc' of the %DFS tree.
2.810 + ///Returns the 'previous arc' of the %DFS tree for a node.
2.811
2.812 - ///For a node \c v it returns the 'previous arc'
2.813 - ///of the %DFS path,
2.814 - ///i.e. it returns the last arc of a %DFS path from the root(s) to \c
2.815 - ///v. It is \ref INVALID
2.816 - ///if \c v is unreachable from the root(s) or \c v is a root. The
2.817 - ///%DFS tree used here is equal to the %DFS tree used in
2.818 + ///This function returns the 'previous arc' of the %DFS tree for the
2.819 + ///node \c v, i.e. it returns the last arc of a %DFS path from the
2.820 + ///root to \c v. It is \c INVALID
2.821 + ///if \c v is not reachable from the root(s) or if \c v is a root.
2.822 + ///
2.823 + ///The %DFS tree used here is equal to the %DFS tree used in
2.824 ///\ref predNode().
2.825 + ///
2.826 ///\pre Either \ref run() or \ref start() must be called before using
2.827 ///this function.
2.828 Arc predArc(Node v) const { return (*_pred)[v];}
2.829
2.830 ///Returns the 'previous node' of the %DFS tree.
2.831
2.832 - ///For a node \c v it returns the 'previous node'
2.833 - ///of the %DFS tree,
2.834 - ///i.e. it returns the last but one node from a %DFS path from the
2.835 - ///root(s) to \c v.
2.836 - ///It is INVALID if \c v is unreachable from the root(s) or
2.837 - ///if \c v itself a root.
2.838 - ///The %DFS tree used here is equal to the %DFS
2.839 - ///tree used in \ref predArc().
2.840 + ///This function returns the 'previous node' of the %DFS
2.841 + ///tree for the node \c v, i.e. it returns the last but one node
2.842 + ///from a %DFS path from the root to \c v. It is \c INVALID
2.843 + ///if \c v is not reachable from the root(s) or if \c v is a root.
2.844 + ///
2.845 + ///The %DFS tree used here is equal to the %DFS tree used in
2.846 + ///\ref predArc().
2.847 + ///
2.848 ///\pre Either \ref run() or \ref start() must be called before
2.849 ///using this function.
2.850 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
2.851 G->source((*_pred)[v]); }
2.852
2.853 - ///Returns a reference to the NodeMap of distances.
2.854 -
2.855 - ///Returns a reference to the NodeMap of distances.
2.856 - ///\pre Either \ref run() or \ref init() must
2.857 - ///be called before using this function.
2.858 + ///\brief Returns a const reference to the node map that stores the
2.859 + ///distances of the nodes.
2.860 + ///
2.861 + ///Returns a const reference to the node map that stores the
2.862 + ///distances of the nodes calculated by the algorithm.
2.863 + ///
2.864 + ///\pre Either \ref run() or \ref init()
2.865 + ///must be called before using this function.
2.866 const DistMap &distMap() const { return *_dist;}
2.867
2.868 - ///Returns a reference to the %DFS arc-tree map.
2.869 -
2.870 - ///Returns a reference to the NodeMap of the arcs of the
2.871 - ///%DFS tree.
2.872 + ///\brief Returns a const reference to the node map that stores the
2.873 + ///predecessor arcs.
2.874 + ///
2.875 + ///Returns a const reference to the node map that stores the predecessor
2.876 + ///arcs, which form the DFS tree.
2.877 + ///
2.878 ///\pre Either \ref run() or \ref init()
2.879 ///must be called before using this function.
2.880 const PredMap &predMap() const { return *_pred;}
2.881
2.882 - ///Checks if a node is reachable from the root.
2.883 + ///Checks if a node is reachable from the root(s).
2.884
2.885 ///Returns \c true if \c v is reachable from the root(s).
2.886 - ///\warning The source nodes are inditated as unreachable.
2.887 ///\pre Either \ref run() or \ref start()
2.888 ///must be called before using this function.
2.889 - ///
2.890 - bool reached(Node v) { return (*_reached)[v]; }
2.891 + bool reached(Node v) const { return (*_reached)[v]; }
2.892
2.893 ///@}
2.894 };
2.895
2.896 - ///Default traits class of Dfs function.
2.897 + ///Default traits class of dfs() function.
2.898
2.899 - ///Default traits class of Dfs function.
2.900 + ///Default traits class of dfs() function.
2.901 ///\tparam GR Digraph type.
2.902 template<class GR>
2.903 struct DfsWizardDefaultTraits
2.904 {
2.905 - ///The digraph type the algorithm runs on.
2.906 + ///The type of the digraph the algorithm runs on.
2.907 typedef GR Digraph;
2.908 - ///\brief The type of the map that stores the last
2.909 +
2.910 + ///\brief The type of the map that stores the predecessor
2.911 ///arcs of the %DFS paths.
2.912 ///
2.913 - ///The type of the map that stores the last
2.914 + ///The type of the map that stores the predecessor
2.915 ///arcs of the %DFS paths.
2.916 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
2.917 ///
2.918 - typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
2.919 - ///Instantiates a PredMap.
2.920 + typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
2.921 + ///Instantiates a \ref PredMap.
2.922
2.923 ///This function instantiates a \ref PredMap.
2.924 - ///\param g is the digraph, to which we would like to define the PredMap.
2.925 + ///\param g is the digraph, to which we would like to define the
2.926 + ///\ref PredMap.
2.927 ///\todo The digraph alone may be insufficient to initialize
2.928 #ifdef DOXYGEN
2.929 - static PredMap *createPredMap(const GR &g)
2.930 + static PredMap *createPredMap(const Digraph &g)
2.931 #else
2.932 - static PredMap *createPredMap(const GR &)
2.933 + static PredMap *createPredMap(const Digraph &)
2.934 #endif
2.935 {
2.936 return new PredMap();
2.937 @@ -770,63 +798,63 @@
2.938
2.939 ///The type of the map that indicates which nodes are processed.
2.940 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
2.941 - ///\todo named parameter to set this type, function to read and write.
2.942 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
2.943 - ///Instantiates a ProcessedMap.
2.944 + ///Instantiates a \ref ProcessedMap.
2.945
2.946 ///This function instantiates a \ref ProcessedMap.
2.947 ///\param g is the digraph, to which
2.948 - ///we would like to define the \ref ProcessedMap
2.949 + ///we would like to define the \ref ProcessedMap.
2.950 #ifdef DOXYGEN
2.951 - static ProcessedMap *createProcessedMap(const GR &g)
2.952 + static ProcessedMap *createProcessedMap(const Digraph &g)
2.953 #else
2.954 - static ProcessedMap *createProcessedMap(const GR &)
2.955 + static ProcessedMap *createProcessedMap(const Digraph &)
2.956 #endif
2.957 {
2.958 return new ProcessedMap();
2.959 }
2.960 +
2.961 ///The type of the map that indicates which nodes are reached.
2.962
2.963 ///The type of the map that indicates which nodes are reached.
2.964 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
2.965 - ///\todo named parameter to set this type, function to read and write.
2.966 + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
2.967 typedef typename Digraph::template NodeMap<bool> ReachedMap;
2.968 - ///Instantiates a ReachedMap.
2.969 + ///Instantiates a \ref ReachedMap.
2.970
2.971 ///This function instantiates a \ref ReachedMap.
2.972 - ///\param G is the digraph, to which
2.973 + ///\param g is the digraph, to which
2.974 ///we would like to define the \ref ReachedMap.
2.975 - static ReachedMap *createReachedMap(const GR &G)
2.976 + static ReachedMap *createReachedMap(const Digraph &g)
2.977 {
2.978 - return new ReachedMap(G);
2.979 + return new ReachedMap(g);
2.980 }
2.981 - ///The type of the map that stores the dists of the nodes.
2.982
2.983 - ///The type of the map that stores the dists of the nodes.
2.984 + ///The type of the map that stores the distances of the nodes.
2.985 +
2.986 + ///The type of the map that stores the distances of the nodes.
2.987 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
2.988 ///
2.989 typedef NullMap<typename Digraph::Node,int> DistMap;
2.990 - ///Instantiates a DistMap.
2.991 + ///Instantiates a \ref DistMap.
2.992
2.993 ///This function instantiates a \ref DistMap.
2.994 ///\param g is the digraph, to which we would like to define
2.995 ///the \ref DistMap
2.996 #ifdef DOXYGEN
2.997 - static DistMap *createDistMap(const GR &g)
2.998 + static DistMap *createDistMap(const Digraph &g)
2.999 #else
2.1000 - static DistMap *createDistMap(const GR &)
2.1001 + static DistMap *createDistMap(const Digraph &)
2.1002 #endif
2.1003 {
2.1004 return new DistMap();
2.1005 }
2.1006 };
2.1007
2.1008 - /// Default traits used by \ref DfsWizard
2.1009 + /// Default traits class used by \ref DfsWizard
2.1010
2.1011 /// To make it easier to use Dfs algorithm
2.1012 - ///we have created a wizard class.
2.1013 + /// we have created a wizard class.
2.1014 /// This \ref DfsWizard class needs default traits,
2.1015 - ///as well as the \ref Dfs class.
2.1016 + /// as well as the \ref Dfs class.
2.1017 /// The \ref DfsWizardBase is a class to be the default traits of the
2.1018 /// \ref DfsWizard class.
2.1019 template<class GR>
2.1020 @@ -835,20 +863,20 @@
2.1021
2.1022 typedef DfsWizardDefaultTraits<GR> Base;
2.1023 protected:
2.1024 - /// Type of the nodes in the digraph.
2.1025 + //The type of the nodes in the digraph.
2.1026 typedef typename Base::Digraph::Node Node;
2.1027
2.1028 - /// Pointer to the underlying digraph.
2.1029 + //Pointer to the digraph the algorithm runs on.
2.1030 void *_g;
2.1031 - ///Pointer to the map of reached nodes.
2.1032 + //Pointer to the map of reached nodes.
2.1033 void *_reached;
2.1034 - ///Pointer to the map of processed nodes.
2.1035 + //Pointer to the map of processed nodes.
2.1036 void *_processed;
2.1037 - ///Pointer to the map of predecessors arcs.
2.1038 + //Pointer to the map of predecessors arcs.
2.1039 void *_pred;
2.1040 - ///Pointer to the map of distances.
2.1041 + //Pointer to the map of distances.
2.1042 void *_dist;
2.1043 - ///Pointer to the source node.
2.1044 + //Pointer to the source node.
2.1045 Node _source;
2.1046
2.1047 public:
2.1048 @@ -857,26 +885,28 @@
2.1049 /// This constructor does not require parameters, therefore it initiates
2.1050 /// all of the attributes to default values (0, INVALID).
2.1051 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
2.1052 - _dist(0), _source(INVALID) {}
2.1053 + _dist(0), _source(INVALID) {}
2.1054
2.1055 /// Constructor.
2.1056
2.1057 /// This constructor requires some parameters,
2.1058 /// listed in the parameters list.
2.1059 /// Others are initiated to 0.
2.1060 - /// \param g is the initial value of \ref _g
2.1061 - /// \param s is the initial value of \ref _source
2.1062 + /// \param g The digraph the algorithm runs on.
2.1063 + /// \param s The source node.
2.1064 DfsWizardBase(const GR &g, Node s=INVALID) :
2.1065 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
2.1066 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
2.1067
2.1068 };
2.1069
2.1070 - /// A class to make the usage of the Dfs algorithm easier
2.1071 + /// Auxiliary class for the function type interface of DFS algorithm.
2.1072
2.1073 - /// This class is created to make it easier to use the Dfs algorithm.
2.1074 - /// It uses the functions and features of the plain \ref Dfs,
2.1075 - /// but it is much simpler to use it.
2.1076 + /// This auxiliary class is created to implement the function type
2.1077 + /// interface of \ref Dfs algorithm. It uses the functions and features
2.1078 + /// of the plain \ref Dfs, but it is much simpler to use it.
2.1079 + /// It should only be used through the \ref dfs() function, which makes
2.1080 + /// it easier to use the algorithm.
2.1081 ///
2.1082 /// Simplicity means that the way to change the types defined
2.1083 /// in the traits class is based on functions that returns the new class
2.1084 @@ -885,41 +915,37 @@
2.1085 /// the new class with the modified type comes from
2.1086 /// the original class by using the ::
2.1087 /// operator. In the case of \ref DfsWizard only
2.1088 - /// a function have to be called and it will
2.1089 + /// a function have to be called, and it will
2.1090 /// return the needed class.
2.1091 ///
2.1092 - /// It does not have own \ref run method. When its \ref run method is called
2.1093 - /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
2.1094 - /// method of it.
2.1095 + /// It does not have own \ref run() method. When its \ref run() method
2.1096 + /// is called, it initiates a plain \ref Dfs object, and calls the
2.1097 + /// \ref Dfs::run() method of it.
2.1098 template<class TR>
2.1099 class DfsWizard : public TR
2.1100 {
2.1101 typedef TR Base;
2.1102
2.1103 - ///The type of the underlying digraph.
2.1104 + ///The type of the digraph the algorithm runs on.
2.1105 typedef typename TR::Digraph Digraph;
2.1106 - //\e
2.1107 +
2.1108 typedef typename Digraph::Node Node;
2.1109 - //\e
2.1110 typedef typename Digraph::NodeIt NodeIt;
2.1111 - //\e
2.1112 typedef typename Digraph::Arc Arc;
2.1113 - //\e
2.1114 typedef typename Digraph::OutArcIt OutArcIt;
2.1115
2.1116 - ///\brief The type of the map that stores
2.1117 - ///the reached nodes
2.1118 + ///\brief The type of the map that stores the predecessor
2.1119 + ///arcs of the shortest paths.
2.1120 + typedef typename TR::PredMap PredMap;
2.1121 + ///\brief The type of the map that stores the distances of the nodes.
2.1122 + typedef typename TR::DistMap DistMap;
2.1123 + ///\brief The type of the map that indicates which nodes are reached.
2.1124 typedef typename TR::ReachedMap ReachedMap;
2.1125 - ///\brief The type of the map that stores
2.1126 - ///the processed nodes
2.1127 + ///\brief The type of the map that indicates which nodes are processed.
2.1128 typedef typename TR::ProcessedMap ProcessedMap;
2.1129 - ///\brief The type of the map that stores the last
2.1130 - ///arcs of the %DFS paths.
2.1131 - typedef typename TR::PredMap PredMap;
2.1132 - ///The type of the map that stores the distances of the nodes.
2.1133 - typedef typename TR::DistMap DistMap;
2.1134
2.1135 public:
2.1136 +
2.1137 /// Constructor.
2.1138 DfsWizard() : TR() {}
2.1139
2.1140 @@ -935,10 +961,10 @@
2.1141
2.1142 ~DfsWizard() {}
2.1143
2.1144 - ///Runs Dfs algorithm from a given node.
2.1145 + ///Runs DFS algorithm from a source node.
2.1146
2.1147 - ///Runs Dfs algorithm from a given node.
2.1148 - ///The node can be given by the \ref source function.
2.1149 + ///Runs DFS algorithm from a source node.
2.1150 + ///The node can be given with the \ref source() function.
2.1151 void run()
2.1152 {
2.1153 if(Base::_source==INVALID) throw UninitializedParameter();
2.1154 @@ -954,9 +980,9 @@
2.1155 alg.run(Base::_source);
2.1156 }
2.1157
2.1158 - ///Runs Dfs algorithm from the given node.
2.1159 + ///Runs DFS algorithm from the given node.
2.1160
2.1161 - ///Runs Dfs algorithm from the given node.
2.1162 + ///Runs DFS algorithm from the given node.
2.1163 ///\param s is the given source.
2.1164 void run(Node s)
2.1165 {
2.1166 @@ -964,19 +990,27 @@
2.1167 run();
2.1168 }
2.1169
2.1170 + /// Sets the source node, from which the Dfs algorithm runs.
2.1171 +
2.1172 + /// Sets the source node, from which the Dfs algorithm runs.
2.1173 + /// \param s is the source node.
2.1174 + DfsWizard<TR> &source(Node s)
2.1175 + {
2.1176 + Base::_source=s;
2.1177 + return *this;
2.1178 + }
2.1179 +
2.1180 template<class T>
2.1181 struct DefPredMapBase : public Base {
2.1182 typedef T PredMap;
2.1183 static PredMap *createPredMap(const Digraph &) { return 0; };
2.1184 DefPredMapBase(const TR &b) : TR(b) {}
2.1185 };
2.1186 -
2.1187 ///\brief \ref named-templ-param "Named parameter"
2.1188 - ///function for setting PredMap type
2.1189 + ///for setting \ref PredMap object.
2.1190 ///
2.1191 - /// \ref named-templ-param "Named parameter"
2.1192 - ///function for setting PredMap type
2.1193 - ///
2.1194 + ///\ref named-templ-param "Named parameter"
2.1195 + ///for setting \ref PredMap object.
2.1196 template<class T>
2.1197 DfsWizard<DefPredMapBase<T> > predMap(const T &t)
2.1198 {
2.1199 @@ -984,20 +1018,17 @@
2.1200 return DfsWizard<DefPredMapBase<T> >(*this);
2.1201 }
2.1202
2.1203 -
2.1204 template<class T>
2.1205 struct DefReachedMapBase : public Base {
2.1206 typedef T ReachedMap;
2.1207 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
2.1208 DefReachedMapBase(const TR &b) : TR(b) {}
2.1209 };
2.1210 -
2.1211 ///\brief \ref named-templ-param "Named parameter"
2.1212 - ///function for setting ReachedMap
2.1213 + ///for setting \ref ReachedMap object.
2.1214 ///
2.1215 /// \ref named-templ-param "Named parameter"
2.1216 - ///function for setting ReachedMap
2.1217 - ///
2.1218 + ///for setting \ref ReachedMap object.
2.1219 template<class T>
2.1220 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
2.1221 {
2.1222 @@ -1005,20 +1036,17 @@
2.1223 return DfsWizard<DefReachedMapBase<T> >(*this);
2.1224 }
2.1225
2.1226 -
2.1227 template<class T>
2.1228 struct DefProcessedMapBase : public Base {
2.1229 typedef T ProcessedMap;
2.1230 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
2.1231 DefProcessedMapBase(const TR &b) : TR(b) {}
2.1232 };
2.1233 -
2.1234 ///\brief \ref named-templ-param "Named parameter"
2.1235 - ///function for setting ProcessedMap
2.1236 + ///for setting \ref ProcessedMap object.
2.1237 ///
2.1238 /// \ref named-templ-param "Named parameter"
2.1239 - ///function for setting ProcessedMap
2.1240 - ///
2.1241 + ///for setting \ref ProcessedMap object.
2.1242 template<class T>
2.1243 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
2.1244 {
2.1245 @@ -1032,13 +1060,11 @@
2.1246 static DistMap *createDistMap(const Digraph &) { return 0; };
2.1247 DefDistMapBase(const TR &b) : TR(b) {}
2.1248 };
2.1249 -
2.1250 ///\brief \ref named-templ-param "Named parameter"
2.1251 - ///function for setting DistMap type
2.1252 + ///for setting \ref DistMap object.
2.1253 ///
2.1254 - /// \ref named-templ-param "Named parameter"
2.1255 - ///function for setting DistMap type
2.1256 - ///
2.1257 + ///\ref named-templ-param "Named parameter"
2.1258 + ///for setting \ref DistMap object.
2.1259 template<class T>
2.1260 DfsWizard<DefDistMapBase<T> > distMap(const T &t)
2.1261 {
2.1262 @@ -1046,16 +1072,6 @@
2.1263 return DfsWizard<DefDistMapBase<T> >(*this);
2.1264 }
2.1265
2.1266 - /// Sets the source node, from which the Dfs algorithm runs.
2.1267 -
2.1268 - /// Sets the source node, from which the Dfs algorithm runs.
2.1269 - /// \param s is the source node.
2.1270 - DfsWizard<TR> &source(Node s)
2.1271 - {
2.1272 - Base::_source=s;
2.1273 - return *this;
2.1274 - }
2.1275 -
2.1276 };
2.1277
2.1278 ///Function type interface for Dfs algorithm.
2.1279 @@ -1083,47 +1099,46 @@
2.1280 }
2.1281
2.1282 #ifdef DOXYGEN
2.1283 - /// \brief Visitor class for dfs.
2.1284 + /// \brief Visitor class for DFS.
2.1285 ///
2.1286 - /// It gives a simple interface for a functional interface for dfs
2.1287 - /// traversal. The traversal on a linear data structure.
2.1288 + /// This class defines the interface of the DfsVisit events, and
2.1289 + /// it could be the base of a real visitor class.
2.1290 template <typename _Digraph>
2.1291 struct DfsVisitor {
2.1292 typedef _Digraph Digraph;
2.1293 typedef typename Digraph::Arc Arc;
2.1294 typedef typename Digraph::Node Node;
2.1295 - /// \brief Called when the arc reach a node.
2.1296 + /// \brief Called for the source node of the DFS.
2.1297 ///
2.1298 - /// It is called when the dfs find an arc which target is not
2.1299 - /// reached yet.
2.1300 + /// This function is called for the source node of the DFS.
2.1301 + void start(const Node& node) {}
2.1302 + /// \brief Called when the source node is leaved.
2.1303 + ///
2.1304 + /// This function is called when the source node is leaved.
2.1305 + void stop(const Node& node) {}
2.1306 + /// \brief Called when a node is reached first time.
2.1307 + ///
2.1308 + /// This function is called when a node is reached first time.
2.1309 + void reach(const Node& node) {}
2.1310 + /// \brief Called when an arc reaches a new node.
2.1311 + ///
2.1312 + /// This function is called when the DFS finds an arc whose target node
2.1313 + /// is not reached yet.
2.1314 void discover(const Arc& arc) {}
2.1315 - /// \brief Called when the node reached first time.
2.1316 - ///
2.1317 - /// It is Called when the node reached first time.
2.1318 - void reach(const Node& node) {}
2.1319 - /// \brief Called when we step back on an arc.
2.1320 - ///
2.1321 - /// It is called when the dfs should step back on the arc.
2.1322 - void backtrack(const Arc& arc) {}
2.1323 - /// \brief Called when we step back from the node.
2.1324 - ///
2.1325 - /// It is called when we step back from the node.
2.1326 - void leave(const Node& node) {}
2.1327 - /// \brief Called when the arc examined but target of the arc
2.1328 + /// \brief Called when an arc is examined but its target node is
2.1329 /// already discovered.
2.1330 ///
2.1331 - /// It called when the arc examined but the target of the arc
2.1332 + /// This function is called when an arc is examined but its target node is
2.1333 /// already discovered.
2.1334 void examine(const Arc& arc) {}
2.1335 - /// \brief Called for the source node of the dfs.
2.1336 + /// \brief Called when the DFS steps back from a node.
2.1337 ///
2.1338 - /// It is called for the source node of the dfs.
2.1339 - void start(const Node& node) {}
2.1340 - /// \brief Called when we leave the source node of the dfs.
2.1341 + /// This function is called when the DFS steps back from a node.
2.1342 + void leave(const Node& node) {}
2.1343 + /// \brief Called when the DFS steps back on an arc.
2.1344 ///
2.1345 - /// It is called when we leave the source node of the dfs.
2.1346 - void stop(const Node& node) {}
2.1347 -
2.1348 + /// This function is called when the DFS steps back on an arc.
2.1349 + void backtrack(const Arc& arc) {}
2.1350 };
2.1351 #else
2.1352 template <typename _Digraph>
2.1353 @@ -1131,26 +1146,26 @@
2.1354 typedef _Digraph Digraph;
2.1355 typedef typename Digraph::Arc Arc;
2.1356 typedef typename Digraph::Node Node;
2.1357 - void discover(const Arc&) {}
2.1358 - void reach(const Node&) {}
2.1359 - void backtrack(const Arc&) {}
2.1360 - void leave(const Node&) {}
2.1361 - void examine(const Arc&) {}
2.1362 void start(const Node&) {}
2.1363 void stop(const Node&) {}
2.1364 + void reach(const Node&) {}
2.1365 + void discover(const Arc&) {}
2.1366 + void examine(const Arc&) {}
2.1367 + void leave(const Node&) {}
2.1368 + void backtrack(const Arc&) {}
2.1369
2.1370 template <typename _Visitor>
2.1371 struct Constraints {
2.1372 void constraints() {
2.1373 Arc arc;
2.1374 Node node;
2.1375 - visitor.discover(arc);
2.1376 - visitor.reach(node);
2.1377 - visitor.backtrack(arc);
2.1378 - visitor.leave(node);
2.1379 - visitor.examine(arc);
2.1380 visitor.start(node);
2.1381 visitor.stop(arc);
2.1382 + visitor.reach(node);
2.1383 + visitor.discover(arc);
2.1384 + visitor.examine(arc);
2.1385 + visitor.leave(node);
2.1386 + visitor.backtrack(arc);
2.1387 }
2.1388 _Visitor& visitor;
2.1389 };
2.1390 @@ -1160,21 +1175,20 @@
2.1391 /// \brief Default traits class of DfsVisit class.
2.1392 ///
2.1393 /// Default traits class of DfsVisit class.
2.1394 - /// \tparam _Digraph Digraph type.
2.1395 + /// \tparam _Digraph The type of the digraph the algorithm runs on.
2.1396 template<class _Digraph>
2.1397 struct DfsVisitDefaultTraits {
2.1398
2.1399 - /// \brief The digraph type the algorithm runs on.
2.1400 + /// \brief The type of the digraph the algorithm runs on.
2.1401 typedef _Digraph Digraph;
2.1402
2.1403 /// \brief The type of the map that indicates which nodes are reached.
2.1404 ///
2.1405 /// The type of the map that indicates which nodes are reached.
2.1406 - /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
2.1407 - /// \todo named parameter to set this type, function to read and write.
2.1408 + /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
2.1409 typedef typename Digraph::template NodeMap<bool> ReachedMap;
2.1410
2.1411 - /// \brief Instantiates a ReachedMap.
2.1412 + /// \brief Instantiates a \ref ReachedMap.
2.1413 ///
2.1414 /// This function instantiates a \ref ReachedMap.
2.1415 /// \param digraph is the digraph, to which
2.1416 @@ -1185,31 +1199,30 @@
2.1417
2.1418 };
2.1419
2.1420 - /// %DFS Visit algorithm class.
2.1421 -
2.1422 /// \ingroup search
2.1423 + ///
2.1424 + /// \brief %DFS algorithm class with visitor interface.
2.1425 + ///
2.1426 /// This class provides an efficient implementation of the %DFS algorithm
2.1427 /// with visitor interface.
2.1428 ///
2.1429 /// The %DfsVisit class provides an alternative interface to the Dfs
2.1430 /// class. It works with callback mechanism, the DfsVisit object calls
2.1431 - /// on every dfs event the \c Visitor class member functions.
2.1432 + /// the member functions of the \c Visitor class on every DFS event.
2.1433 ///
2.1434 - /// \tparam _Digraph The digraph type the algorithm runs on.
2.1435 + /// \tparam _Digraph The type of the digraph the algorithm runs on.
2.1436 /// The default value is
2.1437 - /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it
2.1438 - /// is only passed to \ref DfsDefaultTraits.
2.1439 - /// \tparam _Visitor The Visitor object for the algorithm. The
2.1440 - /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which
2.1441 - /// does not observe the Dfs events. If you want to observe the dfs
2.1442 - /// events you should implement your own Visitor class.
2.1443 + /// \ref ListDigraph. The value of _Digraph is not used directly by
2.1444 + /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
2.1445 + /// \tparam _Visitor The Visitor type that is used by the algorithm.
2.1446 + /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
2.1447 + /// does not observe the DFS events. If you want to observe the DFS
2.1448 + /// events, you should implement your own visitor class.
2.1449 /// \tparam _Traits Traits class to set various data types used by the
2.1450 /// algorithm. The default traits class is
2.1451 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
2.1452 /// See \ref DfsVisitDefaultTraits for the documentation of
2.1453 - /// a Dfs visit traits class.
2.1454 - ///
2.1455 - /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
2.1456 + /// a DFS visit traits class.
2.1457 #ifdef DOXYGEN
2.1458 template <typename _Digraph, typename _Visitor, typename _Traits>
2.1459 #else
2.1460 @@ -1223,7 +1236,7 @@
2.1461 /// \brief \ref Exception for uninitialized parameters.
2.1462 ///
2.1463 /// This error represents problems in the initialization
2.1464 - /// of the parameters of the algorithms.
2.1465 + /// of the parameters of the algorithm.
2.1466 class UninitializedParameter : public lemon::UninitializedParameter {
2.1467 public:
2.1468 virtual const char* what() const throw()
2.1469 @@ -1232,13 +1245,16 @@
2.1470 }
2.1471 };
2.1472
2.1473 + ///The traits class.
2.1474 typedef _Traits Traits;
2.1475
2.1476 + ///The type of the digraph the algorithm runs on.
2.1477 typedef typename Traits::Digraph Digraph;
2.1478
2.1479 + ///The visitor type used by the algorithm.
2.1480 typedef _Visitor Visitor;
2.1481
2.1482 - ///The type of the map indicating which nodes are reached.
2.1483 + ///The type of the map that indicates which nodes are reached.
2.1484 typedef typename Traits::ReachedMap ReachedMap;
2.1485
2.1486 private:
2.1487 @@ -1248,21 +1264,20 @@
2.1488 typedef typename Digraph::Arc Arc;
2.1489 typedef typename Digraph::OutArcIt OutArcIt;
2.1490
2.1491 - /// Pointer to the underlying digraph.
2.1492 + //Pointer to the underlying digraph.
2.1493 const Digraph *_digraph;
2.1494 - /// Pointer to the visitor object.
2.1495 + //Pointer to the visitor object.
2.1496 Visitor *_visitor;
2.1497 - ///Pointer to the map of reached status of the nodes.
2.1498 + //Pointer to the map of reached status of the nodes.
2.1499 ReachedMap *_reached;
2.1500 - ///Indicates if \ref _reached is locally allocated (\c true) or not.
2.1501 + //Indicates if _reached is locally allocated (true) or not.
2.1502 bool local_reached;
2.1503
2.1504 std::vector<typename Digraph::Arc> _stack;
2.1505 int _stack_head;
2.1506
2.1507 - /// \brief Creates the maps if necessary.
2.1508 - ///
2.1509 - /// Creates the maps if necessary.
2.1510 + ///Creates the maps if necessary.
2.1511 + ///\todo Better memory allocation (instead of new).
2.1512 void create_maps() {
2.1513 if(!_reached) {
2.1514 local_reached = true;
2.1515 @@ -1289,9 +1304,9 @@
2.1516 }
2.1517 };
2.1518 /// \brief \ref named-templ-param "Named parameter" for setting
2.1519 - /// ReachedMap type
2.1520 + /// ReachedMap type.
2.1521 ///
2.1522 - /// \ref named-templ-param "Named parameter" for setting ReachedMap type
2.1523 + /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
2.1524 template <class T>
2.1525 struct DefReachedMap : public DfsVisit< Digraph, Visitor,
2.1526 DefReachedMapTraits<T> > {
2.1527 @@ -1305,25 +1320,22 @@
2.1528 ///
2.1529 /// Constructor.
2.1530 ///
2.1531 - /// \param digraph the digraph the algorithm will run on.
2.1532 - /// \param visitor The visitor of the algorithm.
2.1533 - ///
2.1534 + /// \param digraph The digraph the algorithm runs on.
2.1535 + /// \param visitor The visitor object of the algorithm.
2.1536 DfsVisit(const Digraph& digraph, Visitor& visitor)
2.1537 : _digraph(&digraph), _visitor(&visitor),
2.1538 _reached(0), local_reached(false) {}
2.1539
2.1540 /// \brief Destructor.
2.1541 - ///
2.1542 - /// Destructor.
2.1543 ~DfsVisit() {
2.1544 if(local_reached) delete _reached;
2.1545 }
2.1546
2.1547 - /// \brief Sets the map indicating if a node is reached.
2.1548 + /// \brief Sets the map that indicates which nodes are reached.
2.1549 ///
2.1550 - /// Sets the map indicating if a node is reached.
2.1551 + /// Sets the map that indicates which nodes are reached.
2.1552 /// If you don't use this function before calling \ref run(),
2.1553 - /// it will allocate one. The destuctor deallocates this
2.1554 + /// it will allocate one. The destructor deallocates this
2.1555 /// automatically allocated map, of course.
2.1556 /// \return <tt> (*this) </tt>
2.1557 DfsVisit &reachedMap(ReachedMap &m) {
2.1558 @@ -1336,21 +1348,23 @@
2.1559 }
2.1560
2.1561 public:
2.1562 +
2.1563 /// \name Execution control
2.1564 /// The simplest way to execute the algorithm is to use
2.1565 - /// one of the member functions called \c run(...).
2.1566 + /// one of the member functions called \ref lemon::DfsVisit::run()
2.1567 + /// "run()".
2.1568 /// \n
2.1569 - /// If you need more control on the execution,
2.1570 - /// first you must call \ref init(), then you can adda source node
2.1571 - /// with \ref addSource().
2.1572 - /// Finally \ref start() will perform the actual path
2.1573 - /// computation.
2.1574 + /// If you need more control on the execution, first you must call
2.1575 + /// \ref lemon::DfsVisit::init() "init()", then you can add several
2.1576 + /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
2.1577 + /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
2.1578 + /// actual path computation.
2.1579
2.1580 /// @{
2.1581 +
2.1582 /// \brief Initializes the internal data structures.
2.1583 ///
2.1584 /// Initializes the internal data structures.
2.1585 - ///
2.1586 void init() {
2.1587 create_maps();
2.1588 _stack.resize(countNodes(*_digraph));
2.1589 @@ -1360,10 +1374,18 @@
2.1590 }
2.1591 }
2.1592
2.1593 - /// \brief Adds a new source node.
2.1594 + ///Adds a new source node.
2.1595 +
2.1596 + ///Adds a new source node to the set of nodes to be processed.
2.1597 ///
2.1598 - /// Adds a new source node to the set of nodes to be processed.
2.1599 - void addSource(Node s) {
2.1600 + ///\pre The stack must be empty. (Otherwise the algorithm gives
2.1601 + ///false results.)
2.1602 + ///
2.1603 + ///\warning Distances will be wrong (or at least strange) in case of
2.1604 + ///multiple sources.
2.1605 + void addSource(Node s)
2.1606 + {
2.1607 + LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
2.1608 if(!(*_reached)[s]) {
2.1609 _reached->set(s,true);
2.1610 _visitor->start(s);
2.1611 @@ -1384,7 +1406,7 @@
2.1612 ///
2.1613 /// \return The processed arc.
2.1614 ///
2.1615 - /// \pre The stack must not be empty!
2.1616 + /// \pre The stack must not be empty.
2.1617 Arc processNextArc() {
2.1618 Arc e = _stack[_stack_head];
2.1619 Node m = _digraph->target(e);
2.1620 @@ -1418,37 +1440,58 @@
2.1621 ///
2.1622 /// \return The next arc to be processed or INVALID if the stack is
2.1623 /// empty.
2.1624 - Arc nextArc() {
2.1625 + Arc nextArc() const {
2.1626 return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
2.1627 }
2.1628
2.1629 /// \brief Returns \c false if there are nodes
2.1630 - /// to be processed in the queue
2.1631 + /// to be processed.
2.1632 ///
2.1633 /// Returns \c false if there are nodes
2.1634 - /// to be processed in the queue
2.1635 - bool emptyQueue() { return _stack_head < 0; }
2.1636 + /// to be processed in the queue (stack).
2.1637 + bool emptyQueue() const { return _stack_head < 0; }
2.1638
2.1639 /// \brief Returns the number of the nodes to be processed.
2.1640 ///
2.1641 - /// Returns the number of the nodes to be processed in the queue.
2.1642 - int queueSize() { return _stack_head + 1; }
2.1643 + /// Returns the number of the nodes to be processed in the queue (stack).
2.1644 + int queueSize() const { return _stack_head + 1; }
2.1645
2.1646 /// \brief Executes the algorithm.
2.1647 ///
2.1648 /// Executes the algorithm.
2.1649 ///
2.1650 - /// \pre init() must be called and at least one node should be added
2.1651 - /// with addSource() before using this function.
2.1652 + /// This method runs the %DFS algorithm from the root node
2.1653 + /// in order to compute the %DFS path to each node.
2.1654 + ///
2.1655 + /// The algorithm computes
2.1656 + /// - the %DFS tree,
2.1657 + /// - the distance of each node from the root in the %DFS tree.
2.1658 + ///
2.1659 + /// \pre init() must be called and a root node should be
2.1660 + /// added with addSource() before using this function.
2.1661 + ///
2.1662 + /// \note <tt>d.start()</tt> is just a shortcut of the following code.
2.1663 + /// \code
2.1664 + /// while ( !d.emptyQueue() ) {
2.1665 + /// d.processNextArc();
2.1666 + /// }
2.1667 + /// \endcode
2.1668 void start() {
2.1669 while ( !emptyQueue() ) processNextArc();
2.1670 }
2.1671
2.1672 - /// \brief Executes the algorithm until \c dest is reached.
2.1673 + /// \brief Executes the algorithm until the given target node is reached.
2.1674 ///
2.1675 - /// Executes the algorithm until \c dest is reached.
2.1676 + /// Executes the algorithm until the given target node is reached.
2.1677 ///
2.1678 - /// \pre init() must be called and at least one node should be added
2.1679 + /// This method runs the %DFS algorithm from the root node
2.1680 + /// in order to compute the DFS path to \c dest.
2.1681 + ///
2.1682 + /// The algorithm computes
2.1683 + /// - the %DFS path to \c dest,
2.1684 + /// - the distance of \c dest from the root in the %DFS tree.
2.1685 + ///
2.1686 + /// \pre init() must be called and a root node should be added
2.1687 /// with addSource() before using this function.
2.1688 void start(Node dest) {
2.1689 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
2.1690 @@ -1459,28 +1502,37 @@
2.1691 ///
2.1692 /// Executes the algorithm until a condition is met.
2.1693 ///
2.1694 - /// \pre init() must be called and at least one node should be added
2.1695 + /// This method runs the %DFS algorithm from the root node
2.1696 + /// until an arc \c a with <tt>am[a]</tt> true is found.
2.1697 + ///
2.1698 + /// \param am A \c bool (or convertible) arc map. The algorithm
2.1699 + /// will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
2.1700 + ///
2.1701 + /// \return The reached arc \c a with <tt>am[a]</tt> true or
2.1702 + /// \c INVALID if no such arc was found.
2.1703 + ///
2.1704 + /// \pre init() must be called and a root node should be added
2.1705 /// with addSource() before using this function.
2.1706 ///
2.1707 - /// \param em must be a bool (or convertible) arc map. The algorithm
2.1708 - /// will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
2.1709 - ///
2.1710 - ///\return The reached arc \c e with <tt>em[e]</tt> true or
2.1711 - ///\c INVALID if no such arc was found.
2.1712 - ///
2.1713 - /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
2.1714 + /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
2.1715 /// not a node map.
2.1716 - template <typename EM>
2.1717 - Arc start(const EM &em) {
2.1718 - while ( !emptyQueue() && !em[_stack[_stack_head]] )
2.1719 + template <typename AM>
2.1720 + Arc start(const AM &am) {
2.1721 + while ( !emptyQueue() && !am[_stack[_stack_head]] )
2.1722 processNextArc();
2.1723 return emptyQueue() ? INVALID : _stack[_stack_head];
2.1724 }
2.1725
2.1726 - /// \brief Runs %DFSVisit algorithm from node \c s.
2.1727 + /// \brief Runs the algorithm from the given node.
2.1728 ///
2.1729 - /// This method runs the %DFS algorithm from a root node \c s.
2.1730 - /// \note d.run(s) is just a shortcut of the following code.
2.1731 + /// This method runs the %DFS algorithm from node \c s.
2.1732 + /// in order to compute the DFS path to each node.
2.1733 + ///
2.1734 + /// The algorithm computes
2.1735 + /// - the %DFS tree,
2.1736 + /// - the distance of each node from the root in the %DFS tree.
2.1737 + ///
2.1738 + /// \note <tt>d.run(s)</tt> is just a shortcut of the following code.
2.1739 ///\code
2.1740 /// d.init();
2.1741 /// d.addSource(s);
2.1742 @@ -1492,22 +1544,46 @@
2.1743 start();
2.1744 }
2.1745
2.1746 - /// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph.
2.1747 + /// \brief Finds the %DFS path between \c s and \c t.
2.1748 +
2.1749 + /// This method runs the %DFS algorithm from node \c s
2.1750 + /// in order to compute the DFS path to \c t.
2.1751 + ///
2.1752 + /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
2.1753 + /// if \c t is reachable form \c s, \c 0 otherwise.
2.1754 + ///
2.1755 + /// \note Apart from the return value, <tt>d.run(s,t)</tt> is
2.1756 + /// just a shortcut of the following code.
2.1757 + ///\code
2.1758 + /// d.init();
2.1759 + /// d.addSource(s);
2.1760 + /// d.start(t);
2.1761 + ///\endcode
2.1762 + int run(Node s,Node t) {
2.1763 + init();
2.1764 + addSource(s);
2.1765 + start(t);
2.1766 + return reached(t)?_stack_head+1:0;
2.1767 + }
2.1768 +
2.1769 + /// \brief Runs the algorithm to visit all nodes in the digraph.
2.1770
2.1771 /// This method runs the %DFS algorithm in order to
2.1772 - /// compute the %DFS path to each node. The algorithm computes
2.1773 - /// - The %DFS tree.
2.1774 - /// - The distance of each node from the root in the %DFS tree.
2.1775 + /// compute the %DFS path to each node.
2.1776 ///
2.1777 - ///\note d.run() is just a shortcut of the following code.
2.1778 + /// The algorithm computes
2.1779 + /// - the %DFS tree,
2.1780 + /// - the distance of each node from the root in the %DFS tree.
2.1781 + ///
2.1782 + /// \note <tt>d.run()</tt> is just a shortcut of the following code.
2.1783 ///\code
2.1784 - /// d.init();
2.1785 - /// for (NodeIt it(digraph); it != INVALID; ++it) {
2.1786 - /// if (!d.reached(it)) {
2.1787 - /// d.addSource(it);
2.1788 - /// d.start();
2.1789 - /// }
2.1790 - /// }
2.1791 + /// d.init();
2.1792 + /// for (NodeIt n(digraph); n != INVALID; ++n) {
2.1793 + /// if (!d.reached(n)) {
2.1794 + /// d.addSource(n);
2.1795 + /// d.start();
2.1796 + /// }
2.1797 + /// }
2.1798 ///\endcode
2.1799 void run() {
2.1800 init();
2.1801 @@ -1518,27 +1594,28 @@
2.1802 }
2.1803 }
2.1804 }
2.1805 +
2.1806 ///@}
2.1807
2.1808 /// \name Query Functions
2.1809 /// The result of the %DFS algorithm can be obtained using these
2.1810 /// functions.\n
2.1811 - /// Before the use of these functions,
2.1812 - /// either run() or start() must be called.
2.1813 + /// Either \ref lemon::DfsVisit::run() "run()" or
2.1814 + /// \ref lemon::DfsVisit::start() "start()" must be called before
2.1815 + /// using them.
2.1816 ///@{
2.1817 - /// \brief Checks if a node is reachable from the root.
2.1818 +
2.1819 + /// \brief Checks if a node is reachable from the root(s).
2.1820 ///
2.1821 /// Returns \c true if \c v is reachable from the root(s).
2.1822 - /// \warning The source nodes are inditated as unreachable.
2.1823 /// \pre Either \ref run() or \ref start()
2.1824 /// must be called before using this function.
2.1825 - ///
2.1826 bool reached(Node v) { return (*_reached)[v]; }
2.1827 +
2.1828 ///@}
2.1829 +
2.1830 };
2.1831
2.1832 -
2.1833 } //END OF NAMESPACE LEMON
2.1834
2.1835 #endif
2.1836 -
3.1 --- a/lemon/dijkstra.h Mon Jul 14 15:40:24 2008 +0100
3.2 +++ b/lemon/dijkstra.h Sun Aug 03 13:34:57 2008 +0200
3.3 @@ -33,10 +33,10 @@
3.4
3.5 namespace lemon {
3.6
3.7 - /// \brief Default OperationTraits for the Dijkstra algorithm class.
3.8 + /// \brief Default operation traits for the Dijkstra algorithm class.
3.9 ///
3.10 - /// It defines all computational operations and constants which are
3.11 - /// used in the Dijkstra algorithm.
3.12 + /// This operation traits class defines all computational operations and
3.13 + /// constants which are used in the Dijkstra algorithm.
3.14 template <typename Value>
3.15 struct DijkstraDefaultOperationTraits {
3.16 /// \brief Gives back the zero value of the type.
3.17 @@ -47,16 +47,19 @@
3.18 static Value plus(const Value& left, const Value& right) {
3.19 return left + right;
3.20 }
3.21 - /// \brief Gives back true only if the first value less than the second.
3.22 + /// \brief Gives back true only if the first value is less than the second.
3.23 static bool less(const Value& left, const Value& right) {
3.24 return left < right;
3.25 }
3.26 };
3.27
3.28 - /// \brief Widest path OperationTraits for the Dijkstra algorithm class.
3.29 + /// \brief Widest path operation traits for the Dijkstra algorithm class.
3.30 ///
3.31 - /// It defines all computational operations and constants which are
3.32 - /// used in the Dijkstra algorithm for widest path computation.
3.33 + /// This operation traits class defines all computational operations and
3.34 + /// constants which are used in the Dijkstra algorithm for widest path
3.35 + /// computation.
3.36 + ///
3.37 + /// \see DijkstraDefaultOperationTraits
3.38 template <typename Value>
3.39 struct DijkstraWidestPathOperationTraits {
3.40 /// \brief Gives back the maximum value of the type.
3.41 @@ -67,7 +70,7 @@
3.42 static Value plus(const Value& left, const Value& right) {
3.43 return std::min(left, right);
3.44 }
3.45 - /// \brief Gives back true only if the first value less than the second.
3.46 + /// \brief Gives back true only if the first value is less than the second.
3.47 static bool less(const Value& left, const Value& right) {
3.48 return left < right;
3.49 }
3.50 @@ -76,141 +79,145 @@
3.51 ///Default traits class of Dijkstra class.
3.52
3.53 ///Default traits class of Dijkstra class.
3.54 - ///\tparam GR Digraph type.
3.55 - ///\tparam LM Type of length map.
3.56 + ///\tparam GR The type of the digraph.
3.57 + ///\tparam LM The type of the length map.
3.58 template<class GR, class LM>
3.59 struct DijkstraDefaultTraits
3.60 {
3.61 - ///The digraph type the algorithm runs on.
3.62 + ///The type of the digraph the algorithm runs on.
3.63 typedef GR Digraph;
3.64 +
3.65 ///The type of the map that stores the arc lengths.
3.66
3.67 ///The type of the map that stores the arc lengths.
3.68 ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
3.69 typedef LM LengthMap;
3.70 - //The type of the length of the arcs.
3.71 + ///The type of the length of the arcs.
3.72 typedef typename LM::Value Value;
3.73 +
3.74 /// Operation traits for Dijkstra algorithm.
3.75
3.76 - /// It defines the used operation by the algorithm.
3.77 + /// This class defines the operations that are used in the algorithm.
3.78 /// \see DijkstraDefaultOperationTraits
3.79 typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
3.80 - /// The cross reference type used by heap.
3.81
3.82 + /// The cross reference type used by the heap.
3.83
3.84 - /// The cross reference type used by heap.
3.85 + /// The cross reference type used by the heap.
3.86 /// Usually it is \c Digraph::NodeMap<int>.
3.87 typedef typename Digraph::template NodeMap<int> HeapCrossRef;
3.88 - ///Instantiates a HeapCrossRef.
3.89 + ///Instantiates a \ref HeapCrossRef.
3.90
3.91 - ///This function instantiates a \c HeapCrossRef.
3.92 - /// \param G is the digraph, to which we would like to define the
3.93 - /// HeapCrossRef.
3.94 - static HeapCrossRef *createHeapCrossRef(const GR &G)
3.95 + ///This function instantiates a \ref HeapCrossRef.
3.96 + /// \param g is the digraph, to which we would like to define the
3.97 + /// \ref HeapCrossRef.
3.98 + static HeapCrossRef *createHeapCrossRef(const Digraph &g)
3.99 {
3.100 - return new HeapCrossRef(G);
3.101 + return new HeapCrossRef(g);
3.102 }
3.103
3.104 - ///The heap type used by Dijkstra algorithm.
3.105 + ///The heap type used by the Dijkstra algorithm.
3.106
3.107 - ///The heap type used by Dijkstra algorithm.
3.108 + ///The heap type used by the Dijkstra algorithm.
3.109 ///
3.110 ///\sa BinHeap
3.111 ///\sa Dijkstra
3.112 typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
3.113 + ///Instantiates a \ref Heap.
3.114
3.115 - static Heap *createHeap(HeapCrossRef& R)
3.116 + ///This function instantiates a \ref Heap.
3.117 + static Heap *createHeap(HeapCrossRef& r)
3.118 {
3.119 - return new Heap(R);
3.120 + return new Heap(r);
3.121 }
3.122
3.123 - ///\brief The type of the map that stores the last
3.124 + ///\brief The type of the map that stores the predecessor
3.125 ///arcs of the shortest paths.
3.126 ///
3.127 - ///The type of the map that stores the last
3.128 + ///The type of the map that stores the predecessor
3.129 ///arcs of the shortest paths.
3.130 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
3.131 - ///
3.132 - typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
3.133 - ///Instantiates a PredMap.
3.134 + typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
3.135 + ///Instantiates a \ref PredMap.
3.136
3.137 - ///This function instantiates a \c PredMap.
3.138 - ///\param G is the digraph, to which we would like to define the PredMap.
3.139 + ///This function instantiates a \ref PredMap.
3.140 + ///\param g is the digraph, to which we would like to define the
3.141 + ///\ref PredMap.
3.142 ///\todo The digraph alone may be insufficient for the initialization
3.143 - static PredMap *createPredMap(const GR &G)
3.144 + static PredMap *createPredMap(const Digraph &g)
3.145 {
3.146 - return new PredMap(G);
3.147 + return new PredMap(g);
3.148 }
3.149
3.150 - ///The type of the map that stores whether a nodes is processed.
3.151 + ///The type of the map that indicates which nodes are processed.
3.152
3.153 - ///The type of the map that stores whether a nodes is processed.
3.154 + ///The type of the map that indicates which nodes are processed.
3.155 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
3.156 ///By default it is a NullMap.
3.157 ///\todo If it is set to a real map,
3.158 ///Dijkstra::processed() should read this.
3.159 - ///\todo named parameter to set this type, function to read and write.
3.160 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
3.161 - ///Instantiates a ProcessedMap.
3.162 + ///Instantiates a \ref ProcessedMap.
3.163
3.164 - ///This function instantiates a \c ProcessedMap.
3.165 + ///This function instantiates a \ref ProcessedMap.
3.166 ///\param g is the digraph, to which
3.167 - ///we would like to define the \c ProcessedMap
3.168 + ///we would like to define the \ref ProcessedMap
3.169 #ifdef DOXYGEN
3.170 - static ProcessedMap *createProcessedMap(const GR &g)
3.171 + static ProcessedMap *createProcessedMap(const Digraph &g)
3.172 #else
3.173 - static ProcessedMap *createProcessedMap(const GR &)
3.174 + static ProcessedMap *createProcessedMap(const Digraph &)
3.175 #endif
3.176 {
3.177 return new ProcessedMap();
3.178 }
3.179 - ///The type of the map that stores the dists of the nodes.
3.180
3.181 - ///The type of the map that stores the dists of the nodes.
3.182 + ///The type of the map that stores the distances of the nodes.
3.183 +
3.184 + ///The type of the map that stores the distances of the nodes.
3.185 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
3.186 - ///
3.187 typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
3.188 - ///Instantiates a DistMap.
3.189 + ///Instantiates a \ref DistMap.
3.190
3.191 ///This function instantiates a \ref DistMap.
3.192 - ///\param G is the digraph, to which we would like to define
3.193 + ///\param g is the digraph, to which we would like to define
3.194 ///the \ref DistMap
3.195 - static DistMap *createDistMap(const GR &G)
3.196 + static DistMap *createDistMap(const Digraph &g)
3.197 {
3.198 - return new DistMap(G);
3.199 + return new DistMap(g);
3.200 }
3.201 };
3.202
3.203 ///%Dijkstra algorithm class.
3.204
3.205 /// \ingroup shortest_path
3.206 - ///This class provides an efficient implementation of %Dijkstra algorithm.
3.207 + ///This class provides an efficient implementation of the %Dijkstra algorithm.
3.208 + ///
3.209 ///The arc lengths are passed to the algorithm using a
3.210 ///\ref concepts::ReadMap "ReadMap",
3.211 ///so it is easy to change it to any kind of length.
3.212 - ///
3.213 ///The type of the length is determined by the
3.214 ///\ref concepts::ReadMap::Value "Value" of the length map.
3.215 - ///
3.216 ///It is also possible to change the underlying priority heap.
3.217 ///
3.218 - ///\tparam GR The digraph type the algorithm runs on. The default value
3.219 - ///is \ref ListDigraph. The value of GR is not used directly by
3.220 - ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
3.221 - ///\tparam LM This read-only ArcMap determines the lengths of the
3.222 + ///There is also a \ref dijkstra() "function type interface" for the
3.223 + ///%Dijkstra algorithm, which is convenient in the simplier cases and
3.224 + ///it can be used easier.
3.225 + ///
3.226 + ///\tparam GR The type of the digraph the algorithm runs on.
3.227 + ///The default value is \ref ListDigraph.
3.228 + ///The value of GR is not used directly by \ref Dijkstra, it is only
3.229 + ///passed to \ref DijkstraDefaultTraits.
3.230 + ///\tparam LM A readable arc map that determines the lengths of the
3.231 ///arcs. It is read once for each arc, so the map may involve in
3.232 - ///relatively time consuming process to compute the arc length if
3.233 + ///relatively time consuming process to compute the arc lengths if
3.234 ///it is necessary. The default map type is \ref
3.235 - ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>". The value
3.236 - ///of LM is not used directly by Dijkstra, it is only passed to \ref
3.237 - ///DijkstraDefaultTraits.
3.238 - ///\tparam TR Traits class to set
3.239 - ///various data types used by the algorithm. The default traits
3.240 - ///class is \ref DijkstraDefaultTraits
3.241 - ///"DijkstraDefaultTraits<GR,LM>". See \ref
3.242 - ///DijkstraDefaultTraits for the documentation of a Dijkstra traits
3.243 - ///class.
3.244 -
3.245 + ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
3.246 + ///The value of LM is not used directly by \ref Dijkstra, it is only
3.247 + ///passed to \ref DijkstraDefaultTraits.
3.248 + ///\tparam TR Traits class to set various data types used by the algorithm.
3.249 + ///The default traits class is \ref DijkstraDefaultTraits
3.250 + ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
3.251 + ///for the documentation of a Dijkstra traits class.
3.252 #ifdef DOXYGEN
3.253 template <typename GR, typename LM, typename TR>
3.254 #else
3.255 @@ -220,12 +227,10 @@
3.256 #endif
3.257 class Dijkstra {
3.258 public:
3.259 - /**
3.260 - * \brief \ref Exception for uninitialized parameters.
3.261 - *
3.262 - * This error represents problems in the initialization
3.263 - * of the parameters of the algorithms.
3.264 - */
3.265 + ///\ref Exception for uninitialized parameters.
3.266 +
3.267 + ///This error represents problems in the initialization of the
3.268 + ///parameters of the algorithm.
3.269 class UninitializedParameter : public lemon::UninitializedParameter {
3.270 public:
3.271 virtual const char* what() const throw() {
3.272 @@ -233,63 +238,65 @@
3.273 }
3.274 };
3.275
3.276 - typedef TR Traits;
3.277 - ///The type of the underlying digraph.
3.278 + ///The type of the digraph the algorithm runs on.
3.279 typedef typename TR::Digraph Digraph;
3.280 - ///\e
3.281 - typedef typename Digraph::Node Node;
3.282 - ///\e
3.283 - typedef typename Digraph::NodeIt NodeIt;
3.284 - ///\e
3.285 - typedef typename Digraph::Arc Arc;
3.286 - ///\e
3.287 - typedef typename Digraph::OutArcIt OutArcIt;
3.288
3.289 ///The type of the length of the arcs.
3.290 typedef typename TR::LengthMap::Value Value;
3.291 ///The type of the map that stores the arc lengths.
3.292 typedef typename TR::LengthMap LengthMap;
3.293 - ///\brief The type of the map that stores the last
3.294 - ///arcs of the shortest paths.
3.295 + ///\brief The type of the map that stores the predecessor arcs of the
3.296 + ///shortest paths.
3.297 typedef typename TR::PredMap PredMap;
3.298 - ///The type of the map indicating if a node is processed.
3.299 + ///The type of the map that stores the distances of the nodes.
3.300 + typedef typename TR::DistMap DistMap;
3.301 + ///The type of the map that indicates which nodes are processed.
3.302 typedef typename TR::ProcessedMap ProcessedMap;
3.303 - ///The type of the map that stores the dists of the nodes.
3.304 - typedef typename TR::DistMap DistMap;
3.305 + ///The type of the paths.
3.306 + typedef PredMapPath<Digraph, PredMap> Path;
3.307 ///The cross reference type used for the current heap.
3.308 typedef typename TR::HeapCrossRef HeapCrossRef;
3.309 - ///The heap type used by the dijkstra algorithm.
3.310 + ///The heap type used by the algorithm.
3.311 typedef typename TR::Heap Heap;
3.312 - ///The operation traits.
3.313 + ///The operation traits class.
3.314 typedef typename TR::OperationTraits OperationTraits;
3.315 +
3.316 + ///The traits class.
3.317 + typedef TR Traits;
3.318 +
3.319 private:
3.320 - /// Pointer to the underlying digraph.
3.321 +
3.322 + typedef typename Digraph::Node Node;
3.323 + typedef typename Digraph::NodeIt NodeIt;
3.324 + typedef typename Digraph::Arc Arc;
3.325 + typedef typename Digraph::OutArcIt OutArcIt;
3.326 +
3.327 + //Pointer to the underlying digraph.
3.328 const Digraph *G;
3.329 - /// Pointer to the length map
3.330 + //Pointer to the length map.
3.331 const LengthMap *length;
3.332 - ///Pointer to the map of predecessors arcs.
3.333 + //Pointer to the map of predecessors arcs.
3.334 PredMap *_pred;
3.335 - ///Indicates if \ref _pred is locally allocated (\c true) or not.
3.336 + //Indicates if _pred is locally allocated (true) or not.
3.337 bool local_pred;
3.338 - ///Pointer to the map of distances.
3.339 + //Pointer to the map of distances.
3.340 DistMap *_dist;
3.341 - ///Indicates if \ref _dist is locally allocated (\c true) or not.
3.342 + //Indicates if _dist is locally allocated (true) or not.
3.343 bool local_dist;
3.344 - ///Pointer to the map of processed status of the nodes.
3.345 + //Pointer to the map of processed status of the nodes.
3.346 ProcessedMap *_processed;
3.347 - ///Indicates if \ref _processed is locally allocated (\c true) or not.
3.348 + //Indicates if _processed is locally allocated (true) or not.
3.349 bool local_processed;
3.350 - ///Pointer to the heap cross references.
3.351 + //Pointer to the heap cross references.
3.352 HeapCrossRef *_heap_cross_ref;
3.353 - ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
3.354 + //Indicates if _heap_cross_ref is locally allocated (true) or not.
3.355 bool local_heap_cross_ref;
3.356 - ///Pointer to the heap.
3.357 + //Pointer to the heap.
3.358 Heap *_heap;
3.359 - ///Indicates if \ref _heap is locally allocated (\c true) or not.
3.360 + //Indicates if _heap is locally allocated (true) or not.
3.361 bool local_heap;
3.362
3.363 ///Creates the maps if necessary.
3.364 -
3.365 ///\todo Better memory allocation (instead of new).
3.366 void create_maps()
3.367 {
3.368 @@ -315,7 +322,7 @@
3.369 }
3.370 }
3.371
3.372 - public :
3.373 + public:
3.374
3.375 typedef Dijkstra Create;
3.376
3.377 @@ -331,10 +338,11 @@
3.378 throw UninitializedParameter();
3.379 }
3.380 };
3.381 - ///\ref named-templ-param "Named parameter" for setting PredMap type
3.382 -
3.383 - ///\ref named-templ-param "Named parameter" for setting PredMap type
3.384 + ///\brief \ref named-templ-param "Named parameter" for setting
3.385 + ///\ref PredMap type.
3.386 ///
3.387 + ///\ref named-templ-param "Named parameter" for setting
3.388 + ///\ref PredMap type.
3.389 template <class T>
3.390 struct DefPredMap
3.391 : public Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > {
3.392 @@ -349,10 +357,11 @@
3.393 throw UninitializedParameter();
3.394 }
3.395 };
3.396 - ///\ref named-templ-param "Named parameter" for setting DistMap type
3.397 -
3.398 - ///\ref named-templ-param "Named parameter" for setting DistMap type
3.399 + ///\brief \ref named-templ-param "Named parameter" for setting
3.400 + ///\ref DistMap type.
3.401 ///
3.402 + ///\ref named-templ-param "Named parameter" for setting
3.403 + ///\ref DistMap type.
3.404 template <class T>
3.405 struct DefDistMap
3.406 : public Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > {
3.407 @@ -362,15 +371,16 @@
3.408 template <class T>
3.409 struct DefProcessedMapTraits : public Traits {
3.410 typedef T ProcessedMap;
3.411 - static ProcessedMap *createProcessedMap(const Digraph &G)
3.412 + static ProcessedMap *createProcessedMap(const Digraph &)
3.413 {
3.414 throw UninitializedParameter();
3.415 }
3.416 };
3.417 - ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
3.418 -
3.419 - ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
3.420 + ///\brief \ref named-templ-param "Named parameter" for setting
3.421 + ///\ref ProcessedMap type.
3.422 ///
3.423 + ///\ref named-templ-param "Named parameter" for setting
3.424 + ///\ref ProcessedMap type.
3.425 template <class T>
3.426 struct DefProcessedMap
3.427 : public Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > {
3.428 @@ -379,17 +389,17 @@
3.429
3.430 struct DefDigraphProcessedMapTraits : public Traits {
3.431 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
3.432 - static ProcessedMap *createProcessedMap(const Digraph &G)
3.433 + static ProcessedMap *createProcessedMap(const Digraph &g)
3.434 {
3.435 - return new ProcessedMap(G);
3.436 + return new ProcessedMap(g);
3.437 }
3.438 };
3.439 - ///\brief \ref named-templ-param "Named parameter"
3.440 - ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
3.441 + ///\brief \ref named-templ-param "Named parameter" for setting
3.442 + ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
3.443 ///
3.444 - ///\ref named-templ-param "Named parameter"
3.445 - ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
3.446 - ///If you don't set it explicitely, it will be automatically allocated.
3.447 + ///\ref named-templ-param "Named parameter" for setting
3.448 + ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
3.449 + ///If you don't set it explicitly, it will be automatically allocated.
3.450 template <class T>
3.451 struct DefProcessedMapToBeDefaultMap
3.452 : public Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> {
3.453 @@ -413,8 +423,7 @@
3.454 ///heap and cross reference type
3.455 ///
3.456 ///\ref named-templ-param "Named parameter" for setting heap and cross
3.457 - ///reference type
3.458 - ///
3.459 + ///reference type.
3.460 template <class H, class CR = typename Digraph::template NodeMap<int> >
3.461 struct DefHeap
3.462 : public Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > {
3.463 @@ -453,10 +462,10 @@
3.464 };
3.465
3.466 /// \brief \ref named-templ-param "Named parameter" for setting
3.467 - /// OperationTraits type
3.468 + ///\ref OperationTraits type
3.469 ///
3.470 - /// \ref named-templ-param "Named parameter" for setting OperationTraits
3.471 - /// type
3.472 + ///\ref named-templ-param "Named parameter" for setting
3.473 + ///\ref OperationTraits type.
3.474 template <class T>
3.475 struct DefOperationTraits
3.476 : public Dijkstra<Digraph, LengthMap, DefOperationTraitsTraits<T> > {
3.477 @@ -466,7 +475,6 @@
3.478
3.479 ///@}
3.480
3.481 -
3.482 protected:
3.483
3.484 Dijkstra() {}
3.485 @@ -475,10 +483,11 @@
3.486
3.487 ///Constructor.
3.488
3.489 - ///\param _G the digraph the algorithm will run on.
3.490 - ///\param _length the length map used by the algorithm.
3.491 - Dijkstra(const Digraph& _G, const LengthMap& _length) :
3.492 - G(&_G), length(&_length),
3.493 + ///Constructor.
3.494 + ///\param _g The digraph the algorithm runs on.
3.495 + ///\param _length The length map used by the algorithm.
3.496 + Dijkstra(const Digraph& _g, const LengthMap& _length) :
3.497 + G(&_g), length(&_length),
3.498 _pred(NULL), local_pred(false),
3.499 _dist(NULL), local_dist(false),
3.500 _processed(NULL), local_processed(false),
3.501 @@ -506,11 +515,11 @@
3.502 return *this;
3.503 }
3.504
3.505 - ///Sets the map storing the predecessor arcs.
3.506 + ///Sets the map that stores the predecessor arcs.
3.507
3.508 - ///Sets the map storing the predecessor arcs.
3.509 + ///Sets the map that stores the predecessor arcs.
3.510 ///If you don't use this function before calling \ref run(),
3.511 - ///it will allocate one. The destuctor deallocates this
3.512 + ///it will allocate one. The destructor deallocates this
3.513 ///automatically allocated map, of course.
3.514 ///\return <tt> (*this) </tt>
3.515 Dijkstra &predMap(PredMap &m)
3.516 @@ -523,11 +532,29 @@
3.517 return *this;
3.518 }
3.519
3.520 - ///Sets the map storing the distances calculated by the algorithm.
3.521 + ///Sets the map that indicates which nodes are processed.
3.522
3.523 - ///Sets the map storing the distances calculated by the algorithm.
3.524 + ///Sets the map that indicates which nodes are processed.
3.525 ///If you don't use this function before calling \ref run(),
3.526 - ///it will allocate one. The destuctor deallocates this
3.527 + ///it will allocate one. The destructor deallocates this
3.528 + ///automatically allocated map, of course.
3.529 + ///\return <tt> (*this) </tt>
3.530 + Dijkstra &processedMap(ProcessedMap &m)
3.531 + {
3.532 + if(local_processed) {
3.533 + delete _processed;
3.534 + local_processed=false;
3.535 + }
3.536 + _processed = &m;
3.537 + return *this;
3.538 + }
3.539 +
3.540 + ///Sets the map that stores the distances of the nodes.
3.541 +
3.542 + ///Sets the map that stores the distances of the nodes calculated by the
3.543 + ///algorithm.
3.544 + ///If you don't use this function before calling \ref run(),
3.545 + ///it will allocate one. The destructor deallocates this
3.546 ///automatically allocated map, of course.
3.547 ///\return <tt> (*this) </tt>
3.548 Dijkstra &distMap(DistMap &m)
3.549 @@ -544,7 +571,7 @@
3.550
3.551 ///Sets the heap and the cross reference used by algorithm.
3.552 ///If you don't use this function before calling \ref run(),
3.553 - ///it will allocate one. The destuctor deallocates this
3.554 + ///it will allocate one. The destructor deallocates this
3.555 ///automatically allocated heap and cross reference, of course.
3.556 ///\return <tt> (*this) </tt>
3.557 Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
3.558 @@ -563,6 +590,7 @@
3.559 }
3.560
3.561 private:
3.562 +
3.563 void finalizeNodeData(Node v,Value dst)
3.564 {
3.565 _processed->set(v,true);
3.566 @@ -571,17 +599,15 @@
3.567
3.568 public:
3.569
3.570 - typedef PredMapPath<Digraph, PredMap> Path;
3.571 -
3.572 ///\name Execution control
3.573 - ///The simplest way to execute the algorithm is to use
3.574 - ///one of the member functions called \c run(...).
3.575 + ///The simplest way to execute the algorithm is to use one of the
3.576 + ///member functions called \ref lemon::Dijkstra::run() "run()".
3.577 ///\n
3.578 - ///If you need more control on the execution,
3.579 - ///first you must call \ref init(), then you can add several source nodes
3.580 - ///with \ref addSource().
3.581 - ///Finally \ref start() will perform the actual path
3.582 - ///computation.
3.583 + ///If you need more control on the execution, first you must call
3.584 + ///\ref lemon::Dijkstra::init() "init()", then you can add several
3.585 + ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
3.586 + ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
3.587 + ///actual path computation.
3.588
3.589 ///@{
3.590
3.591 @@ -603,10 +629,9 @@
3.592 ///Adds a new source node.
3.593
3.594 ///Adds a new source node to the priority heap.
3.595 - ///
3.596 ///The optional second parameter is the initial distance of the node.
3.597 ///
3.598 - ///It checks if the node has already been added to the heap and
3.599 + ///The function checks if the node has already been added to the heap and
3.600 ///it is pushed to the heap only if either it was not in the heap
3.601 ///or the shortest path found till then is shorter than \c dst.
3.602 void addSource(Node s,Value dst=OperationTraits::zero())
3.603 @@ -625,7 +650,7 @@
3.604 ///
3.605 ///\return The processed node.
3.606 ///
3.607 - ///\warning The priority heap must not be empty!
3.608 + ///\warning The priority heap must not be empty.
3.609 Node processNextNode()
3.610 {
3.611 Node v=_heap->top();
3.612 @@ -656,62 +681,66 @@
3.613 return v;
3.614 }
3.615
3.616 - ///Next node to be processed.
3.617 + ///The next node to be processed.
3.618
3.619 - ///Next node to be processed.
3.620 - ///
3.621 - ///\return The next node to be processed or INVALID if the priority heap
3.622 - /// is empty.
3.623 - Node nextNode()
3.624 + ///Returns the next node to be processed or \c INVALID if the
3.625 + ///priority heap is empty.
3.626 + Node nextNode() const
3.627 {
3.628 return !_heap->empty()?_heap->top():INVALID;
3.629 }
3.630
3.631 ///\brief Returns \c false if there are nodes
3.632 - ///to be processed in the priority heap
3.633 + ///to be processed.
3.634 ///
3.635 ///Returns \c false if there are nodes
3.636 - ///to be processed in the priority heap
3.637 - bool emptyQueue() { return _heap->empty(); }
3.638 + ///to be processed in the priority heap.
3.639 + bool emptyQueue() const { return _heap->empty(); }
3.640 +
3.641 ///Returns the number of the nodes to be processed in the priority heap
3.642
3.643 - ///Returns the number of the nodes to be processed in the priority heap
3.644 + ///Returns the number of the nodes to be processed in the priority heap.
3.645 ///
3.646 - int queueSize() { return _heap->size(); }
3.647 + int queueSize() const { return _heap->size(); }
3.648
3.649 ///Executes the algorithm.
3.650
3.651 ///Executes the algorithm.
3.652 ///
3.653 - ///\pre init() must be called and at least one node should be added
3.654 - ///with addSource() before using this function.
3.655 + ///This method runs the %Dijkstra algorithm from the root node(s)
3.656 + ///in order to compute the shortest path to each node.
3.657 + ///
3.658 + ///The algorithm computes
3.659 + ///- the shortest path tree (forest),
3.660 + ///- the distance of each node from the root(s).
3.661 + ///
3.662 + ///\pre init() must be called and at least one root node should be
3.663 + ///added with addSource() before using this function.
3.664 + ///
3.665 + ///\note <tt>d.start()</tt> is just a shortcut of the following code.
3.666 + ///\code
3.667 + /// while ( !d.emptyQueue() ) {
3.668 + /// d.processNextNode();
3.669 + /// }
3.670 + ///\endcode
3.671 + void start()
3.672 + {
3.673 + while ( !emptyQueue() ) processNextNode();
3.674 + }
3.675 +
3.676 + ///Executes the algorithm until the given target node is reached.
3.677 +
3.678 + ///Executes the algorithm until the given target node is reached.
3.679 ///
3.680 ///This method runs the %Dijkstra algorithm from the root node(s)
3.681 - ///in order to
3.682 - ///compute the
3.683 - ///shortest path to each node. The algorithm computes
3.684 - ///- The shortest path tree.
3.685 - ///- The distance of each node from the root(s).
3.686 + ///in order to compute the shortest path to \c dest.
3.687 ///
3.688 - void start()
3.689 - {
3.690 - while ( !_heap->empty() ) processNextNode();
3.691 - }
3.692 -
3.693 - ///Executes the algorithm until \c dest is reached.
3.694 -
3.695 - ///Executes the algorithm until \c dest is reached.
3.696 + ///The algorithm computes
3.697 + ///- the shortest path to \c dest,
3.698 + ///- the distance of \c dest from the root(s).
3.699 ///
3.700 - ///\pre init() must be called and at least one node should be added
3.701 - ///with addSource() before using this function.
3.702 - ///
3.703 - ///This method runs the %Dijkstra algorithm from the root node(s)
3.704 - ///in order to
3.705 - ///compute the
3.706 - ///shortest path to \c dest. The algorithm computes
3.707 - ///- The shortest path to \c dest.
3.708 - ///- The distance of \c dest from the root(s).
3.709 - ///
3.710 + ///\pre init() must be called and at least one root node should be
3.711 + ///added with addSource() before using this function.
3.712 void start(Node dest)
3.713 {
3.714 while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
3.715 @@ -722,14 +751,18 @@
3.716
3.717 ///Executes the algorithm until a condition is met.
3.718 ///
3.719 - ///\pre init() must be called and at least one node should be added
3.720 - ///with addSource() before using this function.
3.721 + ///This method runs the %Dijkstra algorithm from the root node(s) in
3.722 + ///order to compute the shortest path to a node \c v with
3.723 + /// <tt>nm[v]</tt> true, if such a node can be found.
3.724 ///
3.725 - ///\param nm must be a bool (or convertible) node map. The algorithm
3.726 + ///\param nm A \c bool (or convertible) node map. The algorithm
3.727 ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
3.728 ///
3.729 ///\return The reached node \c v with <tt>nm[v]</tt> true or
3.730 ///\c INVALID if no such node was found.
3.731 + ///
3.732 + ///\pre init() must be called and at least one root node should be
3.733 + ///added with addSource() before using this function.
3.734 template<class NodeBoolMap>
3.735 Node start(const NodeBoolMap &nm)
3.736 {
3.737 @@ -739,16 +772,16 @@
3.738 return _heap->top();
3.739 }
3.740
3.741 - ///Runs %Dijkstra algorithm from node \c s.
3.742 + ///Runs the algorithm from the given node.
3.743
3.744 - ///This method runs the %Dijkstra algorithm from a root node \c s
3.745 - ///in order to
3.746 - ///compute the
3.747 - ///shortest path to each node. The algorithm computes
3.748 - ///- The shortest path tree.
3.749 - ///- The distance of each node from the root.
3.750 + ///This method runs the %Dijkstra algorithm from node \c s
3.751 + ///in order to compute the shortest path to each node.
3.752 ///
3.753 - ///\note d.run(s) is just a shortcut of the following code.
3.754 + ///The algorithm computes
3.755 + ///- the shortest path tree,
3.756 + ///- the distance of each node from the root.
3.757 + ///
3.758 + ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
3.759 ///\code
3.760 /// d.init();
3.761 /// d.addSource(s);
3.762 @@ -762,12 +795,14 @@
3.763
3.764 ///Finds the shortest path between \c s and \c t.
3.765
3.766 - ///Finds the shortest path between \c s and \c t.
3.767 + ///This method runs the %Dijkstra algorithm from node \c s
3.768 + ///in order to compute the shortest path to \c t.
3.769 ///
3.770 - ///\return The length of the shortest s---t path if there exists one,
3.771 - ///0 otherwise.
3.772 - ///\note Apart from the return value, d.run(s) is
3.773 - ///just a shortcut of the following code.
3.774 + ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
3.775 + ///if \c t is reachable form \c s, \c 0 otherwise.
3.776 + ///
3.777 + ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
3.778 + ///shortcut of the following code.
3.779 ///\code
3.780 /// d.init();
3.781 /// d.addSource(s);
3.782 @@ -785,241 +820,262 @@
3.783 ///\name Query Functions
3.784 ///The result of the %Dijkstra algorithm can be obtained using these
3.785 ///functions.\n
3.786 - ///Before the use of these functions,
3.787 - ///either run() or start() must be called.
3.788 + ///Either \ref lemon::Dijkstra::run() "run()" or
3.789 + ///\ref lemon::Dijkstra::start() "start()" must be called before
3.790 + ///using them.
3.791
3.792 ///@{
3.793
3.794 - ///Gives back the shortest path.
3.795 + ///The shortest path to a node.
3.796
3.797 - ///Gives back the shortest path.
3.798 - ///\pre The \c t should be reachable from the source.
3.799 - Path path(Node t)
3.800 - {
3.801 - return Path(*G, *_pred, t);
3.802 - }
3.803 + ///Returns the shortest path to a node.
3.804 + ///
3.805 + ///\warning \c t should be reachable from the root(s).
3.806 + ///
3.807 + ///\pre Either \ref run() or \ref start() must be called before
3.808 + ///using this function.
3.809 + Path path(Node t) const { return Path(*G, *_pred, t); }
3.810
3.811 - ///The distance of a node from the root.
3.812 + ///The distance of a node from the root(s).
3.813
3.814 - ///Returns the distance of a node from the root.
3.815 - ///\pre \ref run() must be called before using this function.
3.816 - ///\warning If node \c v in unreachable from the root the return value
3.817 - ///of this funcion is undefined.
3.818 + ///Returns the distance of a node from the root(s).
3.819 + ///
3.820 + ///\warning If node \c v is not reachable from the root(s), then
3.821 + ///the return value of this function is undefined.
3.822 + ///
3.823 + ///\pre Either \ref run() or \ref start() must be called before
3.824 + ///using this function.
3.825 Value dist(Node v) const { return (*_dist)[v]; }
3.826
3.827 - ///The current distance of a node from the root.
3.828 + ///Returns the 'previous arc' of the shortest path tree for a node.
3.829
3.830 - ///Returns the current distance of a node from the root.
3.831 - ///It may be decreased in the following processes.
3.832 - ///\pre \c node should be reached but not processed
3.833 - Value currentDist(Node v) const { return (*_heap)[v]; }
3.834 -
3.835 - ///Returns the 'previous arc' of the shortest path tree.
3.836 -
3.837 - ///For a node \c v it returns the 'previous arc' of the shortest path tree,
3.838 - ///i.e. it returns the last arc of a shortest path from the root to \c
3.839 - ///v. It is \ref INVALID
3.840 - ///if \c v is unreachable from the root or if \c v=s. The
3.841 - ///shortest path tree used here is equal to the shortest path tree used in
3.842 - ///\ref predNode(). \pre \ref run() must be called before using
3.843 - ///this function.
3.844 + ///This function returns the 'previous arc' of the shortest path
3.845 + ///tree for the node \c v, i.e. it returns the last arc of a
3.846 + ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
3.847 + ///is not reachable from the root(s) or if \c v is a root.
3.848 + ///
3.849 + ///The shortest path tree used here is equal to the shortest path
3.850 + ///tree used in \ref predNode().
3.851 + ///
3.852 + ///\pre Either \ref run() or \ref start() must be called before
3.853 + ///using this function.
3.854 Arc predArc(Node v) const { return (*_pred)[v]; }
3.855
3.856 - ///Returns the 'previous node' of the shortest path tree.
3.857 + ///Returns the 'previous node' of the shortest path tree for a node.
3.858
3.859 - ///For a node \c v it returns the 'previous node' of the shortest path tree,
3.860 - ///i.e. it returns the last but one node from a shortest path from the
3.861 - ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
3.862 - ///\c v=s. The shortest path tree used here is equal to the shortest path
3.863 - ///tree used in \ref predArc(). \pre \ref run() must be called before
3.864 + ///This function returns the 'previous node' of the shortest path
3.865 + ///tree for the node \c v, i.e. it returns the last but one node
3.866 + ///from a shortest path from the root(s) to \c v. It is \c INVALID
3.867 + ///if \c v is not reachable from the root(s) or if \c v is a root.
3.868 + ///
3.869 + ///The shortest path tree used here is equal to the shortest path
3.870 + ///tree used in \ref predArc().
3.871 + ///
3.872 + ///\pre Either \ref run() or \ref start() must be called before
3.873 ///using this function.
3.874 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
3.875 G->source((*_pred)[v]); }
3.876
3.877 - ///Returns a reference to the NodeMap of distances.
3.878 -
3.879 - ///Returns a reference to the NodeMap of distances. \pre \ref run() must
3.880 - ///be called before using this function.
3.881 + ///\brief Returns a const reference to the node map that stores the
3.882 + ///distances of the nodes.
3.883 + ///
3.884 + ///Returns a const reference to the node map that stores the distances
3.885 + ///of the nodes calculated by the algorithm.
3.886 + ///
3.887 + ///\pre Either \ref run() or \ref init()
3.888 + ///must be called before using this function.
3.889 const DistMap &distMap() const { return *_dist;}
3.890
3.891 - ///Returns a reference to the shortest path tree map.
3.892 -
3.893 - ///Returns a reference to the NodeMap of the arcs of the
3.894 - ///shortest path tree.
3.895 - ///\pre \ref run() must be called before using this function.
3.896 + ///\brief Returns a const reference to the node map that stores the
3.897 + ///predecessor arcs.
3.898 + ///
3.899 + ///Returns a const reference to the node map that stores the predecessor
3.900 + ///arcs, which form the shortest path tree.
3.901 + ///
3.902 + ///\pre Either \ref run() or \ref init()
3.903 + ///must be called before using this function.
3.904 const PredMap &predMap() const { return *_pred;}
3.905
3.906 - ///Checks if a node is reachable from the root.
3.907 + ///Checks if a node is reachable from the root(s).
3.908
3.909 - ///Returns \c true if \c v is reachable from the root.
3.910 - ///\warning The source nodes are inditated as unreached.
3.911 - ///\pre \ref run() must be called before using this function.
3.912 - ///
3.913 - bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
3.914 + ///Returns \c true if \c v is reachable from the root(s).
3.915 + ///\pre Either \ref run() or \ref start()
3.916 + ///must be called before using this function.
3.917 + bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
3.918 + Heap::PRE_HEAP; }
3.919
3.920 ///Checks if a node is processed.
3.921
3.922 ///Returns \c true if \c v is processed, i.e. the shortest
3.923 ///path to \c v has already found.
3.924 - ///\pre \ref run() must be called before using this function.
3.925 - ///
3.926 - bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
3.927 + ///\pre Either \ref run() or \ref start()
3.928 + ///must be called before using this function.
3.929 + bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
3.930 + Heap::POST_HEAP; }
3.931 +
3.932 + ///The current distance of a node from the root(s).
3.933 +
3.934 + ///Returns the current distance of a node from the root(s).
3.935 + ///It may be decreased in the following processes.
3.936 + ///\pre \c v should be reached but not processed.
3.937 + Value currentDist(Node v) const { return (*_heap)[v]; }
3.938
3.939 ///@}
3.940 };
3.941
3.942
3.943 + ///Default traits class of dijkstra() function.
3.944
3.945 -
3.946 -
3.947 - ///Default traits class of Dijkstra function.
3.948 -
3.949 - ///Default traits class of Dijkstra function.
3.950 - ///\tparam GR Digraph type.
3.951 - ///\tparam LM Type of length map.
3.952 + ///Default traits class of dijkstra() function.
3.953 + ///\tparam GR The type of the digraph.
3.954 + ///\tparam LM The type of the length map.
3.955 template<class GR, class LM>
3.956 struct DijkstraWizardDefaultTraits
3.957 {
3.958 - ///The digraph type the algorithm runs on.
3.959 + ///The type of the digraph the algorithm runs on.
3.960 typedef GR Digraph;
3.961 ///The type of the map that stores the arc lengths.
3.962
3.963 ///The type of the map that stores the arc lengths.
3.964 ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
3.965 typedef LM LengthMap;
3.966 - //The type of the length of the arcs.
3.967 + ///The type of the length of the arcs.
3.968 typedef typename LM::Value Value;
3.969 +
3.970 /// Operation traits for Dijkstra algorithm.
3.971
3.972 - /// It defines the used operation by the algorithm.
3.973 + /// This class defines the operations that are used in the algorithm.
3.974 /// \see DijkstraDefaultOperationTraits
3.975 typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
3.976 - ///The heap type used by Dijkstra algorithm.
3.977
3.978 - /// The cross reference type used by heap.
3.979 + /// The cross reference type used by the heap.
3.980
3.981 - /// The cross reference type used by heap.
3.982 + /// The cross reference type used by the heap.
3.983 /// Usually it is \c Digraph::NodeMap<int>.
3.984 typedef typename Digraph::template NodeMap<int> HeapCrossRef;
3.985 - ///Instantiates a HeapCrossRef.
3.986 + ///Instantiates a \ref HeapCrossRef.
3.987
3.988 ///This function instantiates a \ref HeapCrossRef.
3.989 - /// \param G is the digraph, to which we would like to define the
3.990 + /// \param g is the digraph, to which we would like to define the
3.991 /// HeapCrossRef.
3.992 /// \todo The digraph alone may be insufficient for the initialization
3.993 - static HeapCrossRef *createHeapCrossRef(const GR &G)
3.994 + static HeapCrossRef *createHeapCrossRef(const Digraph &g)
3.995 {
3.996 - return new HeapCrossRef(G);
3.997 + return new HeapCrossRef(g);
3.998 }
3.999
3.1000 - ///The heap type used by Dijkstra algorithm.
3.1001 + ///The heap type used by the Dijkstra algorithm.
3.1002
3.1003 - ///The heap type used by Dijkstra algorithm.
3.1004 + ///The heap type used by the Dijkstra algorithm.
3.1005 ///
3.1006 ///\sa BinHeap
3.1007 ///\sa Dijkstra
3.1008 - typedef BinHeap<typename LM::Value, typename GR::template NodeMap<int>,
3.1009 + typedef BinHeap<Value, typename Digraph::template NodeMap<int>,
3.1010 std::less<Value> > Heap;
3.1011
3.1012 - static Heap *createHeap(HeapCrossRef& R)
3.1013 + ///Instantiates a \ref Heap.
3.1014 +
3.1015 + ///This function instantiates a \ref Heap.
3.1016 + /// \param r is the HeapCrossRef which is used.
3.1017 + static Heap *createHeap(HeapCrossRef& r)
3.1018 {
3.1019 - return new Heap(R);
3.1020 + return new Heap(r);
3.1021 }
3.1022
3.1023 - ///\brief The type of the map that stores the last
3.1024 + ///\brief The type of the map that stores the predecessor
3.1025 ///arcs of the shortest paths.
3.1026 ///
3.1027 - ///The type of the map that stores the last
3.1028 + ///The type of the map that stores the predecessor
3.1029 ///arcs of the shortest paths.
3.1030 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
3.1031 - ///
3.1032 - typedef NullMap <typename GR::Node,typename GR::Arc> PredMap;
3.1033 - ///Instantiates a PredMap.
3.1034 + typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;
3.1035 + ///Instantiates a \ref PredMap.
3.1036
3.1037 ///This function instantiates a \ref PredMap.
3.1038 - ///\param g is the digraph, to which we would like to define the PredMap.
3.1039 - ///\todo The digraph alone may be insufficient for the initialization
3.1040 + ///\param g is the digraph, to which we would like to define the
3.1041 + ///\ref PredMap.
3.1042 + ///\todo The digraph alone may be insufficient to initialize
3.1043 #ifdef DOXYGEN
3.1044 - static PredMap *createPredMap(const GR &g)
3.1045 + static PredMap *createPredMap(const Digraph &g)
3.1046 #else
3.1047 - static PredMap *createPredMap(const GR &)
3.1048 + static PredMap *createPredMap(const Digraph &)
3.1049 #endif
3.1050 {
3.1051 return new PredMap();
3.1052 }
3.1053 - ///The type of the map that stores whether a nodes is processed.
3.1054
3.1055 - ///The type of the map that stores whether a nodes is processed.
3.1056 + ///The type of the map that indicates which nodes are processed.
3.1057 +
3.1058 + ///The type of the map that indicates which nodes are processed.
3.1059 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
3.1060 ///By default it is a NullMap.
3.1061 ///\todo If it is set to a real map,
3.1062 ///Dijkstra::processed() should read this.
3.1063 ///\todo named parameter to set this type, function to read and write.
3.1064 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
3.1065 - ///Instantiates a ProcessedMap.
3.1066 + ///Instantiates a \ref ProcessedMap.
3.1067
3.1068 ///This function instantiates a \ref ProcessedMap.
3.1069 ///\param g is the digraph, to which
3.1070 - ///we would like to define the \ref ProcessedMap
3.1071 + ///we would like to define the \ref ProcessedMap.
3.1072 #ifdef DOXYGEN
3.1073 - static ProcessedMap *createProcessedMap(const GR &g)
3.1074 + static ProcessedMap *createProcessedMap(const Digraph &g)
3.1075 #else
3.1076 - static ProcessedMap *createProcessedMap(const GR &)
3.1077 + static ProcessedMap *createProcessedMap(const Digraph &)
3.1078 #endif
3.1079 {
3.1080 return new ProcessedMap();
3.1081 }
3.1082 - ///The type of the map that stores the dists of the nodes.
3.1083
3.1084 - ///The type of the map that stores the dists of the nodes.
3.1085 + ///The type of the map that stores the distances of the nodes.
3.1086 +
3.1087 + ///The type of the map that stores the distances of the nodes.
3.1088 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
3.1089 - ///
3.1090 - typedef NullMap<typename Digraph::Node,typename LM::Value> DistMap;
3.1091 - ///Instantiates a DistMap.
3.1092 + typedef NullMap<typename Digraph::Node,Value> DistMap;
3.1093 + ///Instantiates a \ref DistMap.
3.1094
3.1095 ///This function instantiates a \ref DistMap.
3.1096 ///\param g is the digraph, to which we would like to define
3.1097 ///the \ref DistMap
3.1098 #ifdef DOXYGEN
3.1099 - static DistMap *createDistMap(const GR &g)
3.1100 + static DistMap *createDistMap(const Digraph &g)
3.1101 #else
3.1102 - static DistMap *createDistMap(const GR &)
3.1103 + static DistMap *createDistMap(const Digraph &)
3.1104 #endif
3.1105 {
3.1106 return new DistMap();
3.1107 }
3.1108 };
3.1109
3.1110 - /// Default traits used by \ref DijkstraWizard
3.1111 + /// Default traits class used by \ref DijkstraWizard
3.1112
3.1113 /// To make it easier to use Dijkstra algorithm
3.1114 - ///we have created a wizard class.
3.1115 + /// we have created a wizard class.
3.1116 /// This \ref DijkstraWizard class needs default traits,
3.1117 - ///as well as the \ref Dijkstra class.
3.1118 + /// as well as the \ref Dijkstra class.
3.1119 /// The \ref DijkstraWizardBase is a class to be the default traits of the
3.1120 /// \ref DijkstraWizard class.
3.1121 /// \todo More named parameters are required...
3.1122 template<class GR,class LM>
3.1123 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
3.1124 {
3.1125 -
3.1126 typedef DijkstraWizardDefaultTraits<GR,LM> Base;
3.1127 protected:
3.1128 - /// Type of the nodes in the digraph.
3.1129 + //The type of the nodes in the digraph.
3.1130 typedef typename Base::Digraph::Node Node;
3.1131
3.1132 - /// Pointer to the underlying digraph.
3.1133 + //Pointer to the digraph the algorithm runs on.
3.1134 void *_g;
3.1135 - /// Pointer to the length map
3.1136 + //Pointer to the length map
3.1137 void *_length;
3.1138 - ///Pointer to the map of predecessors arcs.
3.1139 + //Pointer to the map of predecessors arcs.
3.1140 void *_pred;
3.1141 - ///Pointer to the map of distances.
3.1142 + //Pointer to the map of distances.
3.1143 void *_dist;
3.1144 - ///Pointer to the source node.
3.1145 + //Pointer to the source node.
3.1146 Node _source;
3.1147
3.1148 - public:
3.1149 + public:
3.1150 /// Constructor.
3.1151
3.1152 /// This constructor does not require parameters, therefore it initiates
3.1153 @@ -1032,9 +1088,9 @@
3.1154 /// This constructor requires some parameters,
3.1155 /// listed in the parameters list.
3.1156 /// Others are initiated to 0.
3.1157 - /// \param g is the initial value of \ref _g
3.1158 - /// \param l is the initial value of \ref _length
3.1159 - /// \param s is the initial value of \ref _source
3.1160 + /// \param g The digraph the algorithm runs on.
3.1161 + /// \param l The length map.
3.1162 + /// \param s The source node.
3.1163 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
3.1164 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
3.1165 _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
3.1166 @@ -1042,11 +1098,13 @@
3.1167
3.1168 };
3.1169
3.1170 - /// A class to make the usage of Dijkstra algorithm easier
3.1171 + /// Auxiliary class for the function type interface of Dijkstra algorithm.
3.1172
3.1173 - /// This class is created to make it easier to use Dijkstra algorithm.
3.1174 - /// It uses the functions and features of the plain \ref Dijkstra,
3.1175 - /// but it is much simpler to use it.
3.1176 + /// This auxiliary class is created to implement the function type
3.1177 + /// interface of \ref Dijkstra algorithm. It uses the functions and features
3.1178 + /// of the plain \ref Dijkstra, but it is much simpler to use it.
3.1179 + /// It should only be used through the \ref dijkstra() function, which makes
3.1180 + /// it easier to use the algorithm.
3.1181 ///
3.1182 /// Simplicity means that the way to change the types defined
3.1183 /// in the traits class is based on functions that returns the new class
3.1184 @@ -1055,40 +1113,41 @@
3.1185 /// the new class with the modified type comes from
3.1186 /// the original class by using the ::
3.1187 /// operator. In the case of \ref DijkstraWizard only
3.1188 - /// a function have to be called and it will
3.1189 + /// a function have to be called, and it will
3.1190 /// return the needed class.
3.1191 ///
3.1192 - /// It does not have own \ref run method. When its \ref run method is called
3.1193 - /// it initiates a plain \ref Dijkstra class, and calls the \ref
3.1194 - /// Dijkstra::run method of it.
3.1195 + /// It does not have own \ref run() method. When its \ref run() method
3.1196 + /// is called, it initiates a plain \ref Dijkstra object, and calls the
3.1197 + /// \ref Dijkstra::run() method of it.
3.1198 template<class TR>
3.1199 class DijkstraWizard : public TR
3.1200 {
3.1201 typedef TR Base;
3.1202
3.1203 - ///The type of the underlying digraph.
3.1204 + ///The type of the digraph the algorithm runs on.
3.1205 typedef typename TR::Digraph Digraph;
3.1206 - //\e
3.1207 +
3.1208 typedef typename Digraph::Node Node;
3.1209 - //\e
3.1210 typedef typename Digraph::NodeIt NodeIt;
3.1211 - //\e
3.1212 typedef typename Digraph::Arc Arc;
3.1213 - //\e
3.1214 typedef typename Digraph::OutArcIt OutArcIt;
3.1215
3.1216 ///The type of the map that stores the arc lengths.
3.1217 typedef typename TR::LengthMap LengthMap;
3.1218 ///The type of the length of the arcs.
3.1219 typedef typename LengthMap::Value Value;
3.1220 - ///\brief The type of the map that stores the last
3.1221 + ///\brief The type of the map that stores the predecessor
3.1222 ///arcs of the shortest paths.
3.1223 typedef typename TR::PredMap PredMap;
3.1224 - ///The type of the map that stores the dists of the nodes.
3.1225 + ///The type of the map that stores the distances of the nodes.
3.1226 typedef typename TR::DistMap DistMap;
3.1227 + ///The type of the map that indicates which nodes are processed.
3.1228 + typedef typename TR::ProcessedMap ProcessedMap;
3.1229 ///The heap type used by the dijkstra algorithm.
3.1230 typedef typename TR::Heap Heap;
3.1231 +
3.1232 public:
3.1233 +
3.1234 /// Constructor.
3.1235 DijkstraWizard() : TR() {}
3.1236
3.1237 @@ -1104,10 +1163,10 @@
3.1238
3.1239 ~DijkstraWizard() {}
3.1240
3.1241 - ///Runs Dijkstra algorithm from a given node.
3.1242 + ///Runs Dijkstra algorithm from a source node.
3.1243
3.1244 - ///Runs Dijkstra algorithm from a given node.
3.1245 - ///The node can be given by the \ref source function.
3.1246 + ///Runs Dijkstra algorithm from a source node.
3.1247 + ///The node can be given with the \ref source() function.
3.1248 void run()
3.1249 {
3.1250 if(Base::_source==INVALID) throw UninitializedParameter();
3.1251 @@ -1129,19 +1188,27 @@
3.1252 run();
3.1253 }
3.1254
3.1255 + /// Sets the source node, from which the Dijkstra algorithm runs.
3.1256 +
3.1257 + /// Sets the source node, from which the Dijkstra algorithm runs.
3.1258 + /// \param s is the source node.
3.1259 + DijkstraWizard<TR> &source(Node s)
3.1260 + {
3.1261 + Base::_source=s;
3.1262 + return *this;
3.1263 + }
3.1264 +
3.1265 template<class T>
3.1266 struct DefPredMapBase : public Base {
3.1267 typedef T PredMap;
3.1268 static PredMap *createPredMap(const Digraph &) { return 0; };
3.1269 DefPredMapBase(const TR &b) : TR(b) {}
3.1270 };
3.1271 -
3.1272 ///\brief \ref named-templ-param "Named parameter"
3.1273 - ///function for setting PredMap type
3.1274 + ///for setting \ref PredMap object.
3.1275 ///
3.1276 - /// \ref named-templ-param "Named parameter"
3.1277 - ///function for setting PredMap type
3.1278 - ///
3.1279 + ///\ref named-templ-param "Named parameter"
3.1280 + ///for setting \ref PredMap object.
3.1281 template<class T>
3.1282 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
3.1283 {
3.1284 @@ -1150,18 +1217,34 @@
3.1285 }
3.1286
3.1287 template<class T>
3.1288 + struct DefProcessedMapBase : public Base {
3.1289 + typedef T ProcessedMap;
3.1290 + static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
3.1291 + DefProcessedMapBase(const TR &b) : TR(b) {}
3.1292 + };
3.1293 + ///\brief \ref named-templ-param "Named parameter"
3.1294 + ///for setting \ref ProcessedMap object.
3.1295 + ///
3.1296 + /// \ref named-templ-param "Named parameter"
3.1297 + ///for setting \ref ProcessedMap object.
3.1298 + template<class T>
3.1299 + DijkstraWizard<DefProcessedMapBase<T> > processedMap(const T &t)
3.1300 + {
3.1301 + Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
3.1302 + return DijkstraWizard<DefProcessedMapBase<T> >(*this);
3.1303 + }
3.1304 +
3.1305 + template<class T>
3.1306 struct DefDistMapBase : public Base {
3.1307 typedef T DistMap;
3.1308 static DistMap *createDistMap(const Digraph &) { return 0; };
3.1309 DefDistMapBase(const TR &b) : TR(b) {}
3.1310 };
3.1311 -
3.1312 ///\brief \ref named-templ-param "Named parameter"
3.1313 - ///function for setting DistMap type
3.1314 + ///for setting \ref DistMap object.
3.1315 ///
3.1316 - /// \ref named-templ-param "Named parameter"
3.1317 - ///function for setting DistMap type
3.1318 - ///
3.1319 + ///\ref named-templ-param "Named parameter"
3.1320 + ///for setting \ref DistMap object.
3.1321 template<class T>
3.1322 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
3.1323 {
3.1324 @@ -1169,16 +1252,6 @@
3.1325 return DijkstraWizard<DefDistMapBase<T> >(*this);
3.1326 }
3.1327
3.1328 - /// Sets the source node, from which the Dijkstra algorithm runs.
3.1329 -
3.1330 - /// Sets the source node, from which the Dijkstra algorithm runs.
3.1331 - /// \param s is the source node.
3.1332 - DijkstraWizard<TR> &source(Node s)
3.1333 - {
3.1334 - Base::_source=s;
3.1335 - return *this;
3.1336 - }
3.1337 -
3.1338 };
3.1339
3.1340 ///Function type interface for Dijkstra algorithm.