Changes in lemon/dijkstra.h [631:33c6b6e755cd:891:75e6020b19b1] in lemon
- File:
-
- 1 edited
-
lemon/dijkstra.h (modified) (34 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/dijkstra.h
r631 r891 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.135 ///By default it is a NullMap.134 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 135 ///By default, it is a NullMap. 136 136 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 137 137 ///Instantiates a \c 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 … … 189 193 ///it is necessary. The default map type is \ref 190 194 ///concepts::Digraph::ArcMap "GR::ArcMap<int>". 195 ///\tparam TR The traits class that defines various types used by the 196 ///algorithm. By default, it is \ref DijkstraDefaultTraits 197 ///"DijkstraDefaultTraits<GR, LEN>". 198 ///In most cases, this parameter should not be set directly, 199 ///consider to use the named template parameters instead. 191 200 #ifdef DOXYGEN 192 201 template <typename GR, typename LEN, typename TR> … … 202 211 typedef typename TR::Digraph Digraph; 203 212 204 ///The type of the length of the arcs.205 typedef typename TR:: LengthMap::Value Value;213 ///The type of the arc lengths. 214 typedef typename TR::Value Value; 206 215 ///The type of the map that stores the arc lengths. 207 216 typedef typename TR::LengthMap LengthMap; … … 305 314 ///\ref named-templ-param "Named parameter" for setting 306 315 ///\c PredMap type. 307 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.316 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 308 317 template <class T> 309 318 struct SetPredMap … … 326 335 ///\ref named-templ-param "Named parameter" for setting 327 336 ///\c DistMap type. 328 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.337 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 329 338 template <class T> 330 339 struct SetDistMap … … 347 356 ///\ref named-templ-param "Named parameter" for setting 348 357 ///\c ProcessedMap type. 349 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.358 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 350 359 template <class T> 351 360 struct SetProcessedMap … … 423 432 ///passed to the constructor of the cross reference and the cross 424 433 ///reference should be passed to the constructor of the heap). 425 ///However external heap and cross reference objects could also be434 ///However, external heap and cross reference objects could also be 426 435 ///passed to the algorithm using the \ref heap() function before 427 436 ///calling \ref run(Node) "run()" or \ref init(). … … 444 453 ///\ref named-templ-param "Named parameter" for setting 445 454 ///\c OperationTraits type. 455 /// For more information, see \ref DijkstraDefaultOperationTraits. 446 456 template <class T> 447 457 struct SetOperationTraits … … 585 595 ///The simplest way to execute the %Dijkstra algorithm is to use 586 596 ///one of the member functions called \ref run(Node) "run()".\n 587 ///If you need more control on the execution, firstyou have to call588 ///\ref init() , then you can add several source nodes with597 ///If you need better control on the execution, you have to call 598 ///\ref init() first, then you can add several source nodes with 589 599 ///\ref addSource(). Finally the actual path computation can be 590 600 ///performed with one of the \ref start() functions. … … 802 812 ///The results of the %Dijkstra algorithm can be obtained using these 803 813 ///functions.\n 804 ///Either \ref run(Node) "run()" or \ref start() should be called814 ///Either \ref run(Node) "run()" or \ref init() should be called 805 815 ///before using them. 806 816 807 817 ///@{ 808 818 809 ///The shortest path to anode.810 811 ///Returns the shortest path to a node.819 ///The shortest path to the given node. 820 821 ///Returns the shortest path to the given node from the root(s). 812 822 /// 813 823 ///\warning \c t should be reached from the root(s). … … 817 827 Path path(Node t) const { return Path(*G, *_pred, t); } 818 828 819 ///The distance of anode from the root(s).820 821 ///Returns the distance of anode from the root(s).829 ///The distance of the given node from the root(s). 830 831 ///Returns the distance of the given node from the root(s). 822 832 /// 823 833 ///\warning If node \c v is not reached from the root(s), then … … 828 838 Value dist(Node v) const { return (*_dist)[v]; } 829 839 830 ///Returns the 'previous arc' of the shortest path tree for a node. 831 840 ///\brief Returns the 'previous arc' of the shortest path tree for 841 ///the given node. 842 /// 832 843 ///This function returns the 'previous arc' of the shortest path 833 844 ///tree for the node \c v, i.e. it returns the last arc of a … … 836 847 /// 837 848 ///The shortest path tree used here is equal to the shortest path 838 ///tree used in \ref predNode() .849 ///tree used in \ref predNode() and \ref predMap(). 839 850 /// 840 851 ///\pre Either \ref run(Node) "run()" or \ref init() … … 842 853 Arc predArc(Node v) const { return (*_pred)[v]; } 843 854 844 ///Returns the 'previous node' of the shortest path tree for a node. 845 855 ///\brief Returns the 'previous node' of the shortest path tree for 856 ///the given node. 857 /// 846 858 ///This function returns the 'previous node' of the shortest path 847 859 ///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 INVALID860 ///of a shortest path from a root to \c v. It is \c INVALID 849 861 ///if \c v is not reached from the root(s) or if \c v is a root. 850 862 /// 851 863 ///The shortest path tree used here is equal to the shortest path 852 ///tree used in \ref predArc() .864 ///tree used in \ref predArc() and \ref predMap(). 853 865 /// 854 866 ///\pre Either \ref run(Node) "run()" or \ref init() … … 871 883 /// 872 884 ///Returns a const reference to the node map that stores the predecessor 873 ///arcs, which form the shortest path tree .885 ///arcs, which form the shortest path tree (forest). 874 886 /// 875 887 ///\pre Either \ref run(Node) "run()" or \ref init() … … 877 889 const PredMap &predMap() const { return *_pred;} 878 890 879 ///Checks if anode is reached from the root(s).891 ///Checks if the given node is reached from the root(s). 880 892 881 893 ///Returns \c true if \c v is reached from the root(s). … … 896 908 Heap::POST_HEAP; } 897 909 898 ///The current distance of anode from the root(s).899 900 ///Returns the current distance of anode from the root(s).910 ///The current distance of the given node from the root(s). 911 912 ///Returns the current distance of the given node from the root(s). 901 913 ///It may be decreased in the following processes. 902 914 /// … … 925 937 926 938 ///The type of the map that stores the arc lengths. 927 ///It must meetthe \ref concepts::ReadMap "ReadMap" concept.939 ///It must conform to the \ref concepts::ReadMap "ReadMap" concept. 928 940 typedef LEN LengthMap; 929 ///The type of the length of the arcs.941 ///The type of the arc lengths. 930 942 typedef typename LEN::Value Value; 931 943 … … 974 986 ///The type of the map that stores the predecessor 975 987 ///arcs of the shortest paths. 976 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.988 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 977 989 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 978 990 ///Instantiates a PredMap. … … 989 1001 990 1002 ///The type of the map that indicates which nodes are processed. 991 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.992 ///By default it is a NullMap.1003 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 1004 ///By default, it is a NullMap. 993 1005 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 994 1006 ///Instantiates a ProcessedMap. … … 1009 1021 1010 1022 ///The type of the map that stores the distances of the nodes. 1011 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.1023 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 1012 1024 typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap; 1013 1025 ///Instantiates a DistMap. … … 1024 1036 1025 1037 ///The type of the shortest paths. 1026 ///It must meetthe \ref concepts::Path "Path" concept.1038 ///It must conform to the \ref concepts::Path "Path" concept. 1027 1039 typedef lemon::Path<Digraph> Path; 1028 1040 }; … … 1030 1042 /// Default traits class used by DijkstraWizard 1031 1043 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. 1044 /// Default traits class used by DijkstraWizard. 1045 /// \tparam GR The type of the digraph. 1046 /// \tparam LEN The type of the length map. 1038 1047 template<typename GR, typename LEN> 1039 1048 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN> … … 1089 1098 /// This class should only be used through the \ref dijkstra() function, 1090 1099 /// which makes it easier to use the algorithm. 1100 /// 1101 /// \tparam TR The traits class that defines various types used by the 1102 /// algorithm. 1091 1103 template<class TR> 1092 1104 class DijkstraWizard : public TR … … 1094 1106 typedef TR Base; 1095 1107 1096 ///The type of the digraph the algorithm runs on.1097 1108 typedef typename TR::Digraph Digraph; 1098 1109 … … 1102 1113 typedef typename Digraph::OutArcIt OutArcIt; 1103 1114 1104 ///The type of the map that stores the arc lengths.1105 1115 typedef typename TR::LengthMap LengthMap; 1106 ///The type of the length of the arcs.1107 1116 typedef typename LengthMap::Value Value; 1108 ///\brief The type of the map that stores the predecessor1109 ///arcs of the shortest paths.1110 1117 typedef typename TR::PredMap PredMap; 1111 ///The type of the map that stores the distances of the nodes.1112 1118 typedef typename TR::DistMap DistMap; 1113 ///The type of the map that indicates which nodes are processed.1114 1119 typedef typename TR::ProcessedMap ProcessedMap; 1115 ///The type of the shortest paths1116 1120 typedef typename TR::Path Path; 1117 ///The heap type used by the dijkstra algorithm.1118 1121 typedef typename TR::Heap Heap; 1119 1122 … … 1187 1190 SetPredMapBase(const TR &b) : TR(b) {} 1188 1191 }; 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. 1192 1193 ///\brief \ref named-templ-param "Named parameter" for setting 1194 ///the predecessor map. 1195 /// 1196 ///\ref named-templ-param "Named parameter" function for setting 1197 ///the map that stores the predecessor arcs of the nodes. 1194 1198 template<class T> 1195 1199 DijkstraWizard<SetPredMapBase<T> > predMap(const T &t) … … 1205 1209 SetDistMapBase(const TR &b) : TR(b) {} 1206 1210 }; 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. 1211 1212 ///\brief \ref named-templ-param "Named parameter" for setting 1213 ///the distance map. 1214 /// 1215 ///\ref named-templ-param "Named parameter" function for setting 1216 ///the map that stores the distances of the nodes calculated 1217 ///by the algorithm. 1212 1218 template<class T> 1213 1219 DijkstraWizard<SetDistMapBase<T> > distMap(const T &t) … … 1223 1229 SetProcessedMapBase(const TR &b) : TR(b) {} 1224 1230 }; 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. 1231 1232 ///\brief \ref named-func-param "Named parameter" for setting 1233 ///the processed map. 1234 /// 1235 ///\ref named-templ-param "Named parameter" function for setting 1236 ///the map that indicates which nodes are processed. 1230 1237 template<class T> 1231 1238 DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1240 1247 SetPathBase(const TR &b) : TR(b) {} 1241 1248 }; 1249 1242 1250 ///\brief \ref named-func-param "Named parameter" 1243 1251 ///for getting the shortest path to the target node.
Note: See TracChangeset
for help on using the changeset viewer.
