alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@100: * alpar@209: * This file is a part of LEMON, a generic C++ optimization library. alpar@100: * alpar@100: * Copyright (C) 2003-2008 alpar@100: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@100: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@100: * alpar@100: * Permission to use, modify and distribute this software is granted alpar@100: * provided that this copyright notice appears in all copies. For alpar@100: * precise terms see the accompanying LICENSE file. alpar@100: * alpar@100: * This software is provided "AS IS" with no warranty of any kind, alpar@100: * express or implied, and with no claim as to its suitability for any alpar@100: * purpose. alpar@100: * alpar@100: */ alpar@100: kpeter@171: #include kpeter@171: #include alpar@100: #include alpar@100: #include alpar@100: #include kpeter@171: kpeter@171: #include "graph_test.h" kpeter@171: #include "test_tools.h" alpar@100: alpar@100: using namespace lemon; alpar@100: alpar@209: void checkBfsCompile() alpar@100: { alpar@100: typedef concepts::Digraph Digraph; alpar@100: typedef Bfs BType; alpar@209: alpar@100: Digraph G; kpeter@171: Digraph::Node n; kpeter@171: Digraph::Arc e; alpar@100: int l; alpar@100: bool b; alpar@100: BType::DistMap d(G); alpar@100: BType::PredMap p(G); alpar@100: // BType::PredNodeMap pn(G); alpar@209: alpar@100: BType bfs_test(G); alpar@209: alpar@100: bfs_test.run(n); alpar@209: alpar@100: l = bfs_test.dist(n); alpar@100: e = bfs_test.predArc(n); alpar@100: n = bfs_test.predNode(n); alpar@100: d = bfs_test.distMap(); alpar@100: p = bfs_test.predMap(); alpar@100: // pn = bfs_test.predNodeMap(); alpar@100: b = bfs_test.reached(n); alpar@100: alpar@100: Path pp = bfs_test.path(n); alpar@100: } alpar@100: alpar@209: void checkBfsFunctionCompile() alpar@100: { alpar@100: typedef int VType; alpar@100: typedef concepts::Digraph Digraph; alpar@100: typedef Digraph::Arc Arc; alpar@100: typedef Digraph::Node Node; alpar@209: alpar@100: Digraph g; alpar@100: bfs(g,Node()).run(); alpar@100: bfs(g).source(Node()).run(); alpar@100: bfs(g) alpar@100: .predMap(concepts::WriteMap()) alpar@100: .distMap(concepts::WriteMap()) alpar@100: .reachedMap(concepts::ReadWriteMap()) alpar@100: .processedMap(concepts::WriteMap()) alpar@100: .run(Node()); alpar@100: } alpar@100: kpeter@171: template kpeter@171: void checkBfs() { kpeter@171: TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); alpar@100: alpar@100: Digraph G; alpar@100: Node s, t; kpeter@171: PetStruct ps = addPetersen(G, 5); alpar@209: alpar@100: s=ps.outer[2]; alpar@100: t=ps.inner[0]; alpar@209: alpar@100: Bfs bfs_test(G); alpar@100: bfs_test.run(s); alpar@209: kpeter@171: check(bfs_test.dist(t)==3,"Bfs found a wrong path." << bfs_test.dist(t)); alpar@100: alpar@100: Path p = bfs_test.path(t); kpeter@171: check(p.length()==3,"path() found a wrong path."); alpar@100: check(checkPath(G, p),"path() found a wrong path."); alpar@100: check(pathSource(G, p) == s,"path() found a wrong path."); alpar@100: check(pathTarget(G, p) == t,"path() found a wrong path."); alpar@209: alpar@100: deba@222: for(ArcIt e(G); e!=INVALID; ++e) { alpar@100: Node u=G.source(e); alpar@100: Node v=G.target(e); alpar@100: check( !bfs_test.reached(u) || deba@222: (bfs_test.dist(v) <= bfs_test.dist(u)+1), alpar@209: "Wrong output."); alpar@100: } alpar@100: deba@222: for(NodeIt v(G); v!=INVALID; ++v) { alpar@100: check(bfs_test.reached(v),"Each node should be reached."); alpar@100: if ( bfs_test.predArc(v)!=INVALID ) { alpar@100: Arc e=bfs_test.predArc(v); alpar@100: Node u=G.source(e); alpar@100: check(u==bfs_test.predNode(v),"Wrong tree."); alpar@100: check(bfs_test.dist(v) - bfs_test.dist(u) == 1, alpar@209: "Wrong distance. Difference: " alpar@209: << std::abs(bfs_test.dist(v) - bfs_test.dist(u) alpar@209: - 1)); alpar@100: } alpar@100: } alpar@100: } alpar@100: kpeter@171: int main() kpeter@171: { kpeter@171: checkBfs(); kpeter@171: checkBfs(); kpeter@171: return 0; kpeter@171: }