Changes in / [423:e22fc10ab6f1:424:69f33ef03334] in lemon
- Location:
- lemon
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r341 r421 52 52 ///Instantiates a PredMap. 53 53 54 ///This function instantiates a PredMap. 54 ///This function instantiates a PredMap. 55 55 ///\param g is the digraph, to which we would like to define the 56 56 ///PredMap. … … 81 81 ///The type of the map that indicates which nodes are reached. 82 82 83 ///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 83 ///The type of the map that indicates which nodes are reached. 84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 84 85 typedef typename Digraph::template NodeMap<bool> ReachedMap; 85 86 ///Instantiates a ReachedMap. … … 119 120 /// 120 121 ///\tparam GR The type of the digraph the algorithm runs on. 121 ///The default value is \ref ListDigraph. The value of GR is not used 122 ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits. 123 ///\tparam TR Traits class to set various data types used by the algorithm. 124 ///The default traits class is 125 ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>". 126 ///See \ref BfsDefaultTraits for the documentation of 127 ///a Bfs traits class. 122 ///The default type is \ref ListDigraph. 128 123 #ifdef DOXYGEN 129 124 template <typename GR, … … 151 146 typedef PredMapPath<Digraph, PredMap> Path; 152 147 153 ///The traits class.148 ///The \ref BfsDefaultTraits "traits class" of the algorithm. 154 149 typedef TR Traits; 155 150 … … 213 208 typedef Bfs Create; 214 209 215 ///\name Named template parameters210 ///\name Named Template Parameters 216 211 217 212 ///@{ … … 231 226 ///\ref named-templ-param "Named parameter" for setting 232 227 ///PredMap type. 228 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 233 229 template <class T> 234 230 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { … … 250 246 ///\ref named-templ-param "Named parameter" for setting 251 247 ///DistMap type. 248 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 252 249 template <class T> 253 250 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { … … 269 266 ///\ref named-templ-param "Named parameter" for setting 270 267 ///ReachedMap type. 268 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 271 269 template <class T> 272 270 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { … … 288 286 ///\ref named-templ-param "Named parameter" for setting 289 287 ///ProcessedMap type. 288 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 290 289 template <class T> 291 290 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { … … 340 339 341 340 ///Sets the map that stores the predecessor arcs. 342 ///If you don't use this function before calling \ref run(), 343 ///it will allocate one. The destructor deallocates this 344 ///automatically allocated map, of course. 341 ///If you don't use this function before calling \ref run(Node) "run()" 342 ///or \ref init(), an instance will be allocated automatically. 343 ///The destructor deallocates this automatically allocated map, 344 ///of course. 345 345 ///\return <tt> (*this) </tt> 346 346 Bfs &predMap(PredMap &m) … … 357 357 358 358 ///Sets the map that indicates which nodes are reached. 359 ///If you don't use this function before calling \ref run(), 360 ///it will allocate one. The destructor deallocates this 361 ///automatically allocated map, of course. 359 ///If you don't use this function before calling \ref run(Node) "run()" 360 ///or \ref init(), an instance will be allocated automatically. 361 ///The destructor deallocates this automatically allocated map, 362 ///of course. 362 363 ///\return <tt> (*this) </tt> 363 364 Bfs &reachedMap(ReachedMap &m) … … 374 375 375 376 ///Sets the map that indicates which nodes are processed. 376 ///If you don't use this function before calling \ref run(), 377 ///it will allocate one. The destructor deallocates this 378 ///automatically allocated map, of course. 377 ///If you don't use this function before calling \ref run(Node) "run()" 378 ///or \ref init(), an instance will be allocated automatically. 379 ///The destructor deallocates this automatically allocated map, 380 ///of course. 379 381 ///\return <tt> (*this) </tt> 380 382 Bfs &processedMap(ProcessedMap &m) … … 392 394 ///Sets the map that stores the distances of the nodes calculated by 393 395 ///the algorithm. 394 ///If you don't use this function before calling \ref run(), 395 ///it will allocate one. The destructor deallocates this 396 ///automatically allocated map, of course. 396 ///If you don't use this function before calling \ref run(Node) "run()" 397 ///or \ref init(), an instance will be allocated automatically. 398 ///The destructor deallocates this automatically allocated map, 399 ///of course. 397 400 ///\return <tt> (*this) </tt> 398 401 Bfs &distMap(DistMap &m) … … 408 411 public: 409 412 410 ///\name Execution control 411 ///The simplest way to execute the algorithm is to use 412 ///one of the member functions called \ref lemon::Bfs::run() "run()". 413 ///\n 414 ///If you need more control on the execution, first you must call 415 ///\ref lemon::Bfs::init() "init()", then you can add several source 416 ///nodes with \ref lemon::Bfs::addSource() "addSource()". 417 ///Finally \ref lemon::Bfs::start() "start()" will perform the 418 ///actual path computation. 413 ///\name Execution Control 414 ///The simplest way to execute the BFS algorithm is to use one of the 415 ///member functions called \ref run(Node) "run()".\n 416 ///If you need more control on the execution, first you have to call 417 ///\ref init(), then you can add several source nodes with 418 ///\ref addSource(). Finally the actual path computation can be 419 ///performed with one of the \ref start() functions. 419 420 420 421 ///@{ 421 422 423 ///\brief Initializes the internal data structures. 424 /// 422 425 ///Initializes the internal data structures. 423 424 ///Initializes the internal data structures.425 ///426 426 void init() 427 427 { … … 557 557 } 558 558 559 ///\brief Returns \c false if there are nodes 560 ///to be processed. 561 /// 562 ///Returns \c false if there are nodes 563 ///to be processed in the queue. 559 ///Returns \c false if there are nodes to be processed. 560 561 ///Returns \c false if there are nodes to be processed 562 ///in the queue. 564 563 bool emptyQueue() const { return _queue_tail==_queue_head; } 565 564 566 565 ///Returns the number of the nodes to be processed. 567 566 568 ///Returns the number of the nodes to be processed in the queue. 567 ///Returns the number of the nodes to be processed 568 ///in the queue. 569 569 int queueSize() const { return _queue_head-_queue_tail; } 570 570 … … 731 731 732 732 ///\name Query Functions 733 ///The result of the %BFS algorithm can be obtained using these733 ///The results of the BFS algorithm can be obtained using these 734 734 ///functions.\n 735 ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()736 /// "start()" must be calledbefore using them.735 ///Either \ref run(Node) "run()" or \ref start() should be called 736 ///before using them. 737 737 738 738 ///@{ … … 742 742 ///Returns the shortest path to a node. 743 743 /// 744 ///\warning \c t should be reach ablefrom the root(s).745 /// 746 ///\pre Either \ref run( ) or \ref start() must be called before747 /// using this function.744 ///\warning \c t should be reached from the root(s). 745 /// 746 ///\pre Either \ref run(Node) "run()" or \ref init() 747 ///must be called before using this function. 748 748 Path path(Node t) const { return Path(*G, *_pred, t); } 749 749 … … 752 752 ///Returns the distance of a node from the root(s). 753 753 /// 754 ///\warning If node \c v is not reach ablefrom the root(s), then754 ///\warning If node \c v is not reached from the root(s), then 755 755 ///the return value of this function is undefined. 756 756 /// 757 ///\pre Either \ref run( ) or \ref start() must be called before758 /// using this function.757 ///\pre Either \ref run(Node) "run()" or \ref init() 758 ///must be called before using this function. 759 759 int dist(Node v) const { return (*_dist)[v]; } 760 760 … … 763 763 ///This function returns the 'previous arc' of the shortest path 764 764 ///tree for the node \c v, i.e. it returns the last arc of a 765 ///shortest path from the root(s)to \c v. It is \c INVALID if \c v766 ///is not reach ablefrom the root(s) or if \c v is a root.765 ///shortest path from a root to \c v. It is \c INVALID if \c v 766 ///is not reached from the root(s) or if \c v is a root. 767 767 /// 768 768 ///The shortest path tree used here is equal to the shortest path 769 769 ///tree used in \ref predNode(). 770 770 /// 771 ///\pre Either \ref run( ) or \ref start() must be called before772 /// using this function.771 ///\pre Either \ref run(Node) "run()" or \ref init() 772 ///must be called before using this function. 773 773 Arc predArc(Node v) const { return (*_pred)[v];} 774 774 … … 777 777 ///This function returns the 'previous node' of the shortest path 778 778 ///tree for the node \c v, i.e. it returns the last but one node 779 ///from a shortest path from the root(s)to \c v. It is \c INVALID780 ///if \c v is not reach ablefrom the root(s) or if \c v is a root.779 ///from a shortest path from a root to \c v. It is \c INVALID 780 ///if \c v is not reached from the root(s) or if \c v is a root. 781 781 /// 782 782 ///The shortest path tree used here is equal to the shortest path 783 783 ///tree used in \ref predArc(). 784 784 /// 785 ///\pre Either \ref run( ) or \ref start() must be called before786 /// using this function.785 ///\pre Either \ref run(Node) "run()" or \ref init() 786 ///must be called before using this function. 787 787 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 788 788 G->source((*_pred)[v]); } … … 794 794 ///of the nodes calculated by the algorithm. 795 795 /// 796 ///\pre Either \ref run( )or \ref init()796 ///\pre Either \ref run(Node) "run()" or \ref init() 797 797 ///must be called before using this function. 798 798 const DistMap &distMap() const { return *_dist;} … … 804 804 ///arcs, which form the shortest path tree. 805 805 /// 806 ///\pre Either \ref run( )or \ref init()806 ///\pre Either \ref run(Node) "run()" or \ref init() 807 807 ///must be called before using this function. 808 808 const PredMap &predMap() const { return *_pred;} 809 809 810 ///Checks if a node is reachable from the root(s). 811 812 ///Returns \c true if \c v is reachable from the root(s). 813 ///\pre Either \ref run() or \ref start() 810 ///Checks if a node is reached from the root(s). 811 812 ///Returns \c true if \c v is reached from the root(s). 813 /// 814 ///\pre Either \ref run(Node) "run()" or \ref init() 814 815 ///must be called before using this function. 815 816 bool reached(Node v) const { return (*_reached)[v]; } … … 957 958 /// This auxiliary class is created to implement the 958 959 /// \ref bfs() "function-type interface" of \ref Bfs algorithm. 959 /// It does not have own \ref run( ) method, it uses the functions960 /// and features of the plain \ref Bfs.960 /// It does not have own \ref run(Node) "run()" method, it uses the 961 /// functions and features of the plain \ref Bfs. 961 962 /// 962 963 /// This class should only be used through the \ref bfs() function, … … 1178 1179 /// bool reached = bfs(g).path(p).dist(d).run(s,t); 1179 1180 ///\endcode 1180 ///\warning Don't forget to put the \ref BfsWizard::run( ) "run()"1181 ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()" 1181 1182 ///to the end of the parameter list. 1182 1183 ///\sa BfsWizard … … 1364 1365 typedef BfsVisit Create; 1365 1366 1366 /// \name Named template parameters1367 /// \name Named Template Parameters 1367 1368 1368 1369 ///@{ … … 1406 1407 /// 1407 1408 /// Sets the map that indicates which nodes are reached. 1408 /// If you don't use this function before calling \ref run(), 1409 /// it will allocate one. The destructor deallocates this 1410 /// automatically allocated map, of course. 1409 /// If you don't use this function before calling \ref run(Node) "run()" 1410 /// or \ref init(), an instance will be allocated automatically. 1411 /// The destructor deallocates this automatically allocated map, 1412 /// of course. 1411 1413 /// \return <tt> (*this) </tt> 1412 1414 BfsVisit &reachedMap(ReachedMap &m) { … … 1421 1423 public: 1422 1424 1423 /// \name Execution control 1424 /// The simplest way to execute the algorithm is to use 1425 /// one of the member functions called \ref lemon::BfsVisit::run() 1426 /// "run()". 1427 /// \n 1428 /// If you need more control on the execution, first you must call 1429 /// \ref lemon::BfsVisit::init() "init()", then you can add several 1430 /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()". 1431 /// Finally \ref lemon::BfsVisit::start() "start()" will perform the 1432 /// actual path computation. 1425 /// \name Execution Control 1426 /// The simplest way to execute the BFS algorithm is to use one of the 1427 /// member functions called \ref run(Node) "run()".\n 1428 /// If you need more control on the execution, first you have to call 1429 /// \ref init(), then you can add several source nodes with 1430 /// \ref addSource(). Finally the actual path computation can be 1431 /// performed with one of the \ref start() functions. 1433 1432 1434 1433 /// @{ … … 1730 1729 1731 1730 /// \name Query Functions 1732 /// The result of the %BFS algorithm can be obtained using these1731 /// The results of the BFS algorithm can be obtained using these 1733 1732 /// functions.\n 1734 /// Either \ref lemon::BfsVisit::run() "run()" or1735 /// \ref lemon::BfsVisit::start() "start()" must be called before1736 /// using them. 1733 /// Either \ref run(Node) "run()" or \ref start() should be called 1734 /// before using them. 1735 1737 1736 ///@{ 1738 1737 1739 /// \brief Checks if a node is reachable from the root(s). 1740 /// 1741 /// Returns \c true if \c v is reachable from the root(s). 1742 /// \pre Either \ref run() or \ref start() 1738 /// \brief Checks if a node is reached from the root(s). 1739 /// 1740 /// Returns \c true if \c v is reached from the root(s). 1741 /// 1742 /// \pre Either \ref run(Node) "run()" or \ref init() 1743 1743 /// must be called before using this function. 1744 1744 bool reached(Node v) { return (*_reached)[v]; } -
lemon/dfs.h
r319 r421 120 120 /// 121 121 ///\tparam GR The type of the digraph the algorithm runs on. 122 ///The default value is \ref ListDigraph. The value of GR is not used 123 ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits. 124 ///\tparam TR Traits class to set various data types used by the algorithm. 125 ///The default traits class is 126 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>". 127 ///See \ref DfsDefaultTraits for the documentation of 128 ///a Dfs traits class. 122 ///The default type is \ref ListDigraph. 129 123 #ifdef DOXYGEN 130 124 template <typename GR, … … 152 146 typedef PredMapPath<Digraph, PredMap> Path; 153 147 154 ///The traits class.148 ///The \ref DfsDefaultTraits "traits class" of the algorithm. 155 149 typedef TR Traits; 156 150 … … 231 225 ///\ref named-templ-param "Named parameter" for setting 232 226 ///PredMap type. 227 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 233 228 template <class T> 234 229 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > { … … 250 245 ///\ref named-templ-param "Named parameter" for setting 251 246 ///DistMap type. 247 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 252 248 template <class T> 253 249 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > { … … 269 265 ///\ref named-templ-param "Named parameter" for setting 270 266 ///ReachedMap type. 267 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 271 268 template <class T> 272 269 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > { … … 288 285 ///\ref named-templ-param "Named parameter" for setting 289 286 ///ProcessedMap type. 287 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 290 288 template <class T> 291 289 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > { … … 339 337 340 338 ///Sets the map that stores the predecessor arcs. 341 ///If you don't use this function before calling \ref run(), 342 ///it will allocate one. The destructor deallocates this 343 ///automatically allocated map, of course. 339 ///If you don't use this function before calling \ref run(Node) "run()" 340 ///or \ref init(), an instance will be allocated automatically. 341 ///The destructor deallocates this automatically allocated map, 342 ///of course. 344 343 ///\return <tt> (*this) </tt> 345 344 Dfs &predMap(PredMap &m) … … 356 355 357 356 ///Sets the map that indicates which nodes are reached. 358 ///If you don't use this function before calling \ref run(), 359 ///it will allocate one. The destructor deallocates this 360 ///automatically allocated map, of course. 357 ///If you don't use this function before calling \ref run(Node) "run()" 358 ///or \ref init(), an instance will be allocated automatically. 359 ///The destructor deallocates this automatically allocated map, 360 ///of course. 361 361 ///\return <tt> (*this) </tt> 362 362 Dfs &reachedMap(ReachedMap &m) … … 373 373 374 374 ///Sets the map that indicates which nodes are processed. 375 ///If you don't use this function before calling \ref run(), 376 ///it will allocate one. The destructor deallocates this 377 ///automatically allocated map, of course. 375 ///If you don't use this function before calling \ref run(Node) "run()" 376 ///or \ref init(), an instance will be allocated automatically. 377 ///The destructor deallocates this automatically allocated map, 378 ///of course. 378 379 ///\return <tt> (*this) </tt> 379 380 Dfs &processedMap(ProcessedMap &m) … … 391 392 ///Sets the map that stores the distances of the nodes calculated by 392 393 ///the algorithm. 393 ///If you don't use this function before calling \ref run(), 394 ///it will allocate one. The destructor deallocates this 395 ///automatically allocated map, of course. 394 ///If you don't use this function before calling \ref run(Node) "run()" 395 ///or \ref init(), an instance will be allocated automatically. 396 ///The destructor deallocates this automatically allocated map, 397 ///of course. 396 398 ///\return <tt> (*this) </tt> 397 399 Dfs &distMap(DistMap &m) … … 407 409 public: 408 410 409 ///\name Execution control 410 ///The simplest way to execute the algorithm is to use 411 ///one of the member functions called \ref lemon::Dfs::run() "run()". 412 ///\n 413 ///If you need more control on the execution, first you must call 414 ///\ref lemon::Dfs::init() "init()", then you can add a source node 415 ///with \ref lemon::Dfs::addSource() "addSource()". 416 ///Finally \ref lemon::Dfs::start() "start()" will perform the 417 ///actual path computation. 411 ///\name Execution Control 412 ///The simplest way to execute the DFS algorithm is to use one of the 413 ///member functions called \ref run(Node) "run()".\n 414 ///If you need more control on the execution, first you have to call 415 ///\ref init(), then you can add a source node with \ref addSource() 416 ///and perform the actual computation with \ref start(). 417 ///This procedure can be repeated if there are nodes that have not 418 ///been reached. 418 419 419 420 ///@{ 420 421 422 ///\brief Initializes the internal data structures. 423 /// 421 424 ///Initializes the internal data structures. 422 423 ///Initializes the internal data structures.424 ///425 425 void init() 426 426 { … … 439 439 ///Adds a new source node to the set of nodes to be processed. 440 440 /// 441 ///\pre The stack must be empty. (Otherwise the algorithm gives 442 ///false results.) 443 /// 444 ///\warning Distances will be wrong (or at least strange) in case of 445 ///multiple sources. 441 ///\pre The stack must be empty. Otherwise the algorithm gives 442 ///wrong results. (One of the outgoing arcs of all the source nodes 443 ///except for the last one will not be visited and distances will 444 ///also be wrong.) 446 445 void addSource(Node s) 447 446 { … … 507 506 } 508 507 509 ///\brief Returns \c false if there are nodes 510 ///to be processed. 511 /// 512 ///Returns \c false if there are nodes 513 ///to be processed in the queue (stack). 508 ///Returns \c false if there are nodes to be processed. 509 510 ///Returns \c false if there are nodes to be processed 511 ///in the queue (stack). 514 512 bool emptyQueue() const { return _stack_head<0; } 515 513 516 514 ///Returns the number of the nodes to be processed. 517 515 518 ///Returns the number of the nodes to be processed in the queue (stack). 516 ///Returns the number of the nodes to be processed 517 ///in the queue (stack). 519 518 int queueSize() const { return _stack_head+1; } 520 519 … … 638 637 /// 639 638 ///The algorithm computes 640 ///- the %DFS tree ,641 ///- the distance of each node from the root in the %DFS tree.639 ///- the %DFS tree (forest), 640 ///- the distance of each node from the root(s) in the %DFS tree. 642 641 /// 643 642 ///\note <tt>d.run()</tt> is just a shortcut of the following code. … … 664 663 665 664 ///\name Query Functions 666 ///The result of the %DFS algorithm can be obtained using these665 ///The results of the DFS algorithm can be obtained using these 667 666 ///functions.\n 668 ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()669 /// "start()" must be calledbefore using them.667 ///Either \ref run(Node) "run()" or \ref start() should be called 668 ///before using them. 670 669 671 670 ///@{ … … 675 674 ///Returns the DFS path to a node. 676 675 /// 677 ///\warning \c t should be reach able from the root.678 /// 679 ///\pre Either \ref run( ) or \ref start() must be called before680 /// using this function.676 ///\warning \c t should be reached from the root(s). 677 /// 678 ///\pre Either \ref run(Node) "run()" or \ref init() 679 ///must be called before using this function. 681 680 Path path(Node t) const { return Path(*G, *_pred, t); } 682 681 683 ///The distance of a node from the root .684 685 ///Returns the distance of a node from the root .686 /// 687 ///\warning If node \c v is not reach able from the root, then682 ///The distance of a node from the root(s). 683 684 ///Returns the distance of a node from the root(s). 685 /// 686 ///\warning If node \c v is not reached from the root(s), then 688 687 ///the return value of this function is undefined. 689 688 /// 690 ///\pre Either \ref run( ) or \ref start() must be called before691 /// using this function.689 ///\pre Either \ref run(Node) "run()" or \ref init() 690 ///must be called before using this function. 692 691 int dist(Node v) const { return (*_dist)[v]; } 693 692 … … 695 694 696 695 ///This function returns the 'previous arc' of the %DFS tree for the 697 ///node \c v, i.e. it returns the last arc of a %DFS path from the698 ///root to \c v. It is \c INVALID 699 /// if \c v is not reachable from theroot(s) or if \c v is a root.696 ///node \c v, i.e. it returns the last arc of a %DFS path from a 697 ///root to \c v. It is \c INVALID if \c v is not reached from the 698 ///root(s) or if \c v is a root. 700 699 /// 701 700 ///The %DFS tree used here is equal to the %DFS tree used in 702 701 ///\ref predNode(). 703 702 /// 704 ///\pre Either \ref run( ) or \ref start() must be called before using705 /// this function.703 ///\pre Either \ref run(Node) "run()" or \ref init() 704 ///must be called before using this function. 706 705 Arc predArc(Node v) const { return (*_pred)[v];} 707 706 … … 710 709 ///This function returns the 'previous node' of the %DFS 711 710 ///tree for the node \c v, i.e. it returns the last but one node 712 ///from a %DFS path from theroot to \c v. It is \c INVALID713 ///if \c v is not reach ablefrom the root(s) or if \c v is a root.711 ///from a %DFS path from a root to \c v. It is \c INVALID 712 ///if \c v is not reached from the root(s) or if \c v is a root. 714 713 /// 715 714 ///The %DFS tree used here is equal to the %DFS tree used in 716 715 ///\ref predArc(). 717 716 /// 718 ///\pre Either \ref run( ) or \ref start() must be called before719 /// using this function.717 ///\pre Either \ref run(Node) "run()" or \ref init() 718 ///must be called before using this function. 720 719 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 721 720 G->source((*_pred)[v]); } … … 727 726 ///distances of the nodes calculated by the algorithm. 728 727 /// 729 ///\pre Either \ref run( )or \ref init()728 ///\pre Either \ref run(Node) "run()" or \ref init() 730 729 ///must be called before using this function. 731 730 const DistMap &distMap() const { return *_dist;} … … 737 736 ///arcs, which form the DFS tree. 738 737 /// 739 ///\pre Either \ref run( )or \ref init()738 ///\pre Either \ref run(Node) "run()" or \ref init() 740 739 ///must be called before using this function. 741 740 const PredMap &predMap() const { return *_pred;} 742 741 743 ///Checks if a node is reachable from the root(s). 744 745 ///Returns \c true if \c v is reachable from the root(s). 746 ///\pre Either \ref run() or \ref start() 742 ///Checks if a node is reached from the root(s). 743 744 ///Returns \c true if \c v is reached from the root(s). 745 /// 746 ///\pre Either \ref run(Node) "run()" or \ref init() 747 747 ///must be called before using this function. 748 748 bool reached(Node v) const { return (*_reached)[v]; } … … 890 890 /// This auxiliary class is created to implement the 891 891 /// \ref dfs() "function-type interface" of \ref Dfs algorithm. 892 /// It does not have own \ref run( ) method, it uses the functions893 /// and features of the plain \ref Dfs.892 /// It does not have own \ref run(Node) "run()" method, it uses the 893 /// functions and features of the plain \ref Dfs. 894 894 /// 895 895 /// This class should only be used through the \ref dfs() function, … … 1111 1111 /// bool reached = dfs(g).path(p).dist(d).run(s,t); 1112 1112 ///\endcode 1113 1114 ///\warning Don't forget to put the \ref DfsWizard::run() "run()" 1113 ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()" 1115 1114 ///to the end of the parameter list. 1116 1115 ///\sa DfsWizard … … 1310 1309 typedef DfsVisit Create; 1311 1310 1312 /// \name Named template parameters1311 /// \name Named Template Parameters 1313 1312 1314 1313 ///@{ … … 1352 1351 /// 1353 1352 /// Sets the map that indicates which nodes are reached. 1354 /// If you don't use this function before calling \ref run(), 1355 /// it will allocate one. The destructor deallocates this 1356 /// automatically allocated map, of course. 1353 /// If you don't use this function before calling \ref run(Node) "run()" 1354 /// or \ref init(), an instance will be allocated automatically. 1355 /// The destructor deallocates this automatically allocated map, 1356 /// of course. 1357 1357 /// \return <tt> (*this) </tt> 1358 1358 DfsVisit &reachedMap(ReachedMap &m) { … … 1367 1367 public: 1368 1368 1369 /// \name Execution control 1370 /// The simplest way to execute the algorithm is to use 1371 /// one of the member functions called \ref lemon::DfsVisit::run() 1372 /// "run()". 1373 /// \n 1374 /// If you need more control on the execution, first you must call 1375 /// \ref lemon::DfsVisit::init() "init()", then you can add several 1376 /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()". 1377 /// Finally \ref lemon::DfsVisit::start() "start()" will perform the 1378 /// actual path computation. 1369 /// \name Execution Control 1370 /// The simplest way to execute the DFS algorithm is to use one of the 1371 /// member functions called \ref run(Node) "run()".\n 1372 /// If you need more control on the execution, first you have to call 1373 /// \ref init(), then you can add a source node with \ref addSource() 1374 /// and perform the actual computation with \ref start(). 1375 /// This procedure can be repeated if there are nodes that have not 1376 /// been reached. 1379 1377 1380 1378 /// @{ … … 1392 1390 } 1393 1391 1394 ///Adds a new source node. 1395 1396 ///Adds a new source node to the set of nodes to be processed. 1397 /// 1398 ///\pre The stack must be empty. (Otherwise the algorithm gives 1399 ///false results.) 1400 /// 1401 ///\warning Distances will be wrong (or at least strange) in case of 1402 ///multiple sources. 1392 /// \brief Adds a new source node. 1393 /// 1394 /// Adds a new source node to the set of nodes to be processed. 1395 /// 1396 /// \pre The stack must be empty. Otherwise the algorithm gives 1397 /// wrong results. (One of the outgoing arcs of all the source nodes 1398 /// except for the last one will not be visited and distances will 1399 /// also be wrong.) 1403 1400 void addSource(Node s) 1404 1401 { … … 1590 1587 /// 1591 1588 /// The algorithm computes 1592 /// - the %DFS tree ,1593 /// - the distance of each node from the root in the %DFS tree.1589 /// - the %DFS tree (forest), 1590 /// - the distance of each node from the root(s) in the %DFS tree. 1594 1591 /// 1595 1592 /// \note <tt>d.run()</tt> is just a shortcut of the following code. … … 1616 1613 1617 1614 /// \name Query Functions 1618 /// The result of the %DFS algorithm can be obtained using these1615 /// The results of the DFS algorithm can be obtained using these 1619 1616 /// functions.\n 1620 /// Either \ref lemon::DfsVisit::run() "run()" or1621 /// \ref lemon::DfsVisit::start() "start()" must be called before1622 /// using them. 1617 /// Either \ref run(Node) "run()" or \ref start() should be called 1618 /// before using them. 1619 1623 1620 ///@{ 1624 1621 1625 /// \brief Checks if a node is reachable from the root(s). 1626 /// 1627 /// Returns \c true if \c v is reachable from the root(s). 1628 /// \pre Either \ref run() or \ref start() 1622 /// \brief Checks if a node is reached from the root(s). 1623 /// 1624 /// Returns \c true if \c v is reached from the root(s). 1625 /// 1626 /// \pre Either \ref run(Node) "run()" or \ref init() 1629 1627 /// must be called before using this function. 1630 1628 bool reached(Node v) { return (*_reached)[v]; } -
lemon/dijkstra.h
r412 r424 180 180 /// 181 181 ///\tparam GR The type of the digraph the algorithm runs on. 182 ///The default value is \ref ListDigraph. 183 ///The value of GR is not used directly by \ref Dijkstra, it is only 184 ///passed to \ref DijkstraDefaultTraits. 185 ///\tparam LM A readable arc map that determines the lengths of the 186 ///arcs. It is read once for each arc, so the map may involve in 182 ///The default type is \ref ListDigraph. 183 ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies 184 ///the lengths of the arcs. 185 ///It is read once for each arc, so the map may involve in 187 186 ///relatively time consuming process to compute the arc lengths if 188 187 ///it is necessary. The default map type is \ref 189 ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>". 190 ///The value of LM is not used directly by \ref Dijkstra, it is only 191 ///passed to \ref DijkstraDefaultTraits. 192 ///\tparam TR Traits class to set various data types used by the algorithm. 193 ///The default traits class is \ref DijkstraDefaultTraits 194 ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits 195 ///for the documentation of a Dijkstra traits class. 188 ///concepts::Digraph::ArcMap "GR::ArcMap<int>". 196 189 #ifdef DOXYGEN 197 190 template <typename GR, typename LM, typename TR> … … 227 220 typedef typename TR::OperationTraits OperationTraits; 228 221 229 ///The traits class.222 ///The \ref DijkstraDefaultTraits "traits class" of the algorithm. 230 223 typedef TR Traits; 231 224 … … 309 302 ///\ref named-templ-param "Named parameter" for setting 310 303 ///PredMap type. 304 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 311 305 template <class T> 312 306 struct SetPredMap … … 329 323 ///\ref named-templ-param "Named parameter" for setting 330 324 ///DistMap type. 325 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 331 326 template <class T> 332 327 struct SetDistMap … … 349 344 ///\ref named-templ-param "Named parameter" for setting 350 345 ///ProcessedMap type. 346 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 351 347 template <class T> 352 348 struct SetProcessedMap … … 389 385 }; 390 386 ///\brief \ref named-templ-param "Named parameter" for setting 391 ///heap and cross reference type 387 ///heap and cross reference types 392 388 /// 393 389 ///\ref named-templ-param "Named parameter" for setting heap and cross 394 ///reference type. 390 ///reference types. If this named parameter is used, then external 391 ///heap and cross reference objects must be passed to the algorithm 392 ///using the \ref heap() function before calling \ref run(Node) "run()" 393 ///or \ref init(). 394 ///\sa SetStandardHeap 395 395 template <class H, class CR = typename Digraph::template NodeMap<int> > 396 396 struct SetHeap … … 412 412 }; 413 413 ///\brief \ref named-templ-param "Named parameter" for setting 414 ///heap and cross reference type with automatic allocation414 ///heap and cross reference types with automatic allocation 415 415 /// 416 416 ///\ref named-templ-param "Named parameter" for setting heap and cross 417 ///reference type. It can allocate the heap and the cross reference 418 ///object if the cross reference's constructor waits for the digraph as 419 ///parameter and the heap's constructor waits for the cross reference. 417 ///reference types with automatic allocation. 418 ///They should have standard constructor interfaces to be able to 419 ///automatically created by the algorithm (i.e. the digraph should be 420 ///passed to the constructor of the cross reference and the cross 421 ///reference should be passed to the constructor of the heap). 422 ///However external heap and cross reference objects could also be 423 ///passed to the algorithm using the \ref heap() function before 424 ///calling \ref run(Node) "run()" or \ref init(). 425 ///\sa SetHeap 420 426 template <class H, class CR = typename Digraph::template NodeMap<int> > 421 427 struct SetStandardHeap … … 487 493 488 494 ///Sets the map that stores the predecessor arcs. 489 ///If you don't use this function before calling \ref run(), 490 ///it will allocate one. The destructor deallocates this 491 ///automatically allocated map, of course. 495 ///If you don't use this function before calling \ref run(Node) "run()" 496 ///or \ref init(), an instance will be allocated automatically. 497 ///The destructor deallocates this automatically allocated map, 498 ///of course. 492 499 ///\return <tt> (*this) </tt> 493 500 Dijkstra &predMap(PredMap &m) … … 504 511 505 512 ///Sets the map that indicates which nodes are processed. 506 ///If you don't use this function before calling \ref run(), 507 ///it will allocate one. The destructor deallocates this 508 ///automatically allocated map, of course. 513 ///If you don't use this function before calling \ref run(Node) "run()" 514 ///or \ref init(), an instance will be allocated automatically. 515 ///The destructor deallocates this automatically allocated map, 516 ///of course. 509 517 ///\return <tt> (*this) </tt> 510 518 Dijkstra &processedMap(ProcessedMap &m) … … 522 530 ///Sets the map that stores the distances of the nodes calculated by the 523 531 ///algorithm. 524 ///If you don't use this function before calling \ref run(), 525 ///it will allocate one. The destructor deallocates this 526 ///automatically allocated map, of course. 532 ///If you don't use this function before calling \ref run(Node) "run()" 533 ///or \ref init(), an instance will be allocated automatically. 534 ///The destructor deallocates this automatically allocated map, 535 ///of course. 527 536 ///\return <tt> (*this) </tt> 528 537 Dijkstra &distMap(DistMap &m) … … 539 548 540 549 ///Sets the heap and the cross reference used by algorithm. 541 ///If you don't use this function before calling \ref run(), 542 ///it will allocate one. The destructor deallocates this 543 ///automatically allocated heap and cross reference, of course. 550 ///If you don't use this function before calling \ref run(Node) "run()" 551 ///or \ref init(), heap and cross reference instances will be 552 ///allocated automatically. 553 ///The destructor deallocates these automatically allocated objects, 554 ///of course. 544 555 ///\return <tt> (*this) </tt> 545 556 Dijkstra &heap(Heap& hp, HeapCrossRef &cr) … … 568 579 public: 569 580 570 ///\name Execution control 571 ///The simplest way to execute the algorithm is to use one of the 572 ///member functions called \ref lemon::Dijkstra::run() "run()". 573 ///\n 574 ///If you need more control on the execution, first you must call 575 ///\ref lemon::Dijkstra::init() "init()", then you can add several 576 ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()". 577 ///Finally \ref lemon::Dijkstra::start() "start()" will perform the 578 ///actual path computation. 581 ///\name Execution Control 582 ///The simplest way to execute the %Dijkstra algorithm is to use 583 ///one of the member functions called \ref run(Node) "run()".\n 584 ///If you need more control on the execution, first you have to call 585 ///\ref init(), then you can add several source nodes with 586 ///\ref addSource(). Finally the actual path computation can be 587 ///performed with one of the \ref start() functions. 579 588 580 589 ///@{ 581 590 591 ///\brief Initializes the internal data structures. 592 /// 582 593 ///Initializes the internal data structures. 583 584 ///Initializes the internal data structures.585 ///586 594 void init() 587 595 { … … 659 667 } 660 668 661 ///\brief Returns \c false if there are nodes 662 ///to be processed. 663 /// 664 ///Returns \c false if there are nodes 665 ///to be processed in the priority heap. 669 ///Returns \c false if there are nodes to be processed. 670 671 ///Returns \c false if there are nodes to be processed 672 ///in the priority heap. 666 673 bool emptyQueue() const { return _heap->empty(); } 667 674 668 ///Returns the number of the nodes to be processed in the priority heap669 670 ///Returns the number of the nodes to be processed in the priority heap.671 /// 675 ///Returns the number of the nodes to be processed. 676 677 ///Returns the number of the nodes to be processed 678 ///in the priority heap. 672 679 int queueSize() const { return _heap->size(); } 673 680 … … 790 797 791 798 ///\name Query Functions 792 ///The result of the %Dijkstra algorithm can be obtained using these799 ///The results of the %Dijkstra algorithm can be obtained using these 793 800 ///functions.\n 794 ///Either \ref lemon::Dijkstra::run() "run()" or 795 ///\ref lemon::Dijkstra::start() "start()" must be called before 796 ///using them. 801 ///Either \ref run(Node) "run()" or \ref start() should be called 802 ///before using them. 797 803 798 804 ///@{ … … 802 808 ///Returns the shortest path to a node. 803 809 /// 804 ///\warning \c t should be reach ablefrom the root(s).805 /// 806 ///\pre Either \ref run( ) or \ref start() must be called before807 /// using this function.810 ///\warning \c t should be reached from the root(s). 811 /// 812 ///\pre Either \ref run(Node) "run()" or \ref init() 813 ///must be called before using this function. 808 814 Path path(Node t) const { return Path(*G, *_pred, t); } 809 815 … … 812 818 ///Returns the distance of a node from the root(s). 813 819 /// 814 ///\warning If node \c v is not reach ablefrom the root(s), then820 ///\warning If node \c v is not reached from the root(s), then 815 821 ///the return value of this function is undefined. 816 822 /// 817 ///\pre Either \ref run( ) or \ref start() must be called before818 /// using this function.823 ///\pre Either \ref run(Node) "run()" or \ref init() 824 ///must be called before using this function. 819 825 Value dist(Node v) const { return (*_dist)[v]; } 820 826 … … 823 829 ///This function returns the 'previous arc' of the shortest path 824 830 ///tree for the node \c v, i.e. it returns the last arc of a 825 ///shortest path from the root(s)to \c v. It is \c INVALID if \c v826 ///is not reach ablefrom the root(s) or if \c v is a root.831 ///shortest path from a root to \c v. It is \c INVALID if \c v 832 ///is not reached from the root(s) or if \c v is a root. 827 833 /// 828 834 ///The shortest path tree used here is equal to the shortest path 829 835 ///tree used in \ref predNode(). 830 836 /// 831 ///\pre Either \ref run( ) or \ref start() must be called before832 /// using this function.837 ///\pre Either \ref run(Node) "run()" or \ref init() 838 ///must be called before using this function. 833 839 Arc predArc(Node v) const { return (*_pred)[v]; } 834 840 … … 837 843 ///This function returns the 'previous node' of the shortest path 838 844 ///tree for the node \c v, i.e. it returns the last but one node 839 ///from a shortest path from the root(s)to \c v. It is \c INVALID840 ///if \c v is not reach ablefrom the root(s) or if \c v is a root.845 ///from a shortest path from a root to \c v. It is \c INVALID 846 ///if \c v is not reached from the root(s) or if \c v is a root. 841 847 /// 842 848 ///The shortest path tree used here is equal to the shortest path 843 849 ///tree used in \ref predArc(). 844 850 /// 845 ///\pre Either \ref run( ) or \ref start() must be called before846 /// using this function.851 ///\pre Either \ref run(Node) "run()" or \ref init() 852 ///must be called before using this function. 847 853 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 848 854 G->source((*_pred)[v]); } … … 854 860 ///of the nodes calculated by the algorithm. 855 861 /// 856 ///\pre Either \ref run( )or \ref init()862 ///\pre Either \ref run(Node) "run()" or \ref init() 857 863 ///must be called before using this function. 858 864 const DistMap &distMap() const { return *_dist;} … … 864 870 ///arcs, which form the shortest path tree. 865 871 /// 866 ///\pre Either \ref run( )or \ref init()872 ///\pre Either \ref run(Node) "run()" or \ref init() 867 873 ///must be called before using this function. 868 874 const PredMap &predMap() const { return *_pred;} 869 875 870 ///Checks if a node is reachable from the root(s). 871 872 ///Returns \c true if \c v is reachable from the root(s). 873 ///\pre Either \ref run() or \ref start() 876 ///Checks if a node is reached from the root(s). 877 878 ///Returns \c true if \c v is reached from the root(s). 879 /// 880 ///\pre Either \ref run(Node) "run()" or \ref init() 874 881 ///must be called before using this function. 875 882 bool reached(Node v) const { return (*_heap_cross_ref)[v] != … … 880 887 ///Returns \c true if \c v is processed, i.e. the shortest 881 888 ///path to \c v has already found. 882 ///\pre Either \ref run() or \ref init() 889 /// 890 ///\pre Either \ref run(Node) "run()" or \ref init() 883 891 ///must be called before using this function. 884 892 bool processed(Node v) const { return (*_heap_cross_ref)[v] == … … 889 897 ///Returns the current distance of a node from the root(s). 890 898 ///It may be decreased in the following processes. 891 ///\pre Either \ref run() or \ref init() 899 /// 900 ///\pre Either \ref run(Node) "run()" or \ref init() 892 901 ///must be called before using this function and 893 902 ///node \c v must be reached but not necessarily processed. … … 1072 1081 /// This auxiliary class is created to implement the 1073 1082 /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm. 1074 /// It does not have own \ref run( ) method, it uses the functions1075 /// and features of the plain \ref Dijkstra.1083 /// It does not have own \ref run(Node) "run()" method, it uses the 1084 /// functions and features of the plain \ref Dijkstra. 1076 1085 /// 1077 1086 /// This class should only be used through the \ref dijkstra() function, … … 1268 1277 /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t); 1269 1278 ///\endcode 1270 ///\warning Don't forget to put the \ref DijkstraWizard::run( ) "run()"1279 ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()" 1271 1280 ///to the end of the parameter list. 1272 1281 ///\sa DijkstraWizard
Note: See TracChangeset
for help on using the changeset viewer.
