alpar@100: /* -*- C++ -*- alpar@100: * alpar@100: * 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: alpar@100: #include "test_tools.h" alpar@100: //#include alpar@100: #include alpar@100: #include alpar@100: #include alpar@100: #include alpar@100: alpar@100: using namespace lemon; alpar@100: alpar@100: const int PET_SIZE =5; alpar@100: alpar@100: alpar@100: void check_Bfs_Compile() alpar@100: { alpar@100: typedef concepts::Digraph Digraph; alpar@100: alpar@100: typedef Digraph::Arc Arc; alpar@100: typedef Digraph::Node Node; alpar@100: typedef Digraph::ArcIt ArcIt; alpar@100: typedef Digraph::NodeIt NodeIt; alpar@100: alpar@100: typedef Bfs BType; alpar@100: alpar@100: Digraph G; alpar@100: Node n; alpar@100: 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@100: alpar@100: BType bfs_test(G); alpar@100: alpar@100: bfs_test.run(n); alpar@100: 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@100: void check_Bfs_Function_Compile() alpar@100: { alpar@100: typedef int VType; alpar@100: typedef concepts::Digraph Digraph; alpar@100: alpar@100: typedef Digraph::Arc Arc; alpar@100: typedef Digraph::Node Node; alpar@100: typedef Digraph::ArcIt ArcIt; alpar@100: typedef Digraph::NodeIt NodeIt; alpar@100: typedef concepts::ReadMap LengthMap; alpar@100: 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: } alpar@100: alpar@100: int main() alpar@100: { alpar@100: alpar@100: // typedef SmartDigraph Digraph; alpar@100: typedef ListDigraph Digraph; alpar@100: alpar@100: typedef Digraph::Arc Arc; alpar@100: typedef Digraph::Node Node; alpar@100: typedef Digraph::ArcIt ArcIt; alpar@100: typedef Digraph::NodeIt NodeIt; alpar@100: typedef Digraph::ArcMap LengthMap; alpar@100: alpar@100: Digraph G; alpar@100: Node s, t; alpar@100: PetStruct ps = addPetersen(G,PET_SIZE); alpar@100: alpar@100: s=ps.outer[2]; alpar@100: t=ps.inner[0]; alpar@100: alpar@100: Bfs bfs_test(G); alpar@100: bfs_test.run(s); alpar@100: alpar@100: 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); alpar@100: check(p.length()==3,"getPath() 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@100: alpar@100: alpar@100: 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) || alpar@100: (bfs_test.dist(v) > bfs_test.dist(u)+1), alpar@100: "Wrong output."); alpar@100: } alpar@100: alpar@100: 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@100: "Wrong distance. Difference: " alpar@100: << std::abs(bfs_test.dist(v) - bfs_test.dist(u) alpar@100: - 1)); alpar@100: } alpar@100: } alpar@100: } alpar@100: