equal
deleted
inserted
replaced
223 typename LM=typename GR::template ArcMap<int>, |
223 typename LM=typename GR::template ArcMap<int>, |
224 typename TR=DijkstraDefaultTraits<GR,LM> > |
224 typename TR=DijkstraDefaultTraits<GR,LM> > |
225 #endif |
225 #endif |
226 class Dijkstra { |
226 class Dijkstra { |
227 public: |
227 public: |
228 ///\ref Exception for uninitialized parameters. |
|
229 |
|
230 ///This error represents problems in the initialization of the |
|
231 ///parameters of the algorithm. |
|
232 class UninitializedParameter : public lemon::UninitializedParameter { |
|
233 public: |
|
234 virtual const char* what() const throw() { |
|
235 return "lemon::Dijkstra::UninitializedParameter"; |
|
236 } |
|
237 }; |
|
238 |
228 |
239 ///The type of the digraph the algorithm runs on. |
229 ///The type of the digraph the algorithm runs on. |
240 typedef typename TR::Digraph Digraph; |
230 typedef typename TR::Digraph Digraph; |
241 |
231 |
242 ///The type of the length of the arcs. |
232 ///The type of the length of the arcs. |
330 template <class T> |
320 template <class T> |
331 struct SetPredMapTraits : public Traits { |
321 struct SetPredMapTraits : public Traits { |
332 typedef T PredMap; |
322 typedef T PredMap; |
333 static PredMap *createPredMap(const Digraph &) |
323 static PredMap *createPredMap(const Digraph &) |
334 { |
324 { |
335 throw UninitializedParameter(); |
325 LEMON_ASSERT(false, "PredMap is not initialized"); |
|
326 return 0; // ignore warnings |
336 } |
327 } |
337 }; |
328 }; |
338 ///\brief \ref named-templ-param "Named parameter" for setting |
329 ///\brief \ref named-templ-param "Named parameter" for setting |
339 ///\ref PredMap type. |
330 ///\ref PredMap type. |
340 /// |
331 /// |
349 template <class T> |
340 template <class T> |
350 struct SetDistMapTraits : public Traits { |
341 struct SetDistMapTraits : public Traits { |
351 typedef T DistMap; |
342 typedef T DistMap; |
352 static DistMap *createDistMap(const Digraph &) |
343 static DistMap *createDistMap(const Digraph &) |
353 { |
344 { |
354 throw UninitializedParameter(); |
345 LEMON_ASSERT(false, "DistMap is not initialized"); |
|
346 return 0; // ignore warnings |
355 } |
347 } |
356 }; |
348 }; |
357 ///\brief \ref named-templ-param "Named parameter" for setting |
349 ///\brief \ref named-templ-param "Named parameter" for setting |
358 ///\ref DistMap type. |
350 ///\ref DistMap type. |
359 /// |
351 /// |
368 template <class T> |
360 template <class T> |
369 struct SetProcessedMapTraits : public Traits { |
361 struct SetProcessedMapTraits : public Traits { |
370 typedef T ProcessedMap; |
362 typedef T ProcessedMap; |
371 static ProcessedMap *createProcessedMap(const Digraph &) |
363 static ProcessedMap *createProcessedMap(const Digraph &) |
372 { |
364 { |
373 throw UninitializedParameter(); |
365 LEMON_ASSERT(false, "ProcessedMap is not initialized"); |
|
366 return 0; // ignore warnings |
374 } |
367 } |
375 }; |
368 }; |
376 ///\brief \ref named-templ-param "Named parameter" for setting |
369 ///\brief \ref named-templ-param "Named parameter" for setting |
377 ///\ref ProcessedMap type. |
370 ///\ref ProcessedMap type. |
378 /// |
371 /// |
406 template <class H, class CR> |
399 template <class H, class CR> |
407 struct SetHeapTraits : public Traits { |
400 struct SetHeapTraits : public Traits { |
408 typedef CR HeapCrossRef; |
401 typedef CR HeapCrossRef; |
409 typedef H Heap; |
402 typedef H Heap; |
410 static HeapCrossRef *createHeapCrossRef(const Digraph &) { |
403 static HeapCrossRef *createHeapCrossRef(const Digraph &) { |
411 throw UninitializedParameter(); |
404 LEMON_ASSERT(false, "HeapCrossRef is not initialized"); |
|
405 return 0; // ignore warnings |
412 } |
406 } |
413 static Heap *createHeap(HeapCrossRef &) |
407 static Heap *createHeap(HeapCrossRef &) |
414 { |
408 { |
415 throw UninitializedParameter(); |
409 LEMON_ASSERT(false, "Heap is not initialized"); |
|
410 return 0; // ignore warnings |
416 } |
411 } |
417 }; |
412 }; |
418 ///\brief \ref named-templ-param "Named parameter" for setting |
413 ///\brief \ref named-templ-param "Named parameter" for setting |
419 ///heap and cross reference type |
414 ///heap and cross reference type |
420 /// |
415 /// |
1156 |
1151 |
1157 ///This method runs %Dijkstra algorithm from the given source node |
1152 ///This method runs %Dijkstra algorithm from the given source node |
1158 ///in order to compute the shortest path to each node. |
1153 ///in order to compute the shortest path to each node. |
1159 void run(Node s) |
1154 void run(Node s) |
1160 { |
1155 { |
1161 if (s==INVALID) throw UninitializedParameter(); |
|
1162 Dijkstra<Digraph,LengthMap,TR> |
1156 Dijkstra<Digraph,LengthMap,TR> |
1163 dijk(*reinterpret_cast<const Digraph*>(Base::_g), |
1157 dijk(*reinterpret_cast<const Digraph*>(Base::_g), |
1164 *reinterpret_cast<const LengthMap*>(Base::_length)); |
1158 *reinterpret_cast<const LengthMap*>(Base::_length)); |
1165 if (Base::_pred) |
1159 if (Base::_pred) |
1166 dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); |
1160 dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); |
1178 ///(it stops searching when \c t is processed). |
1172 ///(it stops searching when \c t is processed). |
1179 /// |
1173 /// |
1180 ///\return \c true if \c t is reachable form \c s. |
1174 ///\return \c true if \c t is reachable form \c s. |
1181 bool run(Node s, Node t) |
1175 bool run(Node s, Node t) |
1182 { |
1176 { |
1183 if (s==INVALID || t==INVALID) throw UninitializedParameter(); |
|
1184 Dijkstra<Digraph,LengthMap,TR> |
1177 Dijkstra<Digraph,LengthMap,TR> |
1185 dijk(*reinterpret_cast<const Digraph*>(Base::_g), |
1178 dijk(*reinterpret_cast<const Digraph*>(Base::_g), |
1186 *reinterpret_cast<const LengthMap*>(Base::_length)); |
1179 *reinterpret_cast<const LengthMap*>(Base::_length)); |
1187 if (Base::_pred) |
1180 if (Base::_pred) |
1188 dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); |
1181 dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); |