Changes in lemon/dijkstra.h [412:62f9787c516c:525:9605e051942f] in lemon
- File:
-
- 1 edited
-
lemon/dijkstra.h (modified) (38 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/dijkstra.h
r412 r525 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 74 74 typedef typename LM::Value Value; 75 75 76 /// Operation traits for Dijkstra algorithm.76 /// Operation traits for %Dijkstra algorithm. 77 77 78 78 /// This class defines the operations that are used in the algorithm. … … 85 85 /// Usually it is \c Digraph::NodeMap<int>. 86 86 typedef typename Digraph::template NodeMap<int> HeapCrossRef; 87 ///Instantiates a \ refHeapCrossRef.87 ///Instantiates a \c HeapCrossRef. 88 88 89 89 ///This function instantiates a \ref HeapCrossRef. … … 95 95 } 96 96 97 ///The heap type used by the Dijkstra algorithm.97 ///The heap type used by the %Dijkstra algorithm. 98 98 99 99 ///The heap type used by the Dijkstra algorithm. … … 102 102 ///\sa Dijkstra 103 103 typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap; 104 ///Instantiates a \ refHeap.104 ///Instantiates a \c Heap. 105 105 106 106 ///This function instantiates a \ref Heap. … … 117 117 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 118 118 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 119 ///Instantiates a PredMap.120 121 ///This function instantiates a PredMap.119 ///Instantiates a \c PredMap. 120 121 ///This function instantiates a \ref PredMap. 122 122 ///\param g is the digraph, to which we would like to define the 123 /// PredMap.123 ///\ref PredMap. 124 124 static PredMap *createPredMap(const Digraph &g) 125 125 { … … 133 133 ///By default it is a NullMap. 134 134 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 135 ///Instantiates a ProcessedMap.136 137 ///This function instantiates a ProcessedMap.135 ///Instantiates a \c ProcessedMap. 136 137 ///This function instantiates a \ref ProcessedMap. 138 138 ///\param g is the digraph, to which 139 ///we would like to define the ProcessedMap139 ///we would like to define the \ref ProcessedMap. 140 140 #ifdef DOXYGEN 141 141 static ProcessedMap *createProcessedMap(const Digraph &g) … … 152 152 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 153 153 typedef typename Digraph::template NodeMap<typename LM::Value> DistMap; 154 ///Instantiates a DistMap.155 156 ///This function instantiates a DistMap.154 ///Instantiates a \c DistMap. 155 156 ///This function instantiates a \ref DistMap. 157 157 ///\param g is the digraph, to which we would like to define 158 ///the DistMap158 ///the \ref DistMap. 159 159 static DistMap *createDistMap(const Digraph &g) 160 160 { … … 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> … … 224 217 ///The heap type used by the algorithm. 225 218 typedef typename TR::Heap Heap; 226 ///The operation traits class. 219 ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class" 220 ///of the algorithm. 227 221 typedef typename TR::OperationTraits OperationTraits; 228 222 229 ///The traits class.223 ///The \ref DijkstraDefaultTraits "traits class" of the algorithm. 230 224 typedef TR Traits; 231 225 … … 240 234 const Digraph *G; 241 235 //Pointer to the length map. 242 const LengthMap * length;236 const LengthMap *_length; 243 237 //Pointer to the map of predecessors arcs. 244 238 PredMap *_pred; … … 305 299 }; 306 300 ///\brief \ref named-templ-param "Named parameter" for setting 307 /// PredMap type.301 ///\c PredMap type. 308 302 /// 309 303 ///\ref named-templ-param "Named parameter" for setting 310 ///PredMap type. 304 ///\c PredMap type. 305 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 311 306 template <class T> 312 307 struct SetPredMap … … 325 320 }; 326 321 ///\brief \ref named-templ-param "Named parameter" for setting 327 /// DistMap type.322 ///\c DistMap type. 328 323 /// 329 324 ///\ref named-templ-param "Named parameter" for setting 330 ///DistMap type. 325 ///\c DistMap type. 326 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 331 327 template <class T> 332 328 struct SetDistMap … … 345 341 }; 346 342 ///\brief \ref named-templ-param "Named parameter" for setting 347 /// ProcessedMap type.343 ///\c ProcessedMap type. 348 344 /// 349 345 ///\ref named-templ-param "Named parameter" for setting 350 ///ProcessedMap type. 346 ///\c ProcessedMap type. 347 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 351 348 template <class T> 352 349 struct SetProcessedMap … … 363 360 }; 364 361 ///\brief \ref named-templ-param "Named parameter" for setting 365 /// ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.362 ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 366 363 /// 367 364 ///\ref named-templ-param "Named parameter" for setting 368 /// ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.365 ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 369 366 ///If you don't set it explicitly, it will be automatically allocated. 370 367 struct SetStandardProcessedMap … … 389 386 }; 390 387 ///\brief \ref named-templ-param "Named parameter" for setting 391 ///heap and cross reference type 388 ///heap and cross reference types 392 389 /// 393 390 ///\ref named-templ-param "Named parameter" for setting heap and cross 394 ///reference type. 391 ///reference types. If this named parameter is used, then external 392 ///heap and cross reference objects must be passed to the algorithm 393 ///using the \ref heap() function before calling \ref run(Node) "run()" 394 ///or \ref init(). 395 ///\sa SetStandardHeap 395 396 template <class H, class CR = typename Digraph::template NodeMap<int> > 396 397 struct SetHeap … … 412 413 }; 413 414 ///\brief \ref named-templ-param "Named parameter" for setting 414 ///heap and cross reference type with automatic allocation415 ///heap and cross reference types with automatic allocation 415 416 /// 416 417 ///\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. 418 ///reference types with automatic allocation. 419 ///They should have standard constructor interfaces to be able to 420 ///automatically created by the algorithm (i.e. the digraph should be 421 ///passed to the constructor of the cross reference and the cross 422 ///reference should be passed to the constructor of the heap). 423 ///However external heap and cross reference objects could also be 424 ///passed to the algorithm using the \ref heap() function before 425 ///calling \ref run(Node) "run()" or \ref init(). 426 ///\sa SetHeap 420 427 template <class H, class CR = typename Digraph::template NodeMap<int> > 421 428 struct SetStandardHeap … … 434 441 /// 435 442 ///\ref named-templ-param "Named parameter" for setting 436 ///\ refOperationTraits type.443 ///\c OperationTraits type. 437 444 template <class T> 438 445 struct SetOperationTraits … … 453 460 454 461 ///Constructor. 455 ///\param _g The digraph the algorithm runs on.456 ///\param _length The length map used by the algorithm.457 Dijkstra(const Digraph& _g, const LengthMap& _length) :458 G(& _g), length(&_length),462 ///\param g The digraph the algorithm runs on. 463 ///\param length The length map used by the algorithm. 464 Dijkstra(const Digraph& g, const LengthMap& length) : 465 G(&g), _length(&length), 459 466 _pred(NULL), local_pred(false), 460 467 _dist(NULL), local_dist(false), … … 480 487 Dijkstra &lengthMap(const LengthMap &m) 481 488 { 482 length = &m;489 _length = &m; 483 490 return *this; 484 491 } … … 487 494 488 495 ///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. 496 ///If you don't use this function before calling \ref run(Node) "run()" 497 ///or \ref init(), an instance will be allocated automatically. 498 ///The destructor deallocates this automatically allocated map, 499 ///of course. 492 500 ///\return <tt> (*this) </tt> 493 501 Dijkstra &predMap(PredMap &m) … … 504 512 505 513 ///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. 514 ///If you don't use this function before calling \ref run(Node) "run()" 515 ///or \ref init(), an instance will be allocated automatically. 516 ///The destructor deallocates this automatically allocated map, 517 ///of course. 509 518 ///\return <tt> (*this) </tt> 510 519 Dijkstra &processedMap(ProcessedMap &m) … … 522 531 ///Sets the map that stores the distances of the nodes calculated by the 523 532 ///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. 533 ///If you don't use this function before calling \ref run(Node) "run()" 534 ///or \ref init(), an instance will be allocated automatically. 535 ///The destructor deallocates this automatically allocated map, 536 ///of course. 527 537 ///\return <tt> (*this) </tt> 528 538 Dijkstra &distMap(DistMap &m) … … 539 549 540 550 ///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. 551 ///If you don't use this function before calling \ref run(Node) "run()" 552 ///or \ref init(), heap and cross reference instances will be 553 ///allocated automatically. 554 ///The destructor deallocates these automatically allocated objects, 555 ///of course. 544 556 ///\return <tt> (*this) </tt> 545 557 Dijkstra &heap(Heap& hp, HeapCrossRef &cr) … … 568 580 public: 569 581 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. 582 ///\name Execution Control 583 ///The simplest way to execute the %Dijkstra algorithm is to use 584 ///one of the member functions called \ref run(Node) "run()".\n 585 ///If you need more control on the execution, first you have to call 586 ///\ref init(), then you can add several source nodes with 587 ///\ref addSource(). Finally the actual path computation can be 588 ///performed with one of the \ref start() functions. 579 589 580 590 ///@{ 581 591 592 ///\brief Initializes the internal data structures. 593 /// 582 594 ///Initializes the internal data structures. 583 584 ///Initializes the internal data structures.585 ///586 595 void init() 587 596 { … … 631 640 switch(_heap->state(w)) { 632 641 case Heap::PRE_HEAP: 633 _heap->push(w,OperationTraits::plus(oldvalue, (* length)[e]));642 _heap->push(w,OperationTraits::plus(oldvalue, (*_length)[e])); 634 643 _pred->set(w,e); 635 644 break; 636 645 case Heap::IN_HEAP: 637 646 { 638 Value newvalue = OperationTraits::plus(oldvalue, (* length)[e]);647 Value newvalue = OperationTraits::plus(oldvalue, (*_length)[e]); 639 648 if ( OperationTraits::less(newvalue, (*_heap)[w]) ) { 640 649 _heap->decrease(w, newvalue); … … 659 668 } 660 669 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. 670 ///Returns \c false if there are nodes to be processed. 671 672 ///Returns \c false if there are nodes to be processed 673 ///in the priority heap. 666 674 bool emptyQueue() const { return _heap->empty(); } 667 675 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 /// 676 ///Returns the number of the nodes to be processed. 677 678 ///Returns the number of the nodes to be processed 679 ///in the priority heap. 672 680 int queueSize() const { return _heap->size(); } 673 681 … … 790 798 791 799 ///\name Query Functions 792 ///The result of the %Dijkstra algorithm can be obtained using these800 ///The results of the %Dijkstra algorithm can be obtained using these 793 801 ///functions.\n 794 ///Either \ref lemon::Dijkstra::run() "run()" or 795 ///\ref lemon::Dijkstra::start() "start()" must be called before 796 ///using them. 802 ///Either \ref run(Node) "run()" or \ref start() should be called 803 ///before using them. 797 804 798 805 ///@{ … … 802 809 ///Returns the shortest path to a node. 803 810 /// 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.811 ///\warning \c t should be reached from the root(s). 812 /// 813 ///\pre Either \ref run(Node) "run()" or \ref init() 814 ///must be called before using this function. 808 815 Path path(Node t) const { return Path(*G, *_pred, t); } 809 816 … … 812 819 ///Returns the distance of a node from the root(s). 813 820 /// 814 ///\warning If node \c v is not reach ablefrom the root(s), then821 ///\warning If node \c v is not reached from the root(s), then 815 822 ///the return value of this function is undefined. 816 823 /// 817 ///\pre Either \ref run( ) or \ref start() must be called before818 /// using this function.824 ///\pre Either \ref run(Node) "run()" or \ref init() 825 ///must be called before using this function. 819 826 Value dist(Node v) const { return (*_dist)[v]; } 820 827 … … 823 830 ///This function returns the 'previous arc' of the shortest path 824 831 ///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.832 ///shortest path from a root to \c v. It is \c INVALID if \c v 833 ///is not reached from the root(s) or if \c v is a root. 827 834 /// 828 835 ///The shortest path tree used here is equal to the shortest path 829 836 ///tree used in \ref predNode(). 830 837 /// 831 ///\pre Either \ref run( ) or \ref start() must be called before832 /// using this function.838 ///\pre Either \ref run(Node) "run()" or \ref init() 839 ///must be called before using this function. 833 840 Arc predArc(Node v) const { return (*_pred)[v]; } 834 841 … … 837 844 ///This function returns the 'previous node' of the shortest path 838 845 ///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.846 ///from a shortest path from a root to \c v. It is \c INVALID 847 ///if \c v is not reached from the root(s) or if \c v is a root. 841 848 /// 842 849 ///The shortest path tree used here is equal to the shortest path 843 850 ///tree used in \ref predArc(). 844 851 /// 845 ///\pre Either \ref run( ) or \ref start() must be called before846 /// using this function.852 ///\pre Either \ref run(Node) "run()" or \ref init() 853 ///must be called before using this function. 847 854 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 848 855 G->source((*_pred)[v]); } … … 854 861 ///of the nodes calculated by the algorithm. 855 862 /// 856 ///\pre Either \ref run( )or \ref init()863 ///\pre Either \ref run(Node) "run()" or \ref init() 857 864 ///must be called before using this function. 858 865 const DistMap &distMap() const { return *_dist;} … … 864 871 ///arcs, which form the shortest path tree. 865 872 /// 866 ///\pre Either \ref run( )or \ref init()873 ///\pre Either \ref run(Node) "run()" or \ref init() 867 874 ///must be called before using this function. 868 875 const PredMap &predMap() const { return *_pred;} 869 876 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() 877 ///Checks if a node is reached from the root(s). 878 879 ///Returns \c true if \c v is reached from the root(s). 880 /// 881 ///\pre Either \ref run(Node) "run()" or \ref init() 874 882 ///must be called before using this function. 875 883 bool reached(Node v) const { return (*_heap_cross_ref)[v] != … … 880 888 ///Returns \c true if \c v is processed, i.e. the shortest 881 889 ///path to \c v has already found. 882 ///\pre Either \ref run() or \ref init() 890 /// 891 ///\pre Either \ref run(Node) "run()" or \ref init() 883 892 ///must be called before using this function. 884 893 bool processed(Node v) const { return (*_heap_cross_ref)[v] == … … 889 898 ///Returns the current distance of a node from the root(s). 890 899 ///It may be decreased in the following processes. 891 ///\pre Either \ref run() or \ref init() 900 /// 901 ///\pre Either \ref run(Node) "run()" or \ref init() 892 902 ///must be called before using this function and 893 903 ///node \c v must be reached but not necessarily processed. … … 1072 1082 /// This auxiliary class is created to implement the 1073 1083 /// \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.1084 /// It does not have own \ref run(Node) "run()" method, it uses the 1085 /// functions and features of the plain \ref Dijkstra. 1076 1086 /// 1077 1087 /// This class should only be used through the \ref dijkstra() function, … … 1268 1278 /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t); 1269 1279 ///\endcode 1270 ///\warning Don't forget to put the \ref DijkstraWizard::run( ) "run()"1280 ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()" 1271 1281 ///to the end of the parameter list. 1272 1282 ///\sa DijkstraWizard
Note: See TracChangeset
for help on using the changeset viewer.
