Changeset 405:6b9057cdcd8b in lemon-1.2 for lemon/bfs.h
- Timestamp:
- 11/30/08 19:17:51 (15 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r329 r405 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]; }
Note: See TracChangeset
for help on using the changeset viewer.