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: 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: kpeter@171: void checkDfsCompile() alpar@100: { alpar@100: typedef concepts::Digraph Digraph; alpar@100: typedef Dfs DType; alpar@100: alpar@100: Digraph G; kpeter@171: Digraph::Node n; kpeter@171: Digraph::Arc e; alpar@100: int l; alpar@100: bool b; alpar@100: DType::DistMap d(G); alpar@100: DType::PredMap p(G); alpar@100: // DType::PredNodeMap pn(G); alpar@100: alpar@100: DType dfs_test(G); alpar@100: alpar@100: dfs_test.run(n); alpar@100: alpar@100: l = dfs_test.dist(n); alpar@100: e = dfs_test.predArc(n); alpar@100: n = dfs_test.predNode(n); alpar@100: d = dfs_test.distMap(); alpar@100: p = dfs_test.predMap(); alpar@100: // pn = dfs_test.predNodeMap(); alpar@100: b = dfs_test.reached(n); alpar@100: alpar@100: Path pp = dfs_test.path(n); alpar@100: } alpar@100: kpeter@171: void checkDfsFunctionCompile() 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@100: alpar@100: Digraph g; alpar@100: dfs(g,Node()).run(); alpar@100: dfs(g).source(Node()).run(); alpar@100: dfs(g) alpar@100: .predMap(concepts::WriteMap()) alpar@100: .distMap(concepts::WriteMap()) alpar@100: .reachedMap(concepts::ReadWriteMap()) alpar@100: .processedMap(concepts::WriteMap()) kpeter@171: .run(Node()); alpar@100: } alpar@100: kpeter@171: template kpeter@171: void checkDfs() { 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@100: alpar@100: s=ps.outer[2]; alpar@100: t=ps.inner[0]; alpar@100: alpar@100: Dfs dfs_test(G); alpar@100: dfs_test.run(s); alpar@100: alpar@100: Path p = dfs_test.path(t); kpeter@171: check(p.length() == dfs_test.dist(t),"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@100: alpar@100: for(NodeIt v(G); v!=INVALID; ++v) { alpar@100: check(dfs_test.reached(v),"Each node should be reached."); alpar@100: if ( dfs_test.predArc(v)!=INVALID ) { alpar@100: Arc e=dfs_test.predArc(v); alpar@100: Node u=G.source(e); alpar@100: check(u==dfs_test.predNode(v),"Wrong tree."); alpar@100: check(dfs_test.dist(v) - dfs_test.dist(u) == 1, alpar@100: "Wrong distance. (" << dfs_test.dist(u) << "->" alpar@100: <(); kpeter@171: checkDfs(); kpeter@171: return 0; kpeter@171: }