equal
deleted
inserted
replaced
133 ///The default traits class is |
133 ///The default traits class is |
134 ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>". |
134 ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>". |
135 ///See \ref BfsDefaultTraits for the documentation of |
135 ///See \ref BfsDefaultTraits for the documentation of |
136 ///a Bfs traits class. |
136 ///a Bfs traits class. |
137 /// |
137 /// |
138 ///\author Jacint Szabo and Alpar Juttner |
138 ///\author Alpar Juttner |
139 ///\todo A compare object would be nice. |
139 ///\todo A compare object would be nice. |
140 |
140 |
141 #ifdef DOXYGEN |
141 #ifdef DOXYGEN |
142 template <typename GR, |
142 template <typename GR, |
143 typename TR> |
143 typename TR> |
346 ///\brief \ref named-templ-param "Named parameter" |
346 ///\brief \ref named-templ-param "Named parameter" |
347 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>. |
347 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>. |
348 /// |
348 /// |
349 ///\ref named-templ-param "Named parameter" |
349 ///\ref named-templ-param "Named parameter" |
350 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>. |
350 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>. |
351 ///If you don't set it explicitely, it will be automatically allocated. |
351 ///If you don't set it explicitly, it will be automatically allocated. |
352 template <class T> |
352 template <class T> |
353 class DefProcessedMapToBeDefaultMap : |
353 class DefProcessedMapToBeDefaultMap : |
354 public Bfs< Graph, |
354 public Bfs< Graph, |
355 DefGraphProcessedMapTraits> { }; |
355 DefGraphProcessedMapTraits> { }; |
356 |
356 |
383 |
383 |
384 ///Sets the map storing the predecessor edges. |
384 ///Sets the map storing the predecessor edges. |
385 |
385 |
386 ///Sets the map storing the predecessor edges. |
386 ///Sets the map storing the predecessor edges. |
387 ///If you don't use this function before calling \ref run(), |
387 ///If you don't use this function before calling \ref run(), |
388 ///it will allocate one. The destuctor deallocates this |
388 ///it will allocate one. The destructor deallocates this |
389 ///automatically allocated map, of course. |
389 ///automatically allocated map, of course. |
390 ///\return <tt> (*this) </tt> |
390 ///\return <tt> (*this) </tt> |
391 Bfs &predMap(PredMap &m) |
391 Bfs &predMap(PredMap &m) |
392 { |
392 { |
393 if(local_pred) { |
393 if(local_pred) { |
400 |
400 |
401 ///Sets the map indicating the reached nodes. |
401 ///Sets the map indicating the reached nodes. |
402 |
402 |
403 ///Sets the map indicating the reached nodes. |
403 ///Sets the map indicating the reached nodes. |
404 ///If you don't use this function before calling \ref run(), |
404 ///If you don't use this function before calling \ref run(), |
405 ///it will allocate one. The destuctor deallocates this |
405 ///it will allocate one. The destructor deallocates this |
406 ///automatically allocated map, of course. |
406 ///automatically allocated map, of course. |
407 ///\return <tt> (*this) </tt> |
407 ///\return <tt> (*this) </tt> |
408 Bfs &reachedMap(ReachedMap &m) |
408 Bfs &reachedMap(ReachedMap &m) |
409 { |
409 { |
410 if(local_reached) { |
410 if(local_reached) { |
417 |
417 |
418 ///Sets the map indicating the processed nodes. |
418 ///Sets the map indicating the processed nodes. |
419 |
419 |
420 ///Sets the map indicating the processed nodes. |
420 ///Sets the map indicating the processed nodes. |
421 ///If you don't use this function before calling \ref run(), |
421 ///If you don't use this function before calling \ref run(), |
422 ///it will allocate one. The destuctor deallocates this |
422 ///it will allocate one. The destructor deallocates this |
423 ///automatically allocated map, of course. |
423 ///automatically allocated map, of course. |
424 ///\return <tt> (*this) </tt> |
424 ///\return <tt> (*this) </tt> |
425 Bfs &processedMap(ProcessedMap &m) |
425 Bfs &processedMap(ProcessedMap &m) |
426 { |
426 { |
427 if(local_processed) { |
427 if(local_processed) { |
434 |
434 |
435 // ///Sets the map storing the predecessor nodes. |
435 // ///Sets the map storing the predecessor nodes. |
436 |
436 |
437 // ///Sets the map storing the predecessor nodes. |
437 // ///Sets the map storing the predecessor nodes. |
438 // ///If you don't use this function before calling \ref run(), |
438 // ///If you don't use this function before calling \ref run(), |
439 // ///it will allocate one. The destuctor deallocates this |
439 // ///it will allocate one. The destructor deallocates this |
440 // ///automatically allocated map, of course. |
440 // ///automatically allocated map, of course. |
441 // ///\return <tt> (*this) </tt> |
441 // ///\return <tt> (*this) </tt> |
442 // Bfs &predNodeMap(PredNodeMap &m) |
442 // Bfs &predNodeMap(PredNodeMap &m) |
443 // { |
443 // { |
444 // if(local_predNode) { |
444 // if(local_predNode) { |
451 |
451 |
452 ///Sets the map storing the distances calculated by the algorithm. |
452 ///Sets the map storing the distances calculated by the algorithm. |
453 |
453 |
454 ///Sets the map storing the distances calculated by the algorithm. |
454 ///Sets the map storing the distances calculated by the algorithm. |
455 ///If you don't use this function before calling \ref run(), |
455 ///If you don't use this function before calling \ref run(), |
456 ///it will allocate one. The destuctor deallocates this |
456 ///it will allocate one. The destructor deallocates this |
457 ///automatically allocated map, of course. |
457 ///automatically allocated map, of course. |
458 ///\return <tt> (*this) </tt> |
458 ///\return <tt> (*this) </tt> |
459 Bfs &distMap(DistMap &m) |
459 Bfs &distMap(DistMap &m) |
460 { |
460 { |
461 if(local_dist) { |
461 if(local_dist) { |
656 ///The distance of a node from the root(s). |
656 ///The distance of a node from the root(s). |
657 |
657 |
658 ///Returns the distance of a node from the root(s). |
658 ///Returns the distance of a node from the root(s). |
659 ///\pre \ref run() must be called before using this function. |
659 ///\pre \ref run() must be called before using this function. |
660 ///\warning If node \c v in unreachable from the root(s) the return value |
660 ///\warning If node \c v in unreachable from the root(s) the return value |
661 ///of this funcion is undefined. |
661 ///of this function is undefined. |
662 int dist(Node v) const { return (*_dist)[v]; } |
662 int dist(Node v) const { return (*_dist)[v]; } |
663 |
663 |
664 ///Returns the 'previous edge' of the shortest path tree. |
664 ///Returns the 'previous edge' of the shortest path tree. |
665 |
665 |
666 ///For a node \c v it returns the 'previous edge' |
666 ///For a node \c v it returns the 'previous edge' |
713 // const PredNodeMap &predNodeMap() const { return *_predNode;} |
713 // const PredNodeMap &predNodeMap() const { return *_predNode;} |
714 |
714 |
715 ///Checks if a node is reachable from the root. |
715 ///Checks if a node is reachable from the root. |
716 |
716 |
717 ///Returns \c true if \c v is reachable from the root. |
717 ///Returns \c true if \c v is reachable from the root. |
718 ///\warning The source nodes are inditated as unreached. |
718 ///\warning The source nodes are indicated as unreached. |
719 ///\pre Either \ref run() or \ref start() |
719 ///\pre Either \ref run() or \ref start() |
720 ///must be called before using this function. |
720 ///must be called before using this function. |
721 /// |
721 /// |
722 bool reached(Node v) { return (*_reached)[v]; } |
722 bool reached(Node v) { return (*_reached)[v]; } |
723 |
723 |