Changeset 247:f1158744a112 in lemon1.0
 Timestamp:
 08/04/08 22:00:36 (11 years ago)
 Branch:
 default
 Parents:
 246:7c67988fca07 (diff), 244:c30731a37f91 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Location:
 lemon
 Files:

 6 edited
Legend:
 Unmodified
 Added
 Removed

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