Changeset 424:69f33ef03334 in lemon
- Timestamp:
- 12/02/08 11:31:20 (16 years ago)
- Branch:
- default
- Parents:
- 423:e22fc10ab6f1 (diff), 421:6b9057cdcd8b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent. - Phase:
- public
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/dijkstra.h
r421 r424 48 48 static Value plus(const Value& left, const Value& right) { 49 49 return left + right; 50 }51 /// \brief Gives back true only if the first value is less than the second.52 static bool less(const Value& left, const Value& right) {53 return left < right;54 }55 };56 57 /// \brief Widest path operation traits for the Dijkstra algorithm class.58 ///59 /// This operation traits class defines all computational operations and60 /// constants which are used in the Dijkstra algorithm for widest path61 /// computation.62 ///63 /// \see DijkstraDefaultOperationTraits64 template <typename Value>65 struct DijkstraWidestPathOperationTraits {66 /// \brief Gives back the maximum value of the type.67 static Value zero() {68 return std::numeric_limits<Value>::max();69 }70 /// \brief Gives back the minimum of the given two elements.71 static Value plus(const Value& left, const Value& right) {72 return std::min(left, right);73 50 } 74 51 /// \brief Gives back true only if the first value is less than the second. -
lemon/dijkstra.h
r412 r424 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.