165 /// BelmannFordDefaultTraits for the documentation of a BelmannFord traits |
165 /// BelmannFordDefaultTraits for the documentation of a BelmannFord traits |
166 /// class. |
166 /// class. |
167 /// |
167 /// |
168 /// \author Balazs Dezso |
168 /// \author Balazs Dezso |
169 |
169 |
|
170 #ifdef DOXYGEN |
|
171 template <typename _Graph, typename _LengthMap, typename _Traits> |
|
172 #else |
170 template <typename _Graph=ListGraph, |
173 template <typename _Graph=ListGraph, |
171 typename _LengthMap=typename _Graph::template EdgeMap<int>, |
174 typename _LengthMap=typename _Graph::template EdgeMap<int>, |
172 typename _Traits=BelmannFordDefaultTraits<_Graph,_LengthMap> > |
175 typename _Traits=BelmannFordDefaultTraits<_Graph,_LengthMap> > |
|
176 #endif |
173 class BelmannFord { |
177 class BelmannFord { |
174 public: |
178 public: |
175 |
179 |
176 /// \brief \ref Exception for uninitialized parameters. |
180 /// \brief \ref Exception for uninitialized parameters. |
177 /// |
181 /// |
231 } |
235 } |
232 } |
236 } |
233 |
237 |
234 public : |
238 public : |
235 |
239 |
|
240 typedef BelmannFord Create; |
|
241 |
236 /// \name Named template parameters |
242 /// \name Named template parameters |
237 |
243 |
238 ///@{ |
244 ///@{ |
239 |
245 |
240 template <class T> |
246 template <class T> |
241 struct DefPredMapTraits : public Traits { |
247 struct DefPredMapTraits : public Traits { |
242 typedef T PredMap; |
248 typedef T PredMap; |
243 static PredMap *createPredMap(const Graph& graph) { |
249 static PredMap *createPredMap(const Graph&) { |
244 throw UninitializedParameter(); |
250 throw UninitializedParameter(); |
245 } |
251 } |
246 }; |
252 }; |
247 |
253 |
248 /// \brief \ref named-templ-param "Named parameter" for setting PredMap |
254 /// \brief \ref named-templ-param "Named parameter" for setting PredMap |
249 /// type |
255 /// type |
250 /// \ref named-templ-param "Named parameter" for setting PredMap type |
256 /// \ref named-templ-param "Named parameter" for setting PredMap type |
251 /// |
257 /// |
252 template <class T> |
258 template <class T> |
253 class DefPredMap |
259 struct DefPredMap { |
254 : public BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > {}; |
260 typedef BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > Create; |
|
261 }; |
255 |
262 |
256 template <class T> |
263 template <class T> |
257 struct DefDistMapTraits : public Traits { |
264 struct DefDistMapTraits : public Traits { |
258 typedef T DistMap; |
265 typedef T DistMap; |
259 static DistMap *createDistMap(const Graph& graph) { |
266 static DistMap *createDistMap(const Graph& graph) { |
265 /// type |
272 /// type |
266 /// |
273 /// |
267 /// \ref named-templ-param "Named parameter" for setting DistMap type |
274 /// \ref named-templ-param "Named parameter" for setting DistMap type |
268 /// |
275 /// |
269 template <class T> |
276 template <class T> |
270 class DefDistMap |
277 struct DefDistMap |
271 : public BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > {}; |
278 : public BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > { |
|
279 typedef BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > Create; |
|
280 }; |
272 |
281 |
273 template <class T> |
282 template <class T> |
274 struct DefOperationTraitsTraits : public Traits { |
283 struct DefOperationTraitsTraits : public Traits { |
275 typedef T OperationTraits; |
284 typedef T OperationTraits; |
276 }; |
285 }; |
277 |
286 |
278 /// \brief \ref named-templ-param "Named parameter" for setting |
287 /// \brief \ref named-templ-param "Named parameter" for setting |
279 /// OperationTraits type |
288 /// OperationTraits type |
280 /// |
289 /// |
281 /// \ref named-templ-param "Named parameter" for setting PredMap type |
290 /// \ref named-templ-param "Named parameter" for setting OperationTraits |
|
291 /// type |
282 template <class T> |
292 template <class T> |
283 class DefOperationTraits |
293 struct DefOperationTraits |
284 : public BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> > { |
294 : public BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> > { |
285 public: |
|
286 typedef BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> > |
295 typedef BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> > |
287 BelmannFord; |
296 Create; |
288 }; |
297 }; |
289 |
298 |
290 ///@} |
299 ///@} |
|
300 |
|
301 protected: |
|
302 |
|
303 BelmannFord() {} |
291 |
304 |
292 public: |
305 public: |
293 |
306 |
294 /// \brief Constructor. |
307 /// \brief Constructor. |
295 /// |
308 /// |
360 ///@{ |
373 ///@{ |
361 |
374 |
362 /// \brief Initializes the internal data structures. |
375 /// \brief Initializes the internal data structures. |
363 /// |
376 /// |
364 /// Initializes the internal data structures. |
377 /// Initializes the internal data structures. |
365 void init() { |
378 void init(const Value value = OperationTraits::infinity()) { |
366 create_maps(); |
379 create_maps(); |
367 for (NodeIt it(*graph); it != INVALID; ++it) { |
380 for (NodeIt it(*graph); it != INVALID; ++it) { |
368 _pred->set(it, INVALID); |
381 _pred->set(it, INVALID); |
369 _dist->set(it, OperationTraits::infinity()); |
382 _dist->set(it, value); |
370 } |
383 } |
371 } |
384 } |
372 |
385 |
373 /// \brief Adds a new source node. |
386 /// \brief Adds a new source node. |
374 /// |
387 /// |
738 template<class T> |
751 template<class T> |
739 BelmannFordWizard<DefDistMapBase<T> > distMap(const T &t) { |
752 BelmannFordWizard<DefDistMapBase<T> > distMap(const T &t) { |
740 Base::_dist=(void *)&t; |
753 Base::_dist=(void *)&t; |
741 return BelmannFordWizard<DefDistMapBase<T> >(*this); |
754 return BelmannFordWizard<DefDistMapBase<T> >(*this); |
742 } |
755 } |
|
756 |
|
757 template<class T> |
|
758 struct DefOperationTraitsBase : public Base { |
|
759 typedef T OperationTraits; |
|
760 DefOperationTraitsBase(const _Traits &b) : _Traits(b) {} |
|
761 }; |
|
762 |
|
763 ///\brief \ref named-templ-param "Named parameter" |
|
764 ///function for setting OperationTraits type |
|
765 /// |
|
766 /// \ref named-templ-param "Named parameter" |
|
767 ///function for setting OperationTraits type |
|
768 /// |
|
769 template<class T> |
|
770 BelmannFordWizard<DefOperationTraitsBase<T> > distMap() { |
|
771 return BelmannFordWizard<DefDistMapBase<T> >(*this); |
|
772 } |
743 |
773 |
744 /// \brief Sets the source node, from which the BelmannFord algorithm runs. |
774 /// \brief Sets the source node, from which the BelmannFord algorithm runs. |
745 /// |
775 /// |
746 /// Sets the source node, from which the BelmannFord algorithm runs. |
776 /// Sets the source node, from which the BelmannFord algorithm runs. |
747 /// \param s is the source node. |
777 /// \param s is the source node. |