Changes in / [412:7030149efed2:413:d8b87e9b90c3] in lemon-1.2
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r388 r406 17 17 */ 18 18 19 namespace lemon { 20 19 21 /** 20 22 @defgroup datas Data Structures … … 89 91 90 92 This group describes maps that are specifically designed to assign 91 values to the nodes and arcs of graphs. 93 values to the nodes and arcs/edges of graphs. 94 95 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap, 96 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts". 92 97 */ 93 98 … … 100 105 maps from other maps. 101 106 102 Most of them are \ref lemon::concepts::ReadMap "read-only maps".107 Most of them are \ref concepts::ReadMap "read-only maps". 103 108 They can make arithmetic and logical operations between one or two maps 104 109 (negation, shifting, addition, multiplication, logical 'and', 'or', … … 202 207 \brief Common graph search algorithms. 203 208 204 This group describes the common graph search algorithms like205 Breadth-First Search (BFS) and Depth-First Search (DFS).209 This group describes the common graph search algorithms, namely 210 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS). 206 211 */ 207 212 … … 211 216 \brief Algorithms for finding shortest paths. 212 217 213 This group describes the algorithms for finding shortest paths in graphs. 218 This group describes the algorithms for finding shortest paths in digraphs. 219 220 - \ref Dijkstra algorithm for finding shortest paths from a source node 221 when all arc lengths are non-negative. 222 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths 223 from a source node when arc lenghts can be either positive or negative, 224 but the digraph should not contain directed cycles with negative total 225 length. 226 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms 227 for solving the \e all-pairs \e shortest \e paths \e problem when arc 228 lenghts can be either positive or negative, but the digraph should 229 not contain directed cycles with negative total length. 230 - \ref Suurballe A successive shortest path algorithm for finding 231 arc-disjoint paths between two nodes having minimum total length. 214 232 */ 215 233 … … 222 240 feasible circulations. 223 241 224 The maximum flow problem is to find a flow between a single source and 225 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$ 226 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity 227 function and given \f$s, t \in V\f$ source and target node. The 228 maximum flow is the \f$f_a\f$ solution of the next optimization problem: 229 230 \f[ 0 \le f_a \le c_a \f] 231 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} 232 \qquad \forall u \in V \setminus \{s,t\}\f] 233 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f] 242 The \e maximum \e flow \e problem is to find a flow of maximum value between 243 a single source and a single target. Formally, there is a \f$G=(V,A)\f$ 244 digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and 245 \f$s, t \in V\f$ source and target nodes. 246 A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the 247 following optimization problem. 248 249 \f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f] 250 \f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a) 251 \qquad \forall v\in V\setminus\{s,t\} \f] 252 \f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f] 234 253 235 254 LEMON contains several algorithms for solving maximum flow problems: 236 - \ref lemon::EdmondsKarp "Edmonds-Karp"237 - \ref lemon::Preflow "Goldberg's Preflow algorithm"238 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"239 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"240 241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the242 fastest method to compute the maximum flow. All impelementations243 provides functions to query the minimum cut, which is the dual linear244 pro gramming problem of the maximum flow.255 - \ref EdmondsKarp Edmonds-Karp algorithm. 256 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm. 257 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. 258 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees. 259 260 In most cases the \ref Preflow "Preflow" algorithm provides the 261 fastest method for computing a maximum flow. All implementations 262 provides functions to also query the minimum cut, which is the dual 263 problem of the maximum flow. 245 264 */ 246 265 … … 253 272 This group describes the algorithms for finding minimum cost flows and 254 273 circulations. 274 275 The \e minimum \e cost \e flow \e problem is to find a feasible flow of 276 minimum total cost from a set of supply nodes to a set of demand nodes 277 in a network with capacity constraints and arc costs. 278 Formally, let \f$G=(V,A)\f$ be a digraph, 279 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and 280 upper bounds for the flow values on the arcs, 281 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow 282 on the arcs, and 283 \f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values 284 of the nodes. 285 A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of 286 the following optimization problem. 287 288 \f[ \min\sum_{a\in A} f(a) cost(a) \f] 289 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) = 290 supply(v) \qquad \forall v\in V \f] 291 \f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f] 292 293 LEMON contains several algorithms for solving minimum cost flow problems: 294 - \ref CycleCanceling Cycle-canceling algorithms. 295 - \ref CapacityScaling Successive shortest path algorithm with optional 296 capacity scaling. 297 - \ref CostScaling Push-relabel and augment-relabel algorithms based on 298 cost scaling. 299 - \ref NetworkSimplex Primal network simplex algorithm with various 300 pivot strategies. 255 301 */ 256 302 … … 263 309 This group describes the algorithms for finding minimum cut in graphs. 264 310 265 The minimum cutproblem is to find a non-empty and non-complete266 \f$X\f$ subset of the vertices with minimum overall capacity on267 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an268 \f$c _a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum311 The \e minimum \e cut \e problem is to find a non-empty and non-complete 312 \f$X\f$ subset of the nodes with minimum overall capacity on 313 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a 314 \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum 269 315 cut is the \f$X\f$ solution of the next optimization problem: 270 316 271 317 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} 272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]318 \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f] 273 319 274 320 LEMON contains several algorithms related to minimum cut problems: 275 321 276 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculateminimum cut277 in directed graphs 278 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to279 calculat e minimum cut in undirected graphs280 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all281 pairs minimum cut in undirected graphs322 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut 323 in directed graphs. 324 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for 325 calculating minimum cut in undirected graphs. 326 - \ref GomoryHuTree "Gomory-Hu tree computation" for calculating 327 all-pairs minimum cut in undirected graphs. 282 328 283 329 If you want to find minimum cut just between two distinict nodes, 284 please see the \ref max_flow "Maximum Flow page".330 see the \ref max_flow "maximum flow problem". 285 331 */ 286 332 … … 321 367 graphs. The matching problems in bipartite graphs are generally 322 368 easier than in general graphs. The goal of the matching optimization 323 can be thefinding maximum cardinality, maximum weight or minimum cost369 can be finding maximum cardinality, maximum weight or minimum cost 324 370 matching. The search can be constrained to find perfect or 325 371 maximum cardinality matching. 326 372 327 LEMON contains the next algorithms: 328 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp 329 augmenting path algorithm for calculate maximum cardinality matching in 330 bipartite graphs 331 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel 332 algorithm for calculate maximum cardinality matching in bipartite graphs 333 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" 334 Successive shortest path algorithm for calculate maximum weighted matching 335 and maximum weighted bipartite matching in bipartite graph 336 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" 337 Successive shortest path algorithm for calculate minimum cost maximum 338 matching in bipartite graph 339 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm 340 for calculate maximum cardinality matching in general graph 341 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom 342 shrinking algorithm for calculate maximum weighted matching in general 343 graph 344 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching" 345 Edmond's blossom shrinking algorithm for calculate maximum weighted 346 perfect matching in general graph 373 The matching algorithms implemented in LEMON: 374 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm 375 for calculating maximum cardinality matching in bipartite graphs. 376 - \ref PrBipartiteMatching Push-relabel algorithm 377 for calculating maximum cardinality matching in bipartite graphs. 378 - \ref MaxWeightedBipartiteMatching 379 Successive shortest path algorithm for calculating maximum weighted 380 matching and maximum weighted bipartite matching in bipartite graphs. 381 - \ref MinCostMaxBipartiteMatching 382 Successive shortest path algorithm for calculating minimum cost maximum 383 matching in bipartite graphs. 384 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 385 maximum cardinality matching in general graphs. 386 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating 387 maximum weighted matching in general graphs. 388 - \ref MaxWeightedPerfectMatching 389 Edmond's blossom shrinking algorithm for calculating maximum weighted 390 perfect matching in general graphs. 347 391 348 392 \image html bipartite_matching.png … … 356 400 357 401 This group describes the algorithms for finding a minimum cost spanning 358 tree in a graph 402 tree in a graph. 359 403 */ 360 404 … … 547 591 \anchor demoprograms 548 592 549 @defgroup demos Demo programs593 @defgroup demos Demo Programs 550 594 551 595 Some demo programs are listed here. Their full source codes can be found in … … 557 601 558 602 /** 559 @defgroup tools Standalone utility applications603 @defgroup tools Standalone Utility Applications 560 604 561 605 Some utility applications are listed here. … … 565 609 */ 566 610 611 } -
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]; } -
lemon/dfs.h
r319 r405 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
r397 r408 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.