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/dijkstra.h> |
29 #include <lemon/dijkstra.h> |
30 #include <lemon/bellman_ford.h> |
30 #include <lemon/bellman_ford.h> |
|
31 #include <lemon/bits/path_dump.h> |
31 #include <lemon/bits/invalid.h> |
32 #include <lemon/bits/invalid.h> |
32 #include <lemon/error.h> |
33 #include <lemon/error.h> |
33 #include <lemon/maps.h> |
34 #include <lemon/maps.h> |
34 #include <lemon/matrix_maps.h> |
35 #include <lemon/matrix_maps.h> |
35 |
36 |
627 /// Before the use of these functions, |
628 /// Before the use of these functions, |
628 /// either run() or start() must be called. |
629 /// either run() or start() must be called. |
629 |
630 |
630 ///@{ |
631 ///@{ |
631 |
632 |
632 /// \brief Copies the shortest path to \c t into \c p |
633 typedef PredMatrixMapPath<Graph, PredMap> Path; |
633 /// |
634 |
634 /// This function copies the shortest path to \c t into \c p. |
635 ///Gives back the shortest path. |
635 /// If it \c t is a source itself or unreachable, then it does not |
636 |
636 /// alter \c p. |
637 ///Gives back the shortest path. |
637 /// \return Returns \c true if a path to \c t was actually copied to \c p, |
638 ///\pre The \c t should be reachable from the \c t. |
638 /// \c false otherwise. |
639 Path path(Node s, Node t) |
639 /// \sa DirPath |
640 { |
640 template <typename Path> |
641 return Path(*graph, *_pred, s, t); |
641 bool getPath(Path &p, Node source, Node target) { |
|
642 if (connected(source, target)) { |
|
643 p.clear(); |
|
644 typename Path::Builder b(target); |
|
645 for(b.setStartNode(target); predEdge(source, target) != INVALID; |
|
646 target = predNode(target)) { |
|
647 b.pushFront(predEdge(source, target)); |
|
648 } |
|
649 b.commit(); |
|
650 return true; |
|
651 } |
|
652 return false; |
|
653 } |
642 } |
654 |
643 |
655 /// \brief The distance between two nodes. |
644 /// \brief The distance between two nodes. |
656 /// |
645 /// |
657 /// Returns the distance between two nodes. |
646 /// Returns the distance between two nodes. |