Changeset 228:b6732e0d38c5 in lemon for test/bfs_test.cc
 Timestamp:
 07/21/08 16:30:28 (15 years ago)
 Branch:
 default
 Children:
 229:aebc0161f6e5, 230:af4e8ba94294
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

test/bfs_test.cc
r222 r228 20 20 #include <lemon/smart_graph.h> 21 21 #include <lemon/list_graph.h> 22 #include <lemon/lgf_reader.h> 22 23 #include <lemon/bfs.h> 23 24 #include <lemon/path.h> … … 27 28 28 29 using namespace lemon; 30 31 char test_lgf[] = 32 "@nodes\n" 33 "label\n" 34 "0\n" 35 "1\n" 36 "2\n" 37 "3\n" 38 "4\n" 39 "5\n" 40 "@arcs\n" 41 " label\n" 42 "0 1 0\n" 43 "1 2 1\n" 44 "2 3 2\n" 45 "3 4 3\n" 46 "0 3 4\n" 47 "0 3 5\n" 48 "5 2 6\n" 49 "@attributes\n" 50 "source 0\n" 51 "target 4\n"; 29 52 30 53 void checkBfsCompile() … … 50 73 n = bfs_test.predNode(n); 51 74 d = bfs_test.distMap(); 75 52 76 p = bfs_test.predMap(); 53 77 // pn = bfs_test.predNodeMap(); … … 81 105 Digraph G; 82 106 Node s, t; 83 PetStruct<Digraph> ps = addPetersen(G, 5);84 107 85 s=ps.outer[2]; 86 t=ps.inner[0]; 108 std::istringstream input(test_lgf); 109 digraphReader(input, G). 110 node("source", s). 111 node("target", t). 112 run(); 87 113 88 114 Bfs<Digraph> bfs_test(G); 89 115 bfs_test.run(s); 90 116 91 check(bfs_test.dist(t)== 3,"Bfs found a wrong path." << bfs_test.dist(t));117 check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t)); 92 118 93 119 Path<Digraph> p = bfs_test.path(t); 94 check(p.length()== 3,"path() found a wrong path.");120 check(p.length()==2,"path() found a wrong path."); 95 121 check(checkPath(G, p),"path() found a wrong path."); 96 122 check(pathSource(G, p) == s,"path() found a wrong path."); … … 98 124 99 125 100 for(ArcIt e(G); e!=INVALID; ++e) {101 Node u=G.source( e);102 Node v=G.target( e);126 for(ArcIt a(G); a!=INVALID; ++a) { 127 Node u=G.source(a); 128 Node v=G.target(a); 103 129 check( !bfs_test.reached(u)  104 130 (bfs_test.dist(v) <= bfs_test.dist(u)+1), 105 "Wrong output." );131 "Wrong output." << G.id(v) << ' ' << G.id(u)); 106 132 } 107 133 108 134 for(NodeIt v(G); v!=INVALID; ++v) { 109 check(bfs_test.reached(v),"Each node should be reached."); 110 if ( bfs_test.predArc(v)!=INVALID ) { 111 Arc e=bfs_test.predArc(v); 112 Node u=G.source(e); 113 check(u==bfs_test.predNode(v),"Wrong tree."); 114 check(bfs_test.dist(v)  bfs_test.dist(u) == 1, 115 "Wrong distance. Difference: " 116 << std::abs(bfs_test.dist(v)  bfs_test.dist(u) 117  1)); 135 if (bfs_test.reached(v)) { 136 check(v==s  bfs_test.predArc(v)!=INVALID, "Wrong tree."); 137 if (bfs_test.predArc(v)!=INVALID ) { 138 Arc a=bfs_test.predArc(v); 139 Node u=G.source(a); 140 check(u==bfs_test.predNode(v),"Wrong tree."); 141 check(bfs_test.dist(v)  bfs_test.dist(u) == 1, 142 "Wrong distance. Difference: " 143 << std::abs(bfs_test.dist(v)  bfs_test.dist(u) 144  1)); 145 } 118 146 } 119 147 }
Note: See TracChangeset
for help on using the changeset viewer.