Changeset 244:c30731a37f91 in lemon
- Timestamp:
- 08/03/08 13:34:57 (16 years ago)
- Branch:
- default
- Phase:
- public
- Location:
- lemon
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r210 r244 22 22 ///\ingroup search 23 23 ///\file 24 ///\brief B fsalgorithm.24 ///\brief BFS algorithm. 25 25 26 26 #include <lemon/list_graph.h> … … 33 33 namespace lemon { 34 34 35 36 37 35 ///Default traits class of Bfs class. 38 36 … … 42 40 struct BfsDefaultTraits 43 41 { 44 ///The digraph typethe algorithm runs on.42 ///The type of the digraph the algorithm runs on. 45 43 typedef GR Digraph; 46 ///\brief The type of the map that stores the last 44 45 ///\brief The type of the map that stores the predecessor 47 46 ///arcs of the shortest paths. 48 47 /// 49 ///The type of the map that stores the last48 ///The type of the map that stores the predecessor 50 49 ///arcs of the shortest paths. 51 50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 52 /// 53 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap; 54 ///Instantiates a PredMap. 51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 52 ///Instantiates a \ref PredMap. 55 53 56 54 ///This function instantiates a \ref PredMap. 57 ///\param G is the digraph, to which we would like to define the PredMap. 55 ///\param g is the digraph, to which we would like to define the 56 ///\ref PredMap. 58 57 ///\todo The digraph alone may be insufficient to initialize 59 static PredMap *createPredMap(const GR &G) 60 { 61 return new PredMap(G); 62 } 58 static PredMap *createPredMap(const Digraph &g) 59 { 60 return new PredMap(g); 61 } 62 63 63 ///The type of the map that indicates which nodes are processed. 64 64 65 65 ///The type of the map that indicates which nodes are processed. 66 66 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 67 /// \todo named parameter to set this type, function to read and write.67 ///By default it is a NullMap. 68 68 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 69 ///Instantiates a ProcessedMap.69 ///Instantiates a \ref ProcessedMap. 70 70 71 71 ///This function instantiates a \ref ProcessedMap. … … 73 73 ///we would like to define the \ref ProcessedMap 74 74 #ifdef DOXYGEN 75 static ProcessedMap *createProcessedMap(const GR&g)75 static ProcessedMap *createProcessedMap(const Digraph &g) 76 76 #else 77 static ProcessedMap *createProcessedMap(const GR&)77 static ProcessedMap *createProcessedMap(const Digraph &) 78 78 #endif 79 79 { 80 80 return new ProcessedMap(); 81 81 } 82 82 83 ///The type of the map that indicates which nodes are reached. 83 84 84 85 ///The type of the map that indicates which nodes are reached. 86 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 87 typedef typename Digraph::template NodeMap<bool> ReachedMap; 88 ///Instantiates a \ref ReachedMap. 89 90 ///This function instantiates a \ref ReachedMap. 91 ///\param g is the digraph, to which 92 ///we would like to define the \ref ReachedMap. 93 static ReachedMap *createReachedMap(const Digraph &g) 94 { 95 return new ReachedMap(g); 96 } 97 98 ///The type of the map that stores the distances of the nodes. 99 100 ///The type of the map that stores the distances of the nodes. 85 101 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 86 ///\todo named parameter to set this type, function to read and write.87 typedef typename Digraph::template NodeMap<bool> ReachedMap;88 ///Instantiates a ReachedMap.89 90 ///This function instantiates a \ref ReachedMap.91 ///\param G is the digraph, to which92 ///we would like to define the \ref ReachedMap.93 static ReachedMap *createReachedMap(const GR &G)94 {95 return new ReachedMap(G);96 }97 ///The type of the map that stores the dists of the nodes.98 99 ///The type of the map that stores the dists of the nodes.100 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.101 ///102 102 typedef typename Digraph::template NodeMap<int> DistMap; 103 ///Instantiates a DistMap.103 ///Instantiates a \ref DistMap. 104 104 105 105 ///This function instantiates a \ref DistMap. 106 ///\param G is the digraph, to which we would like to define107 /// the \ref DistMap108 static DistMap *createDistMap(const GR &G)109 { 110 return new DistMap( G);106 ///\param g is the digraph, to which we would like to define the 107 ///\ref DistMap. 108 static DistMap *createDistMap(const Digraph &g) 109 { 110 return new DistMap(g); 111 111 } 112 112 }; … … 117 117 ///This class provides an efficient implementation of the %BFS algorithm. 118 118 /// 119 ///\tparam GR The digraph type the algorithm runs on. The default value is 120 ///\ref ListDigraph. The value of GR is not used directly by Bfs, it 121 ///is only passed to \ref BfsDefaultTraits. 119 ///There is also a \ref bfs() "function type interface" for the BFS 120 ///algorithm, which is convenient in the simplier cases and it can be 121 ///used easier. 122 /// 123 ///\tparam GR The type of the digraph the algorithm runs on. 124 ///The default value is \ref ListDigraph. The value of GR is not used 125 ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits. 122 126 ///\tparam TR Traits class to set various data types used by the algorithm. 123 127 ///The default traits class is … … 125 129 ///See \ref BfsDefaultTraits for the documentation of 126 130 ///a Bfs traits class. 127 128 131 #ifdef DOXYGEN 129 132 template <typename GR, … … 135 138 class Bfs { 136 139 public: 137 /** 138 * \brief \ref Exception for uninitialized parameters. 139 * 140 * This error represents problems in the initialization 141 * of the parameters of the algorithms. 142 */ 140 ///\ref Exception for uninitialized parameters. 141 142 ///This error represents problems in the initialization of the 143 ///parameters of the algorithm. 143 144 class UninitializedParameter : public lemon::UninitializedParameter { 144 145 public: … … 148 149 }; 149 150 151 ///The type of the digraph the algorithm runs on. 152 typedef typename TR::Digraph Digraph; 153 154 ///\brief The type of the map that stores the predecessor arcs of the 155 ///shortest paths. 156 typedef typename TR::PredMap PredMap; 157 ///The type of the map that stores the distances of the nodes. 158 typedef typename TR::DistMap DistMap; 159 ///The type of the map that indicates which nodes are reached. 160 typedef typename TR::ReachedMap ReachedMap; 161 ///The type of the map that indicates which nodes are processed. 162 typedef typename TR::ProcessedMap ProcessedMap; 163 ///The type of the paths. 164 typedef PredMapPath<Digraph, PredMap> Path; 165 166 ///The traits class. 150 167 typedef TR Traits; 151 ///The type of the underlying digraph. 152 typedef typename TR::Digraph Digraph; 153 154 ///\brief The type of the map that stores the last 155 ///arcs of the shortest paths. 156 typedef typename TR::PredMap PredMap; 157 ///The type of the map indicating which nodes are reached. 158 typedef typename TR::ReachedMap ReachedMap; 159 ///The type of the map indicating which nodes are processed. 160 typedef typename TR::ProcessedMap ProcessedMap; 161 ///The type of the map that stores the dists of the nodes. 162 typedef typename TR::DistMap DistMap; 168 163 169 private: 164 170 … … 168 174 typedef typename Digraph::OutArcIt OutArcIt; 169 175 170 // /Pointer to the underlying digraph.176 //Pointer to the underlying digraph. 171 177 const Digraph *G; 172 // /Pointer to the map of predecessorsarcs.178 //Pointer to the map of predecessor arcs. 173 179 PredMap *_pred; 174 // /Indicates if \ref _pred is locally allocated (\ctrue) or not.180 //Indicates if _pred is locally allocated (true) or not. 175 181 bool local_pred; 176 // /Pointer to the map of distances.182 //Pointer to the map of distances. 177 183 DistMap *_dist; 178 // /Indicates if \ref _dist is locally allocated (\ctrue) or not.184 //Indicates if _dist is locally allocated (true) or not. 179 185 bool local_dist; 180 // /Pointer to the map of reached status of the nodes.186 //Pointer to the map of reached status of the nodes. 181 187 ReachedMap *_reached; 182 // /Indicates if \ref _reached is locally allocated (\ctrue) or not.188 //Indicates if _reached is locally allocated (true) or not. 183 189 bool local_reached; 184 // /Pointer to the map of processed status of the nodes.190 //Pointer to the map of processed status of the nodes. 185 191 ProcessedMap *_processed; 186 // /Indicates if \ref _processed is locally allocated (\ctrue) or not.192 //Indicates if _processed is locally allocated (true) or not. 187 193 bool local_processed; 188 194 … … 192 198 193 199 ///Creates the maps if necessary. 194 195 200 ///\todo Better memory allocation (instead of new). 196 201 void create_maps() … … 235 240 }; 236 241 ///\brief \ref named-templ-param "Named parameter" for setting 237 /// PredMap type238 /// 239 ///\ref named-templ-param "Named parameter" for setting PredMap type240 /// 242 ///\ref PredMap type. 243 /// 244 ///\ref named-templ-param "Named parameter" for setting 245 ///\ref PredMap type. 241 246 template <class T> 242 247 struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > { … … 253 258 }; 254 259 ///\brief \ref named-templ-param "Named parameter" for setting 255 /// DistMap type256 /// 257 ///\ref named-templ-param "Named parameter" for setting DistMap type258 /// 260 ///\ref DistMap type. 261 /// 262 ///\ref named-templ-param "Named parameter" for setting 263 ///\ref DistMap type. 259 264 template <class T> 260 265 struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > { … … 271 276 }; 272 277 ///\brief \ref named-templ-param "Named parameter" for setting 273 /// ReachedMap type274 /// 275 ///\ref named-templ-param "Named parameter" for setting ReachedMap type276 /// 278 ///\ref ReachedMap type. 279 /// 280 ///\ref named-templ-param "Named parameter" for setting 281 ///\ref ReachedMap type. 277 282 template <class T> 278 283 struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > { … … 289 294 }; 290 295 ///\brief \ref named-templ-param "Named parameter" for setting 291 /// ProcessedMap type292 /// 293 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type294 /// 296 ///\ref ProcessedMap type. 297 /// 298 ///\ref named-templ-param "Named parameter" for setting 299 ///\ref ProcessedMap type. 295 300 template <class T> 296 301 struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > { … … 300 305 struct DefDigraphProcessedMapTraits : public Traits { 301 306 typedef typename Digraph::template NodeMap<bool> ProcessedMap; 302 static ProcessedMap *createProcessedMap(const Digraph & G)307 static ProcessedMap *createProcessedMap(const Digraph &g) 303 308 { 304 return new ProcessedMap( G);305 } 306 }; 307 ///\brief \ref named-templ-param "Named parameter" 308 /// for setting the ProcessedMap type to be Digraph::NodeMap<bool>.309 /// 310 ///\ref named-templ-param "Named parameter" 311 /// for setting the ProcessedMap type to be Digraph::NodeMap<bool>.309 return new ProcessedMap(g); 310 } 311 }; 312 ///\brief \ref named-templ-param "Named parameter" for setting 313 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 314 /// 315 ///\ref named-templ-param "Named parameter" for setting 316 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 312 317 ///If you don't set it explicitly, it will be automatically allocated. 313 318 template <class T> … … 323 328 ///Constructor. 324 329 325 /// \param _G the digraph the algorithm will run on.326 /// 327 Bfs(const Digraph & _G) :328 G(& _G),330 ///Constructor. 331 ///\param g The digraph the algorithm runs on. 332 Bfs(const Digraph &g) : 333 G(&g), 329 334 _pred(NULL), local_pred(false), 330 335 _dist(NULL), local_dist(false), … … 342 347 } 343 348 344 ///Sets the map storingthe predecessor arcs.345 346 ///Sets the map storingthe predecessor arcs.349 ///Sets the map that stores the predecessor arcs. 350 351 ///Sets the map that stores the predecessor arcs. 347 352 ///If you don't use this function before calling \ref run(), 348 353 ///it will allocate one. The destructor deallocates this … … 359 364 } 360 365 361 ///Sets the map indicating the reached nodes.362 363 ///Sets the map indicating the reached nodes.366 ///Sets the map that indicates which nodes are reached. 367 368 ///Sets the map that indicates which nodes are reached. 364 369 ///If you don't use this function before calling \ref run(), 365 370 ///it will allocate one. The destructor deallocates this … … 376 381 } 377 382 378 ///Sets the map indicating the processed nodes.379 380 ///Sets the map indicating the processed nodes.383 ///Sets the map that indicates which nodes are processed. 384 385 ///Sets the map that indicates which nodes are processed. 381 386 ///If you don't use this function before calling \ref run(), 382 387 ///it will allocate one. The destructor deallocates this … … 393 398 } 394 399 395 ///Sets the map storing the distances calculated by the algorithm. 396 397 ///Sets the map storing the distances calculated by the algorithm. 400 ///Sets the map that stores the distances of the nodes. 401 402 ///Sets the map that stores the distances of the nodes calculated by 403 ///the algorithm. 398 404 ///If you don't use this function before calling \ref run(), 399 405 ///it will allocate one. The destructor deallocates this … … 411 417 412 418 public: 419 413 420 ///\name Execution control 414 421 ///The simplest way to execute the algorithm is to use 415 ///one of the member functions called \ c run(...).422 ///one of the member functions called \ref lemon::Bfs::run() "run()". 416 423 ///\n 417 ///If you need more control on the execution, 418 /// first you must call \ref init(), then you can add several source nodes419 /// with \ref addSource().420 ///Finally \ref start() will perform the actual path421 /// computation.424 ///If you need more control on the execution, first you must call 425 ///\ref lemon::Bfs::init() "init()", then you can add several source 426 ///nodes with \ref lemon::Bfs::addSource() "addSource()". 427 ///Finally \ref lemon::Bfs::start() "start()" will perform the 428 ///actual path computation. 422 429 423 430 ///@{ 424 431 425 /// \briefInitializes the internal data structures.426 /// 432 ///Initializes the internal data structures. 433 427 434 ///Initializes the internal data structures. 428 435 /// … … 462 469 ///\return The processed node. 463 470 /// 464 ///\ warning The queue must not be empty!471 ///\pre The queue must not be empty. 465 472 Node processNextNode() 466 473 { … … 484 491 ///Processes the next node. 485 492 486 ///Processes the next node . And checks thatthe given target node493 ///Processes the next node and checks if the given target node 487 494 ///is reached. If the target node is reachable from the processed 488 ///node then the reached parameter will be set true. The reached 489 ///parameter should be initially false. 495 ///node, then the \c reach parameter will be set to \c true. 490 496 /// 491 497 ///\param target The target node. 492 ///\retval reach Indicates that the target node is reached. 498 ///\retval reach Indicates if the target node is reached. 499 ///It should be initially \c false. 500 /// 493 501 ///\return The processed node. 494 502 /// 495 ///\ warning The queue must not be empty!503 ///\pre The queue must not be empty. 496 504 Node processNextNode(Node target, bool& reach) 497 505 { … … 516 524 ///Processes the next node. 517 525 518 ///Processes the next node. And checks that at least one of 519 ///reached node has true value in the \c nm node map. If one node 520 ///with true value is reachable from the processed node then the 521 ///rnode parameter will be set to the first of such nodes. 522 /// 523 ///\param nm The node map of possible targets. 526 ///Processes the next node and checks if at least one of reached 527 ///nodes has \c true value in the \c nm node map. If one node 528 ///with \c true value is reachable from the processed node, then the 529 ///\c rnode parameter will be set to the first of such nodes. 530 /// 531 ///\param nm A \c bool (or convertible) node map that indicates the 532 ///possible targets. 524 533 ///\retval rnode The reached target node. 534 ///It should be initially \c INVALID. 535 /// 525 536 ///\return The processed node. 526 537 /// 527 ///\ warning The queue must not be empty!538 ///\pre The queue must not be empty. 528 539 template<class NM> 529 540 Node processNextNode(const NM& nm, Node& rnode) … … 547 558 } 548 559 549 ///Next node to be processed. 550 551 ///Next node to be processed. 552 /// 553 ///\return The next node to be processed or INVALID if the queue is 554 /// empty. 555 Node nextNode() 560 ///The next node to be processed. 561 562 ///Returns the next node to be processed or \c INVALID if the queue 563 ///is empty. 564 Node nextNode() const 556 565 { 557 566 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID; … … 559 568 560 569 ///\brief Returns \c false if there are nodes 561 ///to be processed in the queue570 ///to be processed. 562 571 /// 563 572 ///Returns \c false if there are nodes 564 ///to be processed in the queue 565 bool emptyQueue() { return _queue_tail==_queue_head; } 573 ///to be processed in the queue. 574 bool emptyQueue() const { return _queue_tail==_queue_head; } 575 566 576 ///Returns the number of the nodes to be processed. 567 577 568 578 ///Returns the number of the nodes to be processed in the queue. 569 int queueSize() { return _queue_head-_queue_tail; }579 int queueSize() const { return _queue_head-_queue_tail; } 570 580 571 581 ///Executes the algorithm. … … 573 583 ///Executes the algorithm. 574 584 /// 575 ///\pre init() must be called and at least one node should be added576 ///with addSource() before using this function.577 ///578 585 ///This method runs the %BFS algorithm from the root node(s) 579 ///in order to 580 ///compute the 581 ///shortest path to each node. The algorithm computes 582 ///- The shortest path tree. 583 ///- The distance of each node from the root(s). 586 ///in order to compute the shortest path to each node. 587 /// 588 ///The algorithm computes 589 ///- the shortest path tree (forest), 590 ///- the distance of each node from the root(s). 591 /// 592 ///\pre init() must be called and at least one root node should be 593 ///added with addSource() before using this function. 594 /// 595 ///\note <tt>b.start()</tt> is just a shortcut of the following code. 596 ///\code 597 /// while ( !b.emptyQueue() ) { 598 /// b.processNextNode(); 599 /// } 600 ///\endcode 584 601 void start() 585 602 { … … 587 604 } 588 605 589 ///Executes the algorithm until \c dest is reached. 590 591 ///Executes the algorithm until \c dest is reached. 592 /// 593 ///\pre init() must be called and at least one node should be added 594 ///with addSource() before using this function. 606 ///Executes the algorithm until the given target node is reached. 607 608 ///Executes the algorithm until the given target node is reached. 595 609 /// 596 610 ///This method runs the %BFS algorithm from the root node(s) 597 611 ///in order to compute the shortest path to \c dest. 612 /// 598 613 ///The algorithm computes 599 ///- The shortest path to \c dest. 600 ///- The distance of \c dest from the root(s). 614 ///- the shortest path to \c dest, 615 ///- the distance of \c dest from the root(s). 616 /// 617 ///\pre init() must be called and at least one root node should be 618 ///added with addSource() before using this function. 619 /// 620 ///\note <tt>b.start(t)</tt> is just a shortcut of the following code. 621 ///\code 622 /// bool reach = false; 623 /// while ( !b.emptyQueue() && !reach ) { 624 /// b.processNextNode(t, reach); 625 /// } 626 ///\endcode 601 627 void start(Node dest) 602 628 { … … 609 635 ///Executes the algorithm until a condition is met. 610 636 /// 611 /// \pre init() must be called and at least one node should be added612 /// with addSource() before using this function.613 /// 614 /// \param nm must be a bool (or convertible) node map. The615 /// algorithm will stop when it reaches a node \c v with616 /// <tt>nm[v]</tt> true.637 ///This method runs the %BFS algorithm from the root node(s) in 638 ///order to compute the shortest path to a node \c v with 639 /// <tt>nm[v]</tt> true, if such a node can be found. 640 /// 641 ///\param nm A \c bool (or convertible) node map. The algorithm 642 ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true. 617 643 /// 618 644 ///\return The reached node \c v with <tt>nm[v]</tt> true or 619 645 ///\c INVALID if no such node was found. 620 template<class NM> 621 Node start(const NM &nm) 646 /// 647 ///\pre init() must be called and at least one root node should be 648 ///added with addSource() before using this function. 649 /// 650 ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code. 651 ///\code 652 /// Node rnode = INVALID; 653 /// while ( !b.emptyQueue() && rnode == INVALID ) { 654 /// b.processNextNode(nm, rnode); 655 /// } 656 /// return rnode; 657 ///\endcode 658 template<class NodeBoolMap> 659 Node start(const NodeBoolMap &nm) 622 660 { 623 661 Node rnode = INVALID; … … 628 666 } 629 667 630 ///Runs %BFS algorithm from node \c s.631 632 ///This method runs the %BFS algorithm from a rootnode \c s633 ///in order to 634 /// compute the635 /// shortest path to each node.The algorithm computes636 ///- The shortest path tree.637 ///- The distance of each node from the root.638 /// 639 ///\note b.run(s)is just a shortcut of the following code.668 ///Runs the algorithm from the given node. 669 670 ///This method runs the %BFS algorithm from node \c s 671 ///in order to compute the shortest path to each node. 672 /// 673 ///The algorithm computes 674 ///- the shortest path tree, 675 ///- the distance of each node from the root. 676 /// 677 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code. 640 678 ///\code 641 679 /// b.init(); … … 651 689 ///Finds the shortest path between \c s and \c t. 652 690 653 ///Finds the shortest path between \c s and \c t. 654 /// 655 ///\return The length of the shortest s---t path if there exists one, 656 ///0 otherwise. 657 ///\note Apart from the return value, b.run(s) is 658 ///just a shortcut of the following code. 691 ///This method runs the %BFS algorithm from node \c s 692 ///in order to compute the shortest path to \c t. 693 /// 694 ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path, 695 ///if \c t is reachable form \c s, \c 0 otherwise. 696 /// 697 ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a 698 ///shortcut of the following code. 659 699 ///\code 660 700 /// b.init(); … … 669 709 } 670 710 711 ///Runs the algorithm to visit all nodes in the digraph. 712 713 ///This method runs the %BFS algorithm in order to 714 ///compute the shortest path to each node. 715 /// 716 ///The algorithm computes 717 ///- the shortest path tree (forest), 718 ///- the distance of each node from the root(s). 719 /// 720 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code. 721 ///\code 722 /// b.init(); 723 /// for (NodeIt n(gr); n != INVALID; ++n) { 724 /// if (!b.reached(n)) { 725 /// b.addSource(n); 726 /// b.start(); 727 /// } 728 /// } 729 ///\endcode 730 void run() { 731 init(); 732 for (NodeIt n(*G); n != INVALID; ++n) { 733 if (!reached(n)) { 734 addSource(n); 735 start(); 736 } 737 } 738 } 739 671 740 ///@} 672 741 … … 674 743 ///The result of the %BFS algorithm can be obtained using these 675 744 ///functions.\n 676 /// Before the use of these functions,677 /// either run() or start() must be calleb.745 ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start() 746 ///"start()" must be called before using them. 678 747 679 748 ///@{ 680 749 681 typedef PredMapPath<Digraph, PredMap> Path; 682 683 ///Gives back the shortest path. 684 685 ///Gives back the shortest path. 686 ///\pre The \c t should be reachable from the source. 687 Path path(Node t) 688 { 689 return Path(*G, *_pred, t); 690 } 750 ///The shortest path to a node. 751 752 ///Returns the shortest path to a node. 753 /// 754 ///\warning \c t should be reachable from the root(s). 755 /// 756 ///\pre Either \ref run() or \ref start() must be called before 757 ///using this function. 758 Path path(Node t) const { return Path(*G, *_pred, t); } 691 759 692 760 ///The distance of a node from the root(s). 693 761 694 762 ///Returns the distance of a node from the root(s). 695 ///\pre \ref run() must be called before using this function. 696 ///\warning If node \c v in unreachable from the root(s) the return value 697 ///of this function is undefined. 763 /// 764 ///\warning If node \c v is not reachable from the root(s), then 765 ///the return value of this function is undefined. 766 /// 767 ///\pre Either \ref run() or \ref start() must be called before 768 ///using this function. 698 769 int dist(Node v) const { return (*_dist)[v]; } 699 770 700 ///Returns the 'previous arc' of the shortest path tree. 701 702 ///For a node \c v it returns the 'previous arc' 703 ///of the shortest path tree, 704 ///i.e. it returns the last arc of a shortest path from the root(s) to \c 705 ///v. It is \ref INVALID 706 ///if \c v is unreachable from the root(s) or \c v is a root. The 707 ///shortest path tree used here is equal to the shortest path tree used in 708 ///\ref predNode(). 709 ///\pre Either \ref run() or \ref start() must be called before using 710 ///this function. 771 ///Returns the 'previous arc' of the shortest path tree for a node. 772 773 ///This function returns the 'previous arc' of the shortest path 774 ///tree for the node \c v, i.e. it returns the last arc of a 775 ///shortest path from the root(s) to \c v. It is \c INVALID if \c v 776 ///is not reachable from the root(s) or if \c v is a root. 777 /// 778 ///The shortest path tree used here is equal to the shortest path 779 ///tree used in \ref predNode(). 780 /// 781 ///\pre Either \ref run() or \ref start() must be called before 782 ///using this function. 711 783 Arc predArc(Node v) const { return (*_pred)[v];} 712 784 713 ///Returns the 'previous node' of the shortest path tree. 714 715 ///For a node \c v it returns the 'previous node' 716 ///of the shortest path tree, 717 ///i.e. it returns the last but one node from a shortest path from the 718 ///root(a) to \c /v. 719 ///It is INVALID if \c v is unreachable from the root(s) or 720 ///if \c v itself a root. 785 ///Returns the 'previous node' of the shortest path tree for a node. 786 787 ///This function returns the 'previous node' of the shortest path 788 ///tree for the node \c v, i.e. it returns the last but one node 789 ///from a shortest path from the root(s) to \c v. It is \c INVALID 790 ///if \c v is not reachable from the root(s) or if \c v is a root. 791 /// 721 792 ///The shortest path tree used here is equal to the shortest path 722 793 ///tree used in \ref predArc(). 794 /// 723 795 ///\pre Either \ref run() or \ref start() must be called before 724 796 ///using this function. … … 726 798 G->source((*_pred)[v]); } 727 799 728 ///Returns a reference to the NodeMap of distances. 729 730 ///Returns a reference to the NodeMap of distances. 731 ///\pre Either \ref run() or \ref init() must 732 ///be called before using this function. 800 ///\brief Returns a const reference to the node map that stores the 801 /// distances of the nodes. 802 /// 803 ///Returns a const reference to the node map that stores the distances 804 ///of the nodes calculated by the algorithm. 805 /// 806 ///\pre Either \ref run() or \ref init() 807 ///must be called before using this function. 733 808 const DistMap &distMap() const { return *_dist;} 734 809 735 ///Returns a reference to the shortest path tree map. 736 737 ///Returns a reference to the NodeMap of the arcs of the 738 ///shortest path tree. 810 ///\brief Returns a const reference to the node map that stores the 811 ///predecessor arcs. 812 /// 813 ///Returns a const reference to the node map that stores the predecessor 814 ///arcs, which form the shortest path tree. 815 /// 739 816 ///\pre Either \ref run() or \ref init() 740 817 ///must be called before using this function. 741 818 const PredMap &predMap() const { return *_pred;} 742 819 743 ///Checks if a node is reachable from the root. 744 745 ///Returns \c true if \c v is reachable from the root. 746 ///\warning The source nodes are indicated as unreached. 820 ///Checks if a node is reachable from the root(s). 821 822 ///Returns \c true if \c v is reachable from the root(s). 747 823 ///\pre Either \ref run() or \ref start() 748 824 ///must be called before using this function. 749 /// 750 bool reached(Node v) { return (*_reached)[v]; } 825 bool reached(Node v) const { return (*_reached)[v]; } 751 826 752 827 ///@} 753 828 }; 754 829 755 ///Default traits class of Bfsfunction.756 757 ///Default traits class of Bfsfunction.830 ///Default traits class of bfs() function. 831 832 ///Default traits class of bfs() function. 758 833 ///\tparam GR Digraph type. 759 834 template<class GR> 760 835 struct BfsWizardDefaultTraits 761 836 { 762 ///The digraph typethe algorithm runs on.837 ///The type of the digraph the algorithm runs on. 763 838 typedef GR Digraph; 764 ///\brief The type of the map that stores the last 839 840 ///\brief The type of the map that stores the predecessor 765 841 ///arcs of the shortest paths. 766 842 /// 767 ///The type of the map that stores the last843 ///The type of the map that stores the predecessor 768 844 ///arcs of the shortest paths. 769 845 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 770 /// 771 typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap; 772 ///Instantiates a PredMap. 846 typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap; 847 ///Instantiates a \ref PredMap. 773 848 774 849 ///This function instantiates a \ref PredMap. 775 ///\param g is the digraph, to which we would like to define the PredMap. 850 ///\param g is the digraph, to which we would like to define the 851 ///\ref PredMap. 776 852 ///\todo The digraph alone may be insufficient to initialize 777 853 #ifdef DOXYGEN 778 static PredMap *createPredMap(const GR&g)854 static PredMap *createPredMap(const Digraph &g) 779 855 #else 780 static PredMap *createPredMap(const GR&)856 static PredMap *createPredMap(const Digraph &) 781 857 #endif 782 858 { … … 788 864 ///The type of the map that indicates which nodes are processed. 789 865 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 790 ///\todo named parameter to set this type, function to read and write.791 866 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 792 ///Instantiates a ProcessedMap.867 ///Instantiates a \ref ProcessedMap. 793 868 794 869 ///This function instantiates a \ref ProcessedMap. 795 870 ///\param g is the digraph, to which 796 ///we would like to define the \ref ProcessedMap 871 ///we would like to define the \ref ProcessedMap. 797 872 #ifdef DOXYGEN 798 static ProcessedMap *createProcessedMap(const GR&g)873 static ProcessedMap *createProcessedMap(const Digraph &g) 799 874 #else 800 static ProcessedMap *createProcessedMap(const GR&)875 static ProcessedMap *createProcessedMap(const Digraph &) 801 876 #endif 802 877 { 803 878 return new ProcessedMap(); 804 879 } 880 805 881 ///The type of the map that indicates which nodes are reached. 806 882 807 883 ///The type of the map that indicates which nodes are reached. 884 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 885 typedef typename Digraph::template NodeMap<bool> ReachedMap; 886 ///Instantiates a \ref ReachedMap. 887 888 ///This function instantiates a \ref ReachedMap. 889 ///\param g is the digraph, to which 890 ///we would like to define the \ref ReachedMap. 891 static ReachedMap *createReachedMap(const Digraph &g) 892 { 893 return new ReachedMap(g); 894 } 895 896 ///The type of the map that stores the distances of the nodes. 897 898 ///The type of the map that stores the distances of the nodes. 808 899 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 809 ///\todo named parameter to set this type, function to read and write.810 typedef typename Digraph::template NodeMap<bool> ReachedMap;811 ///Instantiates a ReachedMap.812 813 ///This function instantiates a \ref ReachedMap.814 ///\param G is the digraph, to which815 ///we would like to define the \ref ReachedMap.816 static ReachedMap *createReachedMap(const GR &G)817 {818 return new ReachedMap(G);819 }820 ///The type of the map that stores the dists of the nodes.821 822 ///The type of the map that stores the dists of the nodes.823 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.824 900 /// 825 901 typedef NullMap<typename Digraph::Node,int> DistMap; 826 ///Instantiates a DistMap.902 ///Instantiates a \ref DistMap. 827 903 828 904 ///This function instantiates a \ref DistMap. … … 830 906 ///the \ref DistMap 831 907 #ifdef DOXYGEN 832 static DistMap *createDistMap(const GR&g)908 static DistMap *createDistMap(const Digraph &g) 833 909 #else 834 static DistMap *createDistMap(const GR&)910 static DistMap *createDistMap(const Digraph &) 835 911 #endif 836 912 { … … 839 915 }; 840 916 841 /// Default traits used by \ref BfsWizard917 /// Default traits class used by \ref BfsWizard 842 918 843 919 /// To make it easier to use Bfs algorithm 844 /// we have created a wizard class.920 /// we have created a wizard class. 845 921 /// This \ref BfsWizard class needs default traits, 846 /// as well as the \ref Bfs class.922 /// as well as the \ref Bfs class. 847 923 /// The \ref BfsWizardBase is a class to be the default traits of the 848 924 /// \ref BfsWizard class. … … 853 929 typedef BfsWizardDefaultTraits<GR> Base; 854 930 protected: 855 // / Type of the nodes in the digraph.931 //The type of the nodes in the digraph. 856 932 typedef typename Base::Digraph::Node Node; 857 933 858 // / Pointer to the underlying digraph.934 //Pointer to the digraph the algorithm runs on. 859 935 void *_g; 860 // /Pointer to the map of reached nodes.936 //Pointer to the map of reached nodes. 861 937 void *_reached; 862 // /Pointer to the map of processed nodes.938 //Pointer to the map of processed nodes. 863 939 void *_processed; 864 // /Pointer to the map of predecessors arcs.940 //Pointer to the map of predecessors arcs. 865 941 void *_pred; 866 // /Pointer to the map of distances.942 //Pointer to the map of distances. 867 943 void *_dist; 868 // /Pointer to the source node.944 //Pointer to the source node. 869 945 Node _source; 870 946 … … 875 951 /// all of the attributes to default values (0, INVALID). 876 952 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), 877 953 _dist(0), _source(INVALID) {} 878 954 879 955 /// Constructor. … … 882 958 /// listed in the parameters list. 883 959 /// Others are initiated to 0. 884 /// \param g is the initial value of \ref _g885 /// \param s is the initial value of \ref _source960 /// \param g The digraph the algorithm runs on. 961 /// \param s The source node. 886 962 BfsWizardBase(const GR &g, Node s=INVALID) : 887 963 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), … … 890 966 }; 891 967 892 /// A class to make the usage of Bfs algorithm easier 893 894 /// This class is created to make it easier to use Bfs algorithm. 895 /// It uses the functions and features of the plain \ref Bfs, 896 /// but it is much simpler to use it. 968 /// Auxiliary class for the function type interface of BFS algorithm. 969 970 /// This auxiliary class is created to implement the function type 971 /// interface of \ref Bfs algorithm. It uses the functions and features 972 /// of the plain \ref Bfs, but it is much simpler to use it. 973 /// It should only be used through the \ref bfs() function, which makes 974 /// it easier to use the algorithm. 897 975 /// 898 976 /// Simplicity means that the way to change the types defined … … 903 981 /// the original class by using the :: 904 982 /// operator. In the case of \ref BfsWizard only 905 /// a function have to be called and it will983 /// a function have to be called, and it will 906 984 /// return the needed class. 907 985 /// 908 /// It does not have own \ref run method. When its \ref run method is called909 /// i t initiates a plain \ref Bfs class, and calls the \ref Bfs::run910 /// method of it.986 /// It does not have own \ref run() method. When its \ref run() method 987 /// is called, it initiates a plain \ref Bfs object, and calls the 988 /// \ref Bfs::run() method of it. 911 989 template<class TR> 912 990 class BfsWizard : public TR … … 914 992 typedef TR Base; 915 993 916 ///The type of the underlying digraph.994 ///The type of the digraph the algorithm runs on. 917 995 typedef typename TR::Digraph Digraph; 918 //\e 996 919 997 typedef typename Digraph::Node Node; 920 //\e921 998 typedef typename Digraph::NodeIt NodeIt; 922 //\e923 999 typedef typename Digraph::Arc Arc; 924 //\e925 1000 typedef typename Digraph::OutArcIt OutArcIt; 926 1001 927 ///\brief The type of the map that stores 928 ///the reached nodes 929 typedef typename TR::ReachedMap ReachedMap; 930 ///\brief The type of the map that stores 931 ///the processed nodes 932 typedef typename TR::ProcessedMap ProcessedMap; 933 ///\brief The type of the map that stores the last 1002 ///\brief The type of the map that stores the predecessor 934 1003 ///arcs of the shortest paths. 935 1004 typedef typename TR::PredMap PredMap; 936 /// The type of the map that stores the dists of the nodes.1005 ///\brief The type of the map that stores the distances of the nodes. 937 1006 typedef typename TR::DistMap DistMap; 1007 ///\brief The type of the map that indicates which nodes are reached. 1008 typedef typename TR::ReachedMap ReachedMap; 1009 ///\brief The type of the map that indicates which nodes are processed. 1010 typedef typename TR::ProcessedMap ProcessedMap; 938 1011 939 1012 public: 1013 940 1014 /// Constructor. 941 1015 BfsWizard() : TR() {} … … 953 1027 ~BfsWizard() {} 954 1028 955 ///Runs B fs algorithm from a givennode.956 957 ///Runs B fs algorithm from a givennode.958 ///The node can be given by the \ref sourcefunction.1029 ///Runs BFS algorithm from a source node. 1030 1031 ///Runs BFS algorithm from a source node. 1032 ///The node can be given with the \ref source() function. 959 1033 void run() 960 1034 { … … 972 1046 } 973 1047 974 ///Runs B fsalgorithm from the given node.975 976 ///Runs B fsalgorithm from the given node.1048 ///Runs BFS algorithm from the given node. 1049 1050 ///Runs BFS algorithm from the given node. 977 1051 ///\param s is the given source. 978 1052 void run(Node s) … … 980 1054 Base::_source=s; 981 1055 run(); 1056 } 1057 1058 /// Sets the source node, from which the Bfs algorithm runs. 1059 1060 /// Sets the source node, from which the Bfs algorithm runs. 1061 /// \param s is the source node. 1062 BfsWizard<TR> &source(Node s) 1063 { 1064 Base::_source=s; 1065 return *this; 982 1066 } 983 1067 … … 988 1072 DefPredMapBase(const TR &b) : TR(b) {} 989 1073 }; 990 991 1074 ///\brief \ref named-templ-param "Named parameter" 992 ///f unction for setting PredMap1075 ///for setting \ref PredMap object. 993 1076 /// 994 1077 /// \ref named-templ-param "Named parameter" 995 ///function for setting PredMap 996 /// 1078 ///for setting \ref PredMap object. 997 1079 template<class T> 998 1080 BfsWizard<DefPredMapBase<T> > predMap(const T &t) … … 1001 1083 return BfsWizard<DefPredMapBase<T> >(*this); 1002 1084 } 1003 1004 1085 1005 1086 template<class T> … … 1009 1090 DefReachedMapBase(const TR &b) : TR(b) {} 1010 1091 }; 1011 1012 1092 ///\brief \ref named-templ-param "Named parameter" 1013 ///f unction for setting ReachedMap1093 ///for setting \ref ReachedMap object. 1014 1094 /// 1015 1095 /// \ref named-templ-param "Named parameter" 1016 ///function for setting ReachedMap 1017 /// 1096 ///for setting \ref ReachedMap object. 1018 1097 template<class T> 1019 1098 BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) … … 1022 1101 return BfsWizard<DefReachedMapBase<T> >(*this); 1023 1102 } 1024 1025 1103 1026 1104 template<class T> … … 1030 1108 DefProcessedMapBase(const TR &b) : TR(b) {} 1031 1109 }; 1032 1033 1110 ///\brief \ref named-templ-param "Named parameter" 1034 ///f unction for setting ProcessedMap1111 ///for setting \ref ProcessedMap object. 1035 1112 /// 1036 1113 /// \ref named-templ-param "Named parameter" 1037 ///function for setting ProcessedMap 1038 /// 1114 ///for setting \ref ProcessedMap object. 1039 1115 template<class T> 1040 1116 BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) … … 1043 1119 return BfsWizard<DefProcessedMapBase<T> >(*this); 1044 1120 } 1045 1046 1121 1047 1122 template<class T> … … 1051 1126 DefDistMapBase(const TR &b) : TR(b) {} 1052 1127 }; 1053 1054 1128 ///\brief \ref named-templ-param "Named parameter" 1055 ///f unction for setting DistMap type1129 ///for setting \ref DistMap object. 1056 1130 /// 1057 1131 /// \ref named-templ-param "Named parameter" 1058 ///function for setting DistMap type 1059 /// 1132 ///for setting \ref DistMap object. 1060 1133 template<class T> 1061 1134 BfsWizard<DefDistMapBase<T> > distMap(const T &t) … … 1063 1136 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1064 1137 return BfsWizard<DefDistMapBase<T> >(*this); 1065 }1066 1067 /// Sets the source node, from which the Bfs algorithm runs.1068 1069 /// Sets the source node, from which the Bfs algorithm runs.1070 /// \param s is the source node.1071 BfsWizard<TR> &source(Node s)1072 {1073 Base::_source=s;1074 return *this;1075 1138 } 1076 1139 … … 1102 1165 1103 1166 #ifdef DOXYGEN 1104 /// \brief Visitor class for bfs.1167 /// \brief Visitor class for BFS. 1105 1168 /// 1106 1169 /// This class defines the interface of the BfsVisit events, and 1107 /// it could be the base of a real Visitor class.1170 /// it could be the base of a real visitor class. 1108 1171 template <typename _Digraph> 1109 1172 struct BfsVisitor { … … 1111 1174 typedef typename Digraph::Arc Arc; 1112 1175 typedef typename Digraph::Node Node; 1113 /// \brief Called when the arc reach a node. 1114 /// 1115 /// It is called when the bfs find an arc which target is not 1116 /// reached yet. 1176 /// \brief Called for the source node(s) of the BFS. 1177 /// 1178 /// This function is called for the source node(s) of the BFS. 1179 void start(const Node& node) {} 1180 /// \brief Called when a node is reached first time. 1181 /// 1182 /// This function is called when a node is reached first time. 1183 void reach(const Node& node) {} 1184 /// \brief Called when a node is processed. 1185 /// 1186 /// This function is called when a node is processed. 1187 void process(const Node& node) {} 1188 /// \brief Called when an arc reaches a new node. 1189 /// 1190 /// This function is called when the BFS finds an arc whose target node 1191 /// is not reached yet. 1117 1192 void discover(const Arc& arc) {} 1118 /// \brief Called when the node reached first time. 1119 /// 1120 /// It is Called when the node reached first time. 1121 void reach(const Node& node) {} 1122 /// \brief Called when the arc examined but target of the arc 1193 /// \brief Called when an arc is examined but its target node is 1123 1194 /// already discovered. 1124 1195 /// 1125 /// It called when the arc examined but the target of the arc1196 /// This function is called when an arc is examined but its target node is 1126 1197 /// already discovered. 1127 1198 void examine(const Arc& arc) {} 1128 /// \brief Called for the source node of the bfs.1129 ///1130 /// It is called for the source node of the bfs.1131 void start(const Node& node) {}1132 /// \brief Called when the node processed.1133 ///1134 /// It is Called when the node processed.1135 void process(const Node& node) {}1136 1199 }; 1137 1200 #else … … 1141 1204 typedef typename Digraph::Arc Arc; 1142 1205 typedef typename Digraph::Node Node; 1206 void start(const Node&) {} 1207 void reach(const Node&) {} 1208 void process(const Node&) {} 1143 1209 void discover(const Arc&) {} 1144 void reach(const Node&) {}1145 1210 void examine(const Arc&) {} 1146 void start(const Node&) {}1147 void process(const Node&) {}1148 1211 1149 1212 template <typename _Visitor> … … 1152 1215 Arc arc; 1153 1216 Node node; 1217 visitor.start(node); 1218 visitor.reach(node); 1219 visitor.process(node); 1154 1220 visitor.discover(arc); 1155 visitor.reach(node);1156 1221 visitor.examine(arc); 1157 visitor.start(node);1158 visitor.process(node);1159 1222 } 1160 1223 _Visitor& visitor; … … 1166 1229 /// 1167 1230 /// Default traits class of BfsVisit class. 1168 /// \tparam _Digraph Digraph type.1231 /// \tparam _Digraph The type of the digraph the algorithm runs on. 1169 1232 template<class _Digraph> 1170 1233 struct BfsVisitDefaultTraits { 1171 1234 1172 /// \brief The digraph typethe algorithm runs on.1235 /// \brief The type of the digraph the algorithm runs on. 1173 1236 typedef _Digraph Digraph; 1174 1237 … … 1176 1239 /// 1177 1240 /// The type of the map that indicates which nodes are reached. 1178 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. 1179 /// \todo named parameter to set this type, function to read and write. 1241 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1180 1242 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1181 1243 1182 /// \brief Instantiates a ReachedMap.1244 /// \brief Instantiates a \ref ReachedMap. 1183 1245 /// 1184 1246 /// This function instantiates a \ref ReachedMap. … … 1193 1255 /// \ingroup search 1194 1256 /// 1195 /// \brief %BFS Visit algorithm class.1257 /// \brief %BFS algorithm class with visitor interface. 1196 1258 /// 1197 1259 /// This class provides an efficient implementation of the %BFS algorithm … … 1200 1262 /// The %BfsVisit class provides an alternative interface to the Bfs 1201 1263 /// class. It works with callback mechanism, the BfsVisit object calls 1202 /// on every bfs event the \c Visitor class member functions.1264 /// the member functions of the \c Visitor class on every BFS event. 1203 1265 /// 1204 /// \tparam _Digraph The digraph typethe algorithm runs on.1266 /// \tparam _Digraph The type of the digraph the algorithm runs on. 1205 1267 /// The default value is 1206 /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it1207 /// is only passed to \ref BfsDefaultTraits.1208 /// \tparam _Visitor The Visitor object for the algorithm. The1209 /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitorwhich1210 /// does not observe the B fs events. If you want to observe the bfs1211 /// events you should implement your own Visitor class.1268 /// \ref ListDigraph. The value of _Digraph is not used directly by 1269 /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits. 1270 /// \tparam _Visitor The Visitor type that is used by the algorithm. 1271 /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which 1272 /// does not observe the BFS events. If you want to observe the BFS 1273 /// events, you should implement your own visitor class. 1212 1274 /// \tparam _Traits Traits class to set various data types used by the 1213 1275 /// algorithm. The default traits class is 1214 1276 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>". 1215 1277 /// See \ref BfsVisitDefaultTraits for the documentation of 1216 /// a B fsvisit traits class.1278 /// a BFS visit traits class. 1217 1279 #ifdef DOXYGEN 1218 1280 template <typename _Digraph, typename _Visitor, typename _Traits> … … 1228 1290 /// 1229 1291 /// This error represents problems in the initialization 1230 /// of the parameters of the algorithm s.1292 /// of the parameters of the algorithm. 1231 1293 class UninitializedParameter : public lemon::UninitializedParameter { 1232 1294 public: … … 1237 1299 }; 1238 1300 1301 ///The traits class. 1239 1302 typedef _Traits Traits; 1240 1303 1304 ///The type of the digraph the algorithm runs on. 1241 1305 typedef typename Traits::Digraph Digraph; 1242 1306 1307 ///The visitor type used by the algorithm. 1243 1308 typedef _Visitor Visitor; 1244 1309 1245 ///The type of the map indicatingwhich nodes are reached.1310 ///The type of the map that indicates which nodes are reached. 1246 1311 typedef typename Traits::ReachedMap ReachedMap; 1247 1312 … … 1253 1318 typedef typename Digraph::OutArcIt OutArcIt; 1254 1319 1255 // /Pointer to the underlying digraph.1320 //Pointer to the underlying digraph. 1256 1321 const Digraph *_digraph; 1257 // /Pointer to the visitor object.1322 //Pointer to the visitor object. 1258 1323 Visitor *_visitor; 1259 // /Pointer to the map of reached status of the nodes.1324 //Pointer to the map of reached status of the nodes. 1260 1325 ReachedMap *_reached; 1261 // /Indicates if \ref _reached is locally allocated (\ctrue) or not.1326 //Indicates if _reached is locally allocated (true) or not. 1262 1327 bool local_reached; 1263 1328 … … 1265 1330 int _list_front, _list_back; 1266 1331 1267 /// \brief Creates the maps if necessary. 1268 /// 1269 /// Creates the maps if necessary. 1332 ///Creates the maps if necessary. 1333 ///\todo Better memory allocation (instead of new). 1270 1334 void create_maps() { 1271 1335 if(!_reached) { … … 1294 1358 }; 1295 1359 /// \brief \ref named-templ-param "Named parameter" for setting 1296 /// ReachedMap type 1297 /// 1298 /// \ref named-templ-param "Named parameter" for setting ReachedMap type 1360 /// ReachedMap type. 1361 /// 1362 /// \ref named-templ-param "Named parameter" for setting ReachedMap type. 1299 1363 template <class T> 1300 1364 struct DefReachedMap : public BfsVisit< Digraph, Visitor, … … 1310 1374 /// Constructor. 1311 1375 /// 1312 /// \param digraph the digraph the algorithm will run on. 1313 /// \param visitor The visitor of the algorithm. 1314 /// 1376 /// \param digraph The digraph the algorithm runs on. 1377 /// \param visitor The visitor object of the algorithm. 1315 1378 BfsVisit(const Digraph& digraph, Visitor& visitor) 1316 1379 : _digraph(&digraph), _visitor(&visitor), … … 1318 1381 1319 1382 /// \brief Destructor. 1320 ///1321 /// Destructor.1322 1383 ~BfsVisit() { 1323 1384 if(local_reached) delete _reached; 1324 1385 } 1325 1386 1326 /// \brief Sets the map indicating if a node isreached.1327 /// 1328 /// Sets the map indicating if a node isreached.1387 /// \brief Sets the map that indicates which nodes are reached. 1388 /// 1389 /// Sets the map that indicates which nodes are reached. 1329 1390 /// If you don't use this function before calling \ref run(), 1330 /// it will allocate one. The dest uctor deallocates this1391 /// it will allocate one. The destructor deallocates this 1331 1392 /// automatically allocated map, of course. 1332 1393 /// \return <tt> (*this) </tt> … … 1341 1402 1342 1403 public: 1404 1343 1405 /// \name Execution control 1344 1406 /// The simplest way to execute the algorithm is to use 1345 /// one of the member functions called \c run(...). 1407 /// one of the member functions called \ref lemon::BfsVisit::run() 1408 /// "run()". 1346 1409 /// \n 1347 /// If you need more control on the execution, 1348 /// first you must call \ref init(), then you can adda source node1349 /// with \ref addSource().1350 /// Finally \ref start() will perform the actual path1351 /// computation.1410 /// If you need more control on the execution, first you must call 1411 /// \ref lemon::BfsVisit::init() "init()", then you can add several 1412 /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()". 1413 /// Finally \ref lemon::BfsVisit::start() "start()" will perform the 1414 /// actual path computation. 1352 1415 1353 1416 /// @{ 1417 1354 1418 /// \brief Initializes the internal data structures. 1355 1419 /// 1356 1420 /// Initializes the internal data structures. 1357 ///1358 1421 void init() { 1359 1422 create_maps(); … … 1383 1446 /// \return The processed node. 1384 1447 /// 1385 /// \pre The queue must not be empty !1448 /// \pre The queue must not be empty. 1386 1449 Node processNextNode() { 1387 1450 Node n = _list[++_list_front]; … … 1404 1467 /// \brief Processes the next node. 1405 1468 /// 1406 /// Processes the next node . And checks thatthe given target node1469 /// Processes the next node and checks if the given target node 1407 1470 /// is reached. If the target node is reachable from the processed 1408 /// node then the reached parameter will be set true. The reached 1409 /// parameter should be initially false. 1471 /// node, then the \c reach parameter will be set to \c true. 1410 1472 /// 1411 1473 /// \param target The target node. 1412 /// \retval reach Indicates that the target node is reached. 1474 /// \retval reach Indicates if the target node is reached. 1475 /// It should be initially \c false. 1476 /// 1413 1477 /// \return The processed node. 1414 1478 /// 1415 /// \ warning The queue must not be empty!1479 /// \pre The queue must not be empty. 1416 1480 Node processNextNode(Node target, bool& reach) { 1417 1481 Node n = _list[++_list_front]; … … 1435 1499 /// \brief Processes the next node. 1436 1500 /// 1437 /// Processes the next node. And checks that at least one of 1438 /// reached node has true value in the \c nm node map. If one node 1439 /// with true value is reachable from the processed node then the 1440 /// rnode parameter will be set to the first of such nodes. 1441 /// 1442 /// \param nm The node map of possible targets. 1501 /// Processes the next node and checks if at least one of reached 1502 /// nodes has \c true value in the \c nm node map. If one node 1503 /// with \c true value is reachable from the processed node, then the 1504 /// \c rnode parameter will be set to the first of such nodes. 1505 /// 1506 /// \param nm A \c bool (or convertible) node map that indicates the 1507 /// possible targets. 1443 1508 /// \retval rnode The reached target node. 1509 /// It should be initially \c INVALID. 1510 /// 1444 1511 /// \return The processed node. 1445 1512 /// 1446 /// \ warning The queue must not be empty!1513 /// \pre The queue must not be empty. 1447 1514 template <typename NM> 1448 1515 Node processNextNode(const NM& nm, Node& rnode) { … … 1465 1532 } 1466 1533 1467 /// \brief Next node to be processed. 1468 /// 1469 /// Next node to be processed. 1470 /// 1471 /// \return The next node to be processed or INVALID if the stack is 1472 /// empty. 1473 Node nextNode() { 1534 /// \brief The next node to be processed. 1535 /// 1536 /// Returns the next node to be processed or \c INVALID if the queue 1537 /// is empty. 1538 Node nextNode() const { 1474 1539 return _list_front != _list_back ? _list[_list_front + 1] : INVALID; 1475 1540 } 1476 1541 1477 1542 /// \brief Returns \c false if there are nodes 1478 /// to be processed in the queue1543 /// to be processed. 1479 1544 /// 1480 1545 /// Returns \c false if there are nodes 1481 /// to be processed in the queue 1482 bool emptyQueue() { return _list_front == _list_back; }1546 /// to be processed in the queue. 1547 bool emptyQueue() const { return _list_front == _list_back; } 1483 1548 1484 1549 /// \brief Returns the number of the nodes to be processed. 1485 1550 /// 1486 1551 /// Returns the number of the nodes to be processed in the queue. 1487 int queueSize() { return _list_back - _list_front; }1552 int queueSize() const { return _list_back - _list_front; } 1488 1553 1489 1554 /// \brief Executes the algorithm. … … 1491 1556 /// Executes the algorithm. 1492 1557 /// 1493 /// \pre init() must be called and at least one node should be added 1558 /// This method runs the %BFS algorithm from the root node(s) 1559 /// in order to compute the shortest path to each node. 1560 /// 1561 /// The algorithm computes 1562 /// - the shortest path tree (forest), 1563 /// - the distance of each node from the root(s). 1564 /// 1565 /// \pre init() must be called and at least one root node should be added 1494 1566 /// with addSource() before using this function. 1567 /// 1568 /// \note <tt>b.start()</tt> is just a shortcut of the following code. 1569 /// \code 1570 /// while ( !b.emptyQueue() ) { 1571 /// b.processNextNode(); 1572 /// } 1573 /// \endcode 1495 1574 void start() { 1496 1575 while ( !emptyQueue() ) processNextNode(); 1497 1576 } 1498 1577 1499 /// \brief Executes the algorithm until \c dest is reached. 1500 /// 1501 /// Executes the algorithm until \c dest is reached. 1502 /// 1503 /// \pre init() must be called and at least one node should be added 1504 /// with addSource() before using this function. 1578 /// \brief Executes the algorithm until the given target node is reached. 1579 /// 1580 /// Executes the algorithm until the given target node is reached. 1581 /// 1582 /// This method runs the %BFS algorithm from the root node(s) 1583 /// in order to compute the shortest path to \c dest. 1584 /// 1585 /// The algorithm computes 1586 /// - the shortest path to \c dest, 1587 /// - the distance of \c dest from the root(s). 1588 /// 1589 /// \pre init() must be called and at least one root node should be 1590 /// added with addSource() before using this function. 1591 /// 1592 /// \note <tt>b.start(t)</tt> is just a shortcut of the following code. 1593 /// \code 1594 /// bool reach = false; 1595 /// while ( !b.emptyQueue() && !reach ) { 1596 /// b.processNextNode(t, reach); 1597 /// } 1598 /// \endcode 1505 1599 void start(Node dest) { 1506 1600 bool reach = false; … … 1512 1606 /// Executes the algorithm until a condition is met. 1513 1607 /// 1514 /// \pre init() must be called and at least one node should be added 1515 /// with addSource() before using this function. 1516 /// 1517 ///\param nm must be a bool (or convertible) node map. The 1518 ///algorithm will stop when it reaches a node \c v with 1608 /// This method runs the %BFS algorithm from the root node(s) in 1609 /// order to compute the shortest path to a node \c v with 1610 /// <tt>nm[v]</tt> true, if such a node can be found. 1611 /// 1612 /// \param nm must be a bool (or convertible) node map. The 1613 /// algorithm will stop when it reaches a node \c v with 1519 1614 /// <tt>nm[v]</tt> true. 1520 1615 /// 1521 ///\return The reached node \c v with <tt>nm[v]</tt> true or 1522 ///\c INVALID if no such node was found. 1616 /// \return The reached node \c v with <tt>nm[v]</tt> true or 1617 /// \c INVALID if no such node was found. 1618 /// 1619 /// \pre init() must be called and at least one root node should be 1620 /// added with addSource() before using this function. 1621 /// 1622 /// \note <tt>b.start(nm)</tt> is just a shortcut of the following code. 1623 /// \code 1624 /// Node rnode = INVALID; 1625 /// while ( !b.emptyQueue() && rnode == INVALID ) { 1626 /// b.processNextNode(nm, rnode); 1627 /// } 1628 /// return rnode; 1629 /// \endcode 1523 1630 template <typename NM> 1524 1631 Node start(const NM &nm) { … … 1530 1637 } 1531 1638 1532 /// \brief Runs %BFSVisit algorithm from node \c s. 1533 /// 1534 /// This method runs the %BFS algorithm from a root node \c s. 1535 /// \note b.run(s) is just a shortcut of the following code. 1639 /// \brief Runs the algorithm from the given node. 1640 /// 1641 /// This method runs the %BFS algorithm from node \c s 1642 /// in order to compute the shortest path to each node. 1643 /// 1644 /// The algorithm computes 1645 /// - the shortest path tree, 1646 /// - the distance of each node from the root. 1647 /// 1648 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code. 1536 1649 ///\code 1537 1650 /// b.init(); … … 1545 1658 } 1546 1659 1547 /// \brief Runs %BFSVisitalgorithm to visit all nodes in the digraph.1660 /// \brief Runs the algorithm to visit all nodes in the digraph. 1548 1661 /// 1549 1662 /// This method runs the %BFS algorithm in order to 1550 /// compute the %BFS path to each node. The algorithm computes 1551 /// - The %BFS tree. 1552 /// - The distance of each node from the root in the %BFS tree. 1553 /// 1554 ///\note b.run() is just a shortcut of the following code. 1663 /// compute the shortest path to each node. 1664 /// 1665 /// The algorithm computes 1666 /// - the shortest path tree (forest), 1667 /// - the distance of each node from the root(s). 1668 /// 1669 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code. 1555 1670 ///\code 1556 1671 /// b.init(); 1557 /// for (NodeIt it(digraph); it != INVALID; ++it) {1558 /// if (!b.reached( it)) {1559 /// b.addSource( it);1672 /// for (NodeIt n(gr); n != INVALID; ++n) { 1673 /// if (!b.reached(n)) { 1674 /// b.addSource(n); 1560 1675 /// b.start(); 1561 1676 /// } … … 1571 1686 } 1572 1687 } 1688 1573 1689 ///@} 1574 1690 … … 1576 1692 /// The result of the %BFS algorithm can be obtained using these 1577 1693 /// functions.\n 1578 /// Before the use of these functions, 1579 /// either run() or start() must be called. 1694 /// Either \ref lemon::BfsVisit::run() "run()" or 1695 /// \ref lemon::BfsVisit::start() "start()" must be called before 1696 /// using them. 1580 1697 ///@{ 1581 1698 1582 /// \brief Checks if a node is reachable from the root .1699 /// \brief Checks if a node is reachable from the root(s). 1583 1700 /// 1584 1701 /// Returns \c true if \c v is reachable from the root(s). 1585 /// \warning The source nodes are inditated as unreachable.1586 1702 /// \pre Either \ref run() or \ref start() 1587 1703 /// must be called before using this function. 1588 ///1589 1704 bool reached(Node v) { return (*_reached)[v]; } 1705 1590 1706 ///@} 1707 1591 1708 }; 1592 1709 … … 1594 1711 1595 1712 #endif 1596 -
lemon/dfs.h
r210 r244 22 22 ///\ingroup search 23 23 ///\file 24 ///\brief D fsalgorithm.24 ///\brief DFS algorithm. 25 25 26 26 #include <lemon/list_graph.h> … … 29 29 #include <lemon/bits/invalid.h> 30 30 #include <lemon/error.h> 31 #include <lemon/assert.h> 31 32 #include <lemon/maps.h> 32 33 33 #include <lemon/concept_check.h>34 35 34 namespace lemon { 36 37 35 38 36 ///Default traits class of Dfs class. … … 43 41 struct DfsDefaultTraits 44 42 { 45 ///The digraph typethe algorithm runs on.43 ///The type of the digraph the algorithm runs on. 46 44 typedef GR Digraph; 47 ///\brief The type of the map that stores the last 45 46 ///\brief The type of the map that stores the predecessor 48 47 ///arcs of the %DFS paths. 49 48 /// 50 ///The type of the map that stores the last49 ///The type of the map that stores the predecessor 51 50 ///arcs of the %DFS paths. 52 51 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 53 /// 54 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap; 55 ///Instantiates a PredMap. 52 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 53 ///Instantiates a \ref PredMap. 56 54 57 55 ///This function instantiates a \ref PredMap. 58 ///\param G is the digraph, to which we would like to define the PredMap. 56 ///\param g is the digraph, to which we would like to define the 57 ///\ref PredMap. 59 58 ///\todo The digraph alone may be insufficient to initialize 60 static PredMap *createPredMap(const GR &G)61 { 62 return new PredMap( G);59 static PredMap *createPredMap(const Digraph &g) 60 { 61 return new PredMap(g); 63 62 } 64 63 … … 67 66 ///The type of the map that indicates which nodes are processed. 68 67 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 69 /// \todo named parameter to set this type, function to read and write.68 ///By default it is a NullMap. 70 69 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 71 ///Instantiates a ProcessedMap.70 ///Instantiates a \ref ProcessedMap. 72 71 73 72 ///This function instantiates a \ref ProcessedMap. … … 75 74 ///we would like to define the \ref ProcessedMap 76 75 #ifdef DOXYGEN 77 static ProcessedMap *createProcessedMap(const GR&g)76 static ProcessedMap *createProcessedMap(const Digraph &g) 78 77 #else 79 static ProcessedMap *createProcessedMap(const GR&)78 static ProcessedMap *createProcessedMap(const Digraph &) 80 79 #endif 81 80 { 82 81 return new ProcessedMap(); 83 82 } 83 84 84 ///The type of the map that indicates which nodes are reached. 85 85 86 86 ///The type of the map that indicates which nodes are reached. 87 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 88 typedef typename Digraph::template NodeMap<bool> ReachedMap; 89 ///Instantiates a \ref ReachedMap. 90 91 ///This function instantiates a \ref ReachedMap. 92 ///\param g is the digraph, to which 93 ///we would like to define the \ref ReachedMap. 94 static ReachedMap *createReachedMap(const Digraph &g) 95 { 96 return new ReachedMap(g); 97 } 98 99 ///The type of the map that stores the distances of the nodes. 100 101 ///The type of the map that stores the distances of the nodes. 87 102 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 88 ///\todo named parameter to set this type, function to read and write.89 typedef typename Digraph::template NodeMap<bool> ReachedMap;90 ///Instantiates a ReachedMap.91 92 ///This function instantiates a \ref ReachedMap.93 ///\param G is the digraph, to which94 ///we would like to define the \ref ReachedMap.95 static ReachedMap *createReachedMap(const GR &G)96 {97 return new ReachedMap(G);98 }99 ///The type of the map that stores the dists of the nodes.100 101 ///The type of the map that stores the dists of the nodes.102 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.103 ///104 103 typedef typename Digraph::template NodeMap<int> DistMap; 105 ///Instantiates a DistMap.104 ///Instantiates a \ref DistMap. 106 105 107 106 ///This function instantiates a \ref DistMap. 108 ///\param G is the digraph, to which we would like to define109 /// the \ref DistMap110 static DistMap *createDistMap(const GR &G)111 { 112 return new DistMap( G);107 ///\param g is the digraph, to which we would like to define the 108 ///\ref DistMap. 109 static DistMap *createDistMap(const Digraph &g) 110 { 111 return new DistMap(g); 113 112 } 114 113 }; … … 119 118 ///This class provides an efficient implementation of the %DFS algorithm. 120 119 /// 121 ///\tparam GR The digraph type the algorithm runs on. The default value is 122 ///\ref ListDigraph. The value of GR is not used directly by Dfs, it 123 ///is only passed to \ref DfsDefaultTraits. 120 ///There is also a \ref dfs() "function type interface" for the DFS 121 ///algorithm, which is convenient in the simplier cases and it can be 122 ///used easier. 123 /// 124 ///\tparam GR The type of the digraph the algorithm runs on. 125 ///The default value is \ref ListDigraph. The value of GR is not used 126 ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits. 124 127 ///\tparam TR Traits class to set various data types used by the algorithm. 125 128 ///The default traits class is … … 136 139 class Dfs { 137 140 public: 138 /** 139 * \brief \ref Exception for uninitialized parameters. 140 * 141 * This error represents problems in the initialization 142 * of the parameters of the algorithms. 143 */ 141 ///\ref Exception for uninitialized parameters. 142 143 ///This error represents problems in the initialization of the 144 ///parameters of the algorithm. 144 145 class UninitializedParameter : public lemon::UninitializedParameter { 145 146 public: … … 149 150 }; 150 151 152 ///The type of the digraph the algorithm runs on. 153 typedef typename TR::Digraph Digraph; 154 155 ///\brief The type of the map that stores the predecessor arcs of the 156 ///DFS paths. 157 typedef typename TR::PredMap PredMap; 158 ///The type of the map that stores the distances of the nodes. 159 typedef typename TR::DistMap DistMap; 160 ///The type of the map that indicates which nodes are reached. 161 typedef typename TR::ReachedMap ReachedMap; 162 ///The type of the map that indicates which nodes are processed. 163 typedef typename TR::ProcessedMap ProcessedMap; 164 ///The type of the paths. 165 typedef PredMapPath<Digraph, PredMap> Path; 166 167 ///The traits class. 151 168 typedef TR Traits; 152 ///The type of the underlying digraph. 153 typedef typename TR::Digraph Digraph;154 ///\e 169 170 private: 171 155 172 typedef typename Digraph::Node Node; 156 ///\e157 173 typedef typename Digraph::NodeIt NodeIt; 158 ///\e159 174 typedef typename Digraph::Arc Arc; 160 ///\e161 175 typedef typename Digraph::OutArcIt OutArcIt; 162 176 163 ///\brief The type of the map that stores the last 164 ///arcs of the %DFS paths. 165 typedef typename TR::PredMap PredMap; 166 ///The type of the map indicating which nodes are reached. 167 typedef typename TR::ReachedMap ReachedMap; 168 ///The type of the map indicating which nodes are processed. 169 typedef typename TR::ProcessedMap ProcessedMap; 170 ///The type of the map that stores the dists of the nodes. 171 typedef typename TR::DistMap DistMap; 172 private: 173 /// Pointer to the underlying digraph. 177 //Pointer to the underlying digraph. 174 178 const Digraph *G; 175 // /Pointer to the map of predecessorsarcs.179 //Pointer to the map of predecessor arcs. 176 180 PredMap *_pred; 177 // /Indicates if \ref _pred is locally allocated (\ctrue) or not.181 //Indicates if _pred is locally allocated (true) or not. 178 182 bool local_pred; 179 // /Pointer to the map of distances.183 //Pointer to the map of distances. 180 184 DistMap *_dist; 181 // /Indicates if \ref _dist is locally allocated (\ctrue) or not.185 //Indicates if _dist is locally allocated (true) or not. 182 186 bool local_dist; 183 // /Pointer to the map of reached status of the nodes.187 //Pointer to the map of reached status of the nodes. 184 188 ReachedMap *_reached; 185 // /Indicates if \ref _reached is locally allocated (\ctrue) or not.189 //Indicates if _reached is locally allocated (true) or not. 186 190 bool local_reached; 187 // /Pointer to the map of processed status of the nodes.191 //Pointer to the map of processed status of the nodes. 188 192 ProcessedMap *_processed; 189 // /Indicates if \ref _processed is locally allocated (\ctrue) or not.193 //Indicates if _processed is locally allocated (true) or not. 190 194 bool local_processed; 191 195 … … 194 198 195 199 ///Creates the maps if necessary. 196 197 200 ///\todo Better memory allocation (instead of new). 198 201 void create_maps() … … 231 234 struct DefPredMapTraits : public Traits { 232 235 typedef T PredMap; 233 static PredMap *createPredMap(const Digraph & G)236 static PredMap *createPredMap(const Digraph &) 234 237 { 235 238 throw UninitializedParameter(); … … 237 240 }; 238 241 ///\brief \ref named-templ-param "Named parameter" for setting 239 /// PredMap type240 /// 241 ///\ref named-templ-param "Named parameter" for setting PredMap type242 /// 242 ///\ref PredMap type. 243 /// 244 ///\ref named-templ-param "Named parameter" for setting 245 ///\ref PredMap type. 243 246 template <class T> 244 247 struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > { 245 248 typedef Dfs<Digraph, DefPredMapTraits<T> > Create; 246 249 }; 247 248 250 249 251 template <class T> … … 256 258 }; 257 259 ///\brief \ref named-templ-param "Named parameter" for setting 258 /// DistMap type259 /// 260 ///\ref named-templ-param "Named parameter" for setting DistMap261 /// type260 ///\ref DistMap type. 261 /// 262 ///\ref named-templ-param "Named parameter" for setting 263 ///\ref DistMap type. 262 264 template <class T> 263 struct DefDistMap {265 struct DefDistMap : public Dfs< Digraph, DefDistMapTraits<T> > { 264 266 typedef Dfs<Digraph, DefDistMapTraits<T> > Create; 265 267 }; … … 274 276 }; 275 277 ///\brief \ref named-templ-param "Named parameter" for setting 276 /// ReachedMap type277 /// 278 ///\ref named-templ-param "Named parameter" for setting ReachedMap type279 /// 278 ///\ref ReachedMap type. 279 /// 280 ///\ref named-templ-param "Named parameter" for setting 281 ///\ref ReachedMap type. 280 282 template <class T> 281 283 struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > { … … 292 294 }; 293 295 ///\brief \ref named-templ-param "Named parameter" for setting 294 /// ProcessedMap type295 /// 296 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type297 /// 296 ///\ref ProcessedMap type. 297 /// 298 ///\ref named-templ-param "Named parameter" for setting 299 ///\ref ProcessedMap type. 298 300 template <class T> 299 301 struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > { … … 303 305 struct DefDigraphProcessedMapTraits : public Traits { 304 306 typedef typename Digraph::template NodeMap<bool> ProcessedMap; 305 static ProcessedMap *createProcessedMap(const Digraph & G)307 static ProcessedMap *createProcessedMap(const Digraph &g) 306 308 { 307 return new ProcessedMap( G);308 } 309 }; 310 ///\brief \ref named-templ-param "Named parameter" 311 /// for setting the ProcessedMap type to be Digraph::NodeMap<bool>.312 /// 313 ///\ref named-templ-param "Named parameter" 314 /// for setting the ProcessedMap type to be Digraph::NodeMap<bool>.315 ///If you don't set it explicit ely, it will be automatically allocated.309 return new ProcessedMap(g); 310 } 311 }; 312 ///\brief \ref named-templ-param "Named parameter" for setting 313 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 314 /// 315 ///\ref named-templ-param "Named parameter" for setting 316 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 317 ///If you don't set it explicitly, it will be automatically allocated. 316 318 template <class T> 317 classDefProcessedMapToBeDefaultMap :319 struct DefProcessedMapToBeDefaultMap : 318 320 public Dfs< Digraph, DefDigraphProcessedMapTraits> { 319 321 typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create; … … 326 328 ///Constructor. 327 329 328 /// \param _G the digraph the algorithm will run on.329 /// 330 Dfs(const Digraph & _G) :331 G(& _G),330 ///Constructor. 331 ///\param g The digraph the algorithm runs on. 332 Dfs(const Digraph &g) : 333 G(&g), 332 334 _pred(NULL), local_pred(false), 333 335 _dist(NULL), local_dist(false), … … 345 347 } 346 348 347 ///Sets the map storingthe predecessor arcs.348 349 ///Sets the map storingthe predecessor arcs.349 ///Sets the map that stores the predecessor arcs. 350 351 ///Sets the map that stores the predecessor arcs. 350 352 ///If you don't use this function before calling \ref run(), 351 ///it will allocate one. The dest uctor deallocates this353 ///it will allocate one. The destructor deallocates this 352 354 ///automatically allocated map, of course. 353 355 ///\return <tt> (*this) </tt> … … 362 364 } 363 365 364 ///Sets the map storing the distances calculated by the algorithm.365 366 ///Sets the map storing the distances calculated by the algorithm.366 ///Sets the map that indicates which nodes are reached. 367 368 ///Sets the map that indicates which nodes are reached. 367 369 ///If you don't use this function before calling \ref run(), 368 ///it will allocate one. The destuctor deallocates this 370 ///it will allocate one. The destructor deallocates this 371 ///automatically allocated map, of course. 372 ///\return <tt> (*this) </tt> 373 Dfs &reachedMap(ReachedMap &m) 374 { 375 if(local_reached) { 376 delete _reached; 377 local_reached=false; 378 } 379 _reached = &m; 380 return *this; 381 } 382 383 ///Sets the map that indicates which nodes are processed. 384 385 ///Sets the map that indicates which nodes are processed. 386 ///If you don't use this function before calling \ref run(), 387 ///it will allocate one. The destructor deallocates this 388 ///automatically allocated map, of course. 389 ///\return <tt> (*this) </tt> 390 Dfs &processedMap(ProcessedMap &m) 391 { 392 if(local_processed) { 393 delete _processed; 394 local_processed=false; 395 } 396 _processed = &m; 397 return *this; 398 } 399 400 ///Sets the map that stores the distances of the nodes. 401 402 ///Sets the map that stores the distances of the nodes calculated by 403 ///the algorithm. 404 ///If you don't use this function before calling \ref run(), 405 ///it will allocate one. The destructor deallocates this 369 406 ///automatically allocated map, of course. 370 407 ///\return <tt> (*this) </tt> … … 379 416 } 380 417 381 ///Sets the map indicating if a node is reached.382 383 ///Sets the map indicating if a node is reached.384 ///If you don't use this function before calling \ref run(),385 ///it will allocate one. The destuctor deallocates this386 ///automatically allocated map, of course.387 ///\return <tt> (*this) </tt>388 Dfs &reachedMap(ReachedMap &m)389 {390 if(local_reached) {391 delete _reached;392 local_reached=false;393 }394 _reached = &m;395 return *this;396 }397 398 ///Sets the map indicating if a node is processed.399 400 ///Sets the map indicating if a node is processed.401 ///If you don't use this function before calling \ref run(),402 ///it will allocate one. The destuctor deallocates this403 ///automatically allocated map, of course.404 ///\return <tt> (*this) </tt>405 Dfs &processedMap(ProcessedMap &m)406 {407 if(local_processed) {408 delete _processed;409 local_processed=false;410 }411 _processed = &m;412 return *this;413 }414 415 418 public: 419 416 420 ///\name Execution control 417 421 ///The simplest way to execute the algorithm is to use 418 ///one of the member functions called \ c run(...).422 ///one of the member functions called \ref lemon::Dfs::run() "run()". 419 423 ///\n 420 ///If you need more control on the execution, 421 /// first you must call \ref init(), then you can add a source node422 ///with \ref addSource().423 ///Finally \ref start() will perform the actual path424 /// computation.424 ///If you need more control on the execution, first you must call 425 ///\ref lemon::Dfs::init() "init()", then you can add a source node 426 ///with \ref lemon::Dfs::addSource() "addSource()". 427 ///Finally \ref lemon::Dfs::start() "start()" will perform the 428 ///actual path computation. 425 429 426 430 ///@{ … … 437 441 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { 438 442 _pred->set(u,INVALID); 439 // _predNode->set(u,INVALID);440 443 _reached->set(u,false); 441 444 _processed->set(u,false); … … 447 450 ///Adds a new source node to the set of nodes to be processed. 448 451 /// 449 ///\warning dists are wrong (or at least strange) 450 ///in case of multiple sources. 452 ///\pre The stack must be empty. (Otherwise the algorithm gives 453 ///false results.) 454 /// 455 ///\warning Distances will be wrong (or at least strange) in case of 456 ///multiple sources. 451 457 void addSource(Node s) 452 458 { 459 LEMON_DEBUG(emptyQueue(), "The stack is not empty."); 453 460 if(!(*_reached)[s]) 454 461 { … … 473 480 ///\return The processed arc. 474 481 /// 475 ///\pre The stack must not be empty !482 ///\pre The stack must not be empty. 476 483 Arc processNextArc() 477 484 { … … 499 506 return e; 500 507 } 508 501 509 ///Next arc to be processed. 502 510 503 511 ///Next arc to be processed. 504 512 /// 505 ///\return The next arc to be processed or INVALID if the stack is506 /// empty.507 OutArcIt nextArc() 513 ///\return The next arc to be processed or \c INVALID if the stack 514 ///is empty. 515 OutArcIt nextArc() const 508 516 { 509 517 return _stack_head>=0?_stack[_stack_head]:INVALID; … … 511 519 512 520 ///\brief Returns \c false if there are nodes 513 ///to be processed in the queue521 ///to be processed. 514 522 /// 515 523 ///Returns \c false if there are nodes 516 ///to be processed in the queue 517 bool emptyQueue() { return _stack_head<0; } 524 ///to be processed in the queue (stack). 525 bool emptyQueue() const { return _stack_head<0; } 526 518 527 ///Returns the number of the nodes to be processed. 519 528 520 ///Returns the number of the nodes to be processed in the queue .521 int queueSize() { return _stack_head+1; }529 ///Returns the number of the nodes to be processed in the queue (stack). 530 int queueSize() const { return _stack_head+1; } 522 531 523 532 ///Executes the algorithm. … … 525 534 ///Executes the algorithm. 526 535 /// 527 ///\pre init() must be called and at least one node should be added 528 ///with addSource() before using this function. 529 /// 530 ///This method runs the %DFS algorithm from the root node(s) 531 ///in order to 532 ///compute the 533 ///%DFS path to each node. The algorithm computes 534 ///- The %DFS tree. 535 ///- The distance of each node from the root(s) in the %DFS tree. 536 /// 536 ///This method runs the %DFS algorithm from the root node 537 ///in order to compute the DFS path to each node. 538 /// 539 /// The algorithm computes 540 ///- the %DFS tree, 541 ///- the distance of each node from the root in the %DFS tree. 542 /// 543 ///\pre init() must be called and a root node should be 544 ///added with addSource() before using this function. 545 /// 546 ///\note <tt>d.start()</tt> is just a shortcut of the following code. 547 ///\code 548 /// while ( !d.emptyQueue() ) { 549 /// d.processNextArc(); 550 /// } 551 ///\endcode 537 552 void start() 538 553 { … … 540 555 } 541 556 542 ///Executes the algorithm until \c dest is reached. 543 544 ///Executes the algorithm until \c dest is reached. 545 /// 546 ///\pre init() must be called and at least one node should be added 547 ///with addSource() before using this function. 548 /// 549 ///This method runs the %DFS algorithm from the root node(s) 550 ///in order to 551 ///compute the 552 ///%DFS path to \c dest. The algorithm computes 553 ///- The %DFS path to \c dest. 554 ///- The distance of \c dest from the root(s) in the %DFS tree. 555 /// 557 ///Executes the algorithm until the given target node is reached. 558 559 ///Executes the algorithm until the given target node is reached. 560 /// 561 ///This method runs the %DFS algorithm from the root node 562 ///in order to compute the DFS path to \c dest. 563 /// 564 ///The algorithm computes 565 ///- the %DFS path to \c dest, 566 ///- the distance of \c dest from the root in the %DFS tree. 567 /// 568 ///\pre init() must be called and a root node should be 569 ///added with addSource() before using this function. 556 570 void start(Node dest) 557 571 { … … 564 578 ///Executes the algorithm until a condition is met. 565 579 /// 566 /// \pre init() must be called and at least one node should be added567 /// with addSource() before using this function.568 /// 569 ///\param em must be abool (or convertible) arc map. The algorithm570 ///will stop when it reaches an arc \c e with <tt>em[e]</tt> true.571 /// 572 ///\return The reached arc \c e with <tt>em[e]</tt> true or580 ///This method runs the %DFS algorithm from the root node 581 ///until an arc \c a with <tt>am[a]</tt> true is found. 582 /// 583 ///\param am A \c bool (or convertible) arc map. The algorithm 584 ///will stop when it reaches an arc \c a with <tt>am[a]</tt> true. 585 /// 586 ///\return The reached arc \c a with <tt>am[a]</tt> true or 573 587 ///\c INVALID if no such arc was found. 574 588 /// 575 ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map, 589 ///\pre init() must be called and a root node should be 590 ///added with addSource() before using this function. 591 /// 592 ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map, 576 593 ///not a node map. 577 template<class EM>578 Arc start(const EM &em)579 { 580 while ( !emptyQueue() && ! em[_stack[_stack_head]] )594 template<class ArcBoolMap> 595 Arc start(const ArcBoolMap &am) 596 { 597 while ( !emptyQueue() && !am[_stack[_stack_head]] ) 581 598 processNextArc(); 582 599 return emptyQueue() ? INVALID : _stack[_stack_head]; 583 600 } 584 601 585 ///Runs %DFS algorithm to visit all nodes in the digraph. 586 587 ///This method runs the %DFS algorithm in order to 588 ///compute the 589 ///%DFS path to each node. The algorithm computes 590 ///- The %DFS tree. 591 ///- The distance of each node from the root in the %DFS tree. 592 /// 593 ///\note d.run() is just a shortcut of the following code. 602 ///Runs the algorithm from the given node. 603 604 ///This method runs the %DFS algorithm from node \c s 605 ///in order to compute the DFS path to each node. 606 /// 607 ///The algorithm computes 608 ///- the %DFS tree, 609 ///- the distance of each node from the root in the %DFS tree. 610 /// 611 ///\note <tt>d.run(s)</tt> is just a shortcut of the following code. 594 612 ///\code 595 613 /// d.init(); 596 /// for (NodeIt it(digraph); it != INVALID; ++it) { 597 /// if (!d.reached(it)) { 598 /// d.addSource(it); 614 /// d.addSource(s); 615 /// d.start(); 616 ///\endcode 617 void run(Node s) { 618 init(); 619 addSource(s); 620 start(); 621 } 622 623 ///Finds the %DFS path between \c s and \c t. 624 625 ///This method runs the %DFS algorithm from node \c s 626 ///in order to compute the DFS path to \c t. 627 /// 628 ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path, 629 ///if \c t is reachable form \c s, \c 0 otherwise. 630 /// 631 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is 632 ///just a shortcut of the following code. 633 ///\code 634 /// d.init(); 635 /// d.addSource(s); 636 /// d.start(t); 637 ///\endcode 638 int run(Node s,Node t) { 639 init(); 640 addSource(s); 641 start(t); 642 return reached(t)?_stack_head+1:0; 643 } 644 645 ///Runs the algorithm to visit all nodes in the digraph. 646 647 ///This method runs the %DFS algorithm in order to compute the 648 ///%DFS path to each node. 649 /// 650 ///The algorithm computes 651 ///- the %DFS tree, 652 ///- the distance of each node from the root in the %DFS tree. 653 /// 654 ///\note <tt>d.run()</tt> is just a shortcut of the following code. 655 ///\code 656 /// d.init(); 657 /// for (NodeIt n(digraph); n != INVALID; ++n) { 658 /// if (!d.reached(n)) { 659 /// d.addSource(n); 599 660 /// d.start(); 600 661 /// } … … 611 672 } 612 673 613 ///Runs %DFS algorithm from node \c s.614 615 ///This method runs the %DFS algorithm from a root node \c s616 ///in order to617 ///compute the618 ///%DFS path to each node. The algorithm computes619 ///- The %DFS tree.620 ///- The distance of each node from the root in the %DFS tree.621 ///622 ///\note d.run(s) is just a shortcut of the following code.623 ///\code624 /// d.init();625 /// d.addSource(s);626 /// d.start();627 ///\endcode628 void run(Node s) {629 init();630 addSource(s);631 start();632 }633 634 ///Finds the %DFS path between \c s and \c t.635 636 ///Finds the %DFS path between \c s and \c t.637 ///638 ///\return The length of the %DFS s---t path if there exists one,639 ///0 otherwise.640 ///\note Apart from the return value, d.run(s,t) is641 ///just a shortcut of the following code.642 ///\code643 /// d.init();644 /// d.addSource(s);645 /// d.start(t);646 ///\endcode647 int run(Node s,Node t) {648 init();649 addSource(s);650 start(t);651 return reached(t)?_stack_head+1:0;652 }653 654 674 ///@} 655 675 … … 657 677 ///The result of the %DFS algorithm can be obtained using these 658 678 ///functions.\n 659 /// Before the use of these functions,660 /// either run() or start() must be called.679 ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start() 680 ///"start()" must be called before using them. 661 681 662 682 ///@{ 663 683 664 typedef PredMapPath<Digraph, PredMap> Path; 665 666 ///Gives back the shortest path. 667 668 ///Gives back the shortest path. 669 ///\pre The \c t should be reachable from the source. 670 Path path(Node t) 671 { 672 return Path(*G, *_pred, t); 673 } 674 675 ///The distance of a node from the root(s). 676 677 ///Returns the distance of a node from the root(s). 678 ///\pre \ref run() must be called before using this function. 679 ///\warning If node \c v is unreachable from the root(s) then the return 680 ///value of this funcion is undefined. 684 ///The DFS path to a node. 685 686 ///Returns the DFS path to a node. 687 /// 688 ///\warning \c t should be reachable from the root. 689 /// 690 ///\pre Either \ref run() or \ref start() must be called before 691 ///using this function. 692 Path path(Node t) const { return Path(*G, *_pred, t); } 693 694 ///The distance of a node from the root. 695 696 ///Returns the distance of a node from the root. 697 /// 698 ///\warning If node \c v is not reachable from the root, then 699 ///the return value of this function is undefined. 700 /// 701 ///\pre Either \ref run() or \ref start() must be called before 702 ///using this function. 681 703 int dist(Node v) const { return (*_dist)[v]; } 682 704 683 ///Returns the 'previous arc' of the %DFS tree .684 685 /// For a node \c v it returns the 'previous arc'686 /// of the %DFS path,687 /// i.e. it returns the last arc of a %DFS path from the root(s) to \c688 /// v. It is \ref INVALID689 /// if \c v is unreachable from the root(s) or \c v is a root. The690 /// %DFS tree used here is equal to the %DFS tree used in705 ///Returns the 'previous arc' of the %DFS tree for a node. 706 707 ///This function returns the 'previous arc' of the %DFS tree for the 708 ///node \c v, i.e. it returns the last arc of a %DFS path from the 709 ///root to \c v. It is \c INVALID 710 ///if \c v is not reachable from the root(s) or if \c v is a root. 711 /// 712 ///The %DFS tree used here is equal to the %DFS tree used in 691 713 ///\ref predNode(). 714 /// 692 715 ///\pre Either \ref run() or \ref start() must be called before using 693 716 ///this function. … … 696 719 ///Returns the 'previous node' of the %DFS tree. 697 720 698 /// For a node \c v it returns the 'previous node'699 /// of the %DFS tree,700 /// i.e. it returns the last but one node from a %DFS path from the701 /// root(s) to \c v.702 /// It is INVALID if \c v is unreachable from the root(s) or703 /// if \c v itself a root.704 /// The %DFS tree used here is equal to the %DFS705 /// tree used in \ref predArc().721 ///This function returns the 'previous node' of the %DFS 722 ///tree for the node \c v, i.e. it returns the last but one node 723 ///from a %DFS path from the root to \c v. It is \c INVALID 724 ///if \c v is not reachable from the root(s) or if \c v is a root. 725 /// 726 ///The %DFS tree used here is equal to the %DFS tree used in 727 ///\ref predArc(). 728 /// 706 729 ///\pre Either \ref run() or \ref start() must be called before 707 730 ///using this function. … … 709 732 G->source((*_pred)[v]); } 710 733 711 ///Returns a reference to the NodeMap of distances. 712 713 ///Returns a reference to the NodeMap of distances. 714 ///\pre Either \ref run() or \ref init() must 715 ///be called before using this function. 734 ///\brief Returns a const reference to the node map that stores the 735 ///distances of the nodes. 736 /// 737 ///Returns a const reference to the node map that stores the 738 ///distances of the nodes calculated by the algorithm. 739 /// 740 ///\pre Either \ref run() or \ref init() 741 ///must be called before using this function. 716 742 const DistMap &distMap() const { return *_dist;} 717 743 718 ///Returns a reference to the %DFS arc-tree map. 719 720 ///Returns a reference to the NodeMap of the arcs of the 721 ///%DFS tree. 744 ///\brief Returns a const reference to the node map that stores the 745 ///predecessor arcs. 746 /// 747 ///Returns a const reference to the node map that stores the predecessor 748 ///arcs, which form the DFS tree. 749 /// 722 750 ///\pre Either \ref run() or \ref init() 723 751 ///must be called before using this function. 724 752 const PredMap &predMap() const { return *_pred;} 725 753 726 ///Checks if a node is reachable from the root .754 ///Checks if a node is reachable from the root(s). 727 755 728 756 ///Returns \c true if \c v is reachable from the root(s). 729 ///\warning The source nodes are inditated as unreachable.730 757 ///\pre Either \ref run() or \ref start() 731 758 ///must be called before using this function. 732 /// 733 bool reached(Node v) { return (*_reached)[v]; } 759 bool reached(Node v) const { return (*_reached)[v]; } 734 760 735 761 ///@} 736 762 }; 737 763 738 ///Default traits class of Dfsfunction.739 740 ///Default traits class of Dfsfunction.764 ///Default traits class of dfs() function. 765 766 ///Default traits class of dfs() function. 741 767 ///\tparam GR Digraph type. 742 768 template<class GR> 743 769 struct DfsWizardDefaultTraits 744 770 { 745 ///The digraph typethe algorithm runs on.771 ///The type of the digraph the algorithm runs on. 746 772 typedef GR Digraph; 747 ///\brief The type of the map that stores the last 773 774 ///\brief The type of the map that stores the predecessor 748 775 ///arcs of the %DFS paths. 749 776 /// 750 ///The type of the map that stores the last777 ///The type of the map that stores the predecessor 751 778 ///arcs of the %DFS paths. 752 779 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 753 780 /// 754 typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;755 ///Instantiates a PredMap.781 typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap; 782 ///Instantiates a \ref PredMap. 756 783 757 784 ///This function instantiates a \ref PredMap. 758 ///\param g is the digraph, to which we would like to define the PredMap. 785 ///\param g is the digraph, to which we would like to define the 786 ///\ref PredMap. 759 787 ///\todo The digraph alone may be insufficient to initialize 760 788 #ifdef DOXYGEN 761 static PredMap *createPredMap(const GR&g)789 static PredMap *createPredMap(const Digraph &g) 762 790 #else 763 static PredMap *createPredMap(const GR&)791 static PredMap *createPredMap(const Digraph &) 764 792 #endif 765 793 { … … 771 799 ///The type of the map that indicates which nodes are processed. 772 800 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 773 ///\todo named parameter to set this type, function to read and write.774 801 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 775 ///Instantiates a ProcessedMap.802 ///Instantiates a \ref ProcessedMap. 776 803 777 804 ///This function instantiates a \ref ProcessedMap. 778 805 ///\param g is the digraph, to which 779 ///we would like to define the \ref ProcessedMap 806 ///we would like to define the \ref ProcessedMap. 780 807 #ifdef DOXYGEN 781 static ProcessedMap *createProcessedMap(const GR&g)808 static ProcessedMap *createProcessedMap(const Digraph &g) 782 809 #else 783 static ProcessedMap *createProcessedMap(const GR&)810 static ProcessedMap *createProcessedMap(const Digraph &) 784 811 #endif 785 812 { 786 813 return new ProcessedMap(); 787 814 } 815 788 816 ///The type of the map that indicates which nodes are reached. 789 817 790 818 ///The type of the map that indicates which nodes are reached. 819 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 820 typedef typename Digraph::template NodeMap<bool> ReachedMap; 821 ///Instantiates a \ref ReachedMap. 822 823 ///This function instantiates a \ref ReachedMap. 824 ///\param g is the digraph, to which 825 ///we would like to define the \ref ReachedMap. 826 static ReachedMap *createReachedMap(const Digraph &g) 827 { 828 return new ReachedMap(g); 829 } 830 831 ///The type of the map that stores the distances of the nodes. 832 833 ///The type of the map that stores the distances of the nodes. 791 834 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 792 ///\todo named parameter to set this type, function to read and write.793 typedef typename Digraph::template NodeMap<bool> ReachedMap;794 ///Instantiates a ReachedMap.795 796 ///This function instantiates a \ref ReachedMap.797 ///\param G is the digraph, to which798 ///we would like to define the \ref ReachedMap.799 static ReachedMap *createReachedMap(const GR &G)800 {801 return new ReachedMap(G);802 }803 ///The type of the map that stores the dists of the nodes.804 805 ///The type of the map that stores the dists of the nodes.806 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.807 835 /// 808 836 typedef NullMap<typename Digraph::Node,int> DistMap; 809 ///Instantiates a DistMap.837 ///Instantiates a \ref DistMap. 810 838 811 839 ///This function instantiates a \ref DistMap. … … 813 841 ///the \ref DistMap 814 842 #ifdef DOXYGEN 815 static DistMap *createDistMap(const GR&g)843 static DistMap *createDistMap(const Digraph &g) 816 844 #else 817 static DistMap *createDistMap(const GR&)845 static DistMap *createDistMap(const Digraph &) 818 846 #endif 819 847 { … … 822 850 }; 823 851 824 /// Default traits used by \ref DfsWizard852 /// Default traits class used by \ref DfsWizard 825 853 826 854 /// To make it easier to use Dfs algorithm 827 /// we have created a wizard class.855 /// we have created a wizard class. 828 856 /// This \ref DfsWizard class needs default traits, 829 /// as well as the \ref Dfs class.857 /// as well as the \ref Dfs class. 830 858 /// The \ref DfsWizardBase is a class to be the default traits of the 831 859 /// \ref DfsWizard class. … … 836 864 typedef DfsWizardDefaultTraits<GR> Base; 837 865 protected: 838 // / Type of the nodes in the digraph.866 //The type of the nodes in the digraph. 839 867 typedef typename Base::Digraph::Node Node; 840 868 841 // / Pointer to the underlying digraph.869 //Pointer to the digraph the algorithm runs on. 842 870 void *_g; 843 // /Pointer to the map of reached nodes.871 //Pointer to the map of reached nodes. 844 872 void *_reached; 845 // /Pointer to the map of processed nodes.873 //Pointer to the map of processed nodes. 846 874 void *_processed; 847 // /Pointer to the map of predecessors arcs.875 //Pointer to the map of predecessors arcs. 848 876 void *_pred; 849 // /Pointer to the map of distances.877 //Pointer to the map of distances. 850 878 void *_dist; 851 // /Pointer to the source node.879 //Pointer to the source node. 852 880 Node _source; 853 881 … … 858 886 /// all of the attributes to default values (0, INVALID). 859 887 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), 860 888 _dist(0), _source(INVALID) {} 861 889 862 890 /// Constructor. … … 865 893 /// listed in the parameters list. 866 894 /// Others are initiated to 0. 867 /// \param g is the initial value of \ref _g868 /// \param s is the initial value of \ref _source895 /// \param g The digraph the algorithm runs on. 896 /// \param s The source node. 869 897 DfsWizardBase(const GR &g, Node s=INVALID) : 870 898 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), … … 873 901 }; 874 902 875 /// A class to make the usage of the Dfs algorithm easier 876 877 /// This class is created to make it easier to use the Dfs algorithm. 878 /// It uses the functions and features of the plain \ref Dfs, 879 /// but it is much simpler to use it. 903 /// Auxiliary class for the function type interface of DFS algorithm. 904 905 /// This auxiliary class is created to implement the function type 906 /// interface of \ref Dfs algorithm. It uses the functions and features 907 /// of the plain \ref Dfs, but it is much simpler to use it. 908 /// It should only be used through the \ref dfs() function, which makes 909 /// it easier to use the algorithm. 880 910 /// 881 911 /// Simplicity means that the way to change the types defined … … 886 916 /// the original class by using the :: 887 917 /// operator. In the case of \ref DfsWizard only 888 /// a function have to be called and it will918 /// a function have to be called, and it will 889 919 /// return the needed class. 890 920 /// 891 /// It does not have own \ref run method. When its \ref run method is called892 /// i t initiates a plain \ref Dfs object, and calls the \ref Dfs::run893 /// method of it.921 /// It does not have own \ref run() method. When its \ref run() method 922 /// is called, it initiates a plain \ref Dfs object, and calls the 923 /// \ref Dfs::run() method of it. 894 924 template<class TR> 895 925 class DfsWizard : public TR … … 897 927 typedef TR Base; 898 928 899 ///The type of the underlying digraph.929 ///The type of the digraph the algorithm runs on. 900 930 typedef typename TR::Digraph Digraph; 901 //\e 931 902 932 typedef typename Digraph::Node Node; 903 //\e904 933 typedef typename Digraph::NodeIt NodeIt; 905 //\e906 934 typedef typename Digraph::Arc Arc; 907 //\e908 935 typedef typename Digraph::OutArcIt OutArcIt; 909 936 910 ///\brief The type of the map that stores 911 ///the reached nodes 937 ///\brief The type of the map that stores the predecessor 938 ///arcs of the shortest paths. 939 typedef typename TR::PredMap PredMap; 940 ///\brief The type of the map that stores the distances of the nodes. 941 typedef typename TR::DistMap DistMap; 942 ///\brief The type of the map that indicates which nodes are reached. 912 943 typedef typename TR::ReachedMap ReachedMap; 913 ///\brief The type of the map that stores 914 ///the processed nodes 944 ///\brief The type of the map that indicates which nodes are processed. 915 945 typedef typename TR::ProcessedMap ProcessedMap; 916 ///\brief The type of the map that stores the last917 ///arcs of the %DFS paths.918 typedef typename TR::PredMap PredMap;919 ///The type of the map that stores the distances of the nodes.920 typedef typename TR::DistMap DistMap;921 946 922 947 public: 948 923 949 /// Constructor. 924 950 DfsWizard() : TR() {} … … 936 962 ~DfsWizard() {} 937 963 938 ///Runs D fs algorithm from a givennode.939 940 ///Runs D fs algorithm from a givennode.941 ///The node can be given by the \ref sourcefunction.964 ///Runs DFS algorithm from a source node. 965 966 ///Runs DFS algorithm from a source node. 967 ///The node can be given with the \ref source() function. 942 968 void run() 943 969 { … … 955 981 } 956 982 957 ///Runs D fsalgorithm from the given node.958 959 ///Runs D fsalgorithm from the given node.983 ///Runs DFS algorithm from the given node. 984 985 ///Runs DFS algorithm from the given node. 960 986 ///\param s is the given source. 961 987 void run(Node s) … … 963 989 Base::_source=s; 964 990 run(); 991 } 992 993 /// Sets the source node, from which the Dfs algorithm runs. 994 995 /// Sets the source node, from which the Dfs algorithm runs. 996 /// \param s is the source node. 997 DfsWizard<TR> &source(Node s) 998 { 999 Base::_source=s; 1000 return *this; 965 1001 } 966 1002 … … 971 1007 DefPredMapBase(const TR &b) : TR(b) {} 972 1008 }; 973 974 1009 ///\brief \ref named-templ-param "Named parameter" 975 ///function for setting PredMap type 976 /// 977 /// \ref named-templ-param "Named parameter" 978 ///function for setting PredMap type 979 /// 1010 ///for setting \ref PredMap object. 1011 /// 1012 ///\ref named-templ-param "Named parameter" 1013 ///for setting \ref PredMap object. 980 1014 template<class T> 981 1015 DfsWizard<DefPredMapBase<T> > predMap(const T &t) … … 984 1018 return DfsWizard<DefPredMapBase<T> >(*this); 985 1019 } 986 987 1020 988 1021 template<class T> … … 992 1025 DefReachedMapBase(const TR &b) : TR(b) {} 993 1026 }; 994 995 1027 ///\brief \ref named-templ-param "Named parameter" 996 ///f unction for setting ReachedMap1028 ///for setting \ref ReachedMap object. 997 1029 /// 998 1030 /// \ref named-templ-param "Named parameter" 999 ///function for setting ReachedMap 1000 /// 1031 ///for setting \ref ReachedMap object. 1001 1032 template<class T> 1002 1033 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) … … 1005 1036 return DfsWizard<DefReachedMapBase<T> >(*this); 1006 1037 } 1007 1008 1038 1009 1039 template<class T> … … 1013 1043 DefProcessedMapBase(const TR &b) : TR(b) {} 1014 1044 }; 1015 1016 1045 ///\brief \ref named-templ-param "Named parameter" 1017 ///f unction for setting ProcessedMap1046 ///for setting \ref ProcessedMap object. 1018 1047 /// 1019 1048 /// \ref named-templ-param "Named parameter" 1020 ///function for setting ProcessedMap 1021 /// 1049 ///for setting \ref ProcessedMap object. 1022 1050 template<class T> 1023 1051 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) … … 1033 1061 DefDistMapBase(const TR &b) : TR(b) {} 1034 1062 }; 1035 1036 1063 ///\brief \ref named-templ-param "Named parameter" 1037 ///function for setting DistMap type 1038 /// 1039 /// \ref named-templ-param "Named parameter" 1040 ///function for setting DistMap type 1041 /// 1064 ///for setting \ref DistMap object. 1065 /// 1066 ///\ref named-templ-param "Named parameter" 1067 ///for setting \ref DistMap object. 1042 1068 template<class T> 1043 1069 DfsWizard<DefDistMapBase<T> > distMap(const T &t) … … 1045 1071 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1046 1072 return DfsWizard<DefDistMapBase<T> >(*this); 1047 }1048 1049 /// Sets the source node, from which the Dfs algorithm runs.1050 1051 /// Sets the source node, from which the Dfs algorithm runs.1052 /// \param s is the source node.1053 DfsWizard<TR> &source(Node s)1054 {1055 Base::_source=s;1056 return *this;1057 1073 } 1058 1074 … … 1084 1100 1085 1101 #ifdef DOXYGEN 1086 /// \brief Visitor class for dfs.1102 /// \brief Visitor class for DFS. 1087 1103 /// 1088 /// It gives a simple interface for a functional interface for dfs1089 /// traversal. The traversal on a linear data structure.1104 /// This class defines the interface of the DfsVisit events, and 1105 /// it could be the base of a real visitor class. 1090 1106 template <typename _Digraph> 1091 1107 struct DfsVisitor { … … 1093 1109 typedef typename Digraph::Arc Arc; 1094 1110 typedef typename Digraph::Node Node; 1095 /// \brief Called when the arc reach a node. 1096 /// 1097 /// It is called when the dfs find an arc which target is not 1098 /// reached yet. 1111 /// \brief Called for the source node of the DFS. 1112 /// 1113 /// This function is called for the source node of the DFS. 1114 void start(const Node& node) {} 1115 /// \brief Called when the source node is leaved. 1116 /// 1117 /// This function is called when the source node is leaved. 1118 void stop(const Node& node) {} 1119 /// \brief Called when a node is reached first time. 1120 /// 1121 /// This function is called when a node is reached first time. 1122 void reach(const Node& node) {} 1123 /// \brief Called when an arc reaches a new node. 1124 /// 1125 /// This function is called when the DFS finds an arc whose target node 1126 /// is not reached yet. 1099 1127 void discover(const Arc& arc) {} 1100 /// \brief Called when the node reached first time. 1101 /// 1102 /// It is Called when the node reached first time. 1103 void reach(const Node& node) {} 1104 /// \brief Called when we step back on an arc. 1105 /// 1106 /// It is called when the dfs should step back on the arc. 1107 void backtrack(const Arc& arc) {} 1108 /// \brief Called when we step back from the node. 1109 /// 1110 /// It is called when we step back from the node. 1111 void leave(const Node& node) {} 1112 /// \brief Called when the arc examined but target of the arc 1128 /// \brief Called when an arc is examined but its target node is 1113 1129 /// already discovered. 1114 1130 /// 1115 /// It called when the arc examined but the target of the arc1131 /// This function is called when an arc is examined but its target node is 1116 1132 /// already discovered. 1117 1133 void examine(const Arc& arc) {} 1118 /// \brief Called for the source node of the dfs. 1119 /// 1120 /// It is called for the source node of the dfs. 1121 void start(const Node& node) {} 1122 /// \brief Called when we leave the source node of the dfs. 1123 /// 1124 /// It is called when we leave the source node of the dfs. 1125 void stop(const Node& node) {} 1126 1134 /// \brief Called when the DFS steps back from a node. 1135 /// 1136 /// This function is called when the DFS steps back from a node. 1137 void leave(const Node& node) {} 1138 /// \brief Called when the DFS steps back on an arc. 1139 /// 1140 /// This function is called when the DFS steps back on an arc. 1141 void backtrack(const Arc& arc) {} 1127 1142 }; 1128 1143 #else … … 1132 1147 typedef typename Digraph::Arc Arc; 1133 1148 typedef typename Digraph::Node Node; 1134 void discover(const Arc&) {}1135 void reach(const Node&) {}1136 void backtrack(const Arc&) {}1137 void leave(const Node&) {}1138 void examine(const Arc&) {}1139 1149 void start(const Node&) {} 1140 1150 void stop(const Node&) {} 1151 void reach(const Node&) {} 1152 void discover(const Arc&) {} 1153 void examine(const Arc&) {} 1154 void leave(const Node&) {} 1155 void backtrack(const Arc&) {} 1141 1156 1142 1157 template <typename _Visitor> … … 1145 1160 Arc arc; 1146 1161 Node node; 1147 visitor.discover(arc);1148 visitor.reach(node);1149 visitor.backtrack(arc);1150 visitor.leave(node);1151 visitor.examine(arc);1152 1162 visitor.start(node); 1153 1163 visitor.stop(arc); 1164 visitor.reach(node); 1165 visitor.discover(arc); 1166 visitor.examine(arc); 1167 visitor.leave(node); 1168 visitor.backtrack(arc); 1154 1169 } 1155 1170 _Visitor& visitor; … … 1161 1176 /// 1162 1177 /// Default traits class of DfsVisit class. 1163 /// \tparam _Digraph Digraph type.1178 /// \tparam _Digraph The type of the digraph the algorithm runs on. 1164 1179 template<class _Digraph> 1165 1180 struct DfsVisitDefaultTraits { 1166 1181 1167 /// \brief The digraph typethe algorithm runs on.1182 /// \brief The type of the digraph the algorithm runs on. 1168 1183 typedef _Digraph Digraph; 1169 1184 … … 1171 1186 /// 1172 1187 /// The type of the map that indicates which nodes are reached. 1173 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. 1174 /// \todo named parameter to set this type, function to read and write. 1188 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1175 1189 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1176 1190 1177 /// \brief Instantiates a ReachedMap.1191 /// \brief Instantiates a \ref ReachedMap. 1178 1192 /// 1179 1193 /// This function instantiates a \ref ReachedMap. … … 1186 1200 }; 1187 1201 1188 /// %DFS Visit algorithm class.1189 1190 1202 /// \ingroup search 1203 /// 1204 /// \brief %DFS algorithm class with visitor interface. 1205 /// 1191 1206 /// This class provides an efficient implementation of the %DFS algorithm 1192 1207 /// with visitor interface. … … 1194 1209 /// The %DfsVisit class provides an alternative interface to the Dfs 1195 1210 /// class. It works with callback mechanism, the DfsVisit object calls 1196 /// on every dfs event the \c Visitor class member functions.1211 /// the member functions of the \c Visitor class on every DFS event. 1197 1212 /// 1198 /// \tparam _Digraph The digraph typethe algorithm runs on.1213 /// \tparam _Digraph The type of the digraph the algorithm runs on. 1199 1214 /// The default value is 1200 /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it1201 /// is only passed to \ref DfsDefaultTraits.1202 /// \tparam _Visitor The Visitor object for the algorithm. The1203 /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitorwhich1204 /// does not observe the D fs events. If you want to observe the dfs1205 /// events you should implement your own Visitor class.1215 /// \ref ListDigraph. The value of _Digraph is not used directly by 1216 /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits. 1217 /// \tparam _Visitor The Visitor type that is used by the algorithm. 1218 /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which 1219 /// does not observe the DFS events. If you want to observe the DFS 1220 /// events, you should implement your own visitor class. 1206 1221 /// \tparam _Traits Traits class to set various data types used by the 1207 1222 /// algorithm. The default traits class is 1208 1223 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>". 1209 1224 /// See \ref DfsVisitDefaultTraits for the documentation of 1210 /// a Dfs visit traits class. 1211 /// 1212 /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso 1225 /// a DFS visit traits class. 1213 1226 #ifdef DOXYGEN 1214 1227 template <typename _Digraph, typename _Visitor, typename _Traits> … … 1224 1237 /// 1225 1238 /// This error represents problems in the initialization 1226 /// of the parameters of the algorithm s.1239 /// of the parameters of the algorithm. 1227 1240 class UninitializedParameter : public lemon::UninitializedParameter { 1228 1241 public: … … 1233 1246 }; 1234 1247 1248 ///The traits class. 1235 1249 typedef _Traits Traits; 1236 1250 1251 ///The type of the digraph the algorithm runs on. 1237 1252 typedef typename Traits::Digraph Digraph; 1238 1253 1254 ///The visitor type used by the algorithm. 1239 1255 typedef _Visitor Visitor; 1240 1256 1241 ///The type of the map indicatingwhich nodes are reached.1257 ///The type of the map that indicates which nodes are reached. 1242 1258 typedef typename Traits::ReachedMap ReachedMap; 1243 1259 … … 1249 1265 typedef typename Digraph::OutArcIt OutArcIt; 1250 1266 1251 // /Pointer to the underlying digraph.1267 //Pointer to the underlying digraph. 1252 1268 const Digraph *_digraph; 1253 // /Pointer to the visitor object.1269 //Pointer to the visitor object. 1254 1270 Visitor *_visitor; 1255 // /Pointer to the map of reached status of the nodes.1271 //Pointer to the map of reached status of the nodes. 1256 1272 ReachedMap *_reached; 1257 // /Indicates if \ref _reached is locally allocated (\ctrue) or not.1273 //Indicates if _reached is locally allocated (true) or not. 1258 1274 bool local_reached; 1259 1275 … … 1261 1277 int _stack_head; 1262 1278 1263 /// \brief Creates the maps if necessary. 1264 /// 1265 /// Creates the maps if necessary. 1279 ///Creates the maps if necessary. 1280 ///\todo Better memory allocation (instead of new). 1266 1281 void create_maps() { 1267 1282 if(!_reached) { … … 1290 1305 }; 1291 1306 /// \brief \ref named-templ-param "Named parameter" for setting 1292 /// ReachedMap type 1293 /// 1294 /// \ref named-templ-param "Named parameter" for setting ReachedMap type 1307 /// ReachedMap type. 1308 /// 1309 /// \ref named-templ-param "Named parameter" for setting ReachedMap type. 1295 1310 template <class T> 1296 1311 struct DefReachedMap : public DfsVisit< Digraph, Visitor, … … 1306 1321 /// Constructor. 1307 1322 /// 1308 /// \param digraph the digraph the algorithm will run on. 1309 /// \param visitor The visitor of the algorithm. 1310 /// 1323 /// \param digraph The digraph the algorithm runs on. 1324 /// \param visitor The visitor object of the algorithm. 1311 1325 DfsVisit(const Digraph& digraph, Visitor& visitor) 1312 1326 : _digraph(&digraph), _visitor(&visitor), … … 1314 1328 1315 1329 /// \brief Destructor. 1316 ///1317 /// Destructor.1318 1330 ~DfsVisit() { 1319 1331 if(local_reached) delete _reached; 1320 1332 } 1321 1333 1322 /// \brief Sets the map indicating if a node isreached.1323 /// 1324 /// Sets the map indicating if a node isreached.1334 /// \brief Sets the map that indicates which nodes are reached. 1335 /// 1336 /// Sets the map that indicates which nodes are reached. 1325 1337 /// If you don't use this function before calling \ref run(), 1326 /// it will allocate one. The dest uctor deallocates this1338 /// it will allocate one. The destructor deallocates this 1327 1339 /// automatically allocated map, of course. 1328 1340 /// \return <tt> (*this) </tt> … … 1337 1349 1338 1350 public: 1351 1339 1352 /// \name Execution control 1340 1353 /// The simplest way to execute the algorithm is to use 1341 /// one of the member functions called \c run(...). 1354 /// one of the member functions called \ref lemon::DfsVisit::run() 1355 /// "run()". 1342 1356 /// \n 1343 /// If you need more control on the execution, 1344 /// first you must call \ref init(), then you can adda source node1345 /// with \ref addSource().1346 /// Finally \ref start() will perform the actual path1347 /// computation.1357 /// If you need more control on the execution, first you must call 1358 /// \ref lemon::DfsVisit::init() "init()", then you can add several 1359 /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()". 1360 /// Finally \ref lemon::DfsVisit::start() "start()" will perform the 1361 /// actual path computation. 1348 1362 1349 1363 /// @{ 1364 1350 1365 /// \brief Initializes the internal data structures. 1351 1366 /// 1352 1367 /// Initializes the internal data structures. 1353 ///1354 1368 void init() { 1355 1369 create_maps(); … … 1361 1375 } 1362 1376 1363 /// \brief Adds a new source node. 1364 /// 1365 /// Adds a new source node to the set of nodes to be processed. 1366 void addSource(Node s) { 1377 ///Adds a new source node. 1378 1379 ///Adds a new source node to the set of nodes to be processed. 1380 /// 1381 ///\pre The stack must be empty. (Otherwise the algorithm gives 1382 ///false results.) 1383 /// 1384 ///\warning Distances will be wrong (or at least strange) in case of 1385 ///multiple sources. 1386 void addSource(Node s) 1387 { 1388 LEMON_DEBUG(emptyQueue(), "The stack is not empty."); 1367 1389 if(!(*_reached)[s]) { 1368 1390 _reached->set(s,true); … … 1385 1407 /// \return The processed arc. 1386 1408 /// 1387 /// \pre The stack must not be empty !1409 /// \pre The stack must not be empty. 1388 1410 Arc processNextArc() { 1389 1411 Arc e = _stack[_stack_head]; … … 1419 1441 /// \return The next arc to be processed or INVALID if the stack is 1420 1442 /// empty. 1421 Arc nextArc() {1443 Arc nextArc() const { 1422 1444 return _stack_head >= 0 ? _stack[_stack_head] : INVALID; 1423 1445 } 1424 1446 1425 1447 /// \brief Returns \c false if there are nodes 1426 /// to be processed in the queue1448 /// to be processed. 1427 1449 /// 1428 1450 /// Returns \c false if there are nodes 1429 /// to be processed in the queue 1430 bool emptyQueue() { return _stack_head < 0; }1451 /// to be processed in the queue (stack). 1452 bool emptyQueue() const { return _stack_head < 0; } 1431 1453 1432 1454 /// \brief Returns the number of the nodes to be processed. 1433 1455 /// 1434 /// Returns the number of the nodes to be processed in the queue .1435 int queueSize() { return _stack_head + 1; }1456 /// Returns the number of the nodes to be processed in the queue (stack). 1457 int queueSize() const { return _stack_head + 1; } 1436 1458 1437 1459 /// \brief Executes the algorithm. … … 1439 1461 /// Executes the algorithm. 1440 1462 /// 1441 /// \pre init() must be called and at least one node should be added 1442 /// with addSource() before using this function. 1463 /// This method runs the %DFS algorithm from the root node 1464 /// in order to compute the %DFS path to each node. 1465 /// 1466 /// The algorithm computes 1467 /// - the %DFS tree, 1468 /// - the distance of each node from the root in the %DFS tree. 1469 /// 1470 /// \pre init() must be called and a root node should be 1471 /// added with addSource() before using this function. 1472 /// 1473 /// \note <tt>d.start()</tt> is just a shortcut of the following code. 1474 /// \code 1475 /// while ( !d.emptyQueue() ) { 1476 /// d.processNextArc(); 1477 /// } 1478 /// \endcode 1443 1479 void start() { 1444 1480 while ( !emptyQueue() ) processNextArc(); 1445 1481 } 1446 1482 1447 /// \brief Executes the algorithm until \c dest is reached. 1448 /// 1449 /// Executes the algorithm until \c dest is reached. 1450 /// 1451 /// \pre init() must be called and at least one node should be added 1483 /// \brief Executes the algorithm until the given target node is reached. 1484 /// 1485 /// Executes the algorithm until the given target node is reached. 1486 /// 1487 /// This method runs the %DFS algorithm from the root node 1488 /// in order to compute the DFS path to \c dest. 1489 /// 1490 /// The algorithm computes 1491 /// - the %DFS path to \c dest, 1492 /// - the distance of \c dest from the root in the %DFS tree. 1493 /// 1494 /// \pre init() must be called and a root node should be added 1452 1495 /// with addSource() before using this function. 1453 1496 void start(Node dest) { … … 1460 1503 /// Executes the algorithm until a condition is met. 1461 1504 /// 1462 /// \pre init() must be called and at least one node should be added 1505 /// This method runs the %DFS algorithm from the root node 1506 /// until an arc \c a with <tt>am[a]</tt> true is found. 1507 /// 1508 /// \param am A \c bool (or convertible) arc map. The algorithm 1509 /// will stop when it reaches an arc \c a with <tt>am[a]</tt> true. 1510 /// 1511 /// \return The reached arc \c a with <tt>am[a]</tt> true or 1512 /// \c INVALID if no such arc was found. 1513 /// 1514 /// \pre init() must be called and a root node should be added 1463 1515 /// with addSource() before using this function. 1464 1516 /// 1465 /// \param em must be a bool (or convertible) arc map. The algorithm 1466 /// will stop when it reaches an arc \c e with <tt>em[e]</tt> true. 1467 /// 1468 ///\return The reached arc \c e with <tt>em[e]</tt> true or 1469 ///\c INVALID if no such arc was found. 1470 /// 1471 /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map, 1517 /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map, 1472 1518 /// not a node map. 1473 template <typename EM>1474 Arc start(const EM &em) {1475 while ( !emptyQueue() && ! em[_stack[_stack_head]] )1519 template <typename AM> 1520 Arc start(const AM &am) { 1521 while ( !emptyQueue() && !am[_stack[_stack_head]] ) 1476 1522 processNextArc(); 1477 1523 return emptyQueue() ? INVALID : _stack[_stack_head]; 1478 1524 } 1479 1525 1480 /// \brief Runs %DFSVisit algorithm from node \c s. 1481 /// 1482 /// This method runs the %DFS algorithm from a root node \c s. 1483 /// \note d.run(s) is just a shortcut of the following code. 1526 /// \brief Runs the algorithm from the given node. 1527 /// 1528 /// This method runs the %DFS algorithm from node \c s. 1529 /// in order to compute the DFS path to each node. 1530 /// 1531 /// The algorithm computes 1532 /// - the %DFS tree, 1533 /// - the distance of each node from the root in the %DFS tree. 1534 /// 1535 /// \note <tt>d.run(s)</tt> is just a shortcut of the following code. 1484 1536 ///\code 1485 1537 /// d.init(); … … 1493 1545 } 1494 1546 1495 /// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph. 1547 /// \brief Finds the %DFS path between \c s and \c t. 1548 1549 /// This method runs the %DFS algorithm from node \c s 1550 /// in order to compute the DFS path to \c t. 1551 /// 1552 /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path, 1553 /// if \c t is reachable form \c s, \c 0 otherwise. 1554 /// 1555 /// \note Apart from the return value, <tt>d.run(s,t)</tt> is 1556 /// just a shortcut of the following code. 1557 ///\code 1558 /// d.init(); 1559 /// d.addSource(s); 1560 /// d.start(t); 1561 ///\endcode 1562 int run(Node s,Node t) { 1563 init(); 1564 addSource(s); 1565 start(t); 1566 return reached(t)?_stack_head+1:0; 1567 } 1568 1569 /// \brief Runs the algorithm to visit all nodes in the digraph. 1496 1570 1497 1571 /// This method runs the %DFS algorithm in order to 1498 /// compute the %DFS path to each node. The algorithm computes 1499 /// - The %DFS tree. 1500 /// - The distance of each node from the root in the %DFS tree. 1501 /// 1502 ///\note d.run() is just a shortcut of the following code. 1572 /// compute the %DFS path to each node. 1573 /// 1574 /// The algorithm computes 1575 /// - the %DFS tree, 1576 /// - the distance of each node from the root in the %DFS tree. 1577 /// 1578 /// \note <tt>d.run()</tt> is just a shortcut of the following code. 1503 1579 ///\code 1504 /// d.init();1505 /// for (NodeIt it(digraph); it != INVALID; ++it) {1506 /// if (!d.reached(it)) {1507 /// d.addSource(it);1508 /// d.start();1509 /// }1510 /// }1580 /// d.init(); 1581 /// for (NodeIt n(digraph); n != INVALID; ++n) { 1582 /// if (!d.reached(n)) { 1583 /// d.addSource(n); 1584 /// d.start(); 1585 /// } 1586 /// } 1511 1587 ///\endcode 1512 1588 void run() { … … 1519 1595 } 1520 1596 } 1597 1521 1598 ///@} 1522 1599 … … 1524 1601 /// The result of the %DFS algorithm can be obtained using these 1525 1602 /// functions.\n 1526 /// Before the use of these functions, 1527 /// either run() or start() must be called. 1603 /// Either \ref lemon::DfsVisit::run() "run()" or 1604 /// \ref lemon::DfsVisit::start() "start()" must be called before 1605 /// using them. 1528 1606 ///@{ 1529 /// \brief Checks if a node is reachable from the root. 1607 1608 /// \brief Checks if a node is reachable from the root(s). 1530 1609 /// 1531 1610 /// Returns \c true if \c v is reachable from the root(s). 1532 /// \warning The source nodes are inditated as unreachable.1533 1611 /// \pre Either \ref run() or \ref start() 1534 1612 /// must be called before using this function. 1535 ///1536 1613 bool reached(Node v) { return (*_reached)[v]; } 1614 1537 1615 ///@} 1616 1538 1617 }; 1539 1618 1540 1541 1619 } //END OF NAMESPACE LEMON 1542 1620 1543 1621 #endif 1544 -
lemon/dijkstra.h
r210 r244 34 34 namespace lemon { 35 35 36 /// \brief Default OperationTraits for the Dijkstra algorithm class.36 /// \brief Default operation traits for the Dijkstra algorithm class. 37 37 /// 38 /// It defines all computational operations and constants which are39 /// used in the Dijkstra algorithm.38 /// This operation traits class defines all computational operations and 39 /// constants which are used in the Dijkstra algorithm. 40 40 template <typename Value> 41 41 struct DijkstraDefaultOperationTraits { … … 48 48 return left + right; 49 49 } 50 /// \brief Gives back true only if the first value less than the second.50 /// \brief Gives back true only if the first value is less than the second. 51 51 static bool less(const Value& left, const Value& right) { 52 52 return left < right; … … 54 54 }; 55 55 56 /// \brief Widest path OperationTraits for the Dijkstra algorithm class.56 /// \brief Widest path operation traits for the Dijkstra algorithm class. 57 57 /// 58 /// It defines all computational operations and constants which are 59 /// used in the Dijkstra algorithm for widest path computation. 58 /// This operation traits class defines all computational operations and 59 /// constants which are used in the Dijkstra algorithm for widest path 60 /// computation. 61 /// 62 /// \see DijkstraDefaultOperationTraits 60 63 template <typename Value> 61 64 struct DijkstraWidestPathOperationTraits { … … 68 71 return std::min(left, right); 69 72 } 70 /// \brief Gives back true only if the first value less than the second.73 /// \brief Gives back true only if the first value is less than the second. 71 74 static bool less(const Value& left, const Value& right) { 72 75 return left < right; … … 77 80 78 81 ///Default traits class of Dijkstra class. 79 ///\tparam GR Digraph type.80 ///\tparam LM T ype oflength map.82 ///\tparam GR The type of the digraph. 83 ///\tparam LM The type of the length map. 81 84 template<class GR, class LM> 82 85 struct DijkstraDefaultTraits 83 86 { 84 ///The digraph typethe algorithm runs on.87 ///The type of the digraph the algorithm runs on. 85 88 typedef GR Digraph; 89 86 90 ///The type of the map that stores the arc lengths. 87 91 … … 89 93 ///It must meet the \ref concepts::ReadMap "ReadMap" concept. 90 94 typedef LM LengthMap; 91 // The type of the length of the arcs.95 ///The type of the length of the arcs. 92 96 typedef typename LM::Value Value; 97 93 98 /// Operation traits for Dijkstra algorithm. 94 99 95 /// It defines the used operation bythe algorithm.100 /// This class defines the operations that are used in the algorithm. 96 101 /// \see DijkstraDefaultOperationTraits 97 102 typedef DijkstraDefaultOperationTraits<Value> OperationTraits; 98 /// The cross reference type used by heap. 99 100 101 /// The cross reference type used by heap.103 104 /// The cross reference type used by the heap. 105 106 /// The cross reference type used by the heap. 102 107 /// Usually it is \c Digraph::NodeMap<int>. 103 108 typedef typename Digraph::template NodeMap<int> HeapCrossRef; 104 ///Instantiates a HeapCrossRef.105 106 ///This function instantiates a \ cHeapCrossRef.107 /// \param Gis the digraph, to which we would like to define the108 /// HeapCrossRef.109 static HeapCrossRef *createHeapCrossRef(const GR &G)110 { 111 return new HeapCrossRef( G);112 } 113 114 ///The heap type used by Dijkstra algorithm.115 116 ///The heap type used by Dijkstra algorithm.109 ///Instantiates a \ref HeapCrossRef. 110 111 ///This function instantiates a \ref HeapCrossRef. 112 /// \param g is the digraph, to which we would like to define the 113 /// \ref HeapCrossRef. 114 static HeapCrossRef *createHeapCrossRef(const Digraph &g) 115 { 116 return new HeapCrossRef(g); 117 } 118 119 ///The heap type used by the Dijkstra algorithm. 120 121 ///The heap type used by the Dijkstra algorithm. 117 122 /// 118 123 ///\sa BinHeap 119 124 ///\sa Dijkstra 120 125 typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap; 121 122 static Heap *createHeap(HeapCrossRef& R) 123 { 124 return new Heap(R); 125 } 126 127 ///\brief The type of the map that stores the last 126 ///Instantiates a \ref Heap. 127 128 ///This function instantiates a \ref Heap. 129 static Heap *createHeap(HeapCrossRef& r) 130 { 131 return new Heap(r); 132 } 133 134 ///\brief The type of the map that stores the predecessor 128 135 ///arcs of the shortest paths. 129 136 /// 130 ///The type of the map that stores the last137 ///The type of the map that stores the predecessor 131 138 ///arcs of the shortest paths. 132 139 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 133 ///134 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;135 ///Instantiates a PredMap. 136 137 /// This function instantiates a \c PredMap.138 ///\ param G is the digraph, to which we would like to define thePredMap.140 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 141 ///Instantiates a \ref PredMap. 142 143 ///This function instantiates a \ref PredMap. 144 ///\param g is the digraph, to which we would like to define the 145 ///\ref PredMap. 139 146 ///\todo The digraph alone may be insufficient for the initialization 140 static PredMap *createPredMap(const GR &G)141 { 142 return new PredMap( G);143 } 144 145 ///The type of the map that stores whether a nodes isprocessed.146 147 ///The type of the map that stores whether a nodes isprocessed.147 static PredMap *createPredMap(const Digraph &g) 148 { 149 return new PredMap(g); 150 } 151 152 ///The type of the map that indicates which nodes are processed. 153 154 ///The type of the map that indicates which nodes are processed. 148 155 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 149 156 ///By default it is a NullMap. 150 157 ///\todo If it is set to a real map, 151 158 ///Dijkstra::processed() should read this. 152 ///\todo named parameter to set this type, function to read and write.153 159 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 154 ///Instantiates a ProcessedMap.155 156 ///This function instantiates a \ cProcessedMap.160 ///Instantiates a \ref ProcessedMap. 161 162 ///This function instantiates a \ref ProcessedMap. 157 163 ///\param g is the digraph, to which 158 ///we would like to define the \ cProcessedMap164 ///we would like to define the \ref ProcessedMap 159 165 #ifdef DOXYGEN 160 static ProcessedMap *createProcessedMap(const GR&g)166 static ProcessedMap *createProcessedMap(const Digraph &g) 161 167 #else 162 static ProcessedMap *createProcessedMap(const GR&)168 static ProcessedMap *createProcessedMap(const Digraph &) 163 169 #endif 164 170 { 165 171 return new ProcessedMap(); 166 172 } 167 ///The type of the map that stores the dists of the nodes. 168 169 ///The type of the map that stores the dists of the nodes. 173 174 ///The type of the map that stores the distances of the nodes. 175 176 ///The type of the map that stores the distances of the nodes. 170 177 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 171 ///172 178 typedef typename Digraph::template NodeMap<typename LM::Value> DistMap; 173 ///Instantiates a DistMap.179 ///Instantiates a \ref DistMap. 174 180 175 181 ///This function instantiates a \ref DistMap. 176 ///\param Gis the digraph, to which we would like to define182 ///\param g is the digraph, to which we would like to define 177 183 ///the \ref DistMap 178 static DistMap *createDistMap(const GR &G)179 { 180 return new DistMap( G);184 static DistMap *createDistMap(const Digraph &g) 185 { 186 return new DistMap(g); 181 187 } 182 188 }; … … 185 191 186 192 /// \ingroup shortest_path 187 ///This class provides an efficient implementation of %Dijkstra algorithm. 193 ///This class provides an efficient implementation of the %Dijkstra algorithm. 194 /// 188 195 ///The arc lengths are passed to the algorithm using a 189 196 ///\ref concepts::ReadMap "ReadMap", 190 197 ///so it is easy to change it to any kind of length. 191 ///192 198 ///The type of the length is determined by the 193 199 ///\ref concepts::ReadMap::Value "Value" of the length map. 194 ///195 200 ///It is also possible to change the underlying priority heap. 196 201 /// 197 ///\tparam GR The digraph type the algorithm runs on. The default value 198 ///is \ref ListDigraph. The value of GR is not used directly by 199 ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits. 200 ///\tparam LM This read-only ArcMap determines the lengths of the 202 ///There is also a \ref dijkstra() "function type interface" for the 203 ///%Dijkstra algorithm, which is convenient in the simplier cases and 204 ///it can be used easier. 205 /// 206 ///\tparam GR The type of the digraph the algorithm runs on. 207 ///The default value is \ref ListDigraph. 208 ///The value of GR is not used directly by \ref Dijkstra, it is only 209 ///passed to \ref DijkstraDefaultTraits. 210 ///\tparam LM A readable arc map that determines the lengths of the 201 211 ///arcs. It is read once for each arc, so the map may involve in 202 ///relatively time consuming process to compute the arc length if212 ///relatively time consuming process to compute the arc lengths if 203 213 ///it is necessary. The default map type is \ref 204 ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>". The value 205 ///of LM is not used directly by Dijkstra, it is only passed to \ref 206 ///DijkstraDefaultTraits. 207 ///\tparam TR Traits class to set 208 ///various data types used by the algorithm. The default traits 209 ///class is \ref DijkstraDefaultTraits 210 ///"DijkstraDefaultTraits<GR,LM>". See \ref 211 ///DijkstraDefaultTraits for the documentation of a Dijkstra traits 212 ///class. 213 214 ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>". 215 ///The value of LM is not used directly by \ref Dijkstra, it is only 216 ///passed to \ref DijkstraDefaultTraits. 217 ///\tparam TR Traits class to set various data types used by the algorithm. 218 ///The default traits class is \ref DijkstraDefaultTraits 219 ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits 220 ///for the documentation of a Dijkstra traits class. 214 221 #ifdef DOXYGEN 215 222 template <typename GR, typename LM, typename TR> … … 221 228 class Dijkstra { 222 229 public: 223 /** 224 * \brief \ref Exception for uninitialized parameters. 225 * 226 * This error represents problems in the initialization 227 * of the parameters of the algorithms. 228 */ 230 ///\ref Exception for uninitialized parameters. 231 232 ///This error represents problems in the initialization of the 233 ///parameters of the algorithm. 229 234 class UninitializedParameter : public lemon::UninitializedParameter { 230 235 public: … … 234 239 }; 235 240 236 typedef TR Traits; 237 ///The type of the underlying digraph. 241 ///The type of the digraph the algorithm runs on. 238 242 typedef typename TR::Digraph Digraph; 239 ///\e240 typedef typename Digraph::Node Node;241 ///\e242 typedef typename Digraph::NodeIt NodeIt;243 ///\e244 typedef typename Digraph::Arc Arc;245 ///\e246 typedef typename Digraph::OutArcIt OutArcIt;247 243 248 244 ///The type of the length of the arcs. … … 250 246 ///The type of the map that stores the arc lengths. 251 247 typedef typename TR::LengthMap LengthMap; 252 ///\brief The type of the map that stores the last253 /// arcs of theshortest paths.248 ///\brief The type of the map that stores the predecessor arcs of the 249 ///shortest paths. 254 250 typedef typename TR::PredMap PredMap; 255 ///The type of the map indicating if a node is processed. 251 ///The type of the map that stores the distances of the nodes. 252 typedef typename TR::DistMap DistMap; 253 ///The type of the map that indicates which nodes are processed. 256 254 typedef typename TR::ProcessedMap ProcessedMap; 257 ///The type of the map that stores the dists of the nodes.258 typedef typename TR::DistMap DistMap;255 ///The type of the paths. 256 typedef PredMapPath<Digraph, PredMap> Path; 259 257 ///The cross reference type used for the current heap. 260 258 typedef typename TR::HeapCrossRef HeapCrossRef; 261 ///The heap type used by the dijkstraalgorithm.259 ///The heap type used by the algorithm. 262 260 typedef typename TR::Heap Heap; 263 ///The operation traits .261 ///The operation traits class. 264 262 typedef typename TR::OperationTraits OperationTraits; 263 264 ///The traits class. 265 typedef TR Traits; 266 265 267 private: 266 /// Pointer to the underlying digraph. 268 269 typedef typename Digraph::Node Node; 270 typedef typename Digraph::NodeIt NodeIt; 271 typedef typename Digraph::Arc Arc; 272 typedef typename Digraph::OutArcIt OutArcIt; 273 274 //Pointer to the underlying digraph. 267 275 const Digraph *G; 268 // / Pointer to the length map276 //Pointer to the length map. 269 277 const LengthMap *length; 270 // /Pointer to the map of predecessors arcs.278 //Pointer to the map of predecessors arcs. 271 279 PredMap *_pred; 272 // /Indicates if \ref _pred is locally allocated (\ctrue) or not.280 //Indicates if _pred is locally allocated (true) or not. 273 281 bool local_pred; 274 // /Pointer to the map of distances.282 //Pointer to the map of distances. 275 283 DistMap *_dist; 276 // /Indicates if \ref _dist is locally allocated (\ctrue) or not.284 //Indicates if _dist is locally allocated (true) or not. 277 285 bool local_dist; 278 // /Pointer to the map of processed status of the nodes.286 //Pointer to the map of processed status of the nodes. 279 287 ProcessedMap *_processed; 280 // /Indicates if \ref _processed is locally allocated (\ctrue) or not.288 //Indicates if _processed is locally allocated (true) or not. 281 289 bool local_processed; 282 // /Pointer to the heap cross references.290 //Pointer to the heap cross references. 283 291 HeapCrossRef *_heap_cross_ref; 284 // /Indicates if \ref _heap_cross_ref is locally allocated (\ctrue) or not.292 //Indicates if _heap_cross_ref is locally allocated (true) or not. 285 293 bool local_heap_cross_ref; 286 // /Pointer to the heap.294 //Pointer to the heap. 287 295 Heap *_heap; 288 // /Indicates if \ref _heap is locally allocated (\ctrue) or not.296 //Indicates if _heap is locally allocated (true) or not. 289 297 bool local_heap; 290 298 291 299 ///Creates the maps if necessary. 292 293 300 ///\todo Better memory allocation (instead of new). 294 301 void create_maps() … … 316 323 } 317 324 318 public 325 public: 319 326 320 327 typedef Dijkstra Create; … … 332 339 } 333 340 }; 334 ///\ref named-templ-param "Named parameter" for setting PredMap type 335 336 ///\ref named-templ-param "Named parameter" for setting PredMap type 337 /// 341 ///\brief \ref named-templ-param "Named parameter" for setting 342 ///\ref PredMap type. 343 /// 344 ///\ref named-templ-param "Named parameter" for setting 345 ///\ref PredMap type. 338 346 template <class T> 339 347 struct DefPredMap … … 350 358 } 351 359 }; 352 ///\ref named-templ-param "Named parameter" for setting DistMap type 353 354 ///\ref named-templ-param "Named parameter" for setting DistMap type 355 /// 360 ///\brief \ref named-templ-param "Named parameter" for setting 361 ///\ref DistMap type. 362 /// 363 ///\ref named-templ-param "Named parameter" for setting 364 ///\ref DistMap type. 356 365 template <class T> 357 366 struct DefDistMap … … 363 372 struct DefProcessedMapTraits : public Traits { 364 373 typedef T ProcessedMap; 365 static ProcessedMap *createProcessedMap(const Digraph & G)374 static ProcessedMap *createProcessedMap(const Digraph &) 366 375 { 367 376 throw UninitializedParameter(); 368 377 } 369 378 }; 370 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type 371 372 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type 373 /// 379 ///\brief \ref named-templ-param "Named parameter" for setting 380 ///\ref ProcessedMap type. 381 /// 382 ///\ref named-templ-param "Named parameter" for setting 383 ///\ref ProcessedMap type. 374 384 template <class T> 375 385 struct DefProcessedMap … … 380 390 struct DefDigraphProcessedMapTraits : public Traits { 381 391 typedef typename Digraph::template NodeMap<bool> ProcessedMap; 382 static ProcessedMap *createProcessedMap(const Digraph & G)392 static ProcessedMap *createProcessedMap(const Digraph &g) 383 393 { 384 return new ProcessedMap( G);385 } 386 }; 387 ///\brief \ref named-templ-param "Named parameter" 388 /// for setting the ProcessedMap type to be Digraph::NodeMap<bool>.389 /// 390 ///\ref named-templ-param "Named parameter" 391 /// for setting the ProcessedMap type to be Digraph::NodeMap<bool>.392 ///If you don't set it explicit ely, it will be automatically allocated.394 return new ProcessedMap(g); 395 } 396 }; 397 ///\brief \ref named-templ-param "Named parameter" for setting 398 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 399 /// 400 ///\ref named-templ-param "Named parameter" for setting 401 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 402 ///If you don't set it explicitly, it will be automatically allocated. 393 403 template <class T> 394 404 struct DefProcessedMapToBeDefaultMap … … 414 424 /// 415 425 ///\ref named-templ-param "Named parameter" for setting heap and cross 416 ///reference type 417 /// 426 ///reference type. 418 427 template <class H, class CR = typename Digraph::template NodeMap<int> > 419 428 struct DefHeap … … 454 463 455 464 /// \brief \ref named-templ-param "Named parameter" for setting 456 /// OperationTraits type457 /// 458 /// \ref named-templ-param "Named parameter" for setting OperationTraits459 /// type465 ///\ref OperationTraits type 466 /// 467 ///\ref named-templ-param "Named parameter" for setting 468 ///\ref OperationTraits type. 460 469 template <class T> 461 470 struct DefOperationTraits … … 467 476 ///@} 468 477 469 470 478 protected: 471 479 … … 476 484 ///Constructor. 477 485 478 ///\param _G the digraph the algorithm will run on. 479 ///\param _length the length map used by the algorithm. 480 Dijkstra(const Digraph& _G, const LengthMap& _length) : 481 G(&_G), length(&_length), 486 ///Constructor. 487 ///\param _g The digraph the algorithm runs on. 488 ///\param _length The length map used by the algorithm. 489 Dijkstra(const Digraph& _g, const LengthMap& _length) : 490 G(&_g), length(&_length), 482 491 _pred(NULL), local_pred(false), 483 492 _dist(NULL), local_dist(false), … … 507 516 } 508 517 509 ///Sets the map storingthe predecessor arcs.510 511 ///Sets the map storingthe predecessor arcs.518 ///Sets the map that stores the predecessor arcs. 519 520 ///Sets the map that stores the predecessor arcs. 512 521 ///If you don't use this function before calling \ref run(), 513 ///it will allocate one. The dest uctor deallocates this522 ///it will allocate one. The destructor deallocates this 514 523 ///automatically allocated map, of course. 515 524 ///\return <tt> (*this) </tt> … … 524 533 } 525 534 526 ///Sets the map storing the distances calculated by the algorithm.527 528 ///Sets the map storing the distances calculated by the algorithm.535 ///Sets the map that indicates which nodes are processed. 536 537 ///Sets the map that indicates which nodes are processed. 529 538 ///If you don't use this function before calling \ref run(), 530 ///it will allocate one. The destuctor deallocates this 539 ///it will allocate one. The destructor deallocates this 540 ///automatically allocated map, of course. 541 ///\return <tt> (*this) </tt> 542 Dijkstra &processedMap(ProcessedMap &m) 543 { 544 if(local_processed) { 545 delete _processed; 546 local_processed=false; 547 } 548 _processed = &m; 549 return *this; 550 } 551 552 ///Sets the map that stores the distances of the nodes. 553 554 ///Sets the map that stores the distances of the nodes calculated by the 555 ///algorithm. 556 ///If you don't use this function before calling \ref run(), 557 ///it will allocate one. The destructor deallocates this 531 558 ///automatically allocated map, of course. 532 559 ///\return <tt> (*this) </tt> … … 545 572 ///Sets the heap and the cross reference used by algorithm. 546 573 ///If you don't use this function before calling \ref run(), 547 ///it will allocate one. The dest uctor deallocates this574 ///it will allocate one. The destructor deallocates this 548 575 ///automatically allocated heap and cross reference, of course. 549 576 ///\return <tt> (*this) </tt> … … 564 591 565 592 private: 593 566 594 void finalizeNodeData(Node v,Value dst) 567 595 { … … 572 600 public: 573 601 574 typedef PredMapPath<Digraph, PredMap> Path;575 576 602 ///\name Execution control 577 ///The simplest way to execute the algorithm is to use 578 /// one of the member functions called \c run(...).603 ///The simplest way to execute the algorithm is to use one of the 604 ///member functions called \ref lemon::Dijkstra::run() "run()". 579 605 ///\n 580 ///If you need more control on the execution, 581 /// first you must call \ref init(), then you can add several source nodes582 /// with \ref addSource().583 ///Finally \ref start() will perform the actual path584 /// computation.606 ///If you need more control on the execution, first you must call 607 ///\ref lemon::Dijkstra::init() "init()", then you can add several 608 ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()". 609 ///Finally \ref lemon::Dijkstra::start() "start()" will perform the 610 ///actual path computation. 585 611 586 612 ///@{ … … 604 630 605 631 ///Adds a new source node to the priority heap. 606 ///607 632 ///The optional second parameter is the initial distance of the node. 608 633 /// 609 /// Itchecks if the node has already been added to the heap and634 ///The function checks if the node has already been added to the heap and 610 635 ///it is pushed to the heap only if either it was not in the heap 611 636 ///or the shortest path found till then is shorter than \c dst. … … 626 651 ///\return The processed node. 627 652 /// 628 ///\warning The priority heap must not be empty !653 ///\warning The priority heap must not be empty. 629 654 Node processNextNode() 630 655 { … … 657 682 } 658 683 659 ///Next node to be processed. 660 661 ///Next node to be processed. 662 /// 663 ///\return The next node to be processed or INVALID if the priority heap 664 /// is empty. 665 Node nextNode() 684 ///The next node to be processed. 685 686 ///Returns the next node to be processed or \c INVALID if the 687 ///priority heap is empty. 688 Node nextNode() const 666 689 { 667 690 return !_heap->empty()?_heap->top():INVALID; … … 669 692 670 693 ///\brief Returns \c false if there are nodes 671 ///to be processed in the priority heap694 ///to be processed. 672 695 /// 673 696 ///Returns \c false if there are nodes 674 ///to be processed in the priority heap 675 bool emptyQueue() { return _heap->empty(); } 697 ///to be processed in the priority heap. 698 bool emptyQueue() const { return _heap->empty(); } 699 676 700 ///Returns the number of the nodes to be processed in the priority heap 677 701 678 ///Returns the number of the nodes to be processed in the priority heap 679 /// 680 int queueSize() { return _heap->size(); }702 ///Returns the number of the nodes to be processed in the priority heap. 703 /// 704 int queueSize() const { return _heap->size(); } 681 705 682 706 ///Executes the algorithm. … … 684 708 ///Executes the algorithm. 685 709 /// 686 ///\pre init() must be called and at least one node should be added687 ///with addSource() before using this function.688 ///689 710 ///This method runs the %Dijkstra algorithm from the root node(s) 690 ///in order to 691 ///compute the 692 ///shortest path to each node. The algorithm computes 693 ///- The shortest path tree. 694 ///- The distance of each node from the root(s). 695 /// 711 ///in order to compute the shortest path to each node. 712 /// 713 ///The algorithm computes 714 ///- the shortest path tree (forest), 715 ///- the distance of each node from the root(s). 716 /// 717 ///\pre init() must be called and at least one root node should be 718 ///added with addSource() before using this function. 719 /// 720 ///\note <tt>d.start()</tt> is just a shortcut of the following code. 721 ///\code 722 /// while ( !d.emptyQueue() ) { 723 /// d.processNextNode(); 724 /// } 725 ///\endcode 696 726 void start() 697 727 { 698 while ( !_heap->empty() ) processNextNode(); 699 } 700 701 ///Executes the algorithm until \c dest is reached. 702 703 ///Executes the algorithm until \c dest is reached. 704 /// 705 ///\pre init() must be called and at least one node should be added 706 ///with addSource() before using this function. 728 while ( !emptyQueue() ) processNextNode(); 729 } 730 731 ///Executes the algorithm until the given target node is reached. 732 733 ///Executes the algorithm until the given target node is reached. 707 734 /// 708 735 ///This method runs the %Dijkstra algorithm from the root node(s) 709 ///in order to 710 ///compute the 711 ///shortest path to \c dest. The algorithm computes 712 ///- The shortest path to \c dest. 713 ///- The distance of \c dest from the root(s). 714 /// 736 ///in order to compute the shortest path to \c dest. 737 /// 738 ///The algorithm computes 739 ///- the shortest path to \c dest, 740 ///- the distance of \c dest from the root(s). 741 /// 742 ///\pre init() must be called and at least one root node should be 743 ///added with addSource() before using this function. 715 744 void start(Node dest) 716 745 { … … 723 752 ///Executes the algorithm until a condition is met. 724 753 /// 725 ///\pre init() must be called and at least one node should be added 726 ///with addSource() before using this function. 727 /// 728 ///\param nm must be a bool (or convertible) node map. The algorithm 754 ///This method runs the %Dijkstra algorithm from the root node(s) in 755 ///order to compute the shortest path to a node \c v with 756 /// <tt>nm[v]</tt> true, if such a node can be found. 757 /// 758 ///\param nm A \c bool (or convertible) node map. The algorithm 729 759 ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true. 730 760 /// 731 761 ///\return The reached node \c v with <tt>nm[v]</tt> true or 732 762 ///\c INVALID if no such node was found. 763 /// 764 ///\pre init() must be called and at least one root node should be 765 ///added with addSource() before using this function. 733 766 template<class NodeBoolMap> 734 767 Node start(const NodeBoolMap &nm) … … 740 773 } 741 774 742 ///Runs %Dijkstra algorithm from node \c s.743 744 ///This method runs the %Dijkstra algorithm from a rootnode \c s745 ///in order to 746 /// compute the747 /// shortest path to each node.The algorithm computes748 ///- The shortest path tree.749 ///- The distance of each node from the root.750 /// 751 ///\note d.run(s)is just a shortcut of the following code.775 ///Runs the algorithm from the given node. 776 777 ///This method runs the %Dijkstra algorithm from node \c s 778 ///in order to compute the shortest path to each node. 779 /// 780 ///The algorithm computes 781 ///- the shortest path tree, 782 ///- the distance of each node from the root. 783 /// 784 ///\note <tt>d.run(s)</tt> is just a shortcut of the following code. 752 785 ///\code 753 786 /// d.init(); … … 763 796 ///Finds the shortest path between \c s and \c t. 764 797 765 ///Finds the shortest path between \c s and \c t. 766 /// 767 ///\return The length of the shortest s---t path if there exists one, 768 ///0 otherwise. 769 ///\note Apart from the return value, d.run(s) is 770 ///just a shortcut of the following code. 798 ///This method runs the %Dijkstra algorithm from node \c s 799 ///in order to compute the shortest path to \c t. 800 /// 801 ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path, 802 ///if \c t is reachable form \c s, \c 0 otherwise. 803 /// 804 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a 805 ///shortcut of the following code. 771 806 ///\code 772 807 /// d.init(); … … 786 821 ///The result of the %Dijkstra algorithm can be obtained using these 787 822 ///functions.\n 788 ///Before the use of these functions, 789 ///either run() or start() must be called. 823 ///Either \ref lemon::Dijkstra::run() "run()" or 824 ///\ref lemon::Dijkstra::start() "start()" must be called before 825 ///using them. 790 826 791 827 ///@{ 792 828 793 ///Gives back the shortest path. 794 795 ///Gives back the shortest path. 796 ///\pre The \c t should be reachable from the source. 797 Path path(Node t) 798 { 799 return Path(*G, *_pred, t); 800 } 801 802 ///The distance of a node from the root. 803 804 ///Returns the distance of a node from the root. 805 ///\pre \ref run() must be called before using this function. 806 ///\warning If node \c v in unreachable from the root the return value 807 ///of this funcion is undefined. 829 ///The shortest path to a node. 830 831 ///Returns the shortest path to a node. 832 /// 833 ///\warning \c t should be reachable from the root(s). 834 /// 835 ///\pre Either \ref run() or \ref start() must be called before 836 ///using this function. 837 Path path(Node t) const { return Path(*G, *_pred, t); } 838 839 ///The distance of a node from the root(s). 840 841 ///Returns the distance of a node from the root(s). 842 /// 843 ///\warning If node \c v is not reachable from the root(s), then 844 ///the return value of this function is undefined. 845 /// 846 ///\pre Either \ref run() or \ref start() must be called before 847 ///using this function. 808 848 Value dist(Node v) const { return (*_dist)[v]; } 809 849 810 ///The current distance of a node from the root. 811 812 ///Returns the current distance of a node from the root. 813 ///It may be decreased in the following processes. 814 ///\pre \c node should be reached but not processed 815 Value currentDist(Node v) const { return (*_heap)[v]; } 816 817 ///Returns the 'previous arc' of the shortest path tree. 818 819 ///For a node \c v it returns the 'previous arc' of the shortest path tree, 820 ///i.e. it returns the last arc of a shortest path from the root to \c 821 ///v. It is \ref INVALID 822 ///if \c v is unreachable from the root or if \c v=s. The 823 ///shortest path tree used here is equal to the shortest path tree used in 824 ///\ref predNode(). \pre \ref run() must be called before using 825 ///this function. 850 ///Returns the 'previous arc' of the shortest path tree for a node. 851 852 ///This function returns the 'previous arc' of the shortest path 853 ///tree for the node \c v, i.e. it returns the last arc of a 854 ///shortest path from the root(s) to \c v. It is \c INVALID if \c v 855 ///is not reachable from the root(s) or if \c v is a root. 856 /// 857 ///The shortest path tree used here is equal to the shortest path 858 ///tree used in \ref predNode(). 859 /// 860 ///\pre Either \ref run() or \ref start() must be called before 861 ///using this function. 826 862 Arc predArc(Node v) const { return (*_pred)[v]; } 827 863 828 ///Returns the 'previous node' of the shortest path tree. 829 830 ///For a node \c v it returns the 'previous node' of the shortest path tree, 831 ///i.e. it returns the last but one node from a shortest path from the 832 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if 833 ///\c v=s. The shortest path tree used here is equal to the shortest path 834 ///tree used in \ref predArc(). \pre \ref run() must be called before 864 ///Returns the 'previous node' of the shortest path tree for a node. 865 866 ///This function returns the 'previous node' of the shortest path 867 ///tree for the node \c v, i.e. it returns the last but one node 868 ///from a shortest path from the root(s) to \c v. It is \c INVALID 869 ///if \c v is not reachable from the root(s) or if \c v is a root. 870 /// 871 ///The shortest path tree used here is equal to the shortest path 872 ///tree used in \ref predArc(). 873 /// 874 ///\pre Either \ref run() or \ref start() must be called before 835 875 ///using this function. 836 876 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 837 877 G->source((*_pred)[v]); } 838 878 839 ///Returns a reference to the NodeMap of distances. 840 841 ///Returns a reference to the NodeMap of distances. \pre \ref run() must 842 ///be called before using this function. 879 ///\brief Returns a const reference to the node map that stores the 880 ///distances of the nodes. 881 /// 882 ///Returns a const reference to the node map that stores the distances 883 ///of the nodes calculated by the algorithm. 884 /// 885 ///\pre Either \ref run() or \ref init() 886 ///must be called before using this function. 843 887 const DistMap &distMap() const { return *_dist;} 844 888 845 ///Returns a reference to the shortest path tree map. 846 847 ///Returns a reference to the NodeMap of the arcs of the 848 ///shortest path tree. 849 ///\pre \ref run() must be called before using this function. 889 ///\brief Returns a const reference to the node map that stores the 890 ///predecessor arcs. 891 /// 892 ///Returns a const reference to the node map that stores the predecessor 893 ///arcs, which form the shortest path tree. 894 /// 895 ///\pre Either \ref run() or \ref init() 896 ///must be called before using this function. 850 897 const PredMap &predMap() const { return *_pred;} 851 898 852 ///Checks if a node is reachable from the root .853 854 ///Returns \c true if \c v is reachable from the root .855 ///\ warning The source nodes are inditated as unreached.856 /// \pre \ref run()must be called before using this function.857 ///858 bool reached(Node v) { return (*_heap_cross_ref)[v] !=Heap::PRE_HEAP; }899 ///Checks if a node is reachable from the root(s). 900 901 ///Returns \c true if \c v is reachable from the root(s). 902 ///\pre Either \ref run() or \ref start() 903 ///must be called before using this function. 904 bool reached(Node v) const { return (*_heap_cross_ref)[v] != 905 Heap::PRE_HEAP; } 859 906 860 907 ///Checks if a node is processed. … … 862 909 ///Returns \c true if \c v is processed, i.e. the shortest 863 910 ///path to \c v has already found. 864 ///\pre \ref run() must be called before using this function. 865 /// 866 bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; } 911 ///\pre Either \ref run() or \ref start() 912 ///must be called before using this function. 913 bool processed(Node v) const { return (*_heap_cross_ref)[v] == 914 Heap::POST_HEAP; } 915 916 ///The current distance of a node from the root(s). 917 918 ///Returns the current distance of a node from the root(s). 919 ///It may be decreased in the following processes. 920 ///\pre \c v should be reached but not processed. 921 Value currentDist(Node v) const { return (*_heap)[v]; } 867 922 868 923 ///@} … … 870 925 871 926 872 873 874 875 ///Default traits class of Dijkstra function. 876 877 ///Default traits class of Dijkstra function. 878 ///\tparam GR Digraph type. 879 ///\tparam LM Type of length map. 927 ///Default traits class of dijkstra() function. 928 929 ///Default traits class of dijkstra() function. 930 ///\tparam GR The type of the digraph. 931 ///\tparam LM The type of the length map. 880 932 template<class GR, class LM> 881 933 struct DijkstraWizardDefaultTraits 882 934 { 883 ///The digraph typethe algorithm runs on.935 ///The type of the digraph the algorithm runs on. 884 936 typedef GR Digraph; 885 937 ///The type of the map that stores the arc lengths. … … 888 940 ///It must meet the \ref concepts::ReadMap "ReadMap" concept. 889 941 typedef LM LengthMap; 890 // The type of the length of the arcs.942 ///The type of the length of the arcs. 891 943 typedef typename LM::Value Value; 944 892 945 /// Operation traits for Dijkstra algorithm. 893 946 894 /// It defines the used operation bythe algorithm.947 /// This class defines the operations that are used in the algorithm. 895 948 /// \see DijkstraDefaultOperationTraits 896 949 typedef DijkstraDefaultOperationTraits<Value> OperationTraits; 897 ///The heap type used by Dijkstra algorithm. 898 899 /// The cross reference type used by heap. 900 901 /// The cross reference type used by heap. 950 951 /// The cross reference type used by the heap. 952 953 /// The cross reference type used by the heap. 902 954 /// Usually it is \c Digraph::NodeMap<int>. 903 955 typedef typename Digraph::template NodeMap<int> HeapCrossRef; 904 ///Instantiates a HeapCrossRef.956 ///Instantiates a \ref HeapCrossRef. 905 957 906 958 ///This function instantiates a \ref HeapCrossRef. 907 /// \param Gis the digraph, to which we would like to define the959 /// \param g is the digraph, to which we would like to define the 908 960 /// HeapCrossRef. 909 961 /// \todo The digraph alone may be insufficient for the initialization 910 static HeapCrossRef *createHeapCrossRef(const GR &G)911 { 912 return new HeapCrossRef( G);913 } 914 915 ///The heap type used by Dijkstra algorithm.916 917 ///The heap type used by Dijkstra algorithm.962 static HeapCrossRef *createHeapCrossRef(const Digraph &g) 963 { 964 return new HeapCrossRef(g); 965 } 966 967 ///The heap type used by the Dijkstra algorithm. 968 969 ///The heap type used by the Dijkstra algorithm. 918 970 /// 919 971 ///\sa BinHeap 920 972 ///\sa Dijkstra 921 typedef BinHeap< typename LM::Value, typename GR::template NodeMap<int>,973 typedef BinHeap<Value, typename Digraph::template NodeMap<int>, 922 974 std::less<Value> > Heap; 923 975 924 static Heap *createHeap(HeapCrossRef& R) 925 { 926 return new Heap(R); 927 } 928 929 ///\brief The type of the map that stores the last 976 ///Instantiates a \ref Heap. 977 978 ///This function instantiates a \ref Heap. 979 /// \param r is the HeapCrossRef which is used. 980 static Heap *createHeap(HeapCrossRef& r) 981 { 982 return new Heap(r); 983 } 984 985 ///\brief The type of the map that stores the predecessor 930 986 ///arcs of the shortest paths. 931 987 /// 932 ///The type of the map that stores the last988 ///The type of the map that stores the predecessor 933 989 ///arcs of the shortest paths. 934 990 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 935 /// 936 typedef NullMap <typename GR::Node,typename GR::Arc> PredMap; 937 ///Instantiates a PredMap. 991 typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap; 992 ///Instantiates a \ref PredMap. 938 993 939 994 ///This function instantiates a \ref PredMap. 940 ///\param g is the digraph, to which we would like to define the PredMap. 941 ///\todo The digraph alone may be insufficient for the initialization 995 ///\param g is the digraph, to which we would like to define the 996 ///\ref PredMap. 997 ///\todo The digraph alone may be insufficient to initialize 942 998 #ifdef DOXYGEN 943 static PredMap *createPredMap(const GR&g)999 static PredMap *createPredMap(const Digraph &g) 944 1000 #else 945 static PredMap *createPredMap(const GR&)1001 static PredMap *createPredMap(const Digraph &) 946 1002 #endif 947 1003 { 948 1004 return new PredMap(); 949 1005 } 950 ///The type of the map that stores whether a nodes is processed. 951 952 ///The type of the map that stores whether a nodes is processed. 1006 1007 ///The type of the map that indicates which nodes are processed. 1008 1009 ///The type of the map that indicates which nodes are processed. 953 1010 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 954 1011 ///By default it is a NullMap. … … 957 1014 ///\todo named parameter to set this type, function to read and write. 958 1015 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 959 ///Instantiates a ProcessedMap.1016 ///Instantiates a \ref ProcessedMap. 960 1017 961 1018 ///This function instantiates a \ref ProcessedMap. 962 1019 ///\param g is the digraph, to which 963 ///we would like to define the \ref ProcessedMap 1020 ///we would like to define the \ref ProcessedMap. 964 1021 #ifdef DOXYGEN 965 static ProcessedMap *createProcessedMap(const GR&g)1022 static ProcessedMap *createProcessedMap(const Digraph &g) 966 1023 #else 967 static ProcessedMap *createProcessedMap(const GR&)1024 static ProcessedMap *createProcessedMap(const Digraph &) 968 1025 #endif 969 1026 { 970 1027 return new ProcessedMap(); 971 1028 } 972 ///The type of the map that stores the dists of the nodes. 973 974 ///The type of the map that stores the dists of the nodes. 1029 1030 ///The type of the map that stores the distances of the nodes. 1031 1032 ///The type of the map that stores the distances of the nodes. 975 1033 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 976 /// 977 typedef NullMap<typename Digraph::Node,typename LM::Value> DistMap; 978 ///Instantiates a DistMap. 1034 typedef NullMap<typename Digraph::Node,Value> DistMap; 1035 ///Instantiates a \ref DistMap. 979 1036 980 1037 ///This function instantiates a \ref DistMap. … … 982 1039 ///the \ref DistMap 983 1040 #ifdef DOXYGEN 984 static DistMap *createDistMap(const GR&g)1041 static DistMap *createDistMap(const Digraph &g) 985 1042 #else 986 static DistMap *createDistMap(const GR&)1043 static DistMap *createDistMap(const Digraph &) 987 1044 #endif 988 1045 { … … 991 1048 }; 992 1049 993 /// Default traits used by \ref DijkstraWizard1050 /// Default traits class used by \ref DijkstraWizard 994 1051 995 1052 /// To make it easier to use Dijkstra algorithm 996 /// we have created a wizard class.1053 /// we have created a wizard class. 997 1054 /// This \ref DijkstraWizard class needs default traits, 998 /// as well as the \ref Dijkstra class.1055 /// as well as the \ref Dijkstra class. 999 1056 /// The \ref DijkstraWizardBase is a class to be the default traits of the 1000 1057 /// \ref DijkstraWizard class. … … 1003 1060 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM> 1004 1061 { 1005 1006 1062 typedef DijkstraWizardDefaultTraits<GR,LM> Base; 1007 1063 protected: 1008 // / Type of the nodes in the digraph.1064 //The type of the nodes in the digraph. 1009 1065 typedef typename Base::Digraph::Node Node; 1010 1066 1011 // / Pointer to the underlying digraph.1067 //Pointer to the digraph the algorithm runs on. 1012 1068 void *_g; 1013 // /Pointer to the length map1069 //Pointer to the length map 1014 1070 void *_length; 1015 // /Pointer to the map of predecessors arcs.1071 //Pointer to the map of predecessors arcs. 1016 1072 void *_pred; 1017 // /Pointer to the map of distances.1073 //Pointer to the map of distances. 1018 1074 void *_dist; 1019 // /Pointer to the source node.1075 //Pointer to the source node. 1020 1076 Node _source; 1021 1077 1022 1078 public: 1023 1079 /// Constructor. 1024 1080 … … 1033 1089 /// listed in the parameters list. 1034 1090 /// Others are initiated to 0. 1035 /// \param g is the initial value of \ref _g1036 /// \param l is the initial value of \ref _length1037 /// \param s is the initial value of \ref _source1091 /// \param g The digraph the algorithm runs on. 1092 /// \param l The length map. 1093 /// \param s The source node. 1038 1094 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : 1039 1095 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), … … 1043 1099 }; 1044 1100 1045 /// A class to make the usage of Dijkstra algorithm easier 1046 1047 /// This class is created to make it easier to use Dijkstra algorithm. 1048 /// It uses the functions and features of the plain \ref Dijkstra, 1049 /// but it is much simpler to use it. 1101 /// Auxiliary class for the function type interface of Dijkstra algorithm. 1102 1103 /// This auxiliary class is created to implement the function type 1104 /// interface of \ref Dijkstra algorithm. It uses the functions and features 1105 /// of the plain \ref Dijkstra, but it is much simpler to use it. 1106 /// It should only be used through the \ref dijkstra() function, which makes 1107 /// it easier to use the algorithm. 1050 1108 /// 1051 1109 /// Simplicity means that the way to change the types defined … … 1056 1114 /// the original class by using the :: 1057 1115 /// operator. In the case of \ref DijkstraWizard only 1058 /// a function have to be called and it will1116 /// a function have to be called, and it will 1059 1117 /// return the needed class. 1060 1118 /// 1061 /// It does not have own \ref run method. When its \ref run method is called1062 /// i t initiates a plain \ref Dijkstra class, and calls the \ref1063 /// Dijkstra::runmethod of it.1119 /// It does not have own \ref run() method. When its \ref run() method 1120 /// is called, it initiates a plain \ref Dijkstra object, and calls the 1121 /// \ref Dijkstra::run() method of it. 1064 1122 template<class TR> 1065 1123 class DijkstraWizard : public TR … … 1067 1125 typedef TR Base; 1068 1126 1069 ///The type of the underlying digraph.1127 ///The type of the digraph the algorithm runs on. 1070 1128 typedef typename TR::Digraph Digraph; 1071 //\e 1129 1072 1130 typedef typename Digraph::Node Node; 1073 //\e1074 1131 typedef typename Digraph::NodeIt NodeIt; 1075 //\e1076 1132 typedef typename Digraph::Arc Arc; 1077 //\e1078 1133 typedef typename Digraph::OutArcIt OutArcIt; 1079 1134 … … 1082 1137 ///The type of the length of the arcs. 1083 1138 typedef typename LengthMap::Value Value; 1084 ///\brief The type of the map that stores the last1139 ///\brief The type of the map that stores the predecessor 1085 1140 ///arcs of the shortest paths. 1086 1141 typedef typename TR::PredMap PredMap; 1087 ///The type of the map that stores the dist s of the nodes.1142 ///The type of the map that stores the distances of the nodes. 1088 1143 typedef typename TR::DistMap DistMap; 1144 ///The type of the map that indicates which nodes are processed. 1145 typedef typename TR::ProcessedMap ProcessedMap; 1089 1146 ///The heap type used by the dijkstra algorithm. 1090 1147 typedef typename TR::Heap Heap; 1148 1091 1149 public: 1150 1092 1151 /// Constructor. 1093 1152 DijkstraWizard() : TR() {} … … 1105 1164 ~DijkstraWizard() {} 1106 1165 1107 ///Runs Dijkstra algorithm from a givennode.1108 1109 ///Runs Dijkstra algorithm from a givennode.1110 ///The node can be given by the \ref sourcefunction.1166 ///Runs Dijkstra algorithm from a source node. 1167 1168 ///Runs Dijkstra algorithm from a source node. 1169 ///The node can be given with the \ref source() function. 1111 1170 void run() 1112 1171 { … … 1130 1189 } 1131 1190 1191 /// Sets the source node, from which the Dijkstra algorithm runs. 1192 1193 /// Sets the source node, from which the Dijkstra algorithm runs. 1194 /// \param s is the source node. 1195 DijkstraWizard<TR> &source(Node s) 1196 { 1197 Base::_source=s; 1198 return *this; 1199 } 1200 1132 1201 template<class T> 1133 1202 struct DefPredMapBase : public Base { … … 1136 1205 DefPredMapBase(const TR &b) : TR(b) {} 1137 1206 }; 1138 1139 1207 ///\brief \ref named-templ-param "Named parameter" 1140 ///function for setting PredMap type 1141 /// 1142 /// \ref named-templ-param "Named parameter" 1143 ///function for setting PredMap type 1144 /// 1208 ///for setting \ref PredMap object. 1209 /// 1210 ///\ref named-templ-param "Named parameter" 1211 ///for setting \ref PredMap object. 1145 1212 template<class T> 1146 1213 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t) … … 1148 1215 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); 1149 1216 return DijkstraWizard<DefPredMapBase<T> >(*this); 1217 } 1218 1219 template<class T> 1220 struct DefProcessedMapBase : public Base { 1221 typedef T ProcessedMap; 1222 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; 1223 DefProcessedMapBase(const TR &b) : TR(b) {} 1224 }; 1225 ///\brief \ref named-templ-param "Named parameter" 1226 ///for setting \ref ProcessedMap object. 1227 /// 1228 /// \ref named-templ-param "Named parameter" 1229 ///for setting \ref ProcessedMap object. 1230 template<class T> 1231 DijkstraWizard<DefProcessedMapBase<T> > processedMap(const T &t) 1232 { 1233 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); 1234 return DijkstraWizard<DefProcessedMapBase<T> >(*this); 1150 1235 } 1151 1236 … … 1156 1241 DefDistMapBase(const TR &b) : TR(b) {} 1157 1242 }; 1158 1159 1243 ///\brief \ref named-templ-param "Named parameter" 1160 ///function for setting DistMap type 1161 /// 1162 /// \ref named-templ-param "Named parameter" 1163 ///function for setting DistMap type 1164 /// 1244 ///for setting \ref DistMap object. 1245 /// 1246 ///\ref named-templ-param "Named parameter" 1247 ///for setting \ref DistMap object. 1165 1248 template<class T> 1166 1249 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t) … … 1168 1251 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1169 1252 return DijkstraWizard<DefDistMapBase<T> >(*this); 1170 }1171 1172 /// Sets the source node, from which the Dijkstra algorithm runs.1173 1174 /// Sets the source node, from which the Dijkstra algorithm runs.1175 /// \param s is the source node.1176 DijkstraWizard<TR> &source(Node s)1177 {1178 Base::_source=s;1179 return *this;1180 1253 } 1181 1254
Note: See TracChangeset
for help on using the changeset viewer.