alpar@774: #include "test_tools.h" alpar@774: #include alpar@774: #include alpar@774: alpar@774: using namespace hugo; alpar@774: alpar@774: const int PET_SIZE =5; alpar@774: alpar@774: alpar@774: void check_Bfs_SmartGraph_Compile() alpar@774: { alpar@774: typedef int VType; alpar@774: typedef SmartGraph Graph; alpar@774: alpar@774: typedef Graph::Edge Edge; alpar@774: typedef Graph::Node Node; alpar@774: typedef Graph::EdgeIt EdgeIt; alpar@774: typedef Graph::NodeIt NodeIt; alpar@774: typedef Graph::EdgeMap LengthMap; alpar@774: alpar@774: typedef Bfs BType; alpar@774: alpar@774: Graph G; alpar@774: Node n; alpar@774: Edge e; alpar@774: VType l; alpar@774: bool b; alpar@774: BType::DistMap d(G); alpar@774: BType::PredMap p(G); alpar@774: BType::PredNodeMap pn(G); alpar@774: LengthMap cap(G); alpar@774: alpar@774: BType bfs_test(G); alpar@774: alpar@774: bfs_test.run(n); alpar@774: alpar@774: l = bfs_test.dist(n); alpar@774: e = bfs_test.pred(n); alpar@774: n = bfs_test.predNode(n); alpar@774: d = bfs_test.distMap(); alpar@774: p = bfs_test.predMap(); alpar@774: pn = bfs_test.predNodeMap(); alpar@774: b = bfs_test.reached(n); alpar@774: alpar@774: } alpar@774: alpar@774: int main() alpar@774: { alpar@774: alpar@774: typedef SmartGraph Graph; alpar@774: alpar@774: typedef Graph::Edge Edge; alpar@774: typedef Graph::Node Node; alpar@774: typedef Graph::EdgeIt EdgeIt; alpar@774: typedef Graph::NodeIt NodeIt; alpar@774: typedef Graph::EdgeMap LengthMap; alpar@774: alpar@774: Graph G; alpar@774: Node s, t; alpar@774: PetStruct ps = addPetersen(G,PET_SIZE); alpar@774: alpar@774: s=ps.outer[2]; alpar@774: t=ps.inner[0]; alpar@774: alpar@774: Bfs bfs_test(G); alpar@774: bfs_test.run(s); alpar@774: alpar@774: check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t)); alpar@774: alpar@774: alpar@774: for(EdgeIt e(G); e==INVALID; ++e) { alpar@774: Node u=G.tail(e); alpar@774: Node v=G.head(e); alpar@774: check( !bfs_test.reached(u) || alpar@774: (bfs_test.dist(v) > bfs_test.dist(u)+1), alpar@774: "Wrong output."); alpar@774: } alpar@774: alpar@774: ///\bug This works only for integer lengths alpar@774: for(NodeIt v(G); v==INVALID; ++v) alpar@774: if ( bfs_test.reached(v) ) { alpar@774: Edge e=bfs_test.pred(v); alpar@774: Node u=G.tail(e); alpar@774: check(bfs_test.dist(v) - bfs_test.dist(u) == 1, alpar@774: "Bad shortest path tree edge! Difference: " alpar@774: << std::abs(bfs_test.dist(v) - bfs_test.dist(u) alpar@774: - 1)); alpar@774: } alpar@774: }