# HG changeset patch
# User alpar
# Date 1112275899 0
# Node ID fc20371677b9930367a6f524493c2e6a92785a9f
# Parent 81e89e2b90d11f5e090cd9469374971aaa8f0dac
getPath() added to Bfs/Dfs/Dijkstra.
diff -r 81e89e2b90d1 -r fc20371677b9 src/lemon/bfs.h
--- a/src/lemon/bfs.h Thu Mar 31 13:30:27 2005 +0000
+++ b/src/lemon/bfs.h Thu Mar 31 13:31:39 2005 +0000
@@ -653,6 +653,29 @@
///@{
+ ///Copies the shortest path to \c t into \c p
+
+ ///This function copies the shortest path to \c t into \c p.
+ ///If it \c \t is a source itself or unreachable, then it does not
+ ///alter \c p.
+ ///\todo Is it the right way to handle unreachable nodes?
+ ///\return Returns \c true if a path to \c t was actually copied to \c p,
+ ///\c false otherwise.
+ ///\sa DirPath
+ template<class P>
+ bool getPath(P &p,Node t)
+ {
+ if(reached(t)) {
+ p.clear();
+ typename P::Builder b(p);
+ for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
+ b.pushFront(pred(t));
+ b.commit();
+ return true;
+ }
+ return false;
+ }
+
///The distance of a node from the root(s).
///Returns the distance of a node from the root(s).
diff -r 81e89e2b90d1 -r fc20371677b9 src/lemon/dfs.h
--- a/src/lemon/dfs.h Thu Mar 31 13:30:27 2005 +0000
+++ b/src/lemon/dfs.h Thu Mar 31 13:31:39 2005 +0000
@@ -660,6 +660,29 @@
///@{
+ ///Copies the path to \c t on the DFS tree into \c p
+
+ ///This function copies the path on the DFS tree to \c t into \c p.
+ ///If it \c \t is a source itself or unreachable, then it does not
+ ///alter \c p.
+ ///\todo Is it the right way to handle unreachable nodes?
+ ///\return Returns \c true if a path to \c t was actually copied to \c p,
+ ///\c false otherwise.
+ ///\sa DirPath
+ template<class P>
+ bool getPath(P &p,Node t)
+ {
+ if(reached(t)) {
+ p.clear();
+ typename P::Builder b(p);
+ for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
+ b.pushFront(pred(t));
+ b.commit();
+ return true;
+ }
+ return false;
+ }
+
///The distance of a node from the root(s).
///Returns the distance of a node from the root(s).
diff -r 81e89e2b90d1 -r fc20371677b9 src/lemon/dijkstra.h
--- a/src/lemon/dijkstra.h Thu Mar 31 13:30:27 2005 +0000
+++ b/src/lemon/dijkstra.h Thu Mar 31 13:31:39 2005 +0000
@@ -20,6 +20,8 @@
///\ingroup flowalgs
///\file
///\brief Dijkstra algorithm.
+///
+///\todo getPath() should be implemented! (also for BFS and DFS)
#include <lemon/list_graph.h>
#include <lemon/bin_heap.h>
@@ -655,6 +657,29 @@
///@{
+ ///Copies the shortest path to \c t into \c p
+
+ ///This function copies the shortest path to \c t into \c p.
+ ///If it \c \t is a source itself or unreachable, then it does not
+ ///alter \c p.
+ ///\todo Is it the right way to handle unreachable nodes?
+ ///\return Returns \c true if a path to \c t was actually copied to \c p,
+ ///\c false otherwise.
+ ///\sa DirPath
+ template<class P>
+ bool getPath(P &p,Node t)
+ {
+ if(reached(t)) {
+ p.clear();
+ typename P::Builder b(p);
+ for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
+ b.pushFront(pred(t));
+ b.commit();
+ return true;
+ }
+ return false;
+ }
+
///The distance of a node from the root.
///Returns the distance of a node from the root.
diff -r 81e89e2b90d1 -r fc20371677b9 src/test/bfs_test.cc
--- a/src/test/bfs_test.cc Thu Mar 31 13:30:27 2005 +0000
+++ b/src/test/bfs_test.cc Thu Mar 31 13:31:39 2005 +0000
@@ -17,6 +17,7 @@
#include "test_tools.h"
#include <lemon/smart_graph.h>
#include <lemon/bfs.h>
+#include <lemon/path.h>
#include<lemon/concept/graph.h>
using namespace lemon;
@@ -56,6 +57,8 @@
// pn = bfs_test.predNodeMap();
b = bfs_test.reached(n);
+ DirPath<Graph> pp(G);
+ bfs_test.getPath(pp,n);
}
void check_Bfs_Function_Compile()
@@ -103,6 +106,10 @@
check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
+ DirPath<Graph> p(G);
+ check(bfs_test.getPath(p,t),"getPath() failed to set the path.");
+ check(p.length()==3,"getPath() found a wrong path.");
+
for(EdgeIt e(G); e==INVALID; ++e) {
Node u=G.source(e);
diff -r 81e89e2b90d1 -r fc20371677b9 src/test/dfs_test.cc
--- a/src/test/dfs_test.cc Thu Mar 31 13:30:27 2005 +0000
+++ b/src/test/dfs_test.cc Thu Mar 31 13:31:39 2005 +0000
@@ -17,6 +17,7 @@
#include "test_tools.h"
#include <lemon/smart_graph.h>
#include <lemon/dfs.h>
+#include <lemon/path.h>
#include <lemon/concept/graph.h>
using namespace lemon;
@@ -56,6 +57,8 @@
// pn = dfs_test.predNodeMap();
b = dfs_test.reached(n);
+ DirPath<Graph> pp(G);
+ dfs_test.getPath(pp,n);
}
@@ -102,6 +105,10 @@
Dfs<Graph> dfs_test(G);
dfs_test.run(s);
+ DirPath<Graph> p(G);
+ check(dfs_test.getPath(p,t),"getPath() failed to set the path.");
+ check(p.length()==dfs_test.dist(t),"getPath() found a wrong path.");
+
for(NodeIt v(G); v!=INVALID; ++v) {
check(dfs_test.reached(v),"Each node should be reached.");
if ( dfs_test.pred(v)!=INVALID ) {
diff -r 81e89e2b90d1 -r fc20371677b9 src/test/dijkstra_test.cc
--- a/src/test/dijkstra_test.cc Thu Mar 31 13:30:27 2005 +0000
+++ b/src/test/dijkstra_test.cc Thu Mar 31 13:31:39 2005 +0000
@@ -17,6 +17,7 @@
#include "test_tools.h"
#include <lemon/smart_graph.h>
#include <lemon/dijkstra.h>
+#include <lemon/path.h>
#include <lemon/maps.h>
#include <lemon/concept/graph.h>
#include <lemon/concept/maps.h>
@@ -59,7 +60,9 @@
p = dijkstra_test.predMap();
// pn = dijkstra_test.predNodeMap();
b = dijkstra_test.reached(n);
-
+
+ DirPath<Graph> pp(G);
+ dijkstra_test.getPath(pp,n);
}
void check_Dijkstra_Function_Compile()
@@ -114,6 +117,11 @@
check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
+ DirPath<Graph> p(G);
+ check(dijkstra_test.getPath(p,t),"getPath() failed to set the path.");
+ check(p.length()==4,"getPath() found a wrong path.");
+
+
for(EdgeIt e(G); e!=INVALID; ++e) {
Node u=G.source(e);
Node v=G.target(e);