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 deba@228: #include kpeter@170: #include kpeter@170: #include kpeter@286: #include kpeter@170: kpeter@171: #include "graph_test.h" kpeter@170: #include "test_tools.h" kpeter@170: kpeter@170: using namespace lemon; kpeter@170: deba@228: char test_lgf[] = deba@228: "@nodes\n" deba@228: "label\n" deba@228: "0\n" deba@228: "1\n" deba@228: "2\n" deba@228: "3\n" deba@228: "4\n" deba@228: "@arcs\n" deba@228: " label length\n" deba@228: "0 1 0 1\n" deba@228: "1 2 1 1\n" deba@228: "2 3 2 1\n" deba@228: "0 3 4 5\n" deba@228: "0 3 5 10\n" deba@228: "0 3 6 7\n" deba@228: "4 2 7 1\n" deba@228: "@attributes\n" deba@228: "source 0\n" deba@228: "target 3\n"; deba@228: 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; kpeter@286: typedef Digraph::Node Node; kpeter@286: typedef Digraph::Arc Arc; alpar@209: kpeter@170: Digraph G; kpeter@286: Node s, t; kpeter@286: Arc e; kpeter@170: VType l; kpeter@170: bool b; kpeter@170: DType::DistMap d(G); kpeter@170: DType::PredMap p(G); kpeter@170: LengthMap length; kpeter@286: Path pp; kpeter@170: kpeter@286: { kpeter@286: DType dijkstra_test(G,length); kpeter@170: kpeter@286: dijkstra_test.run(s); kpeter@286: dijkstra_test.run(s,t); kpeter@170: kpeter@286: l = dijkstra_test.dist(t); kpeter@286: e = dijkstra_test.predArc(t); kpeter@286: s = dijkstra_test.predNode(t); kpeter@286: b = dijkstra_test.reached(t); kpeter@286: d = dijkstra_test.distMap(); kpeter@286: p = dijkstra_test.predMap(); kpeter@286: pp = dijkstra_test.path(t); kpeter@286: } kpeter@286: { kpeter@286: DType kpeter@286: ::SetPredMap > kpeter@286: ::SetDistMap > kpeter@286: ::SetProcessedMap > kpeter@286: ::SetStandardProcessedMap kpeter@286: ::SetOperationTraits > kpeter@286: ::SetHeap > > kpeter@286: ::SetStandardHeap > > kpeter@286: ::Create dijkstra_test(G,length); kpeter@170: kpeter@286: dijkstra_test.run(s); kpeter@286: dijkstra_test.run(s,t); kpeter@286: kpeter@286: l = dijkstra_test.dist(t); kpeter@286: e = dijkstra_test.predArc(t); kpeter@286: s = dijkstra_test.predNode(t); kpeter@286: b = dijkstra_test.reached(t); kpeter@286: pp = dijkstra_test.path(t); kpeter@286: } kpeter@286: 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@278: bool b; kpeter@278: dijkstra(g,LengthMap()).run(Node()); kpeter@278: b=dijkstra(g,LengthMap()).run(Node(),Node()); kpeter@170: dijkstra(g,LengthMap()) kpeter@278: .predMap(concepts::ReadWriteMap()) kpeter@278: .distMap(concepts::ReadWriteMap()) kpeter@278: .processedMap(concepts::WriteMap()) kpeter@170: .run(Node()); kpeter@278: b=dijkstra(g,LengthMap()) kpeter@278: .predMap(concepts::ReadWriteMap()) kpeter@278: .distMap(concepts::ReadWriteMap()) kpeter@278: .processedMap(concepts::WriteMap()) kpeter@278: .path(concepts::Path()) kpeter@278: .dist(VType()) kpeter@278: .run(Node(),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); alpar@209: deba@228: std::istringstream input(test_lgf); deba@228: digraphReader(input, G). deba@228: arcMap("length", length). deba@228: node("source", s). deba@228: node("target", t). deba@228: run(); alpar@209: alpar@209: Dijkstra alpar@209: dijkstra_test(G, length); kpeter@170: dijkstra_test.run(s); alpar@209: deba@228: check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path."); kpeter@170: kpeter@170: Path p = dijkstra_test.path(t); kpeter@278: check(p.length()==3,"path() 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]), kpeter@278: "Wrong output. dist(target)-dist(source)-arc_length=" << alpar@210: dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]); kpeter@170: } kpeter@170: deba@228: for(NodeIt v(G); v!=INVALID; ++v) { deba@228: if (dijkstra_test.reached(v)) { deba@228: check(v==s || dijkstra_test.predArc(v)!=INVALID, "Wrong tree."); deba@228: if (dijkstra_test.predArc(v)!=INVALID ) { deba@228: Arc e=dijkstra_test.predArc(v); deba@228: Node u=G.source(e); deba@228: check(u==dijkstra_test.predNode(v),"Wrong tree."); deba@228: check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e], deba@228: "Wrong distance! Difference: " << deba@228: std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e])); deba@228: } 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: }