1.1 --- a/test/bfs_test.cc Fri Jul 18 17:26:12 2008 +0100
1.2 +++ b/test/bfs_test.cc Mon Jul 21 16:30:28 2008 +0200
1.3 @@ -19,6 +19,7 @@
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 #include <lemon/bfs.h>
1.9 #include <lemon/path.h>
1.10
1.11 @@ -27,6 +28,28 @@
1.12
1.13 using namespace lemon;
1.14
1.15 +char test_lgf[] =
1.16 + "@nodes\n"
1.17 + "label\n"
1.18 + "0\n"
1.19 + "1\n"
1.20 + "2\n"
1.21 + "3\n"
1.22 + "4\n"
1.23 + "5\n"
1.24 + "@arcs\n"
1.25 + " label\n"
1.26 + "0 1 0\n"
1.27 + "1 2 1\n"
1.28 + "2 3 2\n"
1.29 + "3 4 3\n"
1.30 + "0 3 4\n"
1.31 + "0 3 5\n"
1.32 + "5 2 6\n"
1.33 + "@attributes\n"
1.34 + "source 0\n"
1.35 + "target 4\n";
1.36 +
1.37 void checkBfsCompile()
1.38 {
1.39 typedef concepts::Digraph Digraph;
1.40 @@ -49,6 +72,7 @@
1.41 e = bfs_test.predArc(n);
1.42 n = bfs_test.predNode(n);
1.43 d = bfs_test.distMap();
1.44 +
1.45 p = bfs_test.predMap();
1.46 // pn = bfs_test.predNodeMap();
1.47 b = bfs_test.reached(n);
1.48 @@ -80,41 +104,45 @@
1.49
1.50 Digraph G;
1.51 Node s, t;
1.52 - PetStruct<Digraph> ps = addPetersen(G, 5);
1.53
1.54 - s=ps.outer[2];
1.55 - t=ps.inner[0];
1.56 + std::istringstream input(test_lgf);
1.57 + digraphReader(input, G).
1.58 + node("source", s).
1.59 + node("target", t).
1.60 + run();
1.61
1.62 Bfs<Digraph> bfs_test(G);
1.63 bfs_test.run(s);
1.64
1.65 - check(bfs_test.dist(t)==3,"Bfs found a wrong path." << bfs_test.dist(t));
1.66 + check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t));
1.67
1.68 Path<Digraph> p = bfs_test.path(t);
1.69 - check(p.length()==3,"path() found a wrong path.");
1.70 + check(p.length()==2,"path() found a wrong path.");
1.71 check(checkPath(G, p),"path() found a wrong path.");
1.72 check(pathSource(G, p) == s,"path() found a wrong path.");
1.73 check(pathTarget(G, p) == t,"path() found a wrong path.");
1.74
1.75
1.76 - for(ArcIt e(G); e!=INVALID; ++e) {
1.77 - Node u=G.source(e);
1.78 - Node v=G.target(e);
1.79 + for(ArcIt a(G); a!=INVALID; ++a) {
1.80 + Node u=G.source(a);
1.81 + Node v=G.target(a);
1.82 check( !bfs_test.reached(u) ||
1.83 (bfs_test.dist(v) <= bfs_test.dist(u)+1),
1.84 - "Wrong output.");
1.85 + "Wrong output." << G.id(v) << ' ' << G.id(u));
1.86 }
1.87
1.88 for(NodeIt v(G); v!=INVALID; ++v) {
1.89 - check(bfs_test.reached(v),"Each node should be reached.");
1.90 - if ( bfs_test.predArc(v)!=INVALID ) {
1.91 - Arc e=bfs_test.predArc(v);
1.92 - Node u=G.source(e);
1.93 - check(u==bfs_test.predNode(v),"Wrong tree.");
1.94 - check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
1.95 - "Wrong distance. Difference: "
1.96 - << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
1.97 - - 1));
1.98 + if (bfs_test.reached(v)) {
1.99 + check(v==s || bfs_test.predArc(v)!=INVALID, "Wrong tree.");
1.100 + if (bfs_test.predArc(v)!=INVALID ) {
1.101 + Arc a=bfs_test.predArc(v);
1.102 + Node u=G.source(a);
1.103 + check(u==bfs_test.predNode(v),"Wrong tree.");
1.104 + check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
1.105 + "Wrong distance. Difference: "
1.106 + << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
1.107 + - 1));
1.108 + }
1.109 }
1.110 }
1.111 }