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