Changes in lemon/bfs.h [220:a5d8c039f218:301:9db8964f0cf6] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r220 r301 22 22 ///\ingroup search 23 23 ///\file 24 ///\brief B fsalgorithm.24 ///\brief BFS algorithm. 25 25 26 26 #include <lemon/list_graph.h> … … 29 29 #include <lemon/error.h> 30 30 #include <lemon/maps.h> 31 #include <lemon/path.h> 31 32 32 33 namespace lemon { 33 34 35 34 36 35 ///Default traits class of Bfs class. … … 41 40 struct BfsDefaultTraits 42 41 { 43 ///The digraph typethe algorithm runs on.42 ///The type of the digraph the algorithm runs on. 44 43 typedef GR Digraph; 45 ///\brief The type of the map that stores the last 44 45 ///\brief The type of the map that stores the predecessor 46 46 ///arcs of the shortest paths. 47 47 /// 48 ///The type of the map that stores the last48 ///The type of the map that stores the predecessor 49 49 ///arcs of the shortest paths. 50 50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 51 /// 52 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap; 51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 53 52 ///Instantiates a PredMap. 54 53 55 ///This function instantiates a \ref PredMap. 56 ///\param G is the digraph, to which we would like to define the PredMap. 57 ///\todo The digraph alone may be insufficient to initialize 58 static PredMap *createPredMap(const GR &G) 59 { 60 return new PredMap(G); 61 } 54 ///This function instantiates a PredMap. 55 ///\param g is the digraph, to which we would like to define the 56 ///PredMap. 57 static PredMap *createPredMap(const Digraph &g) 58 { 59 return new PredMap(g); 60 } 61 62 62 ///The type of the map that indicates which nodes are processed. 63 63 64 64 ///The type of the map that indicates which nodes are processed. 65 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 66 ///\todo named parameter to set this type, function to read and write.67 66 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 68 67 ///Instantiates a ProcessedMap. 69 68 70 ///This function instantiates a \refProcessedMap.69 ///This function instantiates a ProcessedMap. 71 70 ///\param g is the digraph, to which 72 ///we would like to define the \refProcessedMap71 ///we would like to define the ProcessedMap 73 72 #ifdef DOXYGEN 74 static ProcessedMap *createProcessedMap(const GR&g)73 static ProcessedMap *createProcessedMap(const Digraph &g) 75 74 #else 76 static ProcessedMap *createProcessedMap(const GR&)75 static ProcessedMap *createProcessedMap(const Digraph &) 77 76 #endif 78 77 { 79 78 return new ProcessedMap(); 80 79 } 80 81 81 ///The type of the map that indicates which nodes are reached. 82 82 83 83 ///The type of the map that indicates which nodes are reached. 84 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 85 ///\todo named parameter to set this type, function to read and write. 84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 86 85 typedef typename Digraph::template NodeMap<bool> ReachedMap; 87 86 ///Instantiates a ReachedMap. 88 87 89 ///This function instantiates a \ref ReachedMap. 90 ///\param G is the digraph, to which 91 ///we would like to define the \ref ReachedMap. 92 static ReachedMap *createReachedMap(const GR &G) 93 { 94 return new ReachedMap(G); 95 } 96 ///The type of the map that stores the dists of the nodes. 97 98 ///The type of the map that stores the dists of the nodes. 88 ///This function instantiates a ReachedMap. 89 ///\param g is the digraph, to which 90 ///we would like to define the ReachedMap. 91 static ReachedMap *createReachedMap(const Digraph &g) 92 { 93 return new ReachedMap(g); 94 } 95 96 ///The type of the map that stores the distances of the nodes. 97 98 ///The type of the map that stores the distances of the nodes. 99 99 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 100 ///101 100 typedef typename Digraph::template NodeMap<int> DistMap; 102 101 ///Instantiates a DistMap. 103 102 104 ///This function instantiates a \refDistMap.105 ///\param G is the digraph, to which we would like to define106 /// the \ref DistMap107 static DistMap *createDistMap(const GR &G)108 { 109 return new DistMap( G);103 ///This function instantiates a DistMap. 104 ///\param g is the digraph, to which we would like to define the 105 ///DistMap. 106 static DistMap *createDistMap(const Digraph &g) 107 { 108 return new DistMap(g); 110 109 } 111 110 }; … … 116 115 ///This class provides an efficient implementation of the %BFS algorithm. 117 116 /// 118 ///\tparam GR The digraph type the algorithm runs on. The default value is 119 ///\ref ListDigraph. The value of GR is not used directly by Bfs, it 120 ///is only passed to \ref BfsDefaultTraits. 117 ///There is also a \ref bfs() "function-type interface" for the BFS 118 ///algorithm, which is convenient in the simplier cases and it can be 119 ///used easier. 120 /// 121 ///\tparam GR The type of the digraph the algorithm runs on. 122 ///The default value is \ref ListDigraph. The value of GR is not used 123 ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits. 121 124 ///\tparam TR Traits class to set various data types used by the algorithm. 122 125 ///The default traits class is … … 124 127 ///See \ref BfsDefaultTraits for the documentation of 125 128 ///a Bfs traits class. 126 127 129 #ifdef DOXYGEN 128 130 template <typename GR, … … 134 136 class Bfs { 135 137 public: 136 /** 137 * \brief \ref Exception for uninitialized parameters. 138 * 139 * This error represents problems in the initialization 140 * of the parameters of the algorithms. 141 */ 142 class UninitializedParameter : public lemon::UninitializedParameter { 143 public: 144 virtual const char* what() const throw() { 145 return "lemon::Bfs::UninitializedParameter"; 146 } 147 }; 148 138 139 ///The type of the digraph the algorithm runs on. 140 typedef typename TR::Digraph Digraph; 141 142 ///\brief The type of the map that stores the predecessor arcs of the 143 ///shortest paths. 144 typedef typename TR::PredMap PredMap; 145 ///The type of the map that stores the distances of the nodes. 146 typedef typename TR::DistMap DistMap; 147 ///The type of the map that indicates which nodes are reached. 148 typedef typename TR::ReachedMap ReachedMap; 149 ///The type of the map that indicates which nodes are processed. 150 typedef typename TR::ProcessedMap ProcessedMap; 151 ///The type of the paths. 152 typedef PredMapPath<Digraph, PredMap> Path; 153 154 ///The traits class. 149 155 typedef TR Traits; 150 ///The type of the underlying digraph. 151 typedef typename TR::Digraph Digraph; 152 153 ///\brief The type of the map that stores the last 154 ///arcs of the shortest paths. 155 typedef typename TR::PredMap PredMap; 156 ///The type of the map indicating which nodes are reached. 157 typedef typename TR::ReachedMap ReachedMap; 158 ///The type of the map indicating which nodes are processed. 159 typedef typename TR::ProcessedMap ProcessedMap; 160 ///The type of the map that stores the dists of the nodes. 161 typedef typename TR::DistMap DistMap; 156 162 157 private: 163 158 … … 167 162 typedef typename Digraph::OutArcIt OutArcIt; 168 163 169 // /Pointer to the underlying digraph.164 //Pointer to the underlying digraph. 170 165 const Digraph *G; 171 // /Pointer to the map of predecessorsarcs.166 //Pointer to the map of predecessor arcs. 172 167 PredMap *_pred; 173 // /Indicates if \ref _pred is locally allocated (\ctrue) or not.168 //Indicates if _pred is locally allocated (true) or not. 174 169 bool local_pred; 175 // /Pointer to the map of distances.170 //Pointer to the map of distances. 176 171 DistMap *_dist; 177 // /Indicates if \ref _dist is locally allocated (\ctrue) or not.172 //Indicates if _dist is locally allocated (true) or not. 178 173 bool local_dist; 179 // /Pointer to the map of reached status of the nodes.174 //Pointer to the map of reached status of the nodes. 180 175 ReachedMap *_reached; 181 // /Indicates if \ref _reached is locally allocated (\ctrue) or not.176 //Indicates if _reached is locally allocated (true) or not. 182 177 bool local_reached; 183 // /Pointer to the map of processed status of the nodes.178 //Pointer to the map of processed status of the nodes. 184 179 ProcessedMap *_processed; 185 // /Indicates if \ref _processed is locally allocated (\ctrue) or not.180 //Indicates if _processed is locally allocated (true) or not. 186 181 bool local_processed; 187 182 … … 190 185 int _curr_dist; 191 186 192 ///Creates the maps if necessary. 193 194 ///\todo Better memory allocation (instead of new). 187 //Creates the maps if necessary. 195 188 void create_maps() 196 189 { … … 226 219 227 220 template <class T> 228 struct DefPredMapTraits : public Traits {221 struct SetPredMapTraits : public Traits { 229 222 typedef T PredMap; 230 223 static PredMap *createPredMap(const Digraph &) 231 224 { 232 throw UninitializedParameter(); 225 LEMON_ASSERT(false, "PredMap is not initialized"); 226 return 0; // ignore warnings 233 227 } 234 228 }; 235 229 ///\brief \ref named-templ-param "Named parameter" for setting 236 ///PredMap type 237 /// 238 ///\ref named-templ-param "Named parameter" for setting PredMap type239 /// 230 ///PredMap type. 231 /// 232 ///\ref named-templ-param "Named parameter" for setting 233 ///PredMap type. 240 234 template <class T> 241 struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {242 typedef Bfs< Digraph, DefPredMapTraits<T> > Create;235 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { 236 typedef Bfs< Digraph, SetPredMapTraits<T> > Create; 243 237 }; 244 238 245 239 template <class T> 246 struct DefDistMapTraits : public Traits {240 struct SetDistMapTraits : public Traits { 247 241 typedef T DistMap; 248 242 static DistMap *createDistMap(const Digraph &) 249 243 { 250 throw UninitializedParameter(); 244 LEMON_ASSERT(false, "DistMap is not initialized"); 245 return 0; // ignore warnings 251 246 } 252 247 }; 253 248 ///\brief \ref named-templ-param "Named parameter" for setting 254 ///DistMap type 255 /// 256 ///\ref named-templ-param "Named parameter" for setting DistMap type257 /// 249 ///DistMap type. 250 /// 251 ///\ref named-templ-param "Named parameter" for setting 252 ///DistMap type. 258 253 template <class T> 259 struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {260 typedef Bfs< Digraph, DefDistMapTraits<T> > Create;254 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { 255 typedef Bfs< Digraph, SetDistMapTraits<T> > Create; 261 256 }; 262 257 263 258 template <class T> 264 struct DefReachedMapTraits : public Traits {259 struct SetReachedMapTraits : public Traits { 265 260 typedef T ReachedMap; 266 261 static ReachedMap *createReachedMap(const Digraph &) 267 262 { 268 throw UninitializedParameter(); 263 LEMON_ASSERT(false, "ReachedMap is not initialized"); 264 return 0; // ignore warnings 269 265 } 270 266 }; 271 267 ///\brief \ref named-templ-param "Named parameter" for setting 272 ///ReachedMap type 273 /// 274 ///\ref named-templ-param "Named parameter" for setting ReachedMap type275 /// 268 ///ReachedMap type. 269 /// 270 ///\ref named-templ-param "Named parameter" for setting 271 ///ReachedMap type. 276 272 template <class T> 277 struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {278 typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;273 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { 274 typedef Bfs< Digraph, SetReachedMapTraits<T> > Create; 279 275 }; 280 276 281 277 template <class T> 282 struct DefProcessedMapTraits : public Traits {278 struct SetProcessedMapTraits : public Traits { 283 279 typedef T ProcessedMap; 284 280 static ProcessedMap *createProcessedMap(const Digraph &) 285 281 { 286 throw UninitializedParameter(); 282 LEMON_ASSERT(false, "ProcessedMap is not initialized"); 283 return 0; // ignore warnings 287 284 } 288 285 }; 289 286 ///\brief \ref named-templ-param "Named parameter" for setting 290 ///ProcessedMap type 291 /// 292 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type293 /// 287 ///ProcessedMap type. 288 /// 289 ///\ref named-templ-param "Named parameter" for setting 290 ///ProcessedMap type. 294 291 template <class T> 295 struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {296 typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;292 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { 293 typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create; 297 294 }; 298 295 299 struct DefDigraphProcessedMapTraits : public Traits {296 struct SetStandardProcessedMapTraits : public Traits { 300 297 typedef typename Digraph::template NodeMap<bool> ProcessedMap; 301 static ProcessedMap *createProcessedMap(const Digraph & G)298 static ProcessedMap *createProcessedMap(const Digraph &g) 302 299 { 303 return new ProcessedMap(G); 300 return new ProcessedMap(g); 301 return 0; // ignore warnings 304 302 } 305 303 }; 306 ///\brief \ref named-templ-param "Named parameter" 307 /// for setting the ProcessedMap type to be Digraph::NodeMap<bool>.308 /// 309 ///\ref named-templ-param "Named parameter" 310 /// for setting the ProcessedMap type to be Digraph::NodeMap<bool>.304 ///\brief \ref named-templ-param "Named parameter" for setting 305 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 306 /// 307 ///\ref named-templ-param "Named parameter" for setting 308 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 311 309 ///If you don't set it explicitly, it will be automatically allocated. 312 template <class T> 313 struct DefProcessedMapToBeDefaultMap : 314 public Bfs< Digraph, DefDigraphProcessedMapTraits> { 315 typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create; 310 struct SetStandardProcessedMap : 311 public Bfs< Digraph, SetStandardProcessedMapTraits > { 312 typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create; 316 313 }; 317 314 … … 322 319 ///Constructor. 323 320 324 /// \param _G the digraph the algorithm will run on.325 /// 326 Bfs(const Digraph & _G) :327 G(& _G),321 ///Constructor. 322 ///\param g The digraph the algorithm runs on. 323 Bfs(const Digraph &g) : 324 G(&g), 328 325 _pred(NULL), local_pred(false), 329 326 _dist(NULL), local_dist(false), … … 341 338 } 342 339 343 ///Sets the map storingthe predecessor arcs.344 345 ///Sets the map storingthe predecessor arcs.340 ///Sets the map that stores the predecessor arcs. 341 342 ///Sets the map that stores the predecessor arcs. 346 343 ///If you don't use this function before calling \ref run(), 347 344 ///it will allocate one. The destructor deallocates this … … 358 355 } 359 356 360 ///Sets the map indicating the reached nodes.361 362 ///Sets the map indicating the reached nodes.357 ///Sets the map that indicates which nodes are reached. 358 359 ///Sets the map that indicates which nodes are reached. 363 360 ///If you don't use this function before calling \ref run(), 364 361 ///it will allocate one. The destructor deallocates this … … 375 372 } 376 373 377 ///Sets the map indicating the processed nodes.378 379 ///Sets the map indicating the processed nodes.374 ///Sets the map that indicates which nodes are processed. 375 376 ///Sets the map that indicates which nodes are processed. 380 377 ///If you don't use this function before calling \ref run(), 381 378 ///it will allocate one. The destructor deallocates this … … 392 389 } 393 390 394 ///Sets the map storing the distances calculated by the algorithm. 395 396 ///Sets the map storing the distances calculated by the algorithm. 391 ///Sets the map that stores the distances of the nodes. 392 393 ///Sets the map that stores the distances of the nodes calculated by 394 ///the algorithm. 397 395 ///If you don't use this function before calling \ref run(), 398 396 ///it will allocate one. The destructor deallocates this … … 410 408 411 409 public: 410 412 411 ///\name Execution control 413 412 ///The simplest way to execute the algorithm is to use 414 ///one of the member functions called \ c run(...).413 ///one of the member functions called \ref lemon::Bfs::run() "run()". 415 414 ///\n 416 ///If you need more control on the execution, 417 /// first you must call \ref init(), then you can add several source nodes418 /// with \ref addSource().419 ///Finally \ref start() will perform the actual path420 /// computation.415 ///If you need more control on the execution, first you must call 416 ///\ref lemon::Bfs::init() "init()", then you can add several source 417 ///nodes with \ref lemon::Bfs::addSource() "addSource()". 418 ///Finally \ref lemon::Bfs::start() "start()" will perform the 419 ///actual path computation. 421 420 422 421 ///@{ 423 422 424 /// \briefInitializes the internal data structures.425 /// 423 ///Initializes the internal data structures. 424 426 425 ///Initializes the internal data structures. 427 426 /// … … 461 460 ///\return The processed node. 462 461 /// 463 ///\ warning The queue must not be empty!462 ///\pre The queue must not be empty. 464 463 Node processNextNode() 465 464 { … … 483 482 ///Processes the next node. 484 483 485 ///Processes the next node . And checks thatthe given target node484 ///Processes the next node and checks if the given target node 486 485 ///is reached. If the target node is reachable from the processed 487 ///node then the reached parameter will be set true. The reached 488 ///parameter should be initially false. 486 ///node, then the \c reach parameter will be set to \c true. 489 487 /// 490 488 ///\param target The target node. 491 ///\retval reach Indicates that the target node is reached. 489 ///\retval reach Indicates if the target node is reached. 490 ///It should be initially \c false. 491 /// 492 492 ///\return The processed node. 493 493 /// 494 ///\ warning The queue must not be empty!494 ///\pre The queue must not be empty. 495 495 Node processNextNode(Node target, bool& reach) 496 496 { … … 515 515 ///Processes the next node. 516 516 517 ///Processes the next node. And checks that at least one of 518 ///reached node has true value in the \c nm node map. If one node 519 ///with true value is reachable from the processed node then the 520 ///rnode parameter will be set to the first of such nodes. 521 /// 522 ///\param nm The node map of possible targets. 517 ///Processes the next node and checks if at least one of reached 518 ///nodes has \c true value in the \c nm node map. If one node 519 ///with \c true value is reachable from the processed node, then the 520 ///\c rnode parameter will be set to the first of such nodes. 521 /// 522 ///\param nm A \c bool (or convertible) node map that indicates the 523 ///possible targets. 523 524 ///\retval rnode The reached target node. 525 ///It should be initially \c INVALID. 526 /// 524 527 ///\return The processed node. 525 528 /// 526 ///\ warning The queue must not be empty!529 ///\pre The queue must not be empty. 527 530 template<class NM> 528 531 Node processNextNode(const NM& nm, Node& rnode) … … 546 549 } 547 550 548 ///Next node to be processed. 549 550 ///Next node to be processed. 551 /// 552 ///\return The next node to be processed or INVALID if the queue is 553 /// empty. 554 Node nextNode() 551 ///The next node to be processed. 552 553 ///Returns the next node to be processed or \c INVALID if the queue 554 ///is empty. 555 Node nextNode() const 555 556 { 556 557 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID; … … 558 559 559 560 ///\brief Returns \c false if there are nodes 560 ///to be processed in the queue561 ///to be processed. 561 562 /// 562 563 ///Returns \c false if there are nodes 563 ///to be processed in the queue 564 bool emptyQueue() { return _queue_tail==_queue_head; } 564 ///to be processed in the queue. 565 bool emptyQueue() const { return _queue_tail==_queue_head; } 566 565 567 ///Returns the number of the nodes to be processed. 566 568 567 569 ///Returns the number of the nodes to be processed in the queue. 568 int queueSize() { return _queue_head-_queue_tail; }570 int queueSize() const { return _queue_head-_queue_tail; } 569 571 570 572 ///Executes the algorithm. … … 572 574 ///Executes the algorithm. 573 575 /// 574 ///\pre init() must be called and at least one node should be added575 ///with addSource() before using this function.576 ///577 576 ///This method runs the %BFS algorithm from the root node(s) 578 ///in order to 579 ///compute the 580 ///shortest path to each node. The algorithm computes 581 ///- The shortest path tree. 582 ///- The distance of each node from the root(s). 577 ///in order to compute the shortest path to each node. 578 /// 579 ///The algorithm computes 580 ///- the shortest path tree (forest), 581 ///- the distance of each node from the root(s). 582 /// 583 ///\pre init() must be called and at least one root node should be 584 ///added with addSource() before using this function. 585 /// 586 ///\note <tt>b.start()</tt> is just a shortcut of the following code. 587 ///\code 588 /// while ( !b.emptyQueue() ) { 589 /// b.processNextNode(); 590 /// } 591 ///\endcode 583 592 void start() 584 593 { … … 586 595 } 587 596 588 ///Executes the algorithm until \c dest is reached. 589 590 ///Executes the algorithm until \c dest is reached. 591 /// 592 ///\pre init() must be called and at least one node should be added 593 ///with addSource() before using this function. 597 ///Executes the algorithm until the given target node is reached. 598 599 ///Executes the algorithm until the given target node is reached. 594 600 /// 595 601 ///This method runs the %BFS algorithm from the root node(s) 596 ///in order to compute the shortest path to \c dest. 602 ///in order to compute the shortest path to \c t. 603 /// 597 604 ///The algorithm computes 598 ///- The shortest path to \c dest. 599 ///- The distance of \c dest from the root(s). 600 void start(Node dest) 605 ///- the shortest path to \c t, 606 ///- the distance of \c t from the root(s). 607 /// 608 ///\pre init() must be called and at least one root node should be 609 ///added with addSource() before using this function. 610 /// 611 ///\note <tt>b.start(t)</tt> is just a shortcut of the following code. 612 ///\code 613 /// bool reach = false; 614 /// while ( !b.emptyQueue() && !reach ) { 615 /// b.processNextNode(t, reach); 616 /// } 617 ///\endcode 618 void start(Node t) 601 619 { 602 620 bool reach = false; 603 while ( !emptyQueue() && !reach ) processNextNode( dest, reach);621 while ( !emptyQueue() && !reach ) processNextNode(t, reach); 604 622 } 605 623 … … 608 626 ///Executes the algorithm until a condition is met. 609 627 /// 610 /// \pre init() must be called and at least one node should be added611 /// with addSource() before using this function.612 /// 613 /// \param nm must be a bool (or convertible) node map. The614 /// algorithm will stop when it reaches a node \c v with615 /// <tt>nm[v]</tt> true.628 ///This method runs the %BFS algorithm from the root node(s) in 629 ///order to compute the shortest path to a node \c v with 630 /// <tt>nm[v]</tt> true, if such a node can be found. 631 /// 632 ///\param nm A \c bool (or convertible) node map. The algorithm 633 ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true. 616 634 /// 617 635 ///\return The reached node \c v with <tt>nm[v]</tt> true or 618 636 ///\c INVALID if no such node was found. 619 template<class NM> 620 Node start(const NM &nm) 637 /// 638 ///\pre init() must be called and at least one root node should be 639 ///added with addSource() before using this function. 640 /// 641 ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code. 642 ///\code 643 /// Node rnode = INVALID; 644 /// while ( !b.emptyQueue() && rnode == INVALID ) { 645 /// b.processNextNode(nm, rnode); 646 /// } 647 /// return rnode; 648 ///\endcode 649 template<class NodeBoolMap> 650 Node start(const NodeBoolMap &nm) 621 651 { 622 652 Node rnode = INVALID; … … 627 657 } 628 658 629 ///Runs %BFS algorithm from node \c s.630 631 ///This method runs the %BFS algorithm from a rootnode \c s632 ///in order to 633 /// compute the634 /// shortest path to each node.The algorithm computes635 ///- The shortest path tree.636 ///- The distance of each node from the root.637 /// 638 ///\note b.run(s)is just a shortcut of the following code.659 ///Runs the algorithm from the given source node. 660 661 ///This method runs the %BFS algorithm from node \c s 662 ///in order to compute the shortest path to each node. 663 /// 664 ///The algorithm computes 665 ///- the shortest path tree, 666 ///- the distance of each node from the root. 667 /// 668 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code. 639 669 ///\code 640 670 /// b.init(); … … 650 680 ///Finds the shortest path between \c s and \c t. 651 681 652 ///Finds the shortest path between \c s and \c t. 653 /// 654 ///\return The length of the shortest s---t path if there exists one, 655 ///0 otherwise. 656 ///\note Apart from the return value, b.run(s) is 657 ///just a shortcut of the following code. 682 ///This method runs the %BFS algorithm from node \c s 683 ///in order to compute the shortest path to node \c t 684 ///(it stops searching when \c t is processed). 685 /// 686 ///\return \c true if \c t is reachable form \c s. 687 /// 688 ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a 689 ///shortcut of the following code. 658 690 ///\code 659 691 /// b.init(); … … 661 693 /// b.start(t); 662 694 ///\endcode 663 intrun(Node s,Node t) {695 bool run(Node s,Node t) { 664 696 init(); 665 697 addSource(s); 666 698 start(t); 667 return reached(t) ? _curr_dist : 0; 699 return reached(t); 700 } 701 702 ///Runs the algorithm to visit all nodes in the digraph. 703 704 ///This method runs the %BFS algorithm in order to 705 ///compute the shortest path to each node. 706 /// 707 ///The algorithm computes 708 ///- the shortest path tree (forest), 709 ///- the distance of each node from the root(s). 710 /// 711 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code. 712 ///\code 713 /// b.init(); 714 /// for (NodeIt n(gr); n != INVALID; ++n) { 715 /// if (!b.reached(n)) { 716 /// b.addSource(n); 717 /// b.start(); 718 /// } 719 /// } 720 ///\endcode 721 void run() { 722 init(); 723 for (NodeIt n(*G); n != INVALID; ++n) { 724 if (!reached(n)) { 725 addSource(n); 726 start(); 727 } 728 } 668 729 } 669 730 … … 673 734 ///The result of the %BFS algorithm can be obtained using these 674 735 ///functions.\n 675 /// Before the use of these functions,676 /// either run() or start() must be calleb.736 ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start() 737 ///"start()" must be called before using them. 677 738 678 739 ///@{ 679 740 680 typedef PredMapPath<Digraph, PredMap> Path; 681 682 ///Gives back the shortest path. 683 684 ///Gives back the shortest path. 685 ///\pre The \c t should be reachable from the source. 686 Path path(Node t) 687 { 688 return Path(*G, *_pred, t); 689 } 741 ///The shortest path to a node. 742 743 ///Returns the shortest path to a node. 744 /// 745 ///\warning \c t should be reachable from the root(s). 746 /// 747 ///\pre Either \ref run() or \ref start() must be called before 748 ///using this function. 749 Path path(Node t) const { return Path(*G, *_pred, t); } 690 750 691 751 ///The distance of a node from the root(s). 692 752 693 753 ///Returns the distance of a node from the root(s). 694 ///\pre \ref run() must be called before using this function. 695 ///\warning If node \c v in unreachable from the root(s) the return value 696 ///of this function is undefined. 754 /// 755 ///\warning If node \c v is not reachable from the root(s), then 756 ///the return value of this function is undefined. 757 /// 758 ///\pre Either \ref run() or \ref start() must be called before 759 ///using this function. 697 760 int dist(Node v) const { return (*_dist)[v]; } 698 761 699 ///Returns the 'previous arc' of the shortest path tree. 700 701 ///For a node \c v it returns the 'previous arc' 702 ///of the shortest path tree, 703 ///i.e. it returns the last arc of a shortest path from the root(s) to \c 704 ///v. It is \ref INVALID 705 ///if \c v is unreachable from the root(s) or \c v is a root. The 706 ///shortest path tree used here is equal to the shortest path tree used in 707 ///\ref predNode(). 708 ///\pre Either \ref run() or \ref start() must be called before using 709 ///this function. 762 ///Returns the 'previous arc' of the shortest path tree for a node. 763 764 ///This function returns the 'previous arc' of the shortest path 765 ///tree for the node \c v, i.e. it returns the last arc of a 766 ///shortest path from the root(s) to \c v. It is \c INVALID if \c v 767 ///is not reachable from the root(s) or if \c v is a root. 768 /// 769 ///The shortest path tree used here is equal to the shortest path 770 ///tree used in \ref predNode(). 771 /// 772 ///\pre Either \ref run() or \ref start() must be called before 773 ///using this function. 710 774 Arc predArc(Node v) const { return (*_pred)[v];} 711 775 712 ///Returns the 'previous node' of the shortest path tree. 713 714 ///For a node \c v it returns the 'previous node' 715 ///of the shortest path tree, 716 ///i.e. it returns the last but one node from a shortest path from the 717 ///root(a) to \c /v. 718 ///It is INVALID if \c v is unreachable from the root(s) or 719 ///if \c v itself a root. 776 ///Returns the 'previous node' of the shortest path tree for a node. 777 778 ///This function returns the 'previous node' of the shortest path 779 ///tree for the node \c v, i.e. it returns the last but one node 780 ///from a shortest path from the root(s) to \c v. It is \c INVALID 781 ///if \c v is not reachable from the root(s) or if \c v is a root. 782 /// 720 783 ///The shortest path tree used here is equal to the shortest path 721 784 ///tree used in \ref predArc(). 785 /// 722 786 ///\pre Either \ref run() or \ref start() must be called before 723 787 ///using this function. … … 725 789 G->source((*_pred)[v]); } 726 790 727 ///Returns a reference to the NodeMap of distances. 728 729 ///Returns a reference to the NodeMap of distances. 730 ///\pre Either \ref run() or \ref init() must 731 ///be called before using this function. 791 ///\brief Returns a const reference to the node map that stores the 792 /// distances of the nodes. 793 /// 794 ///Returns a const reference to the node map that stores the distances 795 ///of the nodes calculated by the algorithm. 796 /// 797 ///\pre Either \ref run() or \ref init() 798 ///must be called before using this function. 732 799 const DistMap &distMap() const { return *_dist;} 733 800 734 ///Returns a reference to the shortest path tree map. 735 736 ///Returns a reference to the NodeMap of the arcs of the 737 ///shortest path tree. 801 ///\brief Returns a const reference to the node map that stores the 802 ///predecessor arcs. 803 /// 804 ///Returns a const reference to the node map that stores the predecessor 805 ///arcs, which form the shortest path tree. 806 /// 738 807 ///\pre Either \ref run() or \ref init() 739 808 ///must be called before using this function. 740 809 const PredMap &predMap() const { return *_pred;} 741 810 742 ///Checks if a node is reachable from the root. 743 744 ///Returns \c true if \c v is reachable from the root. 745 ///\warning The source nodes are indicated as unreached. 811 ///Checks if a node is reachable from the root(s). 812 813 ///Returns \c true if \c v is reachable from the root(s). 746 814 ///\pre Either \ref run() or \ref start() 747 815 ///must be called before using this function. 748 /// 749 bool reached(Node v) { return (*_reached)[v]; } 816 bool reached(Node v) const { return (*_reached)[v]; } 750 817 751 818 ///@} 752 819 }; 753 820 754 ///Default traits class of Bfsfunction.755 756 ///Default traits class of Bfsfunction.821 ///Default traits class of bfs() function. 822 823 ///Default traits class of bfs() function. 757 824 ///\tparam GR Digraph type. 758 825 template<class GR> 759 826 struct BfsWizardDefaultTraits 760 827 { 761 ///The digraph typethe algorithm runs on.828 ///The type of the digraph the algorithm runs on. 762 829 typedef GR Digraph; 763 ///\brief The type of the map that stores the last 830 831 ///\brief The type of the map that stores the predecessor 764 832 ///arcs of the shortest paths. 765 833 /// 766 ///The type of the map that stores the last834 ///The type of the map that stores the predecessor 767 835 ///arcs of the shortest paths. 768 836 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 769 /// 770 typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap; 837 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 771 838 ///Instantiates a PredMap. 772 839 773 ///This function instantiates a \ref PredMap. 774 ///\param g is the digraph, to which we would like to define the PredMap. 775 ///\todo The digraph alone may be insufficient to initialize 776 #ifdef DOXYGEN 777 static PredMap *createPredMap(const GR &g) 778 #else 779 static PredMap *createPredMap(const GR &) 780 #endif 781 { 782 return new PredMap(); 840 ///This function instantiates a PredMap. 841 ///\param g is the digraph, to which we would like to define the 842 ///PredMap. 843 static PredMap *createPredMap(const Digraph &g) 844 { 845 return new PredMap(g); 783 846 } 784 847 … … 787 850 ///The type of the map that indicates which nodes are processed. 788 851 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 789 /// \todo named parameter to set this type, function to read and write.852 ///By default it is a NullMap. 790 853 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 791 854 ///Instantiates a ProcessedMap. 792 855 793 ///This function instantiates a \refProcessedMap.856 ///This function instantiates a ProcessedMap. 794 857 ///\param g is the digraph, to which 795 ///we would like to define the \ref ProcessedMap858 ///we would like to define the ProcessedMap. 796 859 #ifdef DOXYGEN 797 static ProcessedMap *createProcessedMap(const GR&g)860 static ProcessedMap *createProcessedMap(const Digraph &g) 798 861 #else 799 static ProcessedMap *createProcessedMap(const GR&)862 static ProcessedMap *createProcessedMap(const Digraph &) 800 863 #endif 801 864 { 802 865 return new ProcessedMap(); 803 866 } 867 804 868 ///The type of the map that indicates which nodes are reached. 805 869 806 870 ///The type of the map that indicates which nodes are reached. 807 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 808 ///\todo named parameter to set this type, function to read and write. 871 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 809 872 typedef typename Digraph::template NodeMap<bool> ReachedMap; 810 873 ///Instantiates a ReachedMap. 811 874 812 ///This function instantiates a \ref ReachedMap. 813 ///\param G is the digraph, to which 814 ///we would like to define the \ref ReachedMap. 815 static ReachedMap *createReachedMap(const GR &G) 816 { 817 return new ReachedMap(G); 818 } 819 ///The type of the map that stores the dists of the nodes. 820 821 ///The type of the map that stores the dists of the nodes. 875 ///This function instantiates a ReachedMap. 876 ///\param g is the digraph, to which 877 ///we would like to define the ReachedMap. 878 static ReachedMap *createReachedMap(const Digraph &g) 879 { 880 return new ReachedMap(g); 881 } 882 883 ///The type of the map that stores the distances of the nodes. 884 885 ///The type of the map that stores the distances of the nodes. 822 886 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 823 /// 824 typedef NullMap<typename Digraph::Node,int> DistMap; 887 typedef typename Digraph::template NodeMap<int> DistMap; 825 888 ///Instantiates a DistMap. 826 889 827 ///This function instantiates a \refDistMap.890 ///This function instantiates a DistMap. 828 891 ///\param g is the digraph, to which we would like to define 829 ///the \ref DistMap 830 #ifdef DOXYGEN 831 static DistMap *createDistMap(const GR &g) 832 #else 833 static DistMap *createDistMap(const GR &) 834 #endif 835 { 836 return new DistMap(); 837 } 892 ///the DistMap 893 static DistMap *createDistMap(const Digraph &g) 894 { 895 return new DistMap(g); 896 } 897 898 ///The type of the shortest paths. 899 900 ///The type of the shortest paths. 901 ///It must meet the \ref concepts::Path "Path" concept. 902 typedef lemon::Path<Digraph> Path; 838 903 }; 839 904 840 /// Default traits used by \refBfsWizard905 /// Default traits class used by BfsWizard 841 906 842 907 /// To make it easier to use Bfs algorithm 843 /// we have created a wizard class.908 /// we have created a wizard class. 844 909 /// This \ref BfsWizard class needs default traits, 845 /// as well as the \ref Bfs class.910 /// as well as the \ref Bfs class. 846 911 /// The \ref BfsWizardBase is a class to be the default traits of the 847 912 /// \ref BfsWizard class. … … 852 917 typedef BfsWizardDefaultTraits<GR> Base; 853 918 protected: 854 // / Type of the nodes in the digraph.919 //The type of the nodes in the digraph. 855 920 typedef typename Base::Digraph::Node Node; 856 921 857 // / Pointer to the underlying digraph.922 //Pointer to the digraph the algorithm runs on. 858 923 void *_g; 859 // /Pointer to the map of reached nodes.924 //Pointer to the map of reached nodes. 860 925 void *_reached; 861 // /Pointer to the map of processed nodes.926 //Pointer to the map of processed nodes. 862 927 void *_processed; 863 // /Pointer to the map of predecessors arcs.928 //Pointer to the map of predecessors arcs. 864 929 void *_pred; 865 // /Pointer to the map of distances.930 //Pointer to the map of distances. 866 931 void *_dist; 867 ///Pointer to the source node. 868 Node _source; 932 //Pointer to the shortest path to the target node. 933 void *_path; 934 //Pointer to the distance of the target node. 935 int *_di; 869 936 870 937 public: … … 872 939 873 940 /// This constructor does not require parameters, therefore it initiates 874 /// all of the attributes to default values (0, INVALID).941 /// all of the attributes to \c 0. 875 942 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), 876 _dist(0), _source(INVALID) {}943 _dist(0), _path(0), _di(0) {} 877 944 878 945 /// Constructor. 879 946 880 /// This constructor requires some parameters, 881 /// listed in the parameters list. 882 /// Others are initiated to 0. 883 /// \param g is the initial value of \ref _g 884 /// \param s is the initial value of \ref _source 885 BfsWizardBase(const GR &g, Node s=INVALID) : 947 /// This constructor requires one parameter, 948 /// others are initiated to \c 0. 949 /// \param g The digraph the algorithm runs on. 950 BfsWizardBase(const GR &g) : 886 951 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 887 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}952 _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} 888 953 889 954 }; 890 955 891 /// A class to make the usage of Bfs algorithm easier 892 893 /// This class is created to make it easier to use Bfs algorithm. 894 /// It uses the functions and features of the plain \ref Bfs, 895 /// but it is much simpler to use it. 956 /// Auxiliary class for the function-type interface of BFS algorithm. 957 958 /// This auxiliary class is created to implement the 959 /// \ref bfs() "function-type interface" of \ref Bfs algorithm. 960 /// It does not have own \ref run() method, it uses the functions 961 /// and features of the plain \ref Bfs. 896 962 /// 897 /// Simplicity means that the way to change the types defined 898 /// in the traits class is based on functions that returns the new class 899 /// and not on templatable built-in classes. 900 /// When using the plain \ref Bfs 901 /// the new class with the modified type comes from 902 /// the original class by using the :: 903 /// operator. In the case of \ref BfsWizard only 904 /// a function have to be called and it will 905 /// return the needed class. 906 /// 907 /// It does not have own \ref run method. When its \ref run method is called 908 /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run 909 /// method of it. 963 /// This class should only be used through the \ref bfs() function, 964 /// which makes it easier to use the algorithm. 910 965 template<class TR> 911 966 class BfsWizard : public TR … … 913 968 typedef TR Base; 914 969 915 ///The type of the underlying digraph.970 ///The type of the digraph the algorithm runs on. 916 971 typedef typename TR::Digraph Digraph; 917 //\e 972 918 973 typedef typename Digraph::Node Node; 919 //\e920 974 typedef typename Digraph::NodeIt NodeIt; 921 //\e922 975 typedef typename Digraph::Arc Arc; 923 //\e924 976 typedef typename Digraph::OutArcIt OutArcIt; 925 977 926 ///\brief The type of the map that stores 927 ///the reached nodes 928 typedef typename TR::ReachedMap ReachedMap; 929 ///\brief The type of the map that stores 930 ///the processed nodes 931 typedef typename TR::ProcessedMap ProcessedMap; 932 ///\brief The type of the map that stores the last 978 ///\brief The type of the map that stores the predecessor 933 979 ///arcs of the shortest paths. 934 980 typedef typename TR::PredMap PredMap; 935 /// The type of the map that stores the dists of the nodes.981 ///\brief The type of the map that stores the distances of the nodes. 936 982 typedef typename TR::DistMap DistMap; 983 ///\brief The type of the map that indicates which nodes are reached. 984 typedef typename TR::ReachedMap ReachedMap; 985 ///\brief The type of the map that indicates which nodes are processed. 986 typedef typename TR::ProcessedMap ProcessedMap; 987 ///The type of the shortest paths 988 typedef typename TR::Path Path; 937 989 938 990 public: 991 939 992 /// Constructor. 940 993 BfsWizard() : TR() {} … … 944 997 /// Constructor that requires parameters. 945 998 /// These parameters will be the default values for the traits class. 946 BfsWizard(const Digraph &g, Node s=INVALID) : 947 TR(g,s) {} 999 /// \param g The digraph the algorithm runs on. 1000 BfsWizard(const Digraph &g) : 1001 TR(g) {} 948 1002 949 1003 ///Copy constructor … … 952 1006 ~BfsWizard() {} 953 1007 954 ///Runs Bfs algorithm from a given node. 955 956 ///Runs Bfs algorithm from a given node. 957 ///The node can be given by the \ref source function. 1008 ///Runs BFS algorithm from the given source node. 1009 1010 ///This method runs BFS algorithm from node \c s 1011 ///in order to compute the shortest path to each node. 1012 void run(Node s) 1013 { 1014 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 1015 if (Base::_pred) 1016 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1017 if (Base::_dist) 1018 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1019 if (Base::_reached) 1020 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 1021 if (Base::_processed) 1022 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1023 if (s!=INVALID) 1024 alg.run(s); 1025 else 1026 alg.run(); 1027 } 1028 1029 ///Finds the shortest path between \c s and \c t. 1030 1031 ///This method runs BFS algorithm from node \c s 1032 ///in order to compute the shortest path to node \c t 1033 ///(it stops searching when \c t is processed). 1034 /// 1035 ///\return \c true if \c t is reachable form \c s. 1036 bool run(Node s, Node t) 1037 { 1038 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 1039 if (Base::_pred) 1040 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1041 if (Base::_dist) 1042 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1043 if (Base::_reached) 1044 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 1045 if (Base::_processed) 1046 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1047 alg.run(s,t); 1048 if (Base::_path) 1049 *reinterpret_cast<Path*>(Base::_path) = alg.path(t); 1050 if (Base::_di) 1051 *Base::_di = alg.dist(t); 1052 return alg.reached(t); 1053 } 1054 1055 ///Runs BFS algorithm to visit all nodes in the digraph. 1056 1057 ///This method runs BFS algorithm in order to compute 1058 ///the shortest path to each node. 958 1059 void run() 959 1060 { 960 if(Base::_source==INVALID) throw UninitializedParameter(); 961 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 962 if(Base::_reached) 963 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 964 if(Base::_processed) 965 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 966 if(Base::_pred) 967 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 968 if(Base::_dist) 969 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 970 alg.run(Base::_source); 971 } 972 973 ///Runs Bfs algorithm from the given node. 974 975 ///Runs Bfs algorithm from the given node. 976 ///\param s is the given source. 977 void run(Node s) 978 { 979 Base::_source=s; 980 run(); 1061 run(INVALID); 981 1062 } 982 1063 983 1064 template<class T> 984 struct DefPredMapBase : public Base {1065 struct SetPredMapBase : public Base { 985 1066 typedef T PredMap; 986 1067 static PredMap *createPredMap(const Digraph &) { return 0; }; 987 DefPredMapBase(const TR &b) : TR(b) {}1068 SetPredMapBase(const TR &b) : TR(b) {} 988 1069 }; 989 990 ///\brief \ref named-templ-param "Named parameter" 991 ///function for setting PredMap 992 /// 993 /// \ref named-templ-param "Named parameter" 994 ///function for setting PredMap 995 /// 1070 ///\brief \ref named-func-param "Named parameter" 1071 ///for setting PredMap object. 1072 /// 1073 ///\ref named-func-param "Named parameter" 1074 ///for setting PredMap object. 996 1075 template<class T> 997 BfsWizard< DefPredMapBase<T> > predMap(const T &t)1076 BfsWizard<SetPredMapBase<T> > predMap(const T &t) 998 1077 { 999 1078 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); 1000 return BfsWizard<DefPredMapBase<T> >(*this); 1001 } 1002 1079 return BfsWizard<SetPredMapBase<T> >(*this); 1080 } 1003 1081 1004 1082 template<class T> 1005 struct DefReachedMapBase : public Base {1083 struct SetReachedMapBase : public Base { 1006 1084 typedef T ReachedMap; 1007 1085 static ReachedMap *createReachedMap(const Digraph &) { return 0; }; 1008 DefReachedMapBase(const TR &b) : TR(b) {}1086 SetReachedMapBase(const TR &b) : TR(b) {} 1009 1087 }; 1010 1011 ///\brief \ref named-templ-param "Named parameter" 1012 ///function for setting ReachedMap 1013 /// 1014 /// \ref named-templ-param "Named parameter" 1015 ///function for setting ReachedMap 1016 /// 1088 ///\brief \ref named-func-param "Named parameter" 1089 ///for setting ReachedMap object. 1090 /// 1091 /// \ref named-func-param "Named parameter" 1092 ///for setting ReachedMap object. 1017 1093 template<class T> 1018 BfsWizard< DefReachedMapBase<T> > reachedMap(const T &t)1094 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) 1019 1095 { 1020 1096 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); 1021 return BfsWizard<DefReachedMapBase<T> >(*this); 1022 } 1023 1097 return BfsWizard<SetReachedMapBase<T> >(*this); 1098 } 1024 1099 1025 1100 template<class T> 1026 struct DefProcessedMapBase : public Base { 1101 struct SetDistMapBase : public Base { 1102 typedef T DistMap; 1103 static DistMap *createDistMap(const Digraph &) { return 0; }; 1104 SetDistMapBase(const TR &b) : TR(b) {} 1105 }; 1106 ///\brief \ref named-func-param "Named parameter" 1107 ///for setting DistMap object. 1108 /// 1109 /// \ref named-func-param "Named parameter" 1110 ///for setting DistMap object. 1111 template<class T> 1112 BfsWizard<SetDistMapBase<T> > distMap(const T &t) 1113 { 1114 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1115 return BfsWizard<SetDistMapBase<T> >(*this); 1116 } 1117 1118 template<class T> 1119 struct SetProcessedMapBase : public Base { 1027 1120 typedef T ProcessedMap; 1028 1121 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; 1029 DefProcessedMapBase(const TR &b) : TR(b) {}1122 SetProcessedMapBase(const TR &b) : TR(b) {} 1030 1123 }; 1031 1032 ///\brief \ref named-templ-param "Named parameter" 1033 ///function for setting ProcessedMap 1034 /// 1035 /// \ref named-templ-param "Named parameter" 1036 ///function for setting ProcessedMap 1037 /// 1124 ///\brief \ref named-func-param "Named parameter" 1125 ///for setting ProcessedMap object. 1126 /// 1127 /// \ref named-func-param "Named parameter" 1128 ///for setting ProcessedMap object. 1038 1129 template<class T> 1039 BfsWizard< DefProcessedMapBase<T> > processedMap(const T &t)1130 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) 1040 1131 { 1041 1132 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); 1042 return BfsWizard<DefProcessedMapBase<T> >(*this); 1043 } 1044 1133 return BfsWizard<SetProcessedMapBase<T> >(*this); 1134 } 1045 1135 1046 1136 template<class T> 1047 struct DefDistMapBase : public Base { 1048 typedef T DistMap; 1049 static DistMap *createDistMap(const Digraph &) { return 0; }; 1050 DefDistMapBase(const TR &b) : TR(b) {} 1137 struct SetPathBase : public Base { 1138 typedef T Path; 1139 SetPathBase(const TR &b) : TR(b) {} 1051 1140 }; 1052 1053 ///\brief \ref named-templ-param "Named parameter" 1054 ///function for setting DistMap type 1055 /// 1056 /// \ref named-templ-param "Named parameter" 1057 ///function for setting DistMap type 1058 /// 1141 ///\brief \ref named-func-param "Named parameter" 1142 ///for getting the shortest path to the target node. 1143 /// 1144 ///\ref named-func-param "Named parameter" 1145 ///for getting the shortest path to the target node. 1059 1146 template<class T> 1060 BfsWizard<DefDistMapBase<T> > distMap(const T &t) 1061 { 1062 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1063 return BfsWizard<DefDistMapBase<T> >(*this); 1064 } 1065 1066 /// Sets the source node, from which the Bfs algorithm runs. 1067 1068 /// Sets the source node, from which the Bfs algorithm runs. 1069 /// \param s is the source node. 1070 BfsWizard<TR> &source(Node s) 1071 { 1072 Base::_source=s; 1147 BfsWizard<SetPathBase<T> > path(const T &t) 1148 { 1149 Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t)); 1150 return BfsWizard<SetPathBase<T> >(*this); 1151 } 1152 1153 ///\brief \ref named-func-param "Named parameter" 1154 ///for getting the distance of the target node. 1155 /// 1156 ///\ref named-func-param "Named parameter" 1157 ///for getting the distance of the target node. 1158 BfsWizard dist(const int &d) 1159 { 1160 Base::_di=const_cast<int*>(&d); 1073 1161 return *this; 1074 1162 } … … 1076 1164 }; 1077 1165 1078 ///Function type interface for Bfsalgorithm.1166 ///Function-type interface for BFS algorithm. 1079 1167 1080 1168 /// \ingroup search 1081 ///Function type interface for Bfsalgorithm.1169 ///Function-type interface for BFS algorithm. 1082 1170 /// 1083 ///This function also has several 1084 ///\ref named-templ-func-param "named parameters", 1171 ///This function also has several \ref named-func-param "named parameters", 1085 1172 ///they are declared as the members of class \ref BfsWizard. 1086 ///The following 1087 ///example shows how to use these parameters. 1173 ///The following examples show how to use these parameters. 1088 1174 ///\code 1089 /// bfs(g,source).predMap(preds).run(); 1175 /// // Compute shortest path from node s to each node 1176 /// bfs(g).predMap(preds).distMap(dists).run(s); 1177 /// 1178 /// // Compute shortest path from s to t 1179 /// bool reached = bfs(g).path(p).dist(d).run(s,t); 1090 1180 ///\endcode 1091 1181 ///\warning Don't forget to put the \ref BfsWizard::run() "run()" … … 1095 1185 template<class GR> 1096 1186 BfsWizard<BfsWizardBase<GR> > 1097 bfs(const GR & g,typename GR::Node s=INVALID)1187 bfs(const GR &digraph) 1098 1188 { 1099 return BfsWizard<BfsWizardBase<GR> >( g,s);1189 return BfsWizard<BfsWizardBase<GR> >(digraph); 1100 1190 } 1101 1191 1102 1192 #ifdef DOXYGEN 1103 /// \brief Visitor class for bfs.1193 /// \brief Visitor class for BFS. 1104 1194 /// 1105 1195 /// This class defines the interface of the BfsVisit events, and 1106 /// it could be the base of a real Visitor class.1196 /// it could be the base of a real visitor class. 1107 1197 template <typename _Digraph> 1108 1198 struct BfsVisitor { … … 1110 1200 typedef typename Digraph::Arc Arc; 1111 1201 typedef typename Digraph::Node Node; 1112 /// \brief Called when the arc reach a node. 1113 /// 1114 /// It is called when the bfs find an arc which target is not 1115 /// reached yet. 1202 /// \brief Called for the source node(s) of the BFS. 1203 /// 1204 /// This function is called for the source node(s) of the BFS. 1205 void start(const Node& node) {} 1206 /// \brief Called when a node is reached first time. 1207 /// 1208 /// This function is called when a node is reached first time. 1209 void reach(const Node& node) {} 1210 /// \brief Called when a node is processed. 1211 /// 1212 /// This function is called when a node is processed. 1213 void process(const Node& node) {} 1214 /// \brief Called when an arc reaches a new node. 1215 /// 1216 /// This function is called when the BFS finds an arc whose target node 1217 /// is not reached yet. 1116 1218 void discover(const Arc& arc) {} 1117 /// \brief Called when the node reached first time. 1118 /// 1119 /// It is Called when the node reached first time. 1120 void reach(const Node& node) {} 1121 /// \brief Called when the arc examined but target of the arc 1219 /// \brief Called when an arc is examined but its target node is 1122 1220 /// already discovered. 1123 1221 /// 1124 /// It called when the arc examined but the target of the arc1222 /// This function is called when an arc is examined but its target node is 1125 1223 /// already discovered. 1126 1224 void examine(const Arc& arc) {} 1127 /// \brief Called for the source node of the bfs.1128 ///1129 /// It is called for the source node of the bfs.1130 void start(const Node& node) {}1131 /// \brief Called when the node processed.1132 ///1133 /// It is Called when the node processed.1134 void process(const Node& node) {}1135 1225 }; 1136 1226 #else … … 1140 1230 typedef typename Digraph::Arc Arc; 1141 1231 typedef typename Digraph::Node Node; 1232 void start(const Node&) {} 1233 void reach(const Node&) {} 1234 void process(const Node&) {} 1142 1235 void discover(const Arc&) {} 1143 void reach(const Node&) {}1144 1236 void examine(const Arc&) {} 1145 void start(const Node&) {}1146 void process(const Node&) {}1147 1237 1148 1238 template <typename _Visitor> … … 1151 1241 Arc arc; 1152 1242 Node node; 1243 visitor.start(node); 1244 visitor.reach(node); 1245 visitor.process(node); 1153 1246 visitor.discover(arc); 1154 visitor.reach(node);1155 1247 visitor.examine(arc); 1156 visitor.start(node);1157 visitor.process(node);1158 1248 } 1159 1249 _Visitor& visitor; … … 1165 1255 /// 1166 1256 /// Default traits class of BfsVisit class. 1167 /// \tparam _Digraph Digraph type.1257 /// \tparam _Digraph The type of the digraph the algorithm runs on. 1168 1258 template<class _Digraph> 1169 1259 struct BfsVisitDefaultTraits { 1170 1260 1171 /// \brief The digraph typethe algorithm runs on.1261 /// \brief The type of the digraph the algorithm runs on. 1172 1262 typedef _Digraph Digraph; 1173 1263 … … 1175 1265 /// 1176 1266 /// The type of the map that indicates which nodes are reached. 1177 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. 1178 /// \todo named parameter to set this type, function to read and write. 1267 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1179 1268 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1180 1269 1181 1270 /// \brief Instantiates a ReachedMap. 1182 1271 /// 1183 /// This function instantiates a \refReachedMap.1272 /// This function instantiates a ReachedMap. 1184 1273 /// \param digraph is the digraph, to which 1185 /// we would like to define the \refReachedMap.1274 /// we would like to define the ReachedMap. 1186 1275 static ReachedMap *createReachedMap(const Digraph &digraph) { 1187 1276 return new ReachedMap(digraph); … … 1192 1281 /// \ingroup search 1193 1282 /// 1194 /// \brief %BFS Visit algorithm class.1283 /// \brief %BFS algorithm class with visitor interface. 1195 1284 /// 1196 1285 /// This class provides an efficient implementation of the %BFS algorithm … … 1199 1288 /// The %BfsVisit class provides an alternative interface to the Bfs 1200 1289 /// class. It works with callback mechanism, the BfsVisit object calls 1201 /// on every bfs event the \c Visitor class member functions.1290 /// the member functions of the \c Visitor class on every BFS event. 1202 1291 /// 1203 /// \tparam _Digraph The digraph type the algorithm runs on. 1292 /// This interface of the BFS algorithm should be used in special cases 1293 /// when extra actions have to be performed in connection with certain 1294 /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs() 1295 /// instead. 1296 /// 1297 /// \tparam _Digraph The type of the digraph the algorithm runs on. 1204 1298 /// The default value is 1205 /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it1206 /// is only passed to \ref BfsDefaultTraits.1207 /// \tparam _Visitor The Visitor object for the algorithm. The1208 /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitorwhich1209 /// does not observe the B fs events. If you want to observe the bfs1210 /// events you should implement your own Visitor class.1299 /// \ref ListDigraph. The value of _Digraph is not used directly by 1300 /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits. 1301 /// \tparam _Visitor The Visitor type that is used by the algorithm. 1302 /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which 1303 /// does not observe the BFS events. If you want to observe the BFS 1304 /// events, you should implement your own visitor class. 1211 1305 /// \tparam _Traits Traits class to set various data types used by the 1212 1306 /// algorithm. The default traits class is 1213 1307 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>". 1214 1308 /// See \ref BfsVisitDefaultTraits for the documentation of 1215 /// a B fsvisit traits class.1309 /// a BFS visit traits class. 1216 1310 #ifdef DOXYGEN 1217 1311 template <typename _Digraph, typename _Visitor, typename _Traits> … … 1219 1313 template <typename _Digraph = ListDigraph, 1220 1314 typename _Visitor = BfsVisitor<_Digraph>, 1221 typename _Traits = Bfs DefaultTraits<_Digraph> >1315 typename _Traits = BfsVisitDefaultTraits<_Digraph> > 1222 1316 #endif 1223 1317 class BfsVisit { 1224 1318 public: 1225 1319 1226 /// \brief \ref Exception for uninitialized parameters. 1227 /// 1228 /// This error represents problems in the initialization 1229 /// of the parameters of the algorithms. 1230 class UninitializedParameter : public lemon::UninitializedParameter { 1231 public: 1232 virtual const char* what() const throw() 1233 { 1234 return "lemon::BfsVisit::UninitializedParameter"; 1235 } 1236 }; 1237 1320 ///The traits class. 1238 1321 typedef _Traits Traits; 1239 1322 1323 ///The type of the digraph the algorithm runs on. 1240 1324 typedef typename Traits::Digraph Digraph; 1241 1325 1326 ///The visitor type used by the algorithm. 1242 1327 typedef _Visitor Visitor; 1243 1328 1244 ///The type of the map indicatingwhich nodes are reached.1329 ///The type of the map that indicates which nodes are reached. 1245 1330 typedef typename Traits::ReachedMap ReachedMap; 1246 1331 … … 1252 1337 typedef typename Digraph::OutArcIt OutArcIt; 1253 1338 1254 // /Pointer to the underlying digraph.1339 //Pointer to the underlying digraph. 1255 1340 const Digraph *_digraph; 1256 // /Pointer to the visitor object.1341 //Pointer to the visitor object. 1257 1342 Visitor *_visitor; 1258 // /Pointer to the map of reached status of the nodes.1343 //Pointer to the map of reached status of the nodes. 1259 1344 ReachedMap *_reached; 1260 // /Indicates if \ref _reached is locally allocated (\ctrue) or not.1345 //Indicates if _reached is locally allocated (true) or not. 1261 1346 bool local_reached; 1262 1347 … … 1264 1349 int _list_front, _list_back; 1265 1350 1266 /// \brief Creates the maps if necessary. 1267 /// 1268 /// Creates the maps if necessary. 1351 //Creates the maps if necessary. 1269 1352 void create_maps() { 1270 1353 if(!_reached) { … … 1286 1369 ///@{ 1287 1370 template <class T> 1288 struct DefReachedMapTraits : public Traits {1371 struct SetReachedMapTraits : public Traits { 1289 1372 typedef T ReachedMap; 1290 1373 static ReachedMap *createReachedMap(const Digraph &digraph) { 1291 throw UninitializedParameter(); 1374 LEMON_ASSERT(false, "ReachedMap is not initialized"); 1375 return 0; // ignore warnings 1292 1376 } 1293 1377 }; 1294 1378 /// \brief \ref named-templ-param "Named parameter" for setting 1295 /// ReachedMap type 1296 /// 1297 /// \ref named-templ-param "Named parameter" for setting ReachedMap type 1379 /// ReachedMap type. 1380 /// 1381 /// \ref named-templ-param "Named parameter" for setting ReachedMap type. 1298 1382 template <class T> 1299 struct DefReachedMap : public BfsVisit< Digraph, Visitor,1300 DefReachedMapTraits<T> > {1301 typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;1383 struct SetReachedMap : public BfsVisit< Digraph, Visitor, 1384 SetReachedMapTraits<T> > { 1385 typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create; 1302 1386 }; 1303 1387 ///@} … … 1309 1393 /// Constructor. 1310 1394 /// 1311 /// \param digraph the digraph the algorithm will run on. 1312 /// \param visitor The visitor of the algorithm. 1313 /// 1395 /// \param digraph The digraph the algorithm runs on. 1396 /// \param visitor The visitor object of the algorithm. 1314 1397 BfsVisit(const Digraph& digraph, Visitor& visitor) 1315 1398 : _digraph(&digraph), _visitor(&visitor), … … 1317 1400 1318 1401 /// \brief Destructor. 1319 ///1320 /// Destructor.1321 1402 ~BfsVisit() { 1322 1403 if(local_reached) delete _reached; 1323 1404 } 1324 1405 1325 /// \brief Sets the map indicating if a node isreached.1326 /// 1327 /// Sets the map indicating if a node isreached.1406 /// \brief Sets the map that indicates which nodes are reached. 1407 /// 1408 /// Sets the map that indicates which nodes are reached. 1328 1409 /// If you don't use this function before calling \ref run(), 1329 /// it will allocate one. The dest uctor deallocates this1410 /// it will allocate one. The destructor deallocates this 1330 1411 /// automatically allocated map, of course. 1331 1412 /// \return <tt> (*this) </tt> … … 1340 1421 1341 1422 public: 1423 1342 1424 /// \name Execution control 1343 1425 /// The simplest way to execute the algorithm is to use 1344 /// one of the member functions called \c run(...). 1426 /// one of the member functions called \ref lemon::BfsVisit::run() 1427 /// "run()". 1345 1428 /// \n 1346 /// If you need more control on the execution, 1347 /// first you must call \ref init(), then you can adda source node1348 /// with \ref addSource().1349 /// Finally \ref start() will perform the actual path1350 /// computation.1429 /// If you need more control on the execution, first you must call 1430 /// \ref lemon::BfsVisit::init() "init()", then you can add several 1431 /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()". 1432 /// Finally \ref lemon::BfsVisit::start() "start()" will perform the 1433 /// actual path computation. 1351 1434 1352 1435 /// @{ 1436 1353 1437 /// \brief Initializes the internal data structures. 1354 1438 /// 1355 1439 /// Initializes the internal data structures. 1356 ///1357 1440 void init() { 1358 1441 create_maps(); … … 1382 1465 /// \return The processed node. 1383 1466 /// 1384 /// \pre The queue must not be empty !1467 /// \pre The queue must not be empty. 1385 1468 Node processNextNode() { 1386 1469 Node n = _list[++_list_front]; … … 1403 1486 /// \brief Processes the next node. 1404 1487 /// 1405 /// Processes the next node . And checks thatthe given target node1488 /// Processes the next node and checks if the given target node 1406 1489 /// is reached. If the target node is reachable from the processed 1407 /// node then the reached parameter will be set true. The reached 1408 /// parameter should be initially false. 1490 /// node, then the \c reach parameter will be set to \c true. 1409 1491 /// 1410 1492 /// \param target The target node. 1411 /// \retval reach Indicates that the target node is reached. 1493 /// \retval reach Indicates if the target node is reached. 1494 /// It should be initially \c false. 1495 /// 1412 1496 /// \return The processed node. 1413 1497 /// 1414 /// \ warning The queue must not be empty!1498 /// \pre The queue must not be empty. 1415 1499 Node processNextNode(Node target, bool& reach) { 1416 1500 Node n = _list[++_list_front]; … … 1434 1518 /// \brief Processes the next node. 1435 1519 /// 1436 /// Processes the next node. And checks that at least one of 1437 /// reached node has true value in the \c nm node map. If one node 1438 /// with true value is reachable from the processed node then the 1439 /// rnode parameter will be set to the first of such nodes. 1440 /// 1441 /// \param nm The node map of possible targets. 1520 /// Processes the next node and checks if at least one of reached 1521 /// nodes has \c true value in the \c nm node map. If one node 1522 /// with \c true value is reachable from the processed node, then the 1523 /// \c rnode parameter will be set to the first of such nodes. 1524 /// 1525 /// \param nm A \c bool (or convertible) node map that indicates the 1526 /// possible targets. 1442 1527 /// \retval rnode The reached target node. 1528 /// It should be initially \c INVALID. 1529 /// 1443 1530 /// \return The processed node. 1444 1531 /// 1445 /// \ warning The queue must not be empty!1532 /// \pre The queue must not be empty. 1446 1533 template <typename NM> 1447 1534 Node processNextNode(const NM& nm, Node& rnode) { … … 1464 1551 } 1465 1552 1466 /// \brief Next node to be processed. 1467 /// 1468 /// Next node to be processed. 1469 /// 1470 /// \return The next node to be processed or INVALID if the stack is 1471 /// empty. 1472 Node nextNode() { 1553 /// \brief The next node to be processed. 1554 /// 1555 /// Returns the next node to be processed or \c INVALID if the queue 1556 /// is empty. 1557 Node nextNode() const { 1473 1558 return _list_front != _list_back ? _list[_list_front + 1] : INVALID; 1474 1559 } 1475 1560 1476 1561 /// \brief Returns \c false if there are nodes 1477 /// to be processed in the queue1562 /// to be processed. 1478 1563 /// 1479 1564 /// Returns \c false if there are nodes 1480 /// to be processed in the queue 1481 bool emptyQueue() { return _list_front == _list_back; }1565 /// to be processed in the queue. 1566 bool emptyQueue() const { return _list_front == _list_back; } 1482 1567 1483 1568 /// \brief Returns the number of the nodes to be processed. 1484 1569 /// 1485 1570 /// Returns the number of the nodes to be processed in the queue. 1486 int queueSize() { return _list_back - _list_front; }1571 int queueSize() const { return _list_back - _list_front; } 1487 1572 1488 1573 /// \brief Executes the algorithm. … … 1490 1575 /// Executes the algorithm. 1491 1576 /// 1492 /// \pre init() must be called and at least one node should be added 1577 /// This method runs the %BFS algorithm from the root node(s) 1578 /// in order to compute the shortest path to each node. 1579 /// 1580 /// The algorithm computes 1581 /// - the shortest path tree (forest), 1582 /// - the distance of each node from the root(s). 1583 /// 1584 /// \pre init() must be called and at least one root node should be added 1493 1585 /// with addSource() before using this function. 1586 /// 1587 /// \note <tt>b.start()</tt> is just a shortcut of the following code. 1588 /// \code 1589 /// while ( !b.emptyQueue() ) { 1590 /// b.processNextNode(); 1591 /// } 1592 /// \endcode 1494 1593 void start() { 1495 1594 while ( !emptyQueue() ) processNextNode(); 1496 1595 } 1497 1596 1498 /// \brief Executes the algorithm until \c dest is reached. 1499 /// 1500 /// Executes the algorithm until \c dest is reached. 1501 /// 1502 /// \pre init() must be called and at least one node should be added 1503 /// with addSource() before using this function. 1504 void start(Node dest) { 1597 /// \brief Executes the algorithm until the given target node is reached. 1598 /// 1599 /// Executes the algorithm until the given target node is reached. 1600 /// 1601 /// This method runs the %BFS algorithm from the root node(s) 1602 /// in order to compute the shortest path to \c t. 1603 /// 1604 /// The algorithm computes 1605 /// - the shortest path to \c t, 1606 /// - the distance of \c t from the root(s). 1607 /// 1608 /// \pre init() must be called and at least one root node should be 1609 /// added with addSource() before using this function. 1610 /// 1611 /// \note <tt>b.start(t)</tt> is just a shortcut of the following code. 1612 /// \code 1613 /// bool reach = false; 1614 /// while ( !b.emptyQueue() && !reach ) { 1615 /// b.processNextNode(t, reach); 1616 /// } 1617 /// \endcode 1618 void start(Node t) { 1505 1619 bool reach = false; 1506 while ( !emptyQueue() && !reach ) processNextNode( dest, reach);1620 while ( !emptyQueue() && !reach ) processNextNode(t, reach); 1507 1621 } 1508 1622 … … 1511 1625 /// Executes the algorithm until a condition is met. 1512 1626 /// 1513 /// \pre init() must be called and at least one node should be added 1514 /// with addSource() before using this function. 1515 /// 1516 ///\param nm must be a bool (or convertible) node map. The 1517 ///algorithm will stop when it reaches a node \c v with 1627 /// This method runs the %BFS algorithm from the root node(s) in 1628 /// order to compute the shortest path to a node \c v with 1629 /// <tt>nm[v]</tt> true, if such a node can be found. 1630 /// 1631 /// \param nm must be a bool (or convertible) node map. The 1632 /// algorithm will stop when it reaches a node \c v with 1518 1633 /// <tt>nm[v]</tt> true. 1519 1634 /// 1520 ///\return The reached node \c v with <tt>nm[v]</tt> true or 1521 ///\c INVALID if no such node was found. 1635 /// \return The reached node \c v with <tt>nm[v]</tt> true or 1636 /// \c INVALID if no such node was found. 1637 /// 1638 /// \pre init() must be called and at least one root node should be 1639 /// added with addSource() before using this function. 1640 /// 1641 /// \note <tt>b.start(nm)</tt> is just a shortcut of the following code. 1642 /// \code 1643 /// Node rnode = INVALID; 1644 /// while ( !b.emptyQueue() && rnode == INVALID ) { 1645 /// b.processNextNode(nm, rnode); 1646 /// } 1647 /// return rnode; 1648 /// \endcode 1522 1649 template <typename NM> 1523 1650 Node start(const NM &nm) { … … 1529 1656 } 1530 1657 1531 /// \brief Runs %BFSVisit algorithm from node \c s. 1532 /// 1533 /// This method runs the %BFS algorithm from a root node \c s. 1534 /// \note b.run(s) is just a shortcut of the following code. 1658 /// \brief Runs the algorithm from the given source node. 1659 /// 1660 /// This method runs the %BFS algorithm from node \c s 1661 /// in order to compute the shortest path to each node. 1662 /// 1663 /// The algorithm computes 1664 /// - the shortest path tree, 1665 /// - the distance of each node from the root. 1666 /// 1667 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code. 1535 1668 ///\code 1536 1669 /// b.init(); … … 1544 1677 } 1545 1678 1546 /// \brief Runs %BFSVisit algorithm to visit all nodes in the digraph. 1679 /// \brief Finds the shortest path between \c s and \c t. 1680 /// 1681 /// This method runs the %BFS algorithm from node \c s 1682 /// in order to compute the shortest path to node \c t 1683 /// (it stops searching when \c t is processed). 1684 /// 1685 /// \return \c true if \c t is reachable form \c s. 1686 /// 1687 /// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a 1688 /// shortcut of the following code. 1689 ///\code 1690 /// b.init(); 1691 /// b.addSource(s); 1692 /// b.start(t); 1693 ///\endcode 1694 bool run(Node s,Node t) { 1695 init(); 1696 addSource(s); 1697 start(t); 1698 return reached(t); 1699 } 1700 1701 /// \brief Runs the algorithm to visit all nodes in the digraph. 1547 1702 /// 1548 1703 /// This method runs the %BFS algorithm in order to 1549 /// compute the %BFS path to each node. The algorithm computes 1550 /// - The %BFS tree. 1551 /// - The distance of each node from the root in the %BFS tree. 1552 /// 1553 ///\note b.run() is just a shortcut of the following code. 1704 /// compute the shortest path to each node. 1705 /// 1706 /// The algorithm computes 1707 /// - the shortest path tree (forest), 1708 /// - the distance of each node from the root(s). 1709 /// 1710 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code. 1554 1711 ///\code 1555 1712 /// b.init(); 1556 /// for (NodeIt it(digraph); it != INVALID; ++it) {1557 /// if (!b.reached( it)) {1558 /// b.addSource( it);1713 /// for (NodeIt n(gr); n != INVALID; ++n) { 1714 /// if (!b.reached(n)) { 1715 /// b.addSource(n); 1559 1716 /// b.start(); 1560 1717 /// } … … 1570 1727 } 1571 1728 } 1729 1572 1730 ///@} 1573 1731 … … 1575 1733 /// The result of the %BFS algorithm can be obtained using these 1576 1734 /// functions.\n 1577 /// Before the use of these functions, 1578 /// either run() or start() must be called. 1735 /// Either \ref lemon::BfsVisit::run() "run()" or 1736 /// \ref lemon::BfsVisit::start() "start()" must be called before 1737 /// using them. 1579 1738 ///@{ 1580 1739 1581 /// \brief Checks if a node is reachable from the root .1740 /// \brief Checks if a node is reachable from the root(s). 1582 1741 /// 1583 1742 /// Returns \c true if \c v is reachable from the root(s). 1584 /// \warning The source nodes are inditated as unreachable.1585 1743 /// \pre Either \ref run() or \ref start() 1586 1744 /// must be called before using this function. 1587 ///1588 1745 bool reached(Node v) { return (*_reached)[v]; } 1746 1589 1747 ///@} 1748 1590 1749 }; 1591 1750 … … 1593 1752 1594 1753 #endif 1595
Note: See TracChangeset
for help on using the changeset viewer.