Changes in test/bfs_test.cc [228:b6732e0d38c5:209:765619b7cbb2] in lemon-main
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
test/bfs_test.cc
r228 r209 20 20 #include <lemon/smart_graph.h> 21 21 #include <lemon/list_graph.h> 22 #include <lemon/lgf_reader.h>23 22 #include <lemon/bfs.h> 24 23 #include <lemon/path.h> … … 28 27 29 28 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";52 29 53 30 void checkBfsCompile() … … 73 50 n = bfs_test.predNode(n); 74 51 d = bfs_test.distMap(); 75 76 52 p = bfs_test.predMap(); 77 53 // pn = bfs_test.predNodeMap(); … … 105 81 Digraph G; 106 82 Node s, t; 83 PetStruct<Digraph> ps = addPetersen(G, 5); 107 84 108 std::istringstream input(test_lgf); 109 digraphReader(input, G). 110 node("source", s). 111 node("target", t). 112 run(); 85 s=ps.outer[2]; 86 t=ps.inner[0]; 113 87 114 88 Bfs<Digraph> bfs_test(G); 115 89 bfs_test.run(s); 116 90 117 check(bfs_test.dist(t)== 2,"Bfs found a wrong path." << bfs_test.dist(t));91 check(bfs_test.dist(t)==3,"Bfs found a wrong path." << bfs_test.dist(t)); 118 92 119 93 Path<Digraph> p = bfs_test.path(t); 120 check(p.length()== 2,"path() found a wrong path.");94 check(p.length()==3,"path() found a wrong path."); 121 95 check(checkPath(G, p),"path() found a wrong path."); 122 96 check(pathSource(G, p) == s,"path() found a wrong path."); … … 124 98 125 99 126 for(ArcIt a(G); a!=INVALID; ++a) {127 Node u=G.source( a);128 Node v=G.target( a);100 for(ArcIt e(G); e==INVALID; ++e) { 101 Node u=G.source(e); 102 Node v=G.target(e); 129 103 check( !bfs_test.reached(u) || 130 (bfs_test.dist(v) <=bfs_test.dist(u)+1),131 "Wrong output." << G.id(v) << ' ' << G.id(u));104 (bfs_test.dist(v) > bfs_test.dist(u)+1), 105 "Wrong output."); 132 106 } 133 107 134 for(NodeIt v(G); v!=INVALID; ++v) { 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 } 108 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)); 146 118 } 147 119 }
Note: See TracChangeset
for help on using the changeset viewer.