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