1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/test/bfs_test.cc Mon Aug 30 12:01:47 2004 +0000
1.3 @@ -0,0 +1,89 @@
1.4 +#include "test_tools.h"
1.5 +#include <hugo/smart_graph.h>
1.6 +#include <hugo/bfs.h>
1.7 +
1.8 +using namespace hugo;
1.9 +
1.10 +const int PET_SIZE =5;
1.11 +
1.12 +
1.13 +void check_Bfs_SmartGraph_Compile()
1.14 +{
1.15 + typedef int VType;
1.16 + typedef SmartGraph Graph;
1.17 +
1.18 + typedef Graph::Edge Edge;
1.19 + typedef Graph::Node Node;
1.20 + typedef Graph::EdgeIt EdgeIt;
1.21 + typedef Graph::NodeIt NodeIt;
1.22 + typedef Graph::EdgeMap<VType> LengthMap;
1.23 +
1.24 + typedef Bfs<Graph> BType;
1.25 +
1.26 + Graph G;
1.27 + Node n;
1.28 + Edge e;
1.29 + VType l;
1.30 + bool b;
1.31 + BType::DistMap d(G);
1.32 + BType::PredMap p(G);
1.33 + BType::PredNodeMap pn(G);
1.34 + LengthMap cap(G);
1.35 +
1.36 + BType bfs_test(G);
1.37 +
1.38 + bfs_test.run(n);
1.39 +
1.40 + l = bfs_test.dist(n);
1.41 + e = bfs_test.pred(n);
1.42 + n = bfs_test.predNode(n);
1.43 + d = bfs_test.distMap();
1.44 + p = bfs_test.predMap();
1.45 + pn = bfs_test.predNodeMap();
1.46 + b = bfs_test.reached(n);
1.47 +
1.48 +}
1.49 +
1.50 +int main()
1.51 +{
1.52 +
1.53 + typedef SmartGraph Graph;
1.54 +
1.55 + typedef Graph::Edge Edge;
1.56 + typedef Graph::Node Node;
1.57 + typedef Graph::EdgeIt EdgeIt;
1.58 + typedef Graph::NodeIt NodeIt;
1.59 + typedef Graph::EdgeMap<int> LengthMap;
1.60 +
1.61 + Graph G;
1.62 + Node s, t;
1.63 + PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
1.64 +
1.65 + s=ps.outer[2];
1.66 + t=ps.inner[0];
1.67 +
1.68 + Bfs<Graph> bfs_test(G);
1.69 + bfs_test.run(s);
1.70 +
1.71 + check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
1.72 +
1.73 +
1.74 + for(EdgeIt e(G); e==INVALID; ++e) {
1.75 + Node u=G.tail(e);
1.76 + Node v=G.head(e);
1.77 + check( !bfs_test.reached(u) ||
1.78 + (bfs_test.dist(v) > bfs_test.dist(u)+1),
1.79 + "Wrong output.");
1.80 + }
1.81 +
1.82 + ///\bug This works only for integer lengths
1.83 + for(NodeIt v(G); v==INVALID; ++v)
1.84 + if ( bfs_test.reached(v) ) {
1.85 + Edge e=bfs_test.pred(v);
1.86 + Node u=G.tail(e);
1.87 + check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
1.88 + "Bad shortest path tree edge! Difference: "
1.89 + << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
1.90 + - 1));
1.91 + }
1.92 +}