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: * alpar@1081: * Copyright (C) 2003-2011 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@632: Node s, t, n; kpeter@286: Arc e; kpeter@170: VType l; kpeter@632: int i; 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@632: concepts::ReadMap nm; kpeter@170: kpeter@286: { kpeter@286: DType dijkstra_test(G,length); kpeter@632: const DType& const_dijkstra_test = dijkstra_test; kpeter@170: kpeter@286: dijkstra_test.run(s); kpeter@286: dijkstra_test.run(s,t); kpeter@170: kpeter@632: dijkstra_test.init(); kpeter@632: dijkstra_test.addSource(s); kpeter@632: dijkstra_test.addSource(s, 1); kpeter@632: n = dijkstra_test.processNextNode(); kpeter@632: n = const_dijkstra_test.nextNode(); kpeter@632: b = const_dijkstra_test.emptyQueue(); kpeter@632: i = const_dijkstra_test.queueSize(); alpar@1081: kpeter@632: dijkstra_test.start(); kpeter@632: dijkstra_test.start(t); kpeter@632: dijkstra_test.start(nm); kpeter@632: kpeter@632: l = const_dijkstra_test.dist(t); kpeter@632: e = const_dijkstra_test.predArc(t); kpeter@632: s = const_dijkstra_test.predNode(t); kpeter@632: b = const_dijkstra_test.reached(t); kpeter@632: b = const_dijkstra_test.processed(t); kpeter@632: d = const_dijkstra_test.distMap(); kpeter@632: p = const_dijkstra_test.predMap(); kpeter@632: pp = const_dijkstra_test.path(t); kpeter@632: l = const_dijkstra_test.currentDist(t); kpeter@632: } kpeter@632: { kpeter@632: DType kpeter@632: ::SetPredMap > kpeter@632: ::SetDistMap > kpeter@632: ::SetStandardProcessedMap kpeter@632: ::SetProcessedMap > kpeter@632: ::SetOperationTraits > kpeter@632: ::SetHeap > > kpeter@632: ::SetStandardHeap > > alpar@1081: ::SetHeap >, kpeter@632: concepts::ReadWriteMap > kpeter@632: ::Create dijkstra_test(G,length); kpeter@632: kpeter@632: LengthMap length_map; kpeter@632: concepts::ReadWriteMap pred_map; kpeter@632: concepts::ReadWriteMap dist_map; kpeter@632: concepts::WriteMap processed_map; kpeter@632: concepts::ReadWriteMap heap_cross_ref; kpeter@632: BinHeap > heap(heap_cross_ref); alpar@1081: kpeter@632: dijkstra_test kpeter@632: .lengthMap(length_map) kpeter@632: .predMap(pred_map) kpeter@632: .distMap(dist_map) kpeter@632: .processedMap(processed_map) kpeter@632: .heap(heap, heap_cross_ref); kpeter@632: kpeter@632: dijkstra_test.run(s); kpeter@632: dijkstra_test.run(s,t); kpeter@632: kpeter@632: dijkstra_test.addSource(s); kpeter@632: dijkstra_test.addSource(s, 1); kpeter@632: n = dijkstra_test.processNextNode(); kpeter@632: n = dijkstra_test.nextNode(); kpeter@632: b = dijkstra_test.emptyQueue(); kpeter@632: i = dijkstra_test.queueSize(); alpar@1081: kpeter@632: dijkstra_test.start(); kpeter@632: dijkstra_test.start(t); kpeter@632: dijkstra_test.start(nm); kpeter@632: 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@632: b = dijkstra_test.processed(t); kpeter@286: pp = dijkstra_test.path(t); kpeter@632: l = dijkstra_test.currentDist(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); kpeter@293: digraphReader(G, input). 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: }