24 /// \brief FloydWarshall algorithm. |
24 /// \brief FloydWarshall algorithm. |
25 /// |
25 /// |
26 |
26 |
27 #include <lemon/list_graph.h> |
27 #include <lemon/list_graph.h> |
28 #include <lemon/graph_utils.h> |
28 #include <lemon/graph_utils.h> |
|
29 #include <lemon/bits/path_dump.h> |
29 #include <lemon/bits/invalid.h> |
30 #include <lemon/bits/invalid.h> |
30 #include <lemon/error.h> |
31 #include <lemon/error.h> |
31 #include <lemon/matrix_maps.h> |
32 #include <lemon/matrix_maps.h> |
32 #include <lemon/maps.h> |
33 #include <lemon/maps.h> |
33 |
34 |
478 /// Before the use of these functions, |
479 /// Before the use of these functions, |
479 /// either run() or start() must be called. |
480 /// either run() or start() must be called. |
480 |
481 |
481 ///@{ |
482 ///@{ |
482 |
483 |
483 /// \brief Copies the shortest path to \c t into \c p |
484 typedef PredMatrixMapPath<Graph, PredMap> Path; |
484 /// |
485 |
485 /// This function copies the shortest path to \c t into \c p. |
486 ///Gives back the shortest path. |
486 /// If it \c t is a source itself or unreachable, then it does not |
487 |
487 /// alter \c p. |
488 ///Gives back the shortest path. |
488 /// \return Returns \c true if a path to \c t was actually copied to \c p, |
489 ///\pre The \c t should be reachable from the \c t. |
489 /// \c false otherwise. |
490 Path path(Node s, Node t) |
490 /// \sa DirPath |
491 { |
491 template <typename Path> |
492 return Path(*graph, *_pred, s, t); |
492 bool getPath(Path &p, Node source, Node target) { |
|
493 if (connected(source, target)) { |
|
494 p.clear(); |
|
495 typename Path::Builder b(target); |
|
496 for(b.setStartNode(target); predEdge(source, target) != INVALID; |
|
497 target = predNode(target)) { |
|
498 b.pushFront(predEdge(source, target)); |
|
499 } |
|
500 b.commit(); |
|
501 return true; |
|
502 } |
|
503 return false; |
|
504 } |
493 } |
505 |
494 |
506 /// \brief The distance between two nodes. |
495 /// \brief The distance between two nodes. |
507 /// |
496 /// |
508 /// Returns the distance between two nodes. |
497 /// Returns the distance between two nodes. |