/* -*- C++ -*- * src/test/bfs_test.cc - Part of LEMON, a generic C++ optimization library * * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Combinatorial Optimization Research Group, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ #include "test_tools.h" #include #include #include using namespace lemon; const int PET_SIZE =5; void check_Bfs_Compile() { typedef skeleton::StaticGraph Graph; typedef Graph::Edge Edge; typedef Graph::Node Node; typedef Graph::EdgeIt EdgeIt; typedef Graph::NodeIt NodeIt; typedef Bfs BType; Graph G; Node n; Edge e; int l; bool b; BType::DistMap d(G); BType::PredMap p(G); BType::PredNodeMap pn(G); BType bfs_test(G); bfs_test.run(n); l = bfs_test.dist(n); e = bfs_test.pred(n); n = bfs_test.predNode(n); d = bfs_test.distMap(); p = bfs_test.predMap(); pn = bfs_test.predNodeMap(); b = bfs_test.reached(n); } int main() { typedef SmartGraph Graph; typedef Graph::Edge Edge; typedef Graph::Node Node; typedef Graph::EdgeIt EdgeIt; typedef Graph::NodeIt NodeIt; typedef Graph::EdgeMap LengthMap; Graph G; Node s, t; PetStruct ps = addPetersen(G,PET_SIZE); s=ps.outer[2]; t=ps.inner[0]; Bfs bfs_test(G); bfs_test.run(s); check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t)); for(EdgeIt e(G); e==INVALID; ++e) { Node u=G.tail(e); Node v=G.head(e); check( !bfs_test.reached(u) || (bfs_test.dist(v) > bfs_test.dist(u)+1), "Wrong output."); } for(NodeIt v(G); v==INVALID; ++v) { check(bfs_test.reached(v),"Each node should be reached."); if ( bfs_test.pred(v)!=INVALID ) { Edge e=bfs_test.pred(v); Node u=G.tail(e); check(u==bfs_test.predNode(v),"Wrong tree."); check(bfs_test.dist(v) - bfs_test.dist(u) == 1, "Wrong distance. Difference: " << std::abs(bfs_test.dist(v) - bfs_test.dist(u) - 1)); } } }