1.1 --- a/src/lemon/bfs.h Thu Mar 31 13:30:27 2005 +0000
1.2 +++ b/src/lemon/bfs.h Thu Mar 31 13:31:39 2005 +0000
1.3 @@ -653,6 +653,29 @@
1.4
1.5 ///@{
1.6
1.7 + ///Copies the shortest path to \c t into \c p
1.8 +
1.9 + ///This function copies the shortest path to \c t into \c p.
1.10 + ///If it \c \t is a source itself or unreachable, then it does not
1.11 + ///alter \c p.
1.12 + ///\todo Is it the right way to handle unreachable nodes?
1.13 + ///\return Returns \c true if a path to \c t was actually copied to \c p,
1.14 + ///\c false otherwise.
1.15 + ///\sa DirPath
1.16 + template<class P>
1.17 + bool getPath(P &p,Node t)
1.18 + {
1.19 + if(reached(t)) {
1.20 + p.clear();
1.21 + typename P::Builder b(p);
1.22 + for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
1.23 + b.pushFront(pred(t));
1.24 + b.commit();
1.25 + return true;
1.26 + }
1.27 + return false;
1.28 + }
1.29 +
1.30 ///The distance of a node from the root(s).
1.31
1.32 ///Returns the distance of a node from the root(s).
2.1 --- a/src/lemon/dfs.h Thu Mar 31 13:30:27 2005 +0000
2.2 +++ b/src/lemon/dfs.h Thu Mar 31 13:31:39 2005 +0000
2.3 @@ -660,6 +660,29 @@
2.4
2.5 ///@{
2.6
2.7 + ///Copies the path to \c t on the DFS tree into \c p
2.8 +
2.9 + ///This function copies the path on the DFS tree to \c t into \c p.
2.10 + ///If it \c \t is a source itself or unreachable, then it does not
2.11 + ///alter \c p.
2.12 + ///\todo Is it the right way to handle unreachable nodes?
2.13 + ///\return Returns \c true if a path to \c t was actually copied to \c p,
2.14 + ///\c false otherwise.
2.15 + ///\sa DirPath
2.16 + template<class P>
2.17 + bool getPath(P &p,Node t)
2.18 + {
2.19 + if(reached(t)) {
2.20 + p.clear();
2.21 + typename P::Builder b(p);
2.22 + for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
2.23 + b.pushFront(pred(t));
2.24 + b.commit();
2.25 + return true;
2.26 + }
2.27 + return false;
2.28 + }
2.29 +
2.30 ///The distance of a node from the root(s).
2.31
2.32 ///Returns the distance of a node from the root(s).
3.1 --- a/src/lemon/dijkstra.h Thu Mar 31 13:30:27 2005 +0000
3.2 +++ b/src/lemon/dijkstra.h Thu Mar 31 13:31:39 2005 +0000
3.3 @@ -20,6 +20,8 @@
3.4 ///\ingroup flowalgs
3.5 ///\file
3.6 ///\brief Dijkstra algorithm.
3.7 +///
3.8 +///\todo getPath() should be implemented! (also for BFS and DFS)
3.9
3.10 #include <lemon/list_graph.h>
3.11 #include <lemon/bin_heap.h>
3.12 @@ -655,6 +657,29 @@
3.13
3.14 ///@{
3.15
3.16 + ///Copies the shortest path to \c t into \c p
3.17 +
3.18 + ///This function copies the shortest path to \c t into \c p.
3.19 + ///If it \c \t is a source itself or unreachable, then it does not
3.20 + ///alter \c p.
3.21 + ///\todo Is it the right way to handle unreachable nodes?
3.22 + ///\return Returns \c true if a path to \c t was actually copied to \c p,
3.23 + ///\c false otherwise.
3.24 + ///\sa DirPath
3.25 + template<class P>
3.26 + bool getPath(P &p,Node t)
3.27 + {
3.28 + if(reached(t)) {
3.29 + p.clear();
3.30 + typename P::Builder b(p);
3.31 + for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
3.32 + b.pushFront(pred(t));
3.33 + b.commit();
3.34 + return true;
3.35 + }
3.36 + return false;
3.37 + }
3.38 +
3.39 ///The distance of a node from the root.
3.40
3.41 ///Returns the distance of a node from the root.
4.1 --- a/src/test/bfs_test.cc Thu Mar 31 13:30:27 2005 +0000
4.2 +++ b/src/test/bfs_test.cc Thu Mar 31 13:31:39 2005 +0000
4.3 @@ -17,6 +17,7 @@
4.4 #include "test_tools.h"
4.5 #include <lemon/smart_graph.h>
4.6 #include <lemon/bfs.h>
4.7 +#include <lemon/path.h>
4.8 #include<lemon/concept/graph.h>
4.9
4.10 using namespace lemon;
4.11 @@ -56,6 +57,8 @@
4.12 // pn = bfs_test.predNodeMap();
4.13 b = bfs_test.reached(n);
4.14
4.15 + DirPath<Graph> pp(G);
4.16 + bfs_test.getPath(pp,n);
4.17 }
4.18
4.19 void check_Bfs_Function_Compile()
4.20 @@ -103,6 +106,10 @@
4.21
4.22 check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
4.23
4.24 + DirPath<Graph> p(G);
4.25 + check(bfs_test.getPath(p,t),"getPath() failed to set the path.");
4.26 + check(p.length()==3,"getPath() found a wrong path.");
4.27 +
4.28
4.29 for(EdgeIt e(G); e==INVALID; ++e) {
4.30 Node u=G.source(e);
5.1 --- a/src/test/dfs_test.cc Thu Mar 31 13:30:27 2005 +0000
5.2 +++ b/src/test/dfs_test.cc Thu Mar 31 13:31:39 2005 +0000
5.3 @@ -17,6 +17,7 @@
5.4 #include "test_tools.h"
5.5 #include <lemon/smart_graph.h>
5.6 #include <lemon/dfs.h>
5.7 +#include <lemon/path.h>
5.8 #include <lemon/concept/graph.h>
5.9
5.10 using namespace lemon;
5.11 @@ -56,6 +57,8 @@
5.12 // pn = dfs_test.predNodeMap();
5.13 b = dfs_test.reached(n);
5.14
5.15 + DirPath<Graph> pp(G);
5.16 + dfs_test.getPath(pp,n);
5.17 }
5.18
5.19
5.20 @@ -102,6 +105,10 @@
5.21 Dfs<Graph> dfs_test(G);
5.22 dfs_test.run(s);
5.23
5.24 + DirPath<Graph> p(G);
5.25 + check(dfs_test.getPath(p,t),"getPath() failed to set the path.");
5.26 + check(p.length()==dfs_test.dist(t),"getPath() found a wrong path.");
5.27 +
5.28 for(NodeIt v(G); v!=INVALID; ++v) {
5.29 check(dfs_test.reached(v),"Each node should be reached.");
5.30 if ( dfs_test.pred(v)!=INVALID ) {
6.1 --- a/src/test/dijkstra_test.cc Thu Mar 31 13:30:27 2005 +0000
6.2 +++ b/src/test/dijkstra_test.cc Thu Mar 31 13:31:39 2005 +0000
6.3 @@ -17,6 +17,7 @@
6.4 #include "test_tools.h"
6.5 #include <lemon/smart_graph.h>
6.6 #include <lemon/dijkstra.h>
6.7 +#include <lemon/path.h>
6.8 #include <lemon/maps.h>
6.9 #include <lemon/concept/graph.h>
6.10 #include <lemon/concept/maps.h>
6.11 @@ -59,7 +60,9 @@
6.12 p = dijkstra_test.predMap();
6.13 // pn = dijkstra_test.predNodeMap();
6.14 b = dijkstra_test.reached(n);
6.15 -
6.16 +
6.17 + DirPath<Graph> pp(G);
6.18 + dijkstra_test.getPath(pp,n);
6.19 }
6.20
6.21 void check_Dijkstra_Function_Compile()
6.22 @@ -114,6 +117,11 @@
6.23 check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
6.24
6.25
6.26 + DirPath<Graph> p(G);
6.27 + check(dijkstra_test.getPath(p,t),"getPath() failed to set the path.");
6.28 + check(p.length()==4,"getPath() found a wrong path.");
6.29 +
6.30 +
6.31 for(EdgeIt e(G); e!=INVALID; ++e) {
6.32 Node u=G.source(e);
6.33 Node v=G.target(e);