1.1 --- a/test/dijkstra_test.cc Fri Jul 18 17:26:12 2008 +0100
1.2 +++ b/test/dijkstra_test.cc Mon Jul 21 16:30:28 2008 +0200
1.3 @@ -19,6 +19,8 @@
1.4 #include <lemon/concepts/digraph.h>
1.5 #include <lemon/smart_graph.h>
1.6 #include <lemon/list_graph.h>
1.7 +#include <lemon/lgf_reader.h>
1.8 +
1.9 #include <lemon/dijkstra.h>
1.10 #include <lemon/path.h>
1.11
1.12 @@ -27,6 +29,27 @@
1.13
1.14 using namespace lemon;
1.15
1.16 +char test_lgf[] =
1.17 + "@nodes\n"
1.18 + "label\n"
1.19 + "0\n"
1.20 + "1\n"
1.21 + "2\n"
1.22 + "3\n"
1.23 + "4\n"
1.24 + "@arcs\n"
1.25 + " label length\n"
1.26 + "0 1 0 1\n"
1.27 + "1 2 1 1\n"
1.28 + "2 3 2 1\n"
1.29 + "0 3 4 5\n"
1.30 + "0 3 5 10\n"
1.31 + "0 3 6 7\n"
1.32 + "4 2 7 1\n"
1.33 + "@attributes\n"
1.34 + "source 0\n"
1.35 + "target 3\n";
1.36 +
1.37 void checkDijkstraCompile()
1.38 {
1.39 typedef int VType;
1.40 @@ -84,24 +107,22 @@
1.41 Digraph G;
1.42 Node s, t;
1.43 LengthMap length(G);
1.44 - PetStruct<Digraph> ps = addPetersen(G, 5);
1.45
1.46 - for(int i=0;i<5;i++) {
1.47 - length[ps.outcir[i]]=4;
1.48 - length[ps.incir[i]]=1;
1.49 - length[ps.chords[i]]=10;
1.50 - }
1.51 - s=ps.outer[0];
1.52 - t=ps.inner[1];
1.53 + std::istringstream input(test_lgf);
1.54 + digraphReader(input, G).
1.55 + arcMap("length", length).
1.56 + node("source", s).
1.57 + node("target", t).
1.58 + run();
1.59
1.60 Dijkstra<Digraph, LengthMap>
1.61 dijkstra_test(G, length);
1.62 dijkstra_test.run(s);
1.63
1.64 - check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
1.65 + check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
1.66
1.67 Path<Digraph> p = dijkstra_test.path(t);
1.68 - check(p.length()==4,"getPath() found a wrong path.");
1.69 + check(p.length()==3,"getPath() found a wrong path.");
1.70 check(checkPath(G, p),"path() found a wrong path.");
1.71 check(pathSource(G, p) == s,"path() found a wrong path.");
1.72 check(pathTarget(G, p) == t,"path() found a wrong path.");
1.73 @@ -115,15 +136,17 @@
1.74 dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
1.75 }
1.76
1.77 - for(NodeIt v(G); v!=INVALID; ++v){
1.78 - check(dijkstra_test.reached(v),"Each node should be reached.");
1.79 - if ( dijkstra_test.predArc(v)!=INVALID ) {
1.80 - Arc e=dijkstra_test.predArc(v);
1.81 - Node u=G.source(e);
1.82 - check(u==dijkstra_test.predNode(v),"Wrong tree.");
1.83 - check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
1.84 - "Wrong distance! Difference: " <<
1.85 - std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
1.86 + for(NodeIt v(G); v!=INVALID; ++v) {
1.87 + if (dijkstra_test.reached(v)) {
1.88 + check(v==s || dijkstra_test.predArc(v)!=INVALID, "Wrong tree.");
1.89 + if (dijkstra_test.predArc(v)!=INVALID ) {
1.90 + Arc e=dijkstra_test.predArc(v);
1.91 + Node u=G.source(e);
1.92 + check(u==dijkstra_test.predNode(v),"Wrong tree.");
1.93 + check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
1.94 + "Wrong distance! Difference: " <<
1.95 + std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
1.96 + }
1.97 }
1.98 }
1.99