getPath() added to Bfs/Dfs/Dijkstra.
authoralpar
Thu, 31 Mar 2005 13:31:39 +0000
changeset 1283fc20371677b9
parent 1282 81e89e2b90d1
child 1284 b941d044f87b
getPath() added to Bfs/Dfs/Dijkstra.
src/lemon/bfs.h
src/lemon/dfs.h
src/lemon/dijkstra.h
src/test/bfs_test.cc
src/test/dfs_test.cc
src/test/dijkstra_test.cc
     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);