alpar@906: /* -*- C++ -*- alpar@906: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@1956: * Copyright (C) 2003-2006 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1359: * (Egervary Research Group on Combinatorial Optimization, 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: alpar@780: #include "test_tools.h" alpar@921: #include alpar@921: #include alpar@1283: #include alpar@2260: #include alpar@780: alpar@921: using namespace lemon; alpar@780: alpar@780: const int PET_SIZE =5; alpar@780: alpar@780: alpar@780: void check_Dfs_SmartGraph_Compile() alpar@780: { alpar@2260: typedef concepts::Graph Graph; alpar@780: alpar@780: typedef Graph::Edge Edge; alpar@780: typedef Graph::Node Node; alpar@780: typedef Graph::EdgeIt EdgeIt; alpar@780: typedef Graph::NodeIt NodeIt; alpar@780: alpar@793: typedef Dfs DType; alpar@780: alpar@780: Graph G; alpar@780: Node n; alpar@780: Edge e; alpar@793: int l; alpar@780: bool b; alpar@793: DType::DistMap d(G); alpar@793: DType::PredMap p(G); alpar@1218: // DType::PredNodeMap pn(G); alpar@780: alpar@793: DType dfs_test(G); alpar@780: alpar@780: dfs_test.run(n); alpar@780: alpar@780: l = dfs_test.dist(n); deba@1763: e = dfs_test.predEdge(n); alpar@780: n = dfs_test.predNode(n); alpar@780: d = dfs_test.distMap(); alpar@780: p = dfs_test.predMap(); alpar@1218: // pn = dfs_test.predNodeMap(); alpar@780: b = dfs_test.reached(n); alpar@780: deba@2335: Path pp = dfs_test.path(n); alpar@780: } alpar@780: alpar@1220: alpar@1220: void check_Dfs_Function_Compile() alpar@1220: { alpar@1220: typedef int VType; alpar@2260: typedef concepts::Graph Graph; alpar@1220: alpar@1220: typedef Graph::Edge Edge; alpar@1220: typedef Graph::Node Node; alpar@1220: typedef Graph::EdgeIt EdgeIt; alpar@1220: typedef Graph::NodeIt NodeIt; alpar@2260: typedef concepts::ReadMap LengthMap; alpar@1220: alpar@2135: Graph g; alpar@2135: dfs(g,Node()).run(); alpar@2135: dfs(g).source(Node()).run(); alpar@2135: dfs(g) alpar@2260: .predMap(concepts::WriteMap()) alpar@2260: .distMap(concepts::WriteMap()) alpar@2260: .reachedMap(concepts::ReadWriteMap()) alpar@2260: .processedMap(concepts::WriteMap()) alpar@1220: .run(Node()); alpar@1220: alpar@1220: } alpar@1220: alpar@780: int main() alpar@780: { alpar@780: alpar@780: typedef SmartGraph Graph; alpar@780: alpar@780: typedef Graph::Edge Edge; alpar@780: typedef Graph::Node Node; alpar@780: typedef Graph::EdgeIt EdgeIt; alpar@780: typedef Graph::NodeIt NodeIt; alpar@780: typedef Graph::EdgeMap LengthMap; alpar@780: alpar@780: Graph G; alpar@780: Node s, t; alpar@780: PetStruct ps = addPetersen(G,PET_SIZE); alpar@780: alpar@780: s=ps.outer[2]; alpar@780: t=ps.inner[0]; alpar@780: alpar@780: Dfs dfs_test(G); alpar@780: dfs_test.run(s); alpar@780: deba@2335: Path p = dfs_test.path(t); deba@2335: check(p.length()==dfs_test.dist(t),"path() found a wrong path."); deba@2335: check(checkPath(G, p),"path() found a wrong path."); deba@2335: check(pathSource(G, p) == s,"path() found a wrong path."); deba@2335: check(pathTarget(G, p) == t,"path() found a wrong path."); alpar@1283: alpar@780: for(NodeIt v(G); v!=INVALID; ++v) { alpar@780: check(dfs_test.reached(v),"Each node should be reached."); deba@1763: if ( dfs_test.predEdge(v)!=INVALID ) { deba@1763: Edge e=dfs_test.predEdge(v); alpar@986: Node u=G.source(e); alpar@780: check(u==dfs_test.predNode(v),"Wrong tree."); alpar@780: check(dfs_test.dist(v) - dfs_test.dist(u) == 1, alpar@1233: "Wrong distance. (" << dfs_test.dist(u) << "->" alpar@1233: <