36 |
36 |
37 /// \brief Default operation traits for the Dijkstra algorithm class. |
37 /// \brief Default operation traits for the Dijkstra algorithm class. |
38 /// |
38 /// |
39 /// This operation traits class defines all computational operations and |
39 /// This operation traits class defines all computational operations and |
40 /// constants which are used in the Dijkstra algorithm. |
40 /// constants which are used in the Dijkstra algorithm. |
41 template <typename Value> |
41 template <typename V> |
42 struct DijkstraDefaultOperationTraits { |
42 struct DijkstraDefaultOperationTraits { |
|
43 /// \e |
|
44 typedef V Value; |
43 /// \brief Gives back the zero value of the type. |
45 /// \brief Gives back the zero value of the type. |
44 static Value zero() { |
46 static Value zero() { |
45 return static_cast<Value>(0); |
47 return static_cast<Value>(0); |
46 } |
48 } |
47 /// \brief Gives back the sum of the given two elements. |
49 /// \brief Gives back the sum of the given two elements. |
56 |
58 |
57 ///Default traits class of Dijkstra class. |
59 ///Default traits class of Dijkstra class. |
58 |
60 |
59 ///Default traits class of Dijkstra class. |
61 ///Default traits class of Dijkstra class. |
60 ///\tparam GR The type of the digraph. |
62 ///\tparam GR The type of the digraph. |
61 ///\tparam LM The type of the length map. |
63 ///\tparam LEN The type of the length map. |
62 template<class GR, class LM> |
64 template<typename GR, typename LEN> |
63 struct DijkstraDefaultTraits |
65 struct DijkstraDefaultTraits |
64 { |
66 { |
65 ///The type of the digraph the algorithm runs on. |
67 ///The type of the digraph the algorithm runs on. |
66 typedef GR Digraph; |
68 typedef GR Digraph; |
67 |
69 |
68 ///The type of the map that stores the arc lengths. |
70 ///The type of the map that stores the arc lengths. |
69 |
71 |
70 ///The type of the map that stores the arc lengths. |
72 ///The type of the map that stores the arc lengths. |
71 ///It must meet the \ref concepts::ReadMap "ReadMap" concept. |
73 ///It must meet the \ref concepts::ReadMap "ReadMap" concept. |
72 typedef LM LengthMap; |
74 typedef LEN LengthMap; |
73 ///The type of the length of the arcs. |
75 ///The type of the length of the arcs. |
74 typedef typename LM::Value Value; |
76 typedef typename LEN::Value Value; |
75 |
77 |
76 /// Operation traits for %Dijkstra algorithm. |
78 /// Operation traits for %Dijkstra algorithm. |
77 |
79 |
78 /// This class defines the operations that are used in the algorithm. |
80 /// This class defines the operations that are used in the algorithm. |
79 /// \see DijkstraDefaultOperationTraits |
81 /// \see DijkstraDefaultOperationTraits |
98 |
100 |
99 ///The heap type used by the Dijkstra algorithm. |
101 ///The heap type used by the Dijkstra algorithm. |
100 /// |
102 /// |
101 ///\sa BinHeap |
103 ///\sa BinHeap |
102 ///\sa Dijkstra |
104 ///\sa Dijkstra |
103 typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap; |
105 typedef BinHeap<typename LEN::Value, HeapCrossRef, std::less<Value> > Heap; |
104 ///Instantiates a \c Heap. |
106 ///Instantiates a \c Heap. |
105 |
107 |
106 ///This function instantiates a \ref Heap. |
108 ///This function instantiates a \ref Heap. |
107 static Heap *createHeap(HeapCrossRef& r) |
109 static Heap *createHeap(HeapCrossRef& r) |
108 { |
110 { |
148 |
150 |
149 ///The type of the map that stores the distances of the nodes. |
151 ///The type of the map that stores the distances of the nodes. |
150 |
152 |
151 ///The type of the map that stores the distances of the nodes. |
153 ///The type of the map that stores the distances of the nodes. |
152 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
154 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
153 typedef typename Digraph::template NodeMap<typename LM::Value> DistMap; |
155 typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap; |
154 ///Instantiates a \c DistMap. |
156 ///Instantiates a \c DistMap. |
155 |
157 |
156 ///This function instantiates a \ref DistMap. |
158 ///This function instantiates a \ref DistMap. |
157 ///\param g is the digraph, to which we would like to define |
159 ///\param g is the digraph, to which we would like to define |
158 ///the \ref DistMap. |
160 ///the \ref DistMap. |
178 ///%Dijkstra algorithm, which is convenient in the simplier cases and |
180 ///%Dijkstra algorithm, which is convenient in the simplier cases and |
179 ///it can be used easier. |
181 ///it can be used easier. |
180 /// |
182 /// |
181 ///\tparam GR The type of the digraph the algorithm runs on. |
183 ///\tparam GR The type of the digraph the algorithm runs on. |
182 ///The default type is \ref ListDigraph. |
184 ///The default type is \ref ListDigraph. |
183 ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies |
185 ///\tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies |
184 ///the lengths of the arcs. |
186 ///the lengths of the arcs. |
185 ///It is read once for each arc, so the map may involve in |
187 ///It is read once for each arc, so the map may involve in |
186 ///relatively time consuming process to compute the arc lengths if |
188 ///relatively time consuming process to compute the arc lengths if |
187 ///it is necessary. The default map type is \ref |
189 ///it is necessary. The default map type is \ref |
188 ///concepts::Digraph::ArcMap "GR::ArcMap<int>". |
190 ///concepts::Digraph::ArcMap "GR::ArcMap<int>". |
189 #ifdef DOXYGEN |
191 #ifdef DOXYGEN |
190 template <typename GR, typename LM, typename TR> |
192 template <typename GR, typename LEN, typename TR> |
191 #else |
193 #else |
192 template <typename GR=ListDigraph, |
194 template <typename GR=ListDigraph, |
193 typename LM=typename GR::template ArcMap<int>, |
195 typename LEN=typename GR::template ArcMap<int>, |
194 typename TR=DijkstraDefaultTraits<GR,LM> > |
196 typename TR=DijkstraDefaultTraits<GR,LEN> > |
195 #endif |
197 #endif |
196 class Dijkstra { |
198 class Dijkstra { |
197 public: |
199 public: |
198 |
200 |
199 ///The type of the digraph the algorithm runs on. |
201 ///The type of the digraph the algorithm runs on. |
911 |
913 |
912 ///Default traits class of dijkstra() function. |
914 ///Default traits class of dijkstra() function. |
913 |
915 |
914 ///Default traits class of dijkstra() function. |
916 ///Default traits class of dijkstra() function. |
915 ///\tparam GR The type of the digraph. |
917 ///\tparam GR The type of the digraph. |
916 ///\tparam LM The type of the length map. |
918 ///\tparam LEN The type of the length map. |
917 template<class GR, class LM> |
919 template<class GR, class LEN> |
918 struct DijkstraWizardDefaultTraits |
920 struct DijkstraWizardDefaultTraits |
919 { |
921 { |
920 ///The type of the digraph the algorithm runs on. |
922 ///The type of the digraph the algorithm runs on. |
921 typedef GR Digraph; |
923 typedef GR Digraph; |
922 ///The type of the map that stores the arc lengths. |
924 ///The type of the map that stores the arc lengths. |
923 |
925 |
924 ///The type of the map that stores the arc lengths. |
926 ///The type of the map that stores the arc lengths. |
925 ///It must meet the \ref concepts::ReadMap "ReadMap" concept. |
927 ///It must meet the \ref concepts::ReadMap "ReadMap" concept. |
926 typedef LM LengthMap; |
928 typedef LEN LengthMap; |
927 ///The type of the length of the arcs. |
929 ///The type of the length of the arcs. |
928 typedef typename LM::Value Value; |
930 typedef typename LEN::Value Value; |
929 |
931 |
930 /// Operation traits for Dijkstra algorithm. |
932 /// Operation traits for Dijkstra algorithm. |
931 |
933 |
932 /// This class defines the operations that are used in the algorithm. |
934 /// This class defines the operations that are used in the algorithm. |
933 /// \see DijkstraDefaultOperationTraits |
935 /// \see DijkstraDefaultOperationTraits |
1005 |
1007 |
1006 ///The type of the map that stores the distances of the nodes. |
1008 ///The type of the map that stores the distances of the nodes. |
1007 |
1009 |
1008 ///The type of the map that stores the distances of the nodes. |
1010 ///The type of the map that stores the distances of the nodes. |
1009 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
1011 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
1010 typedef typename Digraph::template NodeMap<typename LM::Value> DistMap; |
1012 typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap; |
1011 ///Instantiates a DistMap. |
1013 ///Instantiates a DistMap. |
1012 |
1014 |
1013 ///This function instantiates a DistMap. |
1015 ///This function instantiates a DistMap. |
1014 ///\param g is the digraph, to which we would like to define |
1016 ///\param g is the digraph, to which we would like to define |
1015 ///the DistMap |
1017 ///the DistMap |
1031 /// we have created a wizard class. |
1033 /// we have created a wizard class. |
1032 /// This \ref DijkstraWizard class needs default traits, |
1034 /// This \ref DijkstraWizard class needs default traits, |
1033 /// as well as the \ref Dijkstra class. |
1035 /// as well as the \ref Dijkstra class. |
1034 /// The \ref DijkstraWizardBase is a class to be the default traits of the |
1036 /// The \ref DijkstraWizardBase is a class to be the default traits of the |
1035 /// \ref DijkstraWizard class. |
1037 /// \ref DijkstraWizard class. |
1036 template<class GR,class LM> |
1038 template<typename GR, typename LEN> |
1037 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM> |
1039 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN> |
1038 { |
1040 { |
1039 typedef DijkstraWizardDefaultTraits<GR,LM> Base; |
1041 typedef DijkstraWizardDefaultTraits<GR,LEN> Base; |
1040 protected: |
1042 protected: |
1041 //The type of the nodes in the digraph. |
1043 //The type of the nodes in the digraph. |
1042 typedef typename Base::Digraph::Node Node; |
1044 typedef typename Base::Digraph::Node Node; |
1043 |
1045 |
1044 //Pointer to the digraph the algorithm runs on. |
1046 //Pointer to the digraph the algorithm runs on. |
1068 |
1070 |
1069 /// This constructor requires two parameters, |
1071 /// This constructor requires two parameters, |
1070 /// others are initiated to \c 0. |
1072 /// others are initiated to \c 0. |
1071 /// \param g The digraph the algorithm runs on. |
1073 /// \param g The digraph the algorithm runs on. |
1072 /// \param l The length map. |
1074 /// \param l The length map. |
1073 DijkstraWizardBase(const GR &g,const LM &l) : |
1075 DijkstraWizardBase(const GR &g,const LEN &l) : |
1074 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), |
1076 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), |
1075 _length(reinterpret_cast<void*>(const_cast<LM*>(&l))), |
1077 _length(reinterpret_cast<void*>(const_cast<LEN*>(&l))), |
1076 _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} |
1078 _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} |
1077 |
1079 |
1078 }; |
1080 }; |
1079 |
1081 |
1080 /// Auxiliary class for the function-type interface of Dijkstra algorithm. |
1082 /// Auxiliary class for the function-type interface of Dijkstra algorithm. |
1279 ///\endcode |
1281 ///\endcode |
1280 ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()" |
1282 ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()" |
1281 ///to the end of the parameter list. |
1283 ///to the end of the parameter list. |
1282 ///\sa DijkstraWizard |
1284 ///\sa DijkstraWizard |
1283 ///\sa Dijkstra |
1285 ///\sa Dijkstra |
1284 template<class GR, class LM> |
1286 template<typename GR, typename LEN> |
1285 DijkstraWizard<DijkstraWizardBase<GR,LM> > |
1287 DijkstraWizard<DijkstraWizardBase<GR,LEN> > |
1286 dijkstra(const GR &digraph, const LM &length) |
1288 dijkstra(const GR &digraph, const LEN &length) |
1287 { |
1289 { |
1288 return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length); |
1290 return DijkstraWizard<DijkstraWizardBase<GR,LEN> >(digraph,length); |
1289 } |
1291 } |
1290 |
1292 |
1291 } //END OF NAMESPACE LEMON |
1293 } //END OF NAMESPACE LEMON |
1292 |
1294 |
1293 #endif |
1295 #endif |