alpar@906: /* -*- C++ -*- alpar@921: * src/test/bfs_test.cc - Part of LEMON, a generic C++ optimization library alpar@906: * alpar@1164: * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@906: * (Egervary Combinatorial Optimization Research Group, EGRES). alpar@906: * alpar@906: * Permission to use, modify and distribute this software is granted alpar@906: * provided that this copyright notice appears in all copies. For alpar@906: * precise terms see the accompanying LICENSE file. alpar@906: * alpar@906: * This software is provided "AS IS" with no warranty of any kind, alpar@906: * express or implied, and with no claim as to its suitability for any alpar@906: * purpose. alpar@906: * alpar@906: */ alpar@906: marci@944: #include alpar@921: #include marci@944: #include klao@959: #include alpar@774: alpar@921: using namespace lemon; alpar@774: alpar@774: const int PET_SIZE =5; alpar@774: alpar@774: alpar@793: void check_Bfs_Compile() alpar@774: { klao@959: typedef concept::StaticGraph 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: marci@944: typedef marci::Bfs BType; alpar@774: alpar@774: Graph G; alpar@774: Node n; alpar@774: Edge e; alpar@793: int l; alpar@774: bool b; alpar@774: BType::DistMap d(G); alpar@774: BType::PredMap p(G); alpar@774: BType::PredNodeMap pn(G); marci@944: marci@944: Graph::NodeMap reached(G); marci@944: Graph::NodeMap pred(G); marci@944: Graph::NodeMap pred_node(G); marci@944: Graph::NodeMap dist(G); marci@944: BType bfs_test(G, reached, pred, pred_node, dist); 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: marci@944: Graph::NodeMap reached(G); marci@944: Graph::NodeMap pred(G); marci@944: Graph::NodeMap pred_node(G); marci@944: Graph::NodeMap dist(G); marci@944: marci::Bfs bfs_test(G, reached, pred, pred_node, dist); alpar@774: bfs_test.run(s); alpar@774: marci@944: // check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t)); alpar@774: alpar@774: marci@944: // for(EdgeIt e(G); e==INVALID; ++e) { alpar@986: // Node u=G.source(e); alpar@986: // Node v=G.target(e); marci@944: // check( !bfs_test.reached(u) || marci@944: // (bfs_test.dist(v) > bfs_test.dist(u)+1), marci@944: // "Wrong output."); marci@944: // } alpar@774: marci@944: // for(NodeIt v(G); v==INVALID; ++v) { marci@944: // check(bfs_test.reached(v),"Each node should be reached."); marci@944: // if ( bfs_test.pred(v)!=INVALID ) { marci@944: // Edge e=bfs_test.pred(v); alpar@986: // Node u=G.source(e); marci@944: // check(u==bfs_test.predNode(v),"Wrong tree."); marci@944: // check(bfs_test.dist(v) - bfs_test.dist(u) == 1, marci@944: // "Wrong distance. Difference: " marci@944: // << std::abs(bfs_test.dist(v) - bfs_test.dist(u) marci@944: // - 1)); marci@944: // } marci@944: // } alpar@774: } alpar@780: