Changeset 1283:fc20371677b9 in lemon0.x
 Timestamp:
 03/31/05 15:31:39 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1715
 Location:
 src
 Files:

 6 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/bfs.h
r1270 r1283 654 654 ///@{ 655 655 656 ///Copies the shortest path to \c t into \c p 657 658 ///This function copies the shortest path to \c t into \c p. 659 ///If it \c \t is a source itself or unreachable, then it does not 660 ///alter \c p. 661 ///\todo Is it the right way to handle unreachable nodes? 662 ///\return Returns \c true if a path to \c t was actually copied to \c p, 663 ///\c false otherwise. 664 ///\sa DirPath 665 template<class P> 666 bool getPath(P &p,Node t) 667 { 668 if(reached(t)) { 669 p.clear(); 670 typename P::Builder b(p); 671 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t)) 672 b.pushFront(pred(t)); 673 b.commit(); 674 return true; 675 } 676 return false; 677 } 678 656 679 ///The distance of a node from the root(s). 657 680 
src/lemon/dfs.h
r1236 r1283 661 661 ///@{ 662 662 663 ///Copies the path to \c t on the DFS tree into \c p 664 665 ///This function copies the path on the DFS tree to \c t into \c p. 666 ///If it \c \t is a source itself or unreachable, then it does not 667 ///alter \c p. 668 ///\todo Is it the right way to handle unreachable nodes? 669 ///\return Returns \c true if a path to \c t was actually copied to \c p, 670 ///\c false otherwise. 671 ///\sa DirPath 672 template<class P> 673 bool getPath(P &p,Node t) 674 { 675 if(reached(t)) { 676 p.clear(); 677 typename P::Builder b(p); 678 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t)) 679 b.pushFront(pred(t)); 680 b.commit(); 681 return true; 682 } 683 return false; 684 } 685 663 686 ///The distance of a node from the root(s). 664 687 
src/lemon/dijkstra.h
r1236 r1283 21 21 ///\file 22 22 ///\brief Dijkstra algorithm. 23 /// 24 ///\todo getPath() should be implemented! (also for BFS and DFS) 23 25 24 26 #include <lemon/list_graph.h> … … 656 658 ///@{ 657 659 660 ///Copies the shortest path to \c t into \c p 661 662 ///This function copies the shortest path to \c t into \c p. 663 ///If it \c \t is a source itself or unreachable, then it does not 664 ///alter \c p. 665 ///\todo Is it the right way to handle unreachable nodes? 666 ///\return Returns \c true if a path to \c t was actually copied to \c p, 667 ///\c false otherwise. 668 ///\sa DirPath 669 template<class P> 670 bool getPath(P &p,Node t) 671 { 672 if(reached(t)) { 673 p.clear(); 674 typename P::Builder b(p); 675 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t)) 676 b.pushFront(pred(t)); 677 b.commit(); 678 return true; 679 } 680 return false; 681 } 682 658 683 ///The distance of a node from the root. 659 684 
src/test/bfs_test.cc
r1220 r1283 18 18 #include <lemon/smart_graph.h> 19 19 #include <lemon/bfs.h> 20 #include <lemon/path.h> 20 21 #include<lemon/concept/graph.h> 21 22 … … 57 58 b = bfs_test.reached(n); 58 59 60 DirPath<Graph> pp(G); 61 bfs_test.getPath(pp,n); 59 62 } 60 63 … … 104 107 check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t)); 105 108 109 DirPath<Graph> p(G); 110 check(bfs_test.getPath(p,t),"getPath() failed to set the path."); 111 check(p.length()==3,"getPath() found a wrong path."); 112 106 113 107 114 for(EdgeIt e(G); e==INVALID; ++e) { 
src/test/dfs_test.cc
r1233 r1283 18 18 #include <lemon/smart_graph.h> 19 19 #include <lemon/dfs.h> 20 #include <lemon/path.h> 20 21 #include <lemon/concept/graph.h> 21 22 … … 57 58 b = dfs_test.reached(n); 58 59 60 DirPath<Graph> pp(G); 61 dfs_test.getPath(pp,n); 59 62 } 60 63 … … 103 106 dfs_test.run(s); 104 107 108 DirPath<Graph> p(G); 109 check(dfs_test.getPath(p,t),"getPath() failed to set the path."); 110 check(p.length()==dfs_test.dist(t),"getPath() found a wrong path."); 111 105 112 for(NodeIt v(G); v!=INVALID; ++v) { 106 113 check(dfs_test.reached(v),"Each node should be reached."); 
src/test/dijkstra_test.cc
r1220 r1283 18 18 #include <lemon/smart_graph.h> 19 19 #include <lemon/dijkstra.h> 20 #include <lemon/path.h> 20 21 #include <lemon/maps.h> 21 22 #include <lemon/concept/graph.h> … … 60 61 // pn = dijkstra_test.predNodeMap(); 61 62 b = dijkstra_test.reached(n); 62 63 64 DirPath<Graph> pp(G); 65 dijkstra_test.getPath(pp,n); 63 66 } 64 67 … … 115 118 116 119 120 DirPath<Graph> p(G); 121 check(dijkstra_test.getPath(p,t),"getPath() failed to set the path."); 122 check(p.length()==4,"getPath() found a wrong path."); 123 124 117 125 for(EdgeIt e(G); e!=INVALID; ++e) { 118 126 Node u=G.source(e);
Note: See TracChangeset
for help on using the changeset viewer.