Changes in lemon/bfs.h [525:9605e051942f:301:9db8964f0cf6] in lemon
- File:
-
- 1 edited
-
lemon/bfs.h (modified) (39 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r525 r301 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 50 50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 51 51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 52 ///Instantiates a \cPredMap.53 54 ///This function instantiates a \refPredMap.52 ///Instantiates a PredMap. 53 54 ///This function instantiates a PredMap. 55 55 ///\param g is the digraph, to which we would like to define the 56 /// \refPredMap.56 ///PredMap. 57 57 static PredMap *createPredMap(const Digraph &g) 58 58 { … … 65 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 66 66 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 67 ///Instantiates a \cProcessedMap.68 69 ///This function instantiates a \refProcessedMap.67 ///Instantiates a ProcessedMap. 68 69 ///This function instantiates a ProcessedMap. 70 70 ///\param g is the digraph, to which 71 ///we would like to define the \refProcessedMap71 ///we would like to define the ProcessedMap 72 72 #ifdef DOXYGEN 73 73 static ProcessedMap *createProcessedMap(const Digraph &g) … … 84 84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 85 typedef typename Digraph::template NodeMap<bool> ReachedMap; 86 ///Instantiates a \cReachedMap.87 88 ///This function instantiates a \refReachedMap.86 ///Instantiates a ReachedMap. 87 88 ///This function instantiates a ReachedMap. 89 89 ///\param g is the digraph, to which 90 ///we would like to define the \refReachedMap.90 ///we would like to define the ReachedMap. 91 91 static ReachedMap *createReachedMap(const Digraph &g) 92 92 { … … 99 99 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 100 100 typedef typename Digraph::template NodeMap<int> DistMap; 101 ///Instantiates a \cDistMap.102 103 ///This function instantiates a \refDistMap.101 ///Instantiates a DistMap. 102 103 ///This function instantiates a DistMap. 104 104 ///\param g is the digraph, to which we would like to define the 105 /// \refDistMap.105 ///DistMap. 106 106 static DistMap *createDistMap(const Digraph &g) 107 107 { … … 120 120 /// 121 121 ///\tparam GR The type of the digraph the algorithm runs on. 122 ///The default type is \ref ListDigraph. 122 ///The default value is \ref ListDigraph. The value of GR is not used 123 ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits. 124 ///\tparam TR Traits class to set various data types used by the algorithm. 125 ///The default traits class is 126 ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>". 127 ///See \ref BfsDefaultTraits for the documentation of 128 ///a Bfs traits class. 123 129 #ifdef DOXYGEN 124 130 template <typename GR, … … 146 152 typedef PredMapPath<Digraph, PredMap> Path; 147 153 148 ///The \ref BfsDefaultTraits "traits class" of the algorithm.154 ///The traits class. 149 155 typedef TR Traits; 150 156 … … 208 214 typedef Bfs Create; 209 215 210 ///\name Named Template Parameters216 ///\name Named template parameters 211 217 212 218 ///@{ … … 222 228 }; 223 229 ///\brief \ref named-templ-param "Named parameter" for setting 224 /// \cPredMap type.230 ///PredMap type. 225 231 /// 226 232 ///\ref named-templ-param "Named parameter" for setting 227 ///\c PredMap type. 228 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 233 ///PredMap type. 229 234 template <class T> 230 235 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { … … 242 247 }; 243 248 ///\brief \ref named-templ-param "Named parameter" for setting 244 /// \cDistMap type.249 ///DistMap type. 245 250 /// 246 251 ///\ref named-templ-param "Named parameter" for setting 247 ///\c DistMap type. 248 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 252 ///DistMap type. 249 253 template <class T> 250 254 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { … … 262 266 }; 263 267 ///\brief \ref named-templ-param "Named parameter" for setting 264 /// \cReachedMap type.268 ///ReachedMap type. 265 269 /// 266 270 ///\ref named-templ-param "Named parameter" for setting 267 ///\c ReachedMap type. 268 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 271 ///ReachedMap type. 269 272 template <class T> 270 273 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { … … 282 285 }; 283 286 ///\brief \ref named-templ-param "Named parameter" for setting 284 /// \cProcessedMap type.287 ///ProcessedMap type. 285 288 /// 286 289 ///\ref named-templ-param "Named parameter" for setting 287 ///\c ProcessedMap type. 288 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 290 ///ProcessedMap type. 289 291 template <class T> 290 292 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { … … 301 303 }; 302 304 ///\brief \ref named-templ-param "Named parameter" for setting 303 /// \cProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.305 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 304 306 /// 305 307 ///\ref named-templ-param "Named parameter" for setting 306 /// \cProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.308 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 307 309 ///If you don't set it explicitly, it will be automatically allocated. 308 310 struct SetStandardProcessedMap : … … 339 341 340 342 ///Sets the map that stores the predecessor arcs. 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. 343 ///If you don't use this function before calling \ref run(), 344 ///it will allocate one. The destructor deallocates this 345 ///automatically allocated map, of course. 345 346 ///\return <tt> (*this) </tt> 346 347 Bfs &predMap(PredMap &m) … … 357 358 358 359 ///Sets the map that indicates which nodes are reached. 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. 360 ///If you don't use this function before calling \ref run(), 361 ///it will allocate one. The destructor deallocates this 362 ///automatically allocated map, of course. 363 363 ///\return <tt> (*this) </tt> 364 364 Bfs &reachedMap(ReachedMap &m) … … 375 375 376 376 ///Sets the map that indicates which nodes are processed. 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. 377 ///If you don't use this function before calling \ref run(), 378 ///it will allocate one. The destructor deallocates this 379 ///automatically allocated map, of course. 381 380 ///\return <tt> (*this) </tt> 382 381 Bfs &processedMap(ProcessedMap &m) … … 394 393 ///Sets the map that stores the distances of the nodes calculated by 395 394 ///the algorithm. 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. 395 ///If you don't use this function before calling \ref run(), 396 ///it will allocate one. The destructor deallocates this 397 ///automatically allocated map, of course. 400 398 ///\return <tt> (*this) </tt> 401 399 Bfs &distMap(DistMap &m) … … 411 409 public: 412 410 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. 411 ///\name Execution control 412 ///The simplest way to execute the algorithm is to use 413 ///one of the member functions called \ref lemon::Bfs::run() "run()". 414 ///\n 415 ///If you need more control on the execution, first you must call 416 ///\ref lemon::Bfs::init() "init()", then you can add several source 417 ///nodes with \ref lemon::Bfs::addSource() "addSource()". 418 ///Finally \ref lemon::Bfs::start() "start()" will perform the 419 ///actual path computation. 420 420 421 421 ///@{ 422 422 423 ///\brief Initializes the internal data structures.424 ///425 423 ///Initializes the internal data structures. 424 425 ///Initializes the internal data structures. 426 /// 426 427 void init() 427 428 { … … 557 558 } 558 559 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. 560 ///\brief Returns \c false if there are nodes 561 ///to be processed. 562 /// 563 ///Returns \c false if there are nodes 564 ///to be processed in the queue. 563 565 bool emptyQueue() const { return _queue_tail==_queue_head; } 564 566 565 567 ///Returns the number of the nodes to be processed. 566 568 567 ///Returns the number of the nodes to be processed 568 ///in the queue. 569 ///Returns the number of the nodes to be processed in the queue. 569 570 int queueSize() const { return _queue_head-_queue_tail; } 570 571 … … 731 732 732 733 ///\name Query Functions 733 ///The result s of theBFS algorithm can be obtained using these734 ///The result of the %BFS algorithm can be obtained using these 734 735 ///functions.\n 735 ///Either \ref run(Node) "run()" or \ref start() should be called736 /// before using them.736 ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start() 737 ///"start()" must be called before using them. 737 738 738 739 ///@{ … … 742 743 ///Returns the shortest path to a node. 743 744 /// 744 ///\warning \c t should be reach edfrom the root(s).745 /// 746 ///\pre Either \ref run( Node) "run()" or \ref init()747 /// must be called beforeusing this function.745 ///\warning \c t should be reachable from the root(s). 746 /// 747 ///\pre Either \ref run() or \ref start() must be called before 748 ///using this function. 748 749 Path path(Node t) const { return Path(*G, *_pred, t); } 749 750 … … 752 753 ///Returns the distance of a node from the root(s). 753 754 /// 754 ///\warning If node \c v is not reach edfrom the root(s), then755 ///\warning If node \c v is not reachable from the root(s), then 755 756 ///the return value of this function is undefined. 756 757 /// 757 ///\pre Either \ref run( Node) "run()" or \ref init()758 /// must be called beforeusing this function.758 ///\pre Either \ref run() or \ref start() must be called before 759 ///using this function. 759 760 int dist(Node v) const { return (*_dist)[v]; } 760 761 … … 763 764 ///This function returns the 'previous arc' of the shortest path 764 765 ///tree for the node \c v, i.e. it returns the last arc of a 765 ///shortest path from a rootto \c v. It is \c INVALID if \c v766 ///is not reach edfrom the root(s) or if \c v is a root.766 ///shortest path from the root(s) to \c v. It is \c INVALID if \c v 767 ///is not reachable from the root(s) or if \c v is a root. 767 768 /// 768 769 ///The shortest path tree used here is equal to the shortest path 769 770 ///tree used in \ref predNode(). 770 771 /// 771 ///\pre Either \ref run( Node) "run()" or \ref init()772 /// must be called beforeusing this function.772 ///\pre Either \ref run() or \ref start() must be called before 773 ///using this function. 773 774 Arc predArc(Node v) const { return (*_pred)[v];} 774 775 … … 777 778 ///This function returns the 'previous node' of the shortest path 778 779 ///tree for the node \c v, i.e. it returns the last but one node 779 ///from a shortest path from a rootto \c v. It is \c INVALID780 ///if \c v is not reach edfrom the root(s) or if \c v is a root.780 ///from a shortest path from the root(s) to \c v. It is \c INVALID 781 ///if \c v is not reachable from the root(s) or if \c v is a root. 781 782 /// 782 783 ///The shortest path tree used here is equal to the shortest path 783 784 ///tree used in \ref predArc(). 784 785 /// 785 ///\pre Either \ref run( Node) "run()" or \ref init()786 /// must be called beforeusing this function.786 ///\pre Either \ref run() or \ref start() must be called before 787 ///using this function. 787 788 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 788 789 G->source((*_pred)[v]); } … … 794 795 ///of the nodes calculated by the algorithm. 795 796 /// 796 ///\pre Either \ref run( Node) "run()"or \ref init()797 ///\pre Either \ref run() or \ref init() 797 798 ///must be called before using this function. 798 799 const DistMap &distMap() const { return *_dist;} … … 804 805 ///arcs, which form the shortest path tree. 805 806 /// 806 ///\pre Either \ref run( Node) "run()"or \ref init()807 ///\pre Either \ref run() or \ref init() 807 808 ///must be called before using this function. 808 809 const PredMap &predMap() const { return *_pred;} 809 810 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() 811 ///Checks if a node is reachable from the root(s). 812 813 ///Returns \c true if \c v is reachable from the root(s). 814 ///\pre Either \ref run() or \ref start() 815 815 ///must be called before using this function. 816 816 bool reached(Node v) const { return (*_reached)[v]; } … … 958 958 /// This auxiliary class is created to implement the 959 959 /// \ref bfs() "function-type interface" of \ref Bfs algorithm. 960 /// It does not have own \ref run( Node) "run()" method, it uses the961 /// functionsand features of the plain \ref Bfs.960 /// It does not have own \ref run() method, it uses the functions 961 /// and features of the plain \ref Bfs. 962 962 /// 963 963 /// This class should only be used through the \ref bfs() function, … … 1179 1179 /// bool reached = bfs(g).path(p).dist(d).run(s,t); 1180 1180 ///\endcode 1181 ///\warning Don't forget to put the \ref BfsWizard::run( Node) "run()"1181 ///\warning Don't forget to put the \ref BfsWizard::run() "run()" 1182 1182 ///to the end of the parameter list. 1183 1183 ///\sa BfsWizard … … 1195 1195 /// This class defines the interface of the BfsVisit events, and 1196 1196 /// it could be the base of a real visitor class. 1197 template <typename GR>1197 template <typename _Digraph> 1198 1198 struct BfsVisitor { 1199 typedef GRDigraph;1199 typedef _Digraph Digraph; 1200 1200 typedef typename Digraph::Arc Arc; 1201 1201 typedef typename Digraph::Node Node; … … 1225 1225 }; 1226 1226 #else 1227 template <typename GR>1227 template <typename _Digraph> 1228 1228 struct BfsVisitor { 1229 typedef GRDigraph;1229 typedef _Digraph Digraph; 1230 1230 typedef typename Digraph::Arc Arc; 1231 1231 typedef typename Digraph::Node Node; … … 1255 1255 /// 1256 1256 /// Default traits class of BfsVisit class. 1257 /// \tparam GRThe type of the digraph the algorithm runs on.1258 template<class GR>1257 /// \tparam _Digraph The type of the digraph the algorithm runs on. 1258 template<class _Digraph> 1259 1259 struct BfsVisitDefaultTraits { 1260 1260 1261 1261 /// \brief The type of the digraph the algorithm runs on. 1262 typedef GRDigraph;1262 typedef _Digraph Digraph; 1263 1263 1264 1264 /// \brief The type of the map that indicates which nodes are reached. … … 1281 1281 /// \ingroup search 1282 1282 /// 1283 /// \brief BFS algorithm class with visitor interface.1283 /// \brief %BFS algorithm class with visitor interface. 1284 1284 /// 1285 /// This class provides an efficient implementation of the BFS algorithm1285 /// This class provides an efficient implementation of the %BFS algorithm 1286 1286 /// with visitor interface. 1287 1287 /// 1288 /// The BfsVisit class provides an alternative interface to the Bfs1288 /// The %BfsVisit class provides an alternative interface to the Bfs 1289 1289 /// class. It works with callback mechanism, the BfsVisit object calls 1290 1290 /// the member functions of the \c Visitor class on every BFS event. … … 1295 1295 /// instead. 1296 1296 /// 1297 /// \tparam GRThe type of the digraph the algorithm runs on.1298 /// The default type is \ref ListDigraph.1299 /// The value of GR is not used directly by \ref BfsVisit,1300 /// it is only passed to \ref BfsVisitDefaultTraits.1301 /// \tparam VSThe Visitor type that is used by the algorithm.1302 /// \ref BfsVisitor "BfsVisitor< GR>" is an empty visitor, which1297 /// \tparam _Digraph The type of the digraph the algorithm runs on. 1298 /// The default value is 1299 /// \ref ListDigraph. The value of _Digraph is not used directly by 1300 /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits. 1301 /// \tparam _Visitor The Visitor type that is used by the algorithm. 1302 /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which 1303 1303 /// does not observe the BFS events. If you want to observe the BFS 1304 1304 /// events, you should implement your own visitor class. 1305 /// \tparam TRTraits class to set various data types used by the1305 /// \tparam _Traits Traits class to set various data types used by the 1306 1306 /// algorithm. The default traits class is 1307 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits< GR>".1307 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>". 1308 1308 /// See \ref BfsVisitDefaultTraits for the documentation of 1309 1309 /// a BFS visit traits class. 1310 1310 #ifdef DOXYGEN 1311 template <typename GR, typename VS, typename TR>1311 template <typename _Digraph, typename _Visitor, typename _Traits> 1312 1312 #else 1313 template <typename GR= ListDigraph,1314 typename VS = BfsVisitor<GR>,1315 typename TR = BfsVisitDefaultTraits<GR> >1313 template <typename _Digraph = ListDigraph, 1314 typename _Visitor = BfsVisitor<_Digraph>, 1315 typename _Traits = BfsVisitDefaultTraits<_Digraph> > 1316 1316 #endif 1317 1317 class BfsVisit { … … 1319 1319 1320 1320 ///The traits class. 1321 typedef TRTraits;1321 typedef _Traits Traits; 1322 1322 1323 1323 ///The type of the digraph the algorithm runs on. … … 1325 1325 1326 1326 ///The visitor type used by the algorithm. 1327 typedef VSVisitor;1327 typedef _Visitor Visitor; 1328 1328 1329 1329 ///The type of the map that indicates which nodes are reached. … … 1365 1365 typedef BfsVisit Create; 1366 1366 1367 /// \name Named Template Parameters1367 /// \name Named template parameters 1368 1368 1369 1369 ///@{ … … 1407 1407 /// 1408 1408 /// Sets the map that indicates which nodes are reached. 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. 1409 /// If you don't use this function before calling \ref run(), 1410 /// it will allocate one. The destructor deallocates this 1411 /// automatically allocated map, of course. 1413 1412 /// \return <tt> (*this) </tt> 1414 1413 BfsVisit &reachedMap(ReachedMap &m) { … … 1423 1422 public: 1424 1423 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. 1424 /// \name Execution control 1425 /// The simplest way to execute the algorithm is to use 1426 /// one of the member functions called \ref lemon::BfsVisit::run() 1427 /// "run()". 1428 /// \n 1429 /// If you need more control on the execution, first you must call 1430 /// \ref lemon::BfsVisit::init() "init()", then you can add several 1431 /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()". 1432 /// Finally \ref lemon::BfsVisit::start() "start()" will perform the 1433 /// actual path computation. 1432 1434 1433 1435 /// @{ … … 1729 1731 1730 1732 /// \name Query Functions 1731 /// The result s of theBFS algorithm can be obtained using these1733 /// The result of the %BFS algorithm can be obtained using these 1732 1734 /// functions.\n 1733 /// Either \ref run(Node) "run()" or \ref start() should be called1734 /// before using them.1735 1735 /// Either \ref lemon::BfsVisit::run() "run()" or 1736 /// \ref lemon::BfsVisit::start() "start()" must be called before 1737 /// using them. 1736 1738 ///@{ 1737 1739 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() 1740 /// \brief Checks if a node is reachable from the root(s). 1741 /// 1742 /// Returns \c true if \c v is reachable from the root(s). 1743 /// \pre Either \ref run() or \ref start() 1743 1744 /// must be called before using this function. 1744 bool reached(Node v) const{ return (*_reached)[v]; }1745 bool reached(Node v) { return (*_reached)[v]; } 1745 1746 1746 1747 ///@}
Note: See TracChangeset
for help on using the changeset viewer.
