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

 1 edited
Legend:
 Unmodified
 Added
 Removed

test/dijkstra_test.cc
r220 r228 20 20 #include <lemon/smart_graph.h> 21 21 #include <lemon/list_graph.h> 22 #include <lemon/lgf_reader.h> 23 22 24 #include <lemon/dijkstra.h> 23 25 #include <lemon/path.h> … … 27 29 28 30 using namespace lemon; 31 32 char test_lgf[] = 33 "@nodes\n" 34 "label\n" 35 "0\n" 36 "1\n" 37 "2\n" 38 "3\n" 39 "4\n" 40 "@arcs\n" 41 " label length\n" 42 "0 1 0 1\n" 43 "1 2 1 1\n" 44 "2 3 2 1\n" 45 "0 3 4 5\n" 46 "0 3 5 10\n" 47 "0 3 6 7\n" 48 "4 2 7 1\n" 49 "@attributes\n" 50 "source 0\n" 51 "target 3\n"; 29 52 30 53 void checkDijkstraCompile() … … 85 108 Node s, t; 86 109 LengthMap length(G); 87 PetStruct<Digraph> ps = addPetersen(G, 5);88 110 89 for(int i=0;i<5;i++) { 90 length[ps.outcir[i]]=4; 91 length[ps.incir[i]]=1; 92 length[ps.chords[i]]=10; 93 } 94 s=ps.outer[0]; 95 t=ps.inner[1]; 111 std::istringstream input(test_lgf); 112 digraphReader(input, G). 113 arcMap("length", length). 114 node("source", s). 115 node("target", t). 116 run(); 96 117 97 118 Dijkstra<Digraph, LengthMap> … … 99 120 dijkstra_test.run(s); 100 121 101 check(dijkstra_test.dist(t)== 13,"Dijkstra found a wrong path.");122 check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path."); 102 123 103 124 Path<Digraph> p = dijkstra_test.path(t); 104 check(p.length()== 4,"getPath() found a wrong path.");125 check(p.length()==3,"getPath() found a wrong path."); 105 126 check(checkPath(G, p),"path() found a wrong path."); 106 127 check(pathSource(G, p) == s,"path() found a wrong path."); … … 116 137 } 117 138 118 for(NodeIt v(G); v!=INVALID; ++v){ 119 check(dijkstra_test.reached(v),"Each node should be reached."); 120 if ( dijkstra_test.predArc(v)!=INVALID ) { 121 Arc e=dijkstra_test.predArc(v); 122 Node u=G.source(e); 123 check(u==dijkstra_test.predNode(v),"Wrong tree."); 124 check(dijkstra_test.dist(v)  dijkstra_test.dist(u) == length[e], 125 "Wrong distance! Difference: " << 126 std::abs(dijkstra_test.dist(v)dijkstra_test.dist(u)length[e])); 139 for(NodeIt v(G); v!=INVALID; ++v) { 140 if (dijkstra_test.reached(v)) { 141 check(v==s  dijkstra_test.predArc(v)!=INVALID, "Wrong tree."); 142 if (dijkstra_test.predArc(v)!=INVALID ) { 143 Arc e=dijkstra_test.predArc(v); 144 Node u=G.source(e); 145 check(u==dijkstra_test.predNode(v),"Wrong tree."); 146 check(dijkstra_test.dist(v)  dijkstra_test.dist(u) == length[e], 147 "Wrong distance! Difference: " << 148 std::abs(dijkstra_test.dist(v)dijkstra_test.dist(u)length[e])); 149 } 127 150 } 128 151 }
Note: See TracChangeset
for help on using the changeset viewer.