1.1 --- a/test/CMakeLists.txt Sun Jun 15 09:19:53 2008 +0200
1.2 +++ b/test/CMakeLists.txt Sun Jun 15 22:03:33 2008 +0200
1.3 @@ -7,6 +7,7 @@
1.4 counter_test
1.5 dfs_test
1.6 digraph_test
1.7 + dijkstra_test
1.8 dim_test
1.9 error_test
1.10 graph_test
2.1 --- a/test/Makefile.am Sun Jun 15 09:19:53 2008 +0200
2.2 +++ b/test/Makefile.am Sun Jun 15 22:03:33 2008 +0200
2.3 @@ -13,6 +13,7 @@
2.4 test/counter_test \
2.5 test/dfs_test \
2.6 test/digraph_test \
2.7 + test/dijkstra_test \
2.8 test/dim_test \
2.9 test/error_test \
2.10 test/graph_test \
2.11 @@ -33,6 +34,7 @@
2.12 test_counter_test_SOURCES = test/counter_test.cc
2.13 test_dfs_test_SOURCES = test/dfs_test.cc
2.14 test_digraph_test_SOURCES = test/digraph_test.cc
2.15 +test_dijkstra_test_SOURCES = test/dijkstra_test.cc
2.16 test_dim_test_SOURCES = test/dim_test.cc
2.17 test_error_test_SOURCES = test/error_test.cc
2.18 test_graph_test_SOURCES = test/graph_test.cc
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/test/dijkstra_test.cc Sun Jun 15 22:03:33 2008 +0200
3.3 @@ -0,0 +1,140 @@
3.4 +/* -*- C++ -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library
3.7 + *
3.8 + * Copyright (C) 2003-2008
3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 + *
3.12 + * Permission to use, modify and distribute this software is granted
3.13 + * provided that this copyright notice appears in all copies. For
3.14 + * precise terms see the accompanying LICENSE file.
3.15 + *
3.16 + * This software is provided "AS IS" with no warranty of any kind,
3.17 + * express or implied, and with no claim as to its suitability for any
3.18 + * purpose.
3.19 + *
3.20 + */
3.21 +
3.22 +///\file
3.23 +///\brief Test cases for Dijkstra algorithm.
3.24 +
3.25 +#include <lemon/concepts/digraph.h>
3.26 +#include <lemon/smart_graph.h>
3.27 +#include <lemon/list_graph.h>
3.28 +#include <lemon/graph_utils.h>
3.29 +#include <lemon/dijkstra.h>
3.30 +#include <lemon/path.h>
3.31 +
3.32 +#include "test_tools.h"
3.33 +
3.34 +using namespace lemon;
3.35 +
3.36 +void checkDijkstraCompile()
3.37 +{
3.38 + typedef int VType;
3.39 + typedef concepts::Digraph Digraph;
3.40 + typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
3.41 + typedef Dijkstra<Digraph, LengthMap> DType;
3.42 +
3.43 + Digraph G;
3.44 + Digraph::Node n;
3.45 + Digraph::Arc e;
3.46 + VType l;
3.47 + bool b;
3.48 + DType::DistMap d(G);
3.49 + DType::PredMap p(G);
3.50 + // DType::PredNodeMap pn(G);
3.51 + LengthMap length;
3.52 +
3.53 + DType dijkstra_test(G,length);
3.54 +
3.55 + dijkstra_test.run(n);
3.56 +
3.57 + l = dijkstra_test.dist(n);
3.58 + e = dijkstra_test.predArc(n);
3.59 + n = dijkstra_test.predNode(n);
3.60 + d = dijkstra_test.distMap();
3.61 + p = dijkstra_test.predMap();
3.62 + // pn = dijkstra_test.predNodeMap();
3.63 + b = dijkstra_test.reached(n);
3.64 +
3.65 + Path<Digraph> pp = dijkstra_test.path(n);
3.66 +}
3.67 +
3.68 +void checkDijkstraFunctionCompile()
3.69 +{
3.70 + typedef int VType;
3.71 + typedef concepts::Digraph Digraph;
3.72 + typedef Digraph::Arc Arc;
3.73 + typedef Digraph::Node Node;
3.74 + typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
3.75 +
3.76 + Digraph g;
3.77 + dijkstra(g,LengthMap(),Node()).run();
3.78 + dijkstra(g,LengthMap()).source(Node()).run();
3.79 + dijkstra(g,LengthMap())
3.80 + .predMap(concepts::WriteMap<Node,Arc>())
3.81 + .distMap(concepts::WriteMap<Node,VType>())
3.82 + .run(Node());
3.83 +}
3.84 +
3.85 +template <class Digraph>
3.86 +void checkDijkstra() {
3.87 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
3.88 + typedef typename Digraph::template ArcMap<int> LengthMap;
3.89 +
3.90 + Digraph G;
3.91 + Node s, t;
3.92 + LengthMap length(G);
3.93 + PetStruct<Digraph> ps = addPetersen(G, 5);
3.94 +
3.95 + for(int i=0;i<5;i++) {
3.96 + length[ps.outcir[i]]=4;
3.97 + length[ps.incir[i]]=1;
3.98 + length[ps.chords[i]]=10;
3.99 + }
3.100 + s=ps.outer[0];
3.101 + t=ps.inner[1];
3.102 +
3.103 + Dijkstra<Digraph, LengthMap>
3.104 + dijkstra_test(G, length);
3.105 + dijkstra_test.run(s);
3.106 +
3.107 + check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
3.108 +
3.109 + Path<Digraph> p = dijkstra_test.path(t);
3.110 + check(p.length()==4,"getPath() found a wrong path.");
3.111 + check(checkPath(G, p),"path() found a wrong path.");
3.112 + check(pathSource(G, p) == s,"path() found a wrong path.");
3.113 + check(pathTarget(G, p) == t,"path() found a wrong path.");
3.114 +
3.115 + for(ArcIt e(G); e!=INVALID; ++e) {
3.116 + Node u=G.source(e);
3.117 + Node v=G.target(e);
3.118 + check( !dijkstra_test.reached(u) || (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]),
3.119 + "dist(target)-dist(source)-arc_length= " << dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
3.120 + }
3.121 +
3.122 + for(NodeIt v(G); v!=INVALID; ++v){
3.123 + check(dijkstra_test.reached(v),"Each node should be reached.");
3.124 + if ( dijkstra_test.predArc(v)!=INVALID ) {
3.125 + Arc e=dijkstra_test.predArc(v);
3.126 + Node u=G.source(e);
3.127 + check(u==dijkstra_test.predNode(v),"Wrong tree.");
3.128 + check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
3.129 + "Wrong distance! Difference: " << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]));
3.130 + }
3.131 + }
3.132 +
3.133 + {
3.134 + NullMap<Node,Arc> myPredMap;
3.135 + dijkstra(G,length).predMap(myPredMap).run(s);
3.136 + }
3.137 +}
3.138 +
3.139 +int main() {
3.140 + checkDijkstra<ListDigraph>();
3.141 + checkDijkstra<SmartDigraph>();
3.142 + return 0;
3.143 +}