equal
deleted
inserted
replaced
19 |
19 |
20 ///\ingroup flowalgs |
20 ///\ingroup flowalgs |
21 /// \file |
21 /// \file |
22 /// \brief FloydWarshall algorithm. |
22 /// \brief FloydWarshall algorithm. |
23 /// |
23 /// |
24 /// \todo getPath() should be implemented! (also for BFS and DFS) |
|
25 |
24 |
26 #include <lemon/list_graph.h> |
25 #include <lemon/list_graph.h> |
27 #include <lemon/graph_utils.h> |
26 #include <lemon/graph_utils.h> |
28 #include <lemon/invalid.h> |
27 #include <lemon/invalid.h> |
29 #include <lemon/error.h> |
28 #include <lemon/error.h> |
477 /// \brief Copies the shortest path to \c t into \c p |
476 /// \brief Copies the shortest path to \c t into \c p |
478 /// |
477 /// |
479 /// This function copies the shortest path to \c t into \c p. |
478 /// This function copies the shortest path to \c t into \c p. |
480 /// If it \c t is a source itself or unreachable, then it does not |
479 /// If it \c t is a source itself or unreachable, then it does not |
481 /// alter \c p. |
480 /// alter \c p. |
482 /// \todo Is it the right way to handle unreachable nodes? |
|
483 /// \return Returns \c true if a path to \c t was actually copied to \c p, |
481 /// \return Returns \c true if a path to \c t was actually copied to \c p, |
484 /// \c false otherwise. |
482 /// \c false otherwise. |
485 /// \sa DirPath |
483 /// \sa DirPath |
486 template <typename Path> |
484 template <typename Path> |
487 bool getPath(Path &p, Node source, Node target) { |
485 bool getPath(Path &p, Node source, Node target) { |
515 /// i.e. it returns the last edge of a shortest path from the node \c root |
513 /// i.e. it returns the last edge of a shortest path from the node \c root |
516 /// to \c node. It is \ref INVALID if \c node is unreachable from the root |
514 /// to \c node. It is \ref INVALID if \c node is unreachable from the root |
517 /// or if \c node=root. The shortest path tree used here is equal to the |
515 /// or if \c node=root. The shortest path tree used here is equal to the |
518 /// shortest path tree used in \ref predNode(). |
516 /// shortest path tree used in \ref predNode(). |
519 /// \pre \ref run() must be called before using this function. |
517 /// \pre \ref run() must be called before using this function. |
520 /// \todo predEdge could be a better name. |
|
521 Edge predEdge(Node root, Node node) const { |
518 Edge predEdge(Node root, Node node) const { |
522 return (*_pred)(root, node); |
519 return (*_pred)(root, node); |
523 } |
520 } |
524 |
521 |
525 /// \brief Returns the 'previous node' of the shortest path tree. |
522 /// \brief Returns the 'previous node' of the shortest path tree. |