Changeset 287:bb40b6db0a58 in lemon1.2 for lemon/dijkstra.h
 Timestamp:
 09/27/08 14:33:28 (11 years ago)
 Branch:
 default
 Children:
 288:47b3a3b67837, 290:f6899946c1ac
 Parents:
 286:da414906fe21 (diff), 285:d8dc5acf739b (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
r281 r287 725 725 } 726 726 727 ///Executes the algorithm until the given target node is reached.728 729 ///Executes the algorithm until the given target node is reached.727 ///Executes the algorithm until the given target node is processed. 728 729 ///Executes the algorithm until the given target node is processed. 730 730 /// 731 731 ///This method runs the %Dijkstra algorithm from the root node(s) 732 ///in order to compute the shortest path to \c dest.732 ///in order to compute the shortest path to \c t. 733 733 /// 734 734 ///The algorithm computes 735 /// the shortest path to \c dest,736 /// the distance of \c dest from the root(s).735 /// the shortest path to \c t, 736 /// the distance of \c t from the root(s). 737 737 /// 738 738 ///\pre init() must be called and at least one root node should be 739 739 ///added with addSource() before using this function. 740 void start(Node dest) 741 { 742 while ( !_heap>empty() && _heap>top()!=dest ) processNextNode(); 743 if ( !_heap>empty() ) finalizeNodeData(_heap>top(),_heap>prio()); 740 void start(Node t) 741 { 742 while ( !_heap>empty() && _heap>top()!=t ) processNextNode(); 743 if ( !_heap>empty() ) { 744 finalizeNodeData(_heap>top(),_heap>prio()); 745 _heap>pop(); 746 } 744 747 } 745 748 … … 769 772 } 770 773 771 ///Runs the algorithm from the given node.774 ///Runs the algorithm from the given source node. 772 775 773 776 ///This method runs the %Dijkstra algorithm from node \c s … … 793 796 794 797 ///This method runs the %Dijkstra algorithm from node \c s 795 ///in order to compute the shortest path to \c t.796 /// 797 /// \return The length of the shortest <tt>s</tt><tt>t</tt> path,798 /// if \c t is reachable form \c s, \c 0 otherwise.798 ///in order to compute the shortest path to node \c t 799 ///(it stops searching when \c t is processed). 800 /// 801 ///\return \c true if \c t is reachable form \c s. 799 802 /// 800 803 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a … … 805 808 /// d.start(t); 806 809 ///\endcode 807 Valuerun(Node s,Node t) {810 bool run(Node s,Node t) { 808 811 init(); 809 812 addSource(s); 810 813 start(t); 811 return (*_ pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];814 return (*_heap_cross_ref)[t] == Heap::POST_HEAP; 812 815 } 813 816 … … 905 908 ///Returns \c true if \c v is processed, i.e. the shortest 906 909 ///path to \c v has already found. 907 ///\pre Either \ref run() or \ref start()910 ///\pre Either \ref run() or \ref init() 908 911 ///must be called before using this function. 909 912 bool processed(Node v) const { return (*_heap_cross_ref)[v] == … … 914 917 ///Returns the current distance of a node from the root(s). 915 918 ///It may be decreased in the following processes. 916 ///\pre \c v should be reached but not processed. 917 Value currentDist(Node v) const { return (*_heap)[v]; } 919 ///\pre Either \ref run() or \ref init() 920 ///must be called before using this function and 921 ///node \c v must be reached but not necessarily processed. 922 Value currentDist(Node v) const { 923 return processed(v) ? (*_dist)[v] : (*_heap)[v]; 924 } 918 925 919 926 ///@} 
lemon/dijkstra.h
r286 r287 145 145 ///\param g is the digraph, to which we would like to define the 146 146 ///\ref PredMap. 147 ///\todo The digraph alone may be insufficient for the initialization148 147 static PredMap *createPredMap(const Digraph &g) 149 148 { … … 156 155 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 157 156 ///By default it is a NullMap. 158 ///\todo If it is set to a real map,159 ///Dijkstra::processed() should read this.160 157 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 161 158 ///Instantiates a \ref ProcessedMap. … … 298 295 bool local_heap; 299 296 300 ///Creates the maps if necessary. 301 ///\todo Better memory allocation (instead of new). 297 //Creates the maps if necessary. 302 298 void create_maps() 303 299 { … … 966 962 /// \param g is the digraph, to which we would like to define the 967 963 /// HeapCrossRef. 968 /// \todo The digraph alone may be insufficient for the initialization969 964 static HeapCrossRef *createHeapCrossRef(const Digraph &g) 970 965 { … … 1002 997 ///\param g is the digraph, to which we would like to define the 1003 998 ///\ref PredMap. 1004 ///\todo The digraph alone may be insufficient to initialize1005 999 static PredMap *createPredMap(const Digraph &g) 1006 1000 { … … 1013 1007 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 1014 1008 ///By default it is a NullMap. 1015 ///\todo If it is set to a real map,1016 ///Dijkstra::processed() should read this.1017 ///\todo named parameter to set this type, function to read and write.1018 1009 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 1019 1010 ///Instantiates a \ref ProcessedMap. … … 1061 1052 /// The \ref DijkstraWizardBase is a class to be the default traits of the 1062 1053 /// \ref DijkstraWizard class. 1063 /// \todo More named parameters are required...1064 1054 template<class GR,class LM> 1065 1055 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
Note: See TracChangeset
for help on using the changeset viewer.