Changeset 764:684964884a2e in lemon for lemon/dijkstra.h
- Timestamp:
- 09/25/09 09:13:03 (15 years ago)
- Branch:
- default
- Parents:
- 763:f47b6c94577e (diff), 762:ece80147fb08 (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
-
lemon/dijkstra.h (modified) (30 diffs)
-
lemon/dijkstra.h (modified) (1 diff)
Legend:
- Unmodified
- Added
- Removed
-
lemon/dijkstra.h
r760 r764 71 71 72 72 ///The type of the map that stores the arc lengths. 73 ///It must meetthe \ref concepts::ReadMap "ReadMap" concept.73 ///It must conform to the \ref concepts::ReadMap "ReadMap" concept. 74 74 typedef LEN LengthMap; 75 ///The type of the length of the arcs.75 ///The type of the arc lengths. 76 76 typedef typename LEN::Value Value; 77 77 … … 117 117 ///The type of the map that stores the predecessor 118 118 ///arcs of the shortest paths. 119 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.119 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 120 120 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 121 121 ///Instantiates a \c PredMap. … … 132 132 133 133 ///The type of the map that indicates which nodes are processed. 134 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.134 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 135 135 ///By default it is a NullMap. 136 136 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; … … 152 152 153 153 ///The type of the map that stores the distances of the nodes. 154 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.154 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 155 155 typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap; 156 156 ///Instantiates a \c DistMap. … … 169 169 /// \ingroup shortest_path 170 170 ///This class provides an efficient implementation of the %Dijkstra algorithm. 171 /// 172 ///The %Dijkstra algorithm solves the single-source shortest path problem 173 ///when all arc lengths are non-negative. If there are negative lengths, 174 ///the BellmanFord algorithm should be used instead. 171 175 /// 172 176 ///The arc lengths are passed to the algorithm using a … … 202 206 typedef typename TR::Digraph Digraph; 203 207 204 ///The type of the length of the arcs.208 ///The type of the arc lengths. 205 209 typedef typename TR::LengthMap::Value Value; 206 210 ///The type of the map that stores the arc lengths. … … 305 309 ///\ref named-templ-param "Named parameter" for setting 306 310 ///\c PredMap type. 307 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.311 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 308 312 template <class T> 309 313 struct SetPredMap … … 326 330 ///\ref named-templ-param "Named parameter" for setting 327 331 ///\c DistMap type. 328 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.332 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 329 333 template <class T> 330 334 struct SetDistMap … … 347 351 ///\ref named-templ-param "Named parameter" for setting 348 352 ///\c ProcessedMap type. 349 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.353 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 350 354 template <class T> 351 355 struct SetProcessedMap … … 444 448 ///\ref named-templ-param "Named parameter" for setting 445 449 ///\c OperationTraits type. 450 /// For more information see \ref DijkstraDefaultOperationTraits. 446 451 template <class T> 447 452 struct SetOperationTraits … … 802 807 ///The results of the %Dijkstra algorithm can be obtained using these 803 808 ///functions.\n 804 ///Either \ref run(Node) "run()" or \ref start() should be called809 ///Either \ref run(Node) "run()" or \ref init() should be called 805 810 ///before using them. 806 811 807 812 ///@{ 808 813 809 ///The shortest path to anode.810 811 ///Returns the shortest path to a node.814 ///The shortest path to the given node. 815 816 ///Returns the shortest path to the given node from the root(s). 812 817 /// 813 818 ///\warning \c t should be reached from the root(s). … … 817 822 Path path(Node t) const { return Path(*G, *_pred, t); } 818 823 819 ///The distance of anode from the root(s).820 821 ///Returns the distance of anode from the root(s).824 ///The distance of the given node from the root(s). 825 826 ///Returns the distance of the given node from the root(s). 822 827 /// 823 828 ///\warning If node \c v is not reached from the root(s), then … … 828 833 Value dist(Node v) const { return (*_dist)[v]; } 829 834 830 ///Returns the 'previous arc' of the shortest path tree for a node. 831 835 ///\brief Returns the 'previous arc' of the shortest path tree for 836 ///the given node. 837 /// 832 838 ///This function returns the 'previous arc' of the shortest path 833 839 ///tree for the node \c v, i.e. it returns the last arc of a … … 836 842 /// 837 843 ///The shortest path tree used here is equal to the shortest path 838 ///tree used in \ref predNode() .844 ///tree used in \ref predNode() and \ref predMap(). 839 845 /// 840 846 ///\pre Either \ref run(Node) "run()" or \ref init() … … 842 848 Arc predArc(Node v) const { return (*_pred)[v]; } 843 849 844 ///Returns the 'previous node' of the shortest path tree for a node. 845 850 ///\brief Returns the 'previous node' of the shortest path tree for 851 ///the given node. 852 /// 846 853 ///This function returns the 'previous node' of the shortest path 847 854 ///tree for the node \c v, i.e. it returns the last but one node 848 /// froma shortest path from a root to \c v. It is \c INVALID855 ///of a shortest path from a root to \c v. It is \c INVALID 849 856 ///if \c v is not reached from the root(s) or if \c v is a root. 850 857 /// 851 858 ///The shortest path tree used here is equal to the shortest path 852 ///tree used in \ref predArc() .859 ///tree used in \ref predArc() and \ref predMap(). 853 860 /// 854 861 ///\pre Either \ref run(Node) "run()" or \ref init() … … 871 878 /// 872 879 ///Returns a const reference to the node map that stores the predecessor 873 ///arcs, which form the shortest path tree .880 ///arcs, which form the shortest path tree (forest). 874 881 /// 875 882 ///\pre Either \ref run(Node) "run()" or \ref init() … … 877 884 const PredMap &predMap() const { return *_pred;} 878 885 879 ///Checks if anode is reached from the root(s).886 ///Checks if the given node is reached from the root(s). 880 887 881 888 ///Returns \c true if \c v is reached from the root(s). … … 896 903 Heap::POST_HEAP; } 897 904 898 ///The current distance of anode from the root(s).899 900 ///Returns the current distance of anode from the root(s).905 ///The current distance of the given node from the root(s). 906 907 ///Returns the current distance of the given node from the root(s). 901 908 ///It may be decreased in the following processes. 902 909 /// … … 925 932 926 933 ///The type of the map that stores the arc lengths. 927 ///It must meetthe \ref concepts::ReadMap "ReadMap" concept.934 ///It must conform to the \ref concepts::ReadMap "ReadMap" concept. 928 935 typedef LEN LengthMap; 929 ///The type of the length of the arcs.936 ///The type of the arc lengths. 930 937 typedef typename LEN::Value Value; 931 938 … … 974 981 ///The type of the map that stores the predecessor 975 982 ///arcs of the shortest paths. 976 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.983 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 977 984 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 978 985 ///Instantiates a PredMap. … … 989 996 990 997 ///The type of the map that indicates which nodes are processed. 991 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.998 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 992 999 ///By default it is a NullMap. 993 1000 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; … … 1009 1016 1010 1017 ///The type of the map that stores the distances of the nodes. 1011 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.1018 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 1012 1019 typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap; 1013 1020 ///Instantiates a DistMap. … … 1024 1031 1025 1032 ///The type of the shortest paths. 1026 ///It must meetthe \ref concepts::Path "Path" concept.1033 ///It must conform to the \ref concepts::Path "Path" concept. 1027 1034 typedef lemon::Path<Digraph> Path; 1028 1035 }; … … 1030 1037 /// Default traits class used by DijkstraWizard 1031 1038 1032 /// To make it easier to use Dijkstra algorithm 1033 /// we have created a wizard class. 1034 /// This \ref DijkstraWizard class needs default traits, 1035 /// as well as the \ref Dijkstra class. 1036 /// The \ref DijkstraWizardBase is a class to be the default traits of the 1037 /// \ref DijkstraWizard class. 1039 /// Default traits class used by DijkstraWizard. 1040 /// \tparam GR The type of the digraph. 1041 /// \tparam LEN The type of the length map. 1038 1042 template<typename GR, typename LEN> 1039 1043 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN> … … 1094 1098 typedef TR Base; 1095 1099 1096 ///The type of the digraph the algorithm runs on.1097 1100 typedef typename TR::Digraph Digraph; 1098 1101 … … 1102 1105 typedef typename Digraph::OutArcIt OutArcIt; 1103 1106 1104 ///The type of the map that stores the arc lengths.1105 1107 typedef typename TR::LengthMap LengthMap; 1106 ///The type of the length of the arcs.1107 1108 typedef typename LengthMap::Value Value; 1108 ///\brief The type of the map that stores the predecessor1109 ///arcs of the shortest paths.1110 1109 typedef typename TR::PredMap PredMap; 1111 ///The type of the map that stores the distances of the nodes.1112 1110 typedef typename TR::DistMap DistMap; 1113 ///The type of the map that indicates which nodes are processed.1114 1111 typedef typename TR::ProcessedMap ProcessedMap; 1115 ///The type of the shortest paths1116 1112 typedef typename TR::Path Path; 1117 ///The heap type used by the dijkstra algorithm.1118 1113 typedef typename TR::Heap Heap; 1119 1114 … … 1187 1182 SetPredMapBase(const TR &b) : TR(b) {} 1188 1183 }; 1189 ///\brief \ref named-func-param "Named parameter" 1190 ///for setting PredMap object. 1191 /// 1192 ///\ref named-func-param "Named parameter" 1193 ///for setting PredMap object. 1184 1185 ///\brief \ref named-templ-param "Named parameter" for setting 1186 ///the predecessor map. 1187 /// 1188 ///\ref named-templ-param "Named parameter" function for setting 1189 ///the map that stores the predecessor arcs of the nodes. 1194 1190 template<class T> 1195 1191 DijkstraWizard<SetPredMapBase<T> > predMap(const T &t) … … 1205 1201 SetDistMapBase(const TR &b) : TR(b) {} 1206 1202 }; 1207 ///\brief \ref named-func-param "Named parameter" 1208 ///for setting DistMap object. 1209 /// 1210 ///\ref named-func-param "Named parameter" 1211 ///for setting DistMap object. 1203 1204 ///\brief \ref named-templ-param "Named parameter" for setting 1205 ///the distance map. 1206 /// 1207 ///\ref named-templ-param "Named parameter" function for setting 1208 ///the map that stores the distances of the nodes calculated 1209 ///by the algorithm. 1212 1210 template<class T> 1213 1211 DijkstraWizard<SetDistMapBase<T> > distMap(const T &t) … … 1223 1221 SetProcessedMapBase(const TR &b) : TR(b) {} 1224 1222 }; 1225 ///\brief \ref named-func-param "Named parameter" 1226 ///for setting ProcessedMap object. 1227 /// 1228 /// \ref named-func-param "Named parameter" 1229 ///for setting ProcessedMap object. 1223 1224 ///\brief \ref named-func-param "Named parameter" for setting 1225 ///the processed map. 1226 /// 1227 ///\ref named-templ-param "Named parameter" function for setting 1228 ///the map that indicates which nodes are processed. 1230 1229 template<class T> 1231 1230 DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1240 1239 SetPathBase(const TR &b) : TR(b) {} 1241 1240 }; 1241 1242 1242 ///\brief \ref named-func-param "Named parameter" 1243 1243 ///for getting the shortest path to the target node. -
lemon/dijkstra.h
r763 r764 590 590 ///The simplest way to execute the %Dijkstra algorithm is to use 591 591 ///one of the member functions called \ref run(Node) "run()".\n 592 ///If you need more control on the execution, firstyou have to call593 ///\ref init() , then you can add several source nodes with592 ///If you need better control on the execution, you have to call 593 ///\ref init() first, then you can add several source nodes with 594 594 ///\ref addSource(). Finally the actual path computation can be 595 595 ///performed with one of the \ref start() functions.
Note: See TracChangeset
for help on using the changeset viewer.
