Changeset 244:c30731a37f91 in lemon for lemon/dijkstra.h
 Timestamp:
 08/03/08 13:34:57 (15 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/dijkstra.h
r210 r244 34 34 namespace lemon { 35 35 36 /// \brief Default OperationTraits for the Dijkstra algorithm class.36 /// \brief Default operation traits for the Dijkstra algorithm class. 37 37 /// 38 /// It defines all computational operations and constants which are39 /// used in the Dijkstra algorithm.38 /// This operation traits class defines all computational operations and 39 /// constants which are used in the Dijkstra algorithm. 40 40 template <typename Value> 41 41 struct DijkstraDefaultOperationTraits { … … 48 48 return left + right; 49 49 } 50 /// \brief Gives back true only if the first value less than the second.50 /// \brief Gives back true only if the first value is less than the second. 51 51 static bool less(const Value& left, const Value& right) { 52 52 return left < right; … … 54 54 }; 55 55 56 /// \brief Widest path OperationTraits for the Dijkstra algorithm class.56 /// \brief Widest path operation traits for the Dijkstra algorithm class. 57 57 /// 58 /// It defines all computational operations and constants which are 59 /// used in the Dijkstra algorithm for widest path computation. 58 /// This operation traits class defines all computational operations and 59 /// constants which are used in the Dijkstra algorithm for widest path 60 /// computation. 61 /// 62 /// \see DijkstraDefaultOperationTraits 60 63 template <typename Value> 61 64 struct DijkstraWidestPathOperationTraits { … … 68 71 return std::min(left, right); 69 72 } 70 /// \brief Gives back true only if the first value less than the second.73 /// \brief Gives back true only if the first value is less than the second. 71 74 static bool less(const Value& left, const Value& right) { 72 75 return left < right; … … 77 80 78 81 ///Default traits class of Dijkstra class. 79 ///\tparam GR Digraph type.80 ///\tparam LM T ype oflength map.82 ///\tparam GR The type of the digraph. 83 ///\tparam LM The type of the length map. 81 84 template<class GR, class LM> 82 85 struct DijkstraDefaultTraits 83 86 { 84 ///The digraph typethe algorithm runs on.87 ///The type of the digraph the algorithm runs on. 85 88 typedef GR Digraph; 89 86 90 ///The type of the map that stores the arc lengths. 87 91 … … 89 93 ///It must meet the \ref concepts::ReadMap "ReadMap" concept. 90 94 typedef LM LengthMap; 91 // The type of the length of the arcs.95 ///The type of the length of the arcs. 92 96 typedef typename LM::Value Value; 97 93 98 /// Operation traits for Dijkstra algorithm. 94 99 95 /// It defines the used operation bythe algorithm.100 /// This class defines the operations that are used in the algorithm. 96 101 /// \see DijkstraDefaultOperationTraits 97 102 typedef DijkstraDefaultOperationTraits<Value> OperationTraits; 98 /// The cross reference type used by heap. 99 100 101 /// The cross reference type used by heap.103 104 /// The cross reference type used by the heap. 105 106 /// The cross reference type used by the heap. 102 107 /// Usually it is \c Digraph::NodeMap<int>. 103 108 typedef typename Digraph::template NodeMap<int> HeapCrossRef; 104 ///Instantiates a HeapCrossRef.105 106 ///This function instantiates a \ cHeapCrossRef.107 /// \param Gis the digraph, to which we would like to define the108 /// HeapCrossRef.109 static HeapCrossRef *createHeapCrossRef(const GR &G)110 { 111 return new HeapCrossRef( G);112 } 113 114 ///The heap type used by Dijkstra algorithm.115 116 ///The heap type used by Dijkstra algorithm.109 ///Instantiates a \ref HeapCrossRef. 110 111 ///This function instantiates a \ref HeapCrossRef. 112 /// \param g is the digraph, to which we would like to define the 113 /// \ref HeapCrossRef. 114 static HeapCrossRef *createHeapCrossRef(const Digraph &g) 115 { 116 return new HeapCrossRef(g); 117 } 118 119 ///The heap type used by the Dijkstra algorithm. 120 121 ///The heap type used by the Dijkstra algorithm. 117 122 /// 118 123 ///\sa BinHeap 119 124 ///\sa Dijkstra 120 125 typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap; 121 122 static Heap *createHeap(HeapCrossRef& R) 123 { 124 return new Heap(R); 125 } 126 127 ///\brief The type of the map that stores the last 126 ///Instantiates a \ref Heap. 127 128 ///This function instantiates a \ref Heap. 129 static Heap *createHeap(HeapCrossRef& r) 130 { 131 return new Heap(r); 132 } 133 134 ///\brief The type of the map that stores the predecessor 128 135 ///arcs of the shortest paths. 129 136 /// 130 ///The type of the map that stores the last137 ///The type of the map that stores the predecessor 131 138 ///arcs of the shortest paths. 132 139 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 133 ///134 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;135 ///Instantiates a PredMap. 136 137 /// This function instantiates a \c PredMap.138 ///\ param G is the digraph, to which we would like to define thePredMap.140 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 141 ///Instantiates a \ref PredMap. 142 143 ///This function instantiates a \ref PredMap. 144 ///\param g is the digraph, to which we would like to define the 145 ///\ref PredMap. 139 146 ///\todo The digraph alone may be insufficient for the initialization 140 static PredMap *createPredMap(const GR &G)141 { 142 return new PredMap( G);143 } 144 145 ///The type of the map that stores whether a nodes isprocessed.146 147 ///The type of the map that stores whether a nodes isprocessed.147 static PredMap *createPredMap(const Digraph &g) 148 { 149 return new PredMap(g); 150 } 151 152 ///The type of the map that indicates which nodes are processed. 153 154 ///The type of the map that indicates which nodes are processed. 148 155 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 149 156 ///By default it is a NullMap. 150 157 ///\todo If it is set to a real map, 151 158 ///Dijkstra::processed() should read this. 152 ///\todo named parameter to set this type, function to read and write.153 159 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 154 ///Instantiates a ProcessedMap.155 156 ///This function instantiates a \ cProcessedMap.160 ///Instantiates a \ref ProcessedMap. 161 162 ///This function instantiates a \ref ProcessedMap. 157 163 ///\param g is the digraph, to which 158 ///we would like to define the \ cProcessedMap164 ///we would like to define the \ref ProcessedMap 159 165 #ifdef DOXYGEN 160 static ProcessedMap *createProcessedMap(const GR&g)166 static ProcessedMap *createProcessedMap(const Digraph &g) 161 167 #else 162 static ProcessedMap *createProcessedMap(const GR&)168 static ProcessedMap *createProcessedMap(const Digraph &) 163 169 #endif 164 170 { 165 171 return new ProcessedMap(); 166 172 } 167 ///The type of the map that stores the dists of the nodes. 168 169 ///The type of the map that stores the dists of the nodes. 173 174 ///The type of the map that stores the distances of the nodes. 175 176 ///The type of the map that stores the distances of the nodes. 170 177 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 171 ///172 178 typedef typename Digraph::template NodeMap<typename LM::Value> DistMap; 173 ///Instantiates a DistMap.179 ///Instantiates a \ref DistMap. 174 180 175 181 ///This function instantiates a \ref DistMap. 176 ///\param Gis the digraph, to which we would like to define182 ///\param g is the digraph, to which we would like to define 177 183 ///the \ref DistMap 178 static DistMap *createDistMap(const GR &G)179 { 180 return new DistMap( G);184 static DistMap *createDistMap(const Digraph &g) 185 { 186 return new DistMap(g); 181 187 } 182 188 }; … … 185 191 186 192 /// \ingroup shortest_path 187 ///This class provides an efficient implementation of %Dijkstra algorithm. 193 ///This class provides an efficient implementation of the %Dijkstra algorithm. 194 /// 188 195 ///The arc lengths are passed to the algorithm using a 189 196 ///\ref concepts::ReadMap "ReadMap", 190 197 ///so it is easy to change it to any kind of length. 191 ///192 198 ///The type of the length is determined by the 193 199 ///\ref concepts::ReadMap::Value "Value" of the length map. 194 ///195 200 ///It is also possible to change the underlying priority heap. 196 201 /// 197 ///\tparam GR The digraph type the algorithm runs on. The default value 198 ///is \ref ListDigraph. The value of GR is not used directly by 199 ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits. 200 ///\tparam LM This readonly ArcMap determines the lengths of the 202 ///There is also a \ref dijkstra() "function type interface" for the 203 ///%Dijkstra algorithm, which is convenient in the simplier cases and 204 ///it can be used easier. 205 /// 206 ///\tparam GR The type of the digraph the algorithm runs on. 207 ///The default value is \ref ListDigraph. 208 ///The value of GR is not used directly by \ref Dijkstra, it is only 209 ///passed to \ref DijkstraDefaultTraits. 210 ///\tparam LM A readable arc map that determines the lengths of the 201 211 ///arcs. It is read once for each arc, so the map may involve in 202 ///relatively time consuming process to compute the arc length if212 ///relatively time consuming process to compute the arc lengths if 203 213 ///it is necessary. The default map type is \ref 204 ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>". The value 205 ///of LM is not used directly by Dijkstra, it is only passed to \ref 206 ///DijkstraDefaultTraits. 207 ///\tparam TR Traits class to set 208 ///various data types used by the algorithm. The default traits 209 ///class is \ref DijkstraDefaultTraits 210 ///"DijkstraDefaultTraits<GR,LM>". See \ref 211 ///DijkstraDefaultTraits for the documentation of a Dijkstra traits 212 ///class. 213 214 ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>". 215 ///The value of LM is not used directly by \ref Dijkstra, it is only 216 ///passed to \ref DijkstraDefaultTraits. 217 ///\tparam TR Traits class to set various data types used by the algorithm. 218 ///The default traits class is \ref DijkstraDefaultTraits 219 ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits 220 ///for the documentation of a Dijkstra traits class. 214 221 #ifdef DOXYGEN 215 222 template <typename GR, typename LM, typename TR> … … 221 228 class Dijkstra { 222 229 public: 223 /** 224 * \brief \ref Exception for uninitialized parameters. 225 * 226 * This error represents problems in the initialization 227 * of the parameters of the algorithms. 228 */ 230 ///\ref Exception for uninitialized parameters. 231 232 ///This error represents problems in the initialization of the 233 ///parameters of the algorithm. 229 234 class UninitializedParameter : public lemon::UninitializedParameter { 230 235 public: … … 234 239 }; 235 240 236 typedef TR Traits; 237 ///The type of the underlying digraph. 241 ///The type of the digraph the algorithm runs on. 238 242 typedef typename TR::Digraph Digraph; 239 ///\e240 typedef typename Digraph::Node Node;241 ///\e242 typedef typename Digraph::NodeIt NodeIt;243 ///\e244 typedef typename Digraph::Arc Arc;245 ///\e246 typedef typename Digraph::OutArcIt OutArcIt;247 243 248 244 ///The type of the length of the arcs. … … 250 246 ///The type of the map that stores the arc lengths. 251 247 typedef typename TR::LengthMap LengthMap; 252 ///\brief The type of the map that stores the last253 /// arcs of theshortest paths.248 ///\brief The type of the map that stores the predecessor arcs of the 249 ///shortest paths. 254 250 typedef typename TR::PredMap PredMap; 255 ///The type of the map indicating if a node is processed. 251 ///The type of the map that stores the distances of the nodes. 252 typedef typename TR::DistMap DistMap; 253 ///The type of the map that indicates which nodes are processed. 256 254 typedef typename TR::ProcessedMap ProcessedMap; 257 ///The type of the map that stores the dists of the nodes.258 typedef typename TR::DistMap DistMap;255 ///The type of the paths. 256 typedef PredMapPath<Digraph, PredMap> Path; 259 257 ///The cross reference type used for the current heap. 260 258 typedef typename TR::HeapCrossRef HeapCrossRef; 261 ///The heap type used by the dijkstraalgorithm.259 ///The heap type used by the algorithm. 262 260 typedef typename TR::Heap Heap; 263 ///The operation traits .261 ///The operation traits class. 264 262 typedef typename TR::OperationTraits OperationTraits; 263 264 ///The traits class. 265 typedef TR Traits; 266 265 267 private: 266 /// Pointer to the underlying digraph. 268 269 typedef typename Digraph::Node Node; 270 typedef typename Digraph::NodeIt NodeIt; 271 typedef typename Digraph::Arc Arc; 272 typedef typename Digraph::OutArcIt OutArcIt; 273 274 //Pointer to the underlying digraph. 267 275 const Digraph *G; 268 // / Pointer to the length map276 //Pointer to the length map. 269 277 const LengthMap *length; 270 // /Pointer to the map of predecessors arcs.278 //Pointer to the map of predecessors arcs. 271 279 PredMap *_pred; 272 // /Indicates if \ref _pred is locally allocated (\ctrue) or not.280 //Indicates if _pred is locally allocated (true) or not. 273 281 bool local_pred; 274 // /Pointer to the map of distances.282 //Pointer to the map of distances. 275 283 DistMap *_dist; 276 // /Indicates if \ref _dist is locally allocated (\ctrue) or not.284 //Indicates if _dist is locally allocated (true) or not. 277 285 bool local_dist; 278 // /Pointer to the map of processed status of the nodes.286 //Pointer to the map of processed status of the nodes. 279 287 ProcessedMap *_processed; 280 // /Indicates if \ref _processed is locally allocated (\ctrue) or not.288 //Indicates if _processed is locally allocated (true) or not. 281 289 bool local_processed; 282 // /Pointer to the heap cross references.290 //Pointer to the heap cross references. 283 291 HeapCrossRef *_heap_cross_ref; 284 // /Indicates if \ref _heap_cross_ref is locally allocated (\ctrue) or not.292 //Indicates if _heap_cross_ref is locally allocated (true) or not. 285 293 bool local_heap_cross_ref; 286 // /Pointer to the heap.294 //Pointer to the heap. 287 295 Heap *_heap; 288 // /Indicates if \ref _heap is locally allocated (\ctrue) or not.296 //Indicates if _heap is locally allocated (true) or not. 289 297 bool local_heap; 290 298 291 299 ///Creates the maps if necessary. 292 293 300 ///\todo Better memory allocation (instead of new). 294 301 void create_maps() … … 316 323 } 317 324 318 public 325 public: 319 326 320 327 typedef Dijkstra Create; … … 332 339 } 333 340 }; 334 ///\ref namedtemplparam "Named parameter" for setting PredMap type 335 336 ///\ref namedtemplparam "Named parameter" for setting PredMap type 337 /// 341 ///\brief \ref namedtemplparam "Named parameter" for setting 342 ///\ref PredMap type. 343 /// 344 ///\ref namedtemplparam "Named parameter" for setting 345 ///\ref PredMap type. 338 346 template <class T> 339 347 struct DefPredMap … … 350 358 } 351 359 }; 352 ///\ref namedtemplparam "Named parameter" for setting DistMap type 353 354 ///\ref namedtemplparam "Named parameter" for setting DistMap type 355 /// 360 ///\brief \ref namedtemplparam "Named parameter" for setting 361 ///\ref DistMap type. 362 /// 363 ///\ref namedtemplparam "Named parameter" for setting 364 ///\ref DistMap type. 356 365 template <class T> 357 366 struct DefDistMap … … 363 372 struct DefProcessedMapTraits : public Traits { 364 373 typedef T ProcessedMap; 365 static ProcessedMap *createProcessedMap(const Digraph & G)374 static ProcessedMap *createProcessedMap(const Digraph &) 366 375 { 367 376 throw UninitializedParameter(); 368 377 } 369 378 }; 370 ///\ref namedtemplparam "Named parameter" for setting ProcessedMap type 371 372 ///\ref namedtemplparam "Named parameter" for setting ProcessedMap type 373 /// 379 ///\brief \ref namedtemplparam "Named parameter" for setting 380 ///\ref ProcessedMap type. 381 /// 382 ///\ref namedtemplparam "Named parameter" for setting 383 ///\ref ProcessedMap type. 374 384 template <class T> 375 385 struct DefProcessedMap … … 380 390 struct DefDigraphProcessedMapTraits : public Traits { 381 391 typedef typename Digraph::template NodeMap<bool> ProcessedMap; 382 static ProcessedMap *createProcessedMap(const Digraph & G)392 static ProcessedMap *createProcessedMap(const Digraph &g) 383 393 { 384 return new ProcessedMap( G);385 } 386 }; 387 ///\brief \ref namedtemplparam "Named parameter" 388 /// for setting the ProcessedMap type to be Digraph::NodeMap<bool>.389 /// 390 ///\ref namedtemplparam "Named parameter" 391 /// for setting the ProcessedMap type to be Digraph::NodeMap<bool>.392 ///If you don't set it explicit ely, it will be automatically allocated.394 return new ProcessedMap(g); 395 } 396 }; 397 ///\brief \ref namedtemplparam "Named parameter" for setting 398 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 399 /// 400 ///\ref namedtemplparam "Named parameter" for setting 401 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 402 ///If you don't set it explicitly, it will be automatically allocated. 393 403 template <class T> 394 404 struct DefProcessedMapToBeDefaultMap … … 414 424 /// 415 425 ///\ref namedtemplparam "Named parameter" for setting heap and cross 416 ///reference type 417 /// 426 ///reference type. 418 427 template <class H, class CR = typename Digraph::template NodeMap<int> > 419 428 struct DefHeap … … 454 463 455 464 /// \brief \ref namedtemplparam "Named parameter" for setting 456 /// OperationTraits type457 /// 458 /// \ref namedtemplparam "Named parameter" for setting OperationTraits459 /// type465 ///\ref OperationTraits type 466 /// 467 ///\ref namedtemplparam "Named parameter" for setting 468 ///\ref OperationTraits type. 460 469 template <class T> 461 470 struct DefOperationTraits … … 467 476 ///@} 468 477 469 470 478 protected: 471 479 … … 476 484 ///Constructor. 477 485 478 ///\param _G the digraph the algorithm will run on. 479 ///\param _length the length map used by the algorithm. 480 Dijkstra(const Digraph& _G, const LengthMap& _length) : 481 G(&_G), length(&_length), 486 ///Constructor. 487 ///\param _g The digraph the algorithm runs on. 488 ///\param _length The length map used by the algorithm. 489 Dijkstra(const Digraph& _g, const LengthMap& _length) : 490 G(&_g), length(&_length), 482 491 _pred(NULL), local_pred(false), 483 492 _dist(NULL), local_dist(false), … … 507 516 } 508 517 509 ///Sets the map storingthe predecessor arcs.510 511 ///Sets the map storingthe predecessor arcs.518 ///Sets the map that stores the predecessor arcs. 519 520 ///Sets the map that stores the predecessor arcs. 512 521 ///If you don't use this function before calling \ref run(), 513 ///it will allocate one. The dest uctor deallocates this522 ///it will allocate one. The destructor deallocates this 514 523 ///automatically allocated map, of course. 515 524 ///\return <tt> (*this) </tt> … … 524 533 } 525 534 526 ///Sets the map storing the distances calculated by the algorithm.527 528 ///Sets the map storing the distances calculated by the algorithm.535 ///Sets the map that indicates which nodes are processed. 536 537 ///Sets the map that indicates which nodes are processed. 529 538 ///If you don't use this function before calling \ref run(), 530 ///it will allocate one. The destuctor deallocates this 539 ///it will allocate one. The destructor deallocates this 540 ///automatically allocated map, of course. 541 ///\return <tt> (*this) </tt> 542 Dijkstra &processedMap(ProcessedMap &m) 543 { 544 if(local_processed) { 545 delete _processed; 546 local_processed=false; 547 } 548 _processed = &m; 549 return *this; 550 } 551 552 ///Sets the map that stores the distances of the nodes. 553 554 ///Sets the map that stores the distances of the nodes calculated by the 555 ///algorithm. 556 ///If you don't use this function before calling \ref run(), 557 ///it will allocate one. The destructor deallocates this 531 558 ///automatically allocated map, of course. 532 559 ///\return <tt> (*this) </tt> … … 545 572 ///Sets the heap and the cross reference used by algorithm. 546 573 ///If you don't use this function before calling \ref run(), 547 ///it will allocate one. The dest uctor deallocates this574 ///it will allocate one. The destructor deallocates this 548 575 ///automatically allocated heap and cross reference, of course. 549 576 ///\return <tt> (*this) </tt> … … 564 591 565 592 private: 593 566 594 void finalizeNodeData(Node v,Value dst) 567 595 { … … 572 600 public: 573 601 574 typedef PredMapPath<Digraph, PredMap> Path;575 576 602 ///\name Execution control 577 ///The simplest way to execute the algorithm is to use 578 /// one of the member functions called \c run(...).603 ///The simplest way to execute the algorithm is to use one of the 604 ///member functions called \ref lemon::Dijkstra::run() "run()". 579 605 ///\n 580 ///If you need more control on the execution, 581 /// first you must call \ref init(), then you can add several source nodes582 /// with \ref addSource().583 ///Finally \ref start() will perform the actual path584 /// computation.606 ///If you need more control on the execution, first you must call 607 ///\ref lemon::Dijkstra::init() "init()", then you can add several 608 ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()". 609 ///Finally \ref lemon::Dijkstra::start() "start()" will perform the 610 ///actual path computation. 585 611 586 612 ///@{ … … 604 630 605 631 ///Adds a new source node to the priority heap. 606 ///607 632 ///The optional second parameter is the initial distance of the node. 608 633 /// 609 /// Itchecks if the node has already been added to the heap and634 ///The function checks if the node has already been added to the heap and 610 635 ///it is pushed to the heap only if either it was not in the heap 611 636 ///or the shortest path found till then is shorter than \c dst. … … 626 651 ///\return The processed node. 627 652 /// 628 ///\warning The priority heap must not be empty !653 ///\warning The priority heap must not be empty. 629 654 Node processNextNode() 630 655 { … … 657 682 } 658 683 659 ///Next node to be processed. 660 661 ///Next node to be processed. 662 /// 663 ///\return The next node to be processed or INVALID if the priority heap 664 /// is empty. 665 Node nextNode() 684 ///The next node to be processed. 685 686 ///Returns the next node to be processed or \c INVALID if the 687 ///priority heap is empty. 688 Node nextNode() const 666 689 { 667 690 return !_heap>empty()?_heap>top():INVALID; … … 669 692 670 693 ///\brief Returns \c false if there are nodes 671 ///to be processed in the priority heap694 ///to be processed. 672 695 /// 673 696 ///Returns \c false if there are nodes 674 ///to be processed in the priority heap 675 bool emptyQueue() { return _heap>empty(); } 697 ///to be processed in the priority heap. 698 bool emptyQueue() const { return _heap>empty(); } 699 676 700 ///Returns the number of the nodes to be processed in the priority heap 677 701 678 ///Returns the number of the nodes to be processed in the priority heap 679 /// 680 int queueSize() { return _heap>size(); }702 ///Returns the number of the nodes to be processed in the priority heap. 703 /// 704 int queueSize() const { return _heap>size(); } 681 705 682 706 ///Executes the algorithm. … … 684 708 ///Executes the algorithm. 685 709 /// 686 ///\pre init() must be called and at least one node should be added687 ///with addSource() before using this function.688 ///689 710 ///This method runs the %Dijkstra algorithm from the root node(s) 690 ///in order to 691 ///compute the 692 ///shortest path to each node. The algorithm computes 693 /// The shortest path tree. 694 /// The distance of each node from the root(s). 695 /// 711 ///in order to compute the shortest path to each node. 712 /// 713 ///The algorithm computes 714 /// the shortest path tree (forest), 715 /// the distance of each node from the root(s). 716 /// 717 ///\pre init() must be called and at least one root node should be 718 ///added with addSource() before using this function. 719 /// 720 ///\note <tt>d.start()</tt> is just a shortcut of the following code. 721 ///\code 722 /// while ( !d.emptyQueue() ) { 723 /// d.processNextNode(); 724 /// } 725 ///\endcode 696 726 void start() 697 727 { 698 while ( !_heap>empty() ) processNextNode(); 699 } 700 701 ///Executes the algorithm until \c dest is reached. 702 703 ///Executes the algorithm until \c dest is reached. 704 /// 705 ///\pre init() must be called and at least one node should be added 706 ///with addSource() before using this function. 728 while ( !emptyQueue() ) processNextNode(); 729 } 730 731 ///Executes the algorithm until the given target node is reached. 732 733 ///Executes the algorithm until the given target node is reached. 707 734 /// 708 735 ///This method runs the %Dijkstra algorithm from the root node(s) 709 ///in order to 710 ///compute the 711 ///shortest path to \c dest. The algorithm computes 712 /// The shortest path to \c dest. 713 /// The distance of \c dest from the root(s). 714 /// 736 ///in order to compute the shortest path to \c dest. 737 /// 738 ///The algorithm computes 739 /// the shortest path to \c dest, 740 /// the distance of \c dest from the root(s). 741 /// 742 ///\pre init() must be called and at least one root node should be 743 ///added with addSource() before using this function. 715 744 void start(Node dest) 716 745 { … … 723 752 ///Executes the algorithm until a condition is met. 724 753 /// 725 ///\pre init() must be called and at least one node should be added 726 ///with addSource() before using this function. 727 /// 728 ///\param nm must be a bool (or convertible) node map. The algorithm 754 ///This method runs the %Dijkstra algorithm from the root node(s) in 755 ///order to compute the shortest path to a node \c v with 756 /// <tt>nm[v]</tt> true, if such a node can be found. 757 /// 758 ///\param nm A \c bool (or convertible) node map. The algorithm 729 759 ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true. 730 760 /// 731 761 ///\return The reached node \c v with <tt>nm[v]</tt> true or 732 762 ///\c INVALID if no such node was found. 763 /// 764 ///\pre init() must be called and at least one root node should be 765 ///added with addSource() before using this function. 733 766 template<class NodeBoolMap> 734 767 Node start(const NodeBoolMap &nm) … … 740 773 } 741 774 742 ///Runs %Dijkstra algorithm from node \c s.743 744 ///This method runs the %Dijkstra algorithm from a rootnode \c s745 ///in order to 746 /// compute the747 /// shortest path to each node.The algorithm computes748 /// The shortest path tree.749 /// The distance of each node from the root.750 /// 751 ///\note d.run(s)is just a shortcut of the following code.775 ///Runs the algorithm from the given node. 776 777 ///This method runs the %Dijkstra algorithm from node \c s 778 ///in order to compute the shortest path to each node. 779 /// 780 ///The algorithm computes 781 /// the shortest path tree, 782 /// the distance of each node from the root. 783 /// 784 ///\note <tt>d.run(s)</tt> is just a shortcut of the following code. 752 785 ///\code 753 786 /// d.init(); … … 763 796 ///Finds the shortest path between \c s and \c t. 764 797 765 ///Finds the shortest path between \c s and \c t. 766 /// 767 ///\return The length of the shortest st path if there exists one, 768 ///0 otherwise. 769 ///\note Apart from the return value, d.run(s) is 770 ///just a shortcut of the following code. 798 ///This method runs the %Dijkstra algorithm from node \c s 799 ///in order to compute the shortest path to \c t. 800 /// 801 ///\return The length of the shortest <tt>s</tt><tt>t</tt> path, 802 ///if \c t is reachable form \c s, \c 0 otherwise. 803 /// 804 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a 805 ///shortcut of the following code. 771 806 ///\code 772 807 /// d.init(); … … 786 821 ///The result of the %Dijkstra algorithm can be obtained using these 787 822 ///functions.\n 788 ///Before the use of these functions, 789 ///either run() or start() must be called. 823 ///Either \ref lemon::Dijkstra::run() "run()" or 824 ///\ref lemon::Dijkstra::start() "start()" must be called before 825 ///using them. 790 826 791 827 ///@{ 792 828 793 ///Gives back the shortest path. 794 795 ///Gives back the shortest path. 796 ///\pre The \c t should be reachable from the source. 797 Path path(Node t) 798 { 799 return Path(*G, *_pred, t); 800 } 801 802 ///The distance of a node from the root. 803 804 ///Returns the distance of a node from the root. 805 ///\pre \ref run() must be called before using this function. 806 ///\warning If node \c v in unreachable from the root the return value 807 ///of this funcion is undefined. 829 ///The shortest path to a node. 830 831 ///Returns the shortest path to a node. 832 /// 833 ///\warning \c t should be reachable from the root(s). 834 /// 835 ///\pre Either \ref run() or \ref start() must be called before 836 ///using this function. 837 Path path(Node t) const { return Path(*G, *_pred, t); } 838 839 ///The distance of a node from the root(s). 840 841 ///Returns the distance of a node from the root(s). 842 /// 843 ///\warning If node \c v is not reachable from the root(s), then 844 ///the return value of this function is undefined. 845 /// 846 ///\pre Either \ref run() or \ref start() must be called before 847 ///using this function. 808 848 Value dist(Node v) const { return (*_dist)[v]; } 809 849 810 ///The current distance of a node from the root. 811 812 ///Returns the current distance of a node from the root. 813 ///It may be decreased in the following processes. 814 ///\pre \c node should be reached but not processed 815 Value currentDist(Node v) const { return (*_heap)[v]; } 816 817 ///Returns the 'previous arc' of the shortest path tree. 818 819 ///For a node \c v it returns the 'previous arc' of the shortest path tree, 820 ///i.e. it returns the last arc of a shortest path from the root to \c 821 ///v. It is \ref INVALID 822 ///if \c v is unreachable from the root or if \c v=s. The 823 ///shortest path tree used here is equal to the shortest path tree used in 824 ///\ref predNode(). \pre \ref run() must be called before using 825 ///this function. 850 ///Returns the 'previous arc' of the shortest path tree for a node. 851 852 ///This function returns the 'previous arc' of the shortest path 853 ///tree for the node \c v, i.e. it returns the last arc of a 854 ///shortest path from the root(s) to \c v. It is \c INVALID if \c v 855 ///is not reachable from the root(s) or if \c v is a root. 856 /// 857 ///The shortest path tree used here is equal to the shortest path 858 ///tree used in \ref predNode(). 859 /// 860 ///\pre Either \ref run() or \ref start() must be called before 861 ///using this function. 826 862 Arc predArc(Node v) const { return (*_pred)[v]; } 827 863 828 ///Returns the 'previous node' of the shortest path tree. 829 830 ///For a node \c v it returns the 'previous node' of the shortest path tree, 831 ///i.e. it returns the last but one node from a shortest path from the 832 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if 833 ///\c v=s. The shortest path tree used here is equal to the shortest path 834 ///tree used in \ref predArc(). \pre \ref run() must be called before 864 ///Returns the 'previous node' of the shortest path tree for a node. 865 866 ///This function returns the 'previous node' of the shortest path 867 ///tree for the node \c v, i.e. it returns the last but one node 868 ///from a shortest path from the root(s) to \c v. It is \c INVALID 869 ///if \c v is not reachable from the root(s) or if \c v is a root. 870 /// 871 ///The shortest path tree used here is equal to the shortest path 872 ///tree used in \ref predArc(). 873 /// 874 ///\pre Either \ref run() or \ref start() must be called before 835 875 ///using this function. 836 876 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 837 877 G>source((*_pred)[v]); } 838 878 839 ///Returns a reference to the NodeMap of distances. 840 841 ///Returns a reference to the NodeMap of distances. \pre \ref run() must 842 ///be called before using this function. 879 ///\brief Returns a const reference to the node map that stores the 880 ///distances of the nodes. 881 /// 882 ///Returns a const reference to the node map that stores the distances 883 ///of the nodes calculated by the algorithm. 884 /// 885 ///\pre Either \ref run() or \ref init() 886 ///must be called before using this function. 843 887 const DistMap &distMap() const { return *_dist;} 844 888 845 ///Returns a reference to the shortest path tree map. 846 847 ///Returns a reference to the NodeMap of the arcs of the 848 ///shortest path tree. 849 ///\pre \ref run() must be called before using this function. 889 ///\brief Returns a const reference to the node map that stores the 890 ///predecessor arcs. 891 /// 892 ///Returns a const reference to the node map that stores the predecessor 893 ///arcs, which form the shortest path tree. 894 /// 895 ///\pre Either \ref run() or \ref init() 896 ///must be called before using this function. 850 897 const PredMap &predMap() const { return *_pred;} 851 898 852 ///Checks if a node is reachable from the root .853 854 ///Returns \c true if \c v is reachable from the root .855 ///\ warning The source nodes are inditated as unreached.856 /// \pre \ref run()must be called before using this function.857 ///858 bool reached(Node v) { return (*_heap_cross_ref)[v] !=Heap::PRE_HEAP; }899 ///Checks if a node is reachable from the root(s). 900 901 ///Returns \c true if \c v is reachable from the root(s). 902 ///\pre Either \ref run() or \ref start() 903 ///must be called before using this function. 904 bool reached(Node v) const { return (*_heap_cross_ref)[v] != 905 Heap::PRE_HEAP; } 859 906 860 907 ///Checks if a node is processed. … … 862 909 ///Returns \c true if \c v is processed, i.e. the shortest 863 910 ///path to \c v has already found. 864 ///\pre \ref run() must be called before using this function. 865 /// 866 bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; } 911 ///\pre Either \ref run() or \ref start() 912 ///must be called before using this function. 913 bool processed(Node v) const { return (*_heap_cross_ref)[v] == 914 Heap::POST_HEAP; } 915 916 ///The current distance of a node from the root(s). 917 918 ///Returns the current distance of a node from the root(s). 919 ///It may be decreased in the following processes. 920 ///\pre \c v should be reached but not processed. 921 Value currentDist(Node v) const { return (*_heap)[v]; } 867 922 868 923 ///@} … … 870 925 871 926 872 873 874 875 ///Default traits class of Dijkstra function. 876 877 ///Default traits class of Dijkstra function. 878 ///\tparam GR Digraph type. 879 ///\tparam LM Type of length map. 927 ///Default traits class of dijkstra() function. 928 929 ///Default traits class of dijkstra() function. 930 ///\tparam GR The type of the digraph. 931 ///\tparam LM The type of the length map. 880 932 template<class GR, class LM> 881 933 struct DijkstraWizardDefaultTraits 882 934 { 883 ///The digraph typethe algorithm runs on.935 ///The type of the digraph the algorithm runs on. 884 936 typedef GR Digraph; 885 937 ///The type of the map that stores the arc lengths. … … 888 940 ///It must meet the \ref concepts::ReadMap "ReadMap" concept. 889 941 typedef LM LengthMap; 890 // The type of the length of the arcs.942 ///The type of the length of the arcs. 891 943 typedef typename LM::Value Value; 944 892 945 /// Operation traits for Dijkstra algorithm. 893 946 894 /// It defines the used operation bythe algorithm.947 /// This class defines the operations that are used in the algorithm. 895 948 /// \see DijkstraDefaultOperationTraits 896 949 typedef DijkstraDefaultOperationTraits<Value> OperationTraits; 897 ///The heap type used by Dijkstra algorithm. 898 899 /// The cross reference type used by heap. 900 901 /// The cross reference type used by heap. 950 951 /// The cross reference type used by the heap. 952 953 /// The cross reference type used by the heap. 902 954 /// Usually it is \c Digraph::NodeMap<int>. 903 955 typedef typename Digraph::template NodeMap<int> HeapCrossRef; 904 ///Instantiates a HeapCrossRef.956 ///Instantiates a \ref HeapCrossRef. 905 957 906 958 ///This function instantiates a \ref HeapCrossRef. 907 /// \param Gis the digraph, to which we would like to define the959 /// \param g is the digraph, to which we would like to define the 908 960 /// HeapCrossRef. 909 961 /// \todo The digraph alone may be insufficient for the initialization 910 static HeapCrossRef *createHeapCrossRef(const GR &G)911 { 912 return new HeapCrossRef( G);913 } 914 915 ///The heap type used by Dijkstra algorithm.916 917 ///The heap type used by Dijkstra algorithm.962 static HeapCrossRef *createHeapCrossRef(const Digraph &g) 963 { 964 return new HeapCrossRef(g); 965 } 966 967 ///The heap type used by the Dijkstra algorithm. 968 969 ///The heap type used by the Dijkstra algorithm. 918 970 /// 919 971 ///\sa BinHeap 920 972 ///\sa Dijkstra 921 typedef BinHeap< typename LM::Value, typename GR::template NodeMap<int>,973 typedef BinHeap<Value, typename Digraph::template NodeMap<int>, 922 974 std::less<Value> > Heap; 923 975 924 static Heap *createHeap(HeapCrossRef& R) 925 { 926 return new Heap(R); 927 } 928 929 ///\brief The type of the map that stores the last 976 ///Instantiates a \ref Heap. 977 978 ///This function instantiates a \ref Heap. 979 /// \param r is the HeapCrossRef which is used. 980 static Heap *createHeap(HeapCrossRef& r) 981 { 982 return new Heap(r); 983 } 984 985 ///\brief The type of the map that stores the predecessor 930 986 ///arcs of the shortest paths. 931 987 /// 932 ///The type of the map that stores the last988 ///The type of the map that stores the predecessor 933 989 ///arcs of the shortest paths. 934 990 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 935 /// 936 typedef NullMap <typename GR::Node,typename GR::Arc> PredMap; 937 ///Instantiates a PredMap. 991 typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap; 992 ///Instantiates a \ref PredMap. 938 993 939 994 ///This function instantiates a \ref PredMap. 940 ///\param g is the digraph, to which we would like to define the PredMap. 941 ///\todo The digraph alone may be insufficient for the initialization 995 ///\param g is the digraph, to which we would like to define the 996 ///\ref PredMap. 997 ///\todo The digraph alone may be insufficient to initialize 942 998 #ifdef DOXYGEN 943 static PredMap *createPredMap(const GR&g)999 static PredMap *createPredMap(const Digraph &g) 944 1000 #else 945 static PredMap *createPredMap(const GR&)1001 static PredMap *createPredMap(const Digraph &) 946 1002 #endif 947 1003 { 948 1004 return new PredMap(); 949 1005 } 950 ///The type of the map that stores whether a nodes is processed. 951 952 ///The type of the map that stores whether a nodes is processed. 1006 1007 ///The type of the map that indicates which nodes are processed. 1008 1009 ///The type of the map that indicates which nodes are processed. 953 1010 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 954 1011 ///By default it is a NullMap. … … 957 1014 ///\todo named parameter to set this type, function to read and write. 958 1015 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 959 ///Instantiates a ProcessedMap.1016 ///Instantiates a \ref ProcessedMap. 960 1017 961 1018 ///This function instantiates a \ref ProcessedMap. 962 1019 ///\param g is the digraph, to which 963 ///we would like to define the \ref ProcessedMap 1020 ///we would like to define the \ref ProcessedMap. 964 1021 #ifdef DOXYGEN 965 static ProcessedMap *createProcessedMap(const GR&g)1022 static ProcessedMap *createProcessedMap(const Digraph &g) 966 1023 #else 967 static ProcessedMap *createProcessedMap(const GR&)1024 static ProcessedMap *createProcessedMap(const Digraph &) 968 1025 #endif 969 1026 { 970 1027 return new ProcessedMap(); 971 1028 } 972 ///The type of the map that stores the dists of the nodes. 973 974 ///The type of the map that stores the dists of the nodes. 1029 1030 ///The type of the map that stores the distances of the nodes. 1031 1032 ///The type of the map that stores the distances of the nodes. 975 1033 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 976 /// 977 typedef NullMap<typename Digraph::Node,typename LM::Value> DistMap; 978 ///Instantiates a DistMap. 1034 typedef NullMap<typename Digraph::Node,Value> DistMap; 1035 ///Instantiates a \ref DistMap. 979 1036 980 1037 ///This function instantiates a \ref DistMap. … … 982 1039 ///the \ref DistMap 983 1040 #ifdef DOXYGEN 984 static DistMap *createDistMap(const GR&g)1041 static DistMap *createDistMap(const Digraph &g) 985 1042 #else 986 static DistMap *createDistMap(const GR&)1043 static DistMap *createDistMap(const Digraph &) 987 1044 #endif 988 1045 { … … 991 1048 }; 992 1049 993 /// Default traits used by \ref DijkstraWizard1050 /// Default traits class used by \ref DijkstraWizard 994 1051 995 1052 /// To make it easier to use Dijkstra algorithm 996 /// we have created a wizard class.1053 /// we have created a wizard class. 997 1054 /// This \ref DijkstraWizard class needs default traits, 998 /// as well as the \ref Dijkstra class.1055 /// as well as the \ref Dijkstra class. 999 1056 /// The \ref DijkstraWizardBase is a class to be the default traits of the 1000 1057 /// \ref DijkstraWizard class. … … 1003 1060 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM> 1004 1061 { 1005 1006 1062 typedef DijkstraWizardDefaultTraits<GR,LM> Base; 1007 1063 protected: 1008 // / Type of the nodes in the digraph.1064 //The type of the nodes in the digraph. 1009 1065 typedef typename Base::Digraph::Node Node; 1010 1066 1011 // / Pointer to the underlying digraph.1067 //Pointer to the digraph the algorithm runs on. 1012 1068 void *_g; 1013 // /Pointer to the length map1069 //Pointer to the length map 1014 1070 void *_length; 1015 // /Pointer to the map of predecessors arcs.1071 //Pointer to the map of predecessors arcs. 1016 1072 void *_pred; 1017 // /Pointer to the map of distances.1073 //Pointer to the map of distances. 1018 1074 void *_dist; 1019 // /Pointer to the source node.1075 //Pointer to the source node. 1020 1076 Node _source; 1021 1077 1022 1078 public: 1023 1079 /// Constructor. 1024 1080 … … 1033 1089 /// listed in the parameters list. 1034 1090 /// Others are initiated to 0. 1035 /// \param g is the initial value of \ref _g1036 /// \param l is the initial value of \ref _length1037 /// \param s is the initial value of \ref _source1091 /// \param g The digraph the algorithm runs on. 1092 /// \param l The length map. 1093 /// \param s The source node. 1038 1094 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : 1039 1095 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), … … 1043 1099 }; 1044 1100 1045 /// A class to make the usage of Dijkstra algorithm easier 1046 1047 /// This class is created to make it easier to use Dijkstra algorithm. 1048 /// It uses the functions and features of the plain \ref Dijkstra, 1049 /// but it is much simpler to use it. 1101 /// Auxiliary class for the function type interface of Dijkstra algorithm. 1102 1103 /// This auxiliary class is created to implement the function type 1104 /// interface of \ref Dijkstra algorithm. It uses the functions and features 1105 /// of the plain \ref Dijkstra, but it is much simpler to use it. 1106 /// It should only be used through the \ref dijkstra() function, which makes 1107 /// it easier to use the algorithm. 1050 1108 /// 1051 1109 /// Simplicity means that the way to change the types defined … … 1056 1114 /// the original class by using the :: 1057 1115 /// operator. In the case of \ref DijkstraWizard only 1058 /// a function have to be called and it will1116 /// a function have to be called, and it will 1059 1117 /// return the needed class. 1060 1118 /// 1061 /// It does not have own \ref run method. When its \ref run method is called1062 /// i t initiates a plain \ref Dijkstra class, and calls the \ref1063 /// Dijkstra::runmethod of it.1119 /// It does not have own \ref run() method. When its \ref run() method 1120 /// is called, it initiates a plain \ref Dijkstra object, and calls the 1121 /// \ref Dijkstra::run() method of it. 1064 1122 template<class TR> 1065 1123 class DijkstraWizard : public TR … … 1067 1125 typedef TR Base; 1068 1126 1069 ///The type of the underlying digraph.1127 ///The type of the digraph the algorithm runs on. 1070 1128 typedef typename TR::Digraph Digraph; 1071 //\e 1129 1072 1130 typedef typename Digraph::Node Node; 1073 //\e1074 1131 typedef typename Digraph::NodeIt NodeIt; 1075 //\e1076 1132 typedef typename Digraph::Arc Arc; 1077 //\e1078 1133 typedef typename Digraph::OutArcIt OutArcIt; 1079 1134 … … 1082 1137 ///The type of the length of the arcs. 1083 1138 typedef typename LengthMap::Value Value; 1084 ///\brief The type of the map that stores the last1139 ///\brief The type of the map that stores the predecessor 1085 1140 ///arcs of the shortest paths. 1086 1141 typedef typename TR::PredMap PredMap; 1087 ///The type of the map that stores the dist s of the nodes.1142 ///The type of the map that stores the distances of the nodes. 1088 1143 typedef typename TR::DistMap DistMap; 1144 ///The type of the map that indicates which nodes are processed. 1145 typedef typename TR::ProcessedMap ProcessedMap; 1089 1146 ///The heap type used by the dijkstra algorithm. 1090 1147 typedef typename TR::Heap Heap; 1148 1091 1149 public: 1150 1092 1151 /// Constructor. 1093 1152 DijkstraWizard() : TR() {} … … 1105 1164 ~DijkstraWizard() {} 1106 1165 1107 ///Runs Dijkstra algorithm from a givennode.1108 1109 ///Runs Dijkstra algorithm from a givennode.1110 ///The node can be given by the \ref sourcefunction.1166 ///Runs Dijkstra algorithm from a source node. 1167 1168 ///Runs Dijkstra algorithm from a source node. 1169 ///The node can be given with the \ref source() function. 1111 1170 void run() 1112 1171 { … … 1130 1189 } 1131 1190 1191 /// Sets the source node, from which the Dijkstra algorithm runs. 1192 1193 /// Sets the source node, from which the Dijkstra algorithm runs. 1194 /// \param s is the source node. 1195 DijkstraWizard<TR> &source(Node s) 1196 { 1197 Base::_source=s; 1198 return *this; 1199 } 1200 1132 1201 template<class T> 1133 1202 struct DefPredMapBase : public Base { … … 1136 1205 DefPredMapBase(const TR &b) : TR(b) {} 1137 1206 }; 1138 1139 1207 ///\brief \ref namedtemplparam "Named parameter" 1140 ///function for setting PredMap type 1141 /// 1142 /// \ref namedtemplparam "Named parameter" 1143 ///function for setting PredMap type 1144 /// 1208 ///for setting \ref PredMap object. 1209 /// 1210 ///\ref namedtemplparam "Named parameter" 1211 ///for setting \ref PredMap object. 1145 1212 template<class T> 1146 1213 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t) … … 1148 1215 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); 1149 1216 return DijkstraWizard<DefPredMapBase<T> >(*this); 1217 } 1218 1219 template<class T> 1220 struct DefProcessedMapBase : public Base { 1221 typedef T ProcessedMap; 1222 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; 1223 DefProcessedMapBase(const TR &b) : TR(b) {} 1224 }; 1225 ///\brief \ref namedtemplparam "Named parameter" 1226 ///for setting \ref ProcessedMap object. 1227 /// 1228 /// \ref namedtemplparam "Named parameter" 1229 ///for setting \ref ProcessedMap object. 1230 template<class T> 1231 DijkstraWizard<DefProcessedMapBase<T> > processedMap(const T &t) 1232 { 1233 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); 1234 return DijkstraWizard<DefProcessedMapBase<T> >(*this); 1150 1235 } 1151 1236 … … 1156 1241 DefDistMapBase(const TR &b) : TR(b) {} 1157 1242 }; 1158 1159 1243 ///\brief \ref namedtemplparam "Named parameter" 1160 ///function for setting DistMap type 1161 /// 1162 /// \ref namedtemplparam "Named parameter" 1163 ///function for setting DistMap type 1164 /// 1244 ///for setting \ref DistMap object. 1245 /// 1246 ///\ref namedtemplparam "Named parameter" 1247 ///for setting \ref DistMap object. 1165 1248 template<class T> 1166 1249 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t) … … 1168 1251 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1169 1252 return DijkstraWizard<DefDistMapBase<T> >(*this); 1170 }1171 1172 /// Sets the source node, from which the Dijkstra algorithm runs.1173 1174 /// Sets the source node, from which the Dijkstra algorithm runs.1175 /// \param s is the source node.1176 DijkstraWizard<TR> &source(Node s)1177 {1178 Base::_source=s;1179 return *this;1180 1253 } 1181 1254
Note: See TracChangeset
for help on using the changeset viewer.