Changes in lemon/dijkstra.h [313:64f8f7cc6168:463:88ed40ad0d4f] in lemon
- File:
-
- 1 edited
-
lemon/dijkstra.h (modified) (26 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/dijkstra.h
r313 r463 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). … … 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. … … 203 180 /// 204 181 ///\tparam GR The type of the digraph the algorithm runs on. 205 ///The default value is \ref ListDigraph. 206 ///The value of GR is not used directly by \ref Dijkstra, it is only 207 ///passed to \ref DijkstraDefaultTraits. 208 ///\tparam LM A readable arc map that determines the lengths of the 209 ///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 210 186 ///relatively time consuming process to compute the arc lengths if 211 187 ///it is necessary. The default map type is \ref 212 ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>". 213 ///The value of LM is not used directly by \ref Dijkstra, it is only 214 ///passed to \ref DijkstraDefaultTraits. 215 ///\tparam TR Traits class to set various data types used by the algorithm. 216 ///The default traits class is \ref DijkstraDefaultTraits 217 ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits 218 ///for the documentation of a Dijkstra traits class. 188 ///concepts::Digraph::ArcMap "GR::ArcMap<int>". 219 189 #ifdef DOXYGEN 220 190 template <typename GR, typename LM, typename TR> … … 250 220 typedef typename TR::OperationTraits OperationTraits; 251 221 252 ///The traits class.222 ///The \ref DijkstraDefaultTraits "traits class" of the algorithm. 253 223 typedef TR Traits; 254 224 … … 332 302 ///\ref named-templ-param "Named parameter" for setting 333 303 ///PredMap type. 304 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 334 305 template <class T> 335 306 struct SetPredMap … … 352 323 ///\ref named-templ-param "Named parameter" for setting 353 324 ///DistMap type. 325 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 354 326 template <class T> 355 327 struct SetDistMap … … 372 344 ///\ref named-templ-param "Named parameter" for setting 373 345 ///ProcessedMap type. 346 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 374 347 template <class T> 375 348 struct SetProcessedMap … … 412 385 }; 413 386 ///\brief \ref named-templ-param "Named parameter" for setting 414 ///heap and cross reference type 387 ///heap and cross reference types 415 388 /// 416 389 ///\ref named-templ-param "Named parameter" for setting heap and cross 417 ///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 418 395 template <class H, class CR = typename Digraph::template NodeMap<int> > 419 396 struct SetHeap … … 435 412 }; 436 413 ///\brief \ref named-templ-param "Named parameter" for setting 437 ///heap and cross reference type with automatic allocation414 ///heap and cross reference types with automatic allocation 438 415 /// 439 416 ///\ref named-templ-param "Named parameter" for setting heap and cross 440 ///reference type. It can allocate the heap and the cross reference 441 ///object if the cross reference's constructor waits for the digraph as 442 ///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 443 426 template <class H, class CR = typename Digraph::template NodeMap<int> > 444 427 struct SetStandardHeap … … 510 493 511 494 ///Sets the map that stores the predecessor arcs. 512 ///If you don't use this function before calling \ref run(), 513 ///it will allocate one. The destructor deallocates this 514 ///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. 515 499 ///\return <tt> (*this) </tt> 516 500 Dijkstra &predMap(PredMap &m) … … 527 511 528 512 ///Sets the map that indicates which nodes are processed. 529 ///If you don't use this function before calling \ref run(), 530 ///it will allocate one. The destructor deallocates this 531 ///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. 532 517 ///\return <tt> (*this) </tt> 533 518 Dijkstra &processedMap(ProcessedMap &m) … … 545 530 ///Sets the map that stores the distances of the nodes calculated by the 546 531 ///algorithm. 547 ///If you don't use this function before calling \ref run(), 548 ///it will allocate one. The destructor deallocates this 549 ///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. 550 536 ///\return <tt> (*this) </tt> 551 537 Dijkstra &distMap(DistMap &m) … … 562 548 563 549 ///Sets the heap and the cross reference used by algorithm. 564 ///If you don't use this function before calling \ref run(), 565 ///it will allocate one. The destructor deallocates this 566 ///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. 567 555 ///\return <tt> (*this) </tt> 568 556 Dijkstra &heap(Heap& hp, HeapCrossRef &cr) … … 591 579 public: 592 580 593 ///\name Execution control 594 ///The simplest way to execute the algorithm is to use one of the 595 ///member functions called \ref lemon::Dijkstra::run() "run()". 596 ///\n 597 ///If you need more control on the execution, first you must call 598 ///\ref lemon::Dijkstra::init() "init()", then you can add several 599 ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()". 600 ///Finally \ref lemon::Dijkstra::start() "start()" will perform the 601 ///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. 602 588 603 589 ///@{ 604 590 591 ///\brief Initializes the internal data structures. 592 /// 605 593 ///Initializes the internal data structures. 606 607 ///Initializes the internal data structures.608 ///609 594 void init() 610 595 { … … 682 667 } 683 668 684 ///\brief Returns \c false if there are nodes 685 ///to be processed. 686 /// 687 ///Returns \c false if there are nodes 688 ///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. 689 673 bool emptyQueue() const { return _heap->empty(); } 690 674 691 ///Returns the number of the nodes to be processed in the priority heap692 693 ///Returns the number of the nodes to be processed in the priority heap.694 /// 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. 695 679 int queueSize() const { return _heap->size(); } 696 680 … … 813 797 814 798 ///\name Query Functions 815 ///The result of the %Dijkstra algorithm can be obtained using these799 ///The results of the %Dijkstra algorithm can be obtained using these 816 800 ///functions.\n 817 ///Either \ref lemon::Dijkstra::run() "run()" or 818 ///\ref lemon::Dijkstra::start() "start()" must be called before 819 ///using them. 801 ///Either \ref run(Node) "run()" or \ref start() should be called 802 ///before using them. 820 803 821 804 ///@{ … … 825 808 ///Returns the shortest path to a node. 826 809 /// 827 ///\warning \c t should be reach ablefrom the root(s).828 /// 829 ///\pre Either \ref run( ) or \ref start() must be called before830 /// 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. 831 814 Path path(Node t) const { return Path(*G, *_pred, t); } 832 815 … … 835 818 ///Returns the distance of a node from the root(s). 836 819 /// 837 ///\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 838 821 ///the return value of this function is undefined. 839 822 /// 840 ///\pre Either \ref run( ) or \ref start() must be called before841 /// using this function.823 ///\pre Either \ref run(Node) "run()" or \ref init() 824 ///must be called before using this function. 842 825 Value dist(Node v) const { return (*_dist)[v]; } 843 826 … … 846 829 ///This function returns the 'previous arc' of the shortest path 847 830 ///tree for the node \c v, i.e. it returns the last arc of a 848 ///shortest path from the root(s)to \c v. It is \c INVALID if \c v849 ///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. 850 833 /// 851 834 ///The shortest path tree used here is equal to the shortest path 852 835 ///tree used in \ref predNode(). 853 836 /// 854 ///\pre Either \ref run( ) or \ref start() must be called before855 /// using this function.837 ///\pre Either \ref run(Node) "run()" or \ref init() 838 ///must be called before using this function. 856 839 Arc predArc(Node v) const { return (*_pred)[v]; } 857 840 … … 860 843 ///This function returns the 'previous node' of the shortest path 861 844 ///tree for the node \c v, i.e. it returns the last but one node 862 ///from a shortest path from the root(s)to \c v. It is \c INVALID863 ///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. 864 847 /// 865 848 ///The shortest path tree used here is equal to the shortest path 866 849 ///tree used in \ref predArc(). 867 850 /// 868 ///\pre Either \ref run( ) or \ref start() must be called before869 /// using this function.851 ///\pre Either \ref run(Node) "run()" or \ref init() 852 ///must be called before using this function. 870 853 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 871 854 G->source((*_pred)[v]); } … … 877 860 ///of the nodes calculated by the algorithm. 878 861 /// 879 ///\pre Either \ref run( )or \ref init()862 ///\pre Either \ref run(Node) "run()" or \ref init() 880 863 ///must be called before using this function. 881 864 const DistMap &distMap() const { return *_dist;} … … 887 870 ///arcs, which form the shortest path tree. 888 871 /// 889 ///\pre Either \ref run( )or \ref init()872 ///\pre Either \ref run(Node) "run()" or \ref init() 890 873 ///must be called before using this function. 891 874 const PredMap &predMap() const { return *_pred;} 892 875 893 ///Checks if a node is reachable from the root(s). 894 895 ///Returns \c true if \c v is reachable from the root(s). 896 ///\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() 897 881 ///must be called before using this function. 898 882 bool reached(Node v) const { return (*_heap_cross_ref)[v] != … … 903 887 ///Returns \c true if \c v is processed, i.e. the shortest 904 888 ///path to \c v has already found. 905 ///\pre Either \ref run() or \ref init() 889 /// 890 ///\pre Either \ref run(Node) "run()" or \ref init() 906 891 ///must be called before using this function. 907 892 bool processed(Node v) const { return (*_heap_cross_ref)[v] == … … 912 897 ///Returns the current distance of a node from the root(s). 913 898 ///It may be decreased in the following processes. 914 ///\pre Either \ref run() or \ref init() 899 /// 900 ///\pre Either \ref run(Node) "run()" or \ref init() 915 901 ///must be called before using this function and 916 902 ///node \c v must be reached but not necessarily processed. … … 1095 1081 /// This auxiliary class is created to implement the 1096 1082 /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm. 1097 /// It does not have own \ref run( ) method, it uses the functions1098 /// 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. 1099 1085 /// 1100 1086 /// This class should only be used through the \ref dijkstra() function, … … 1291 1277 /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t); 1292 1278 ///\endcode 1293 ///\warning Don't forget to put the \ref DijkstraWizard::run( ) "run()"1279 ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()" 1294 1280 ///to the end of the parameter list. 1295 1281 ///\sa DijkstraWizard
Note: See TracChangeset
for help on using the changeset viewer.
