1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/dijkstra_test.cc Sun Jun 15 22:03:33 2008 +0200
1.3 @@ -0,0 +1,140 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +///\file
1.23 +///\brief Test cases for Dijkstra algorithm.
1.24 +
1.25 +#include <lemon/concepts/digraph.h>
1.26 +#include <lemon/smart_graph.h>
1.27 +#include <lemon/list_graph.h>
1.28 +#include <lemon/graph_utils.h>
1.29 +#include <lemon/dijkstra.h>
1.30 +#include <lemon/path.h>
1.31 +
1.32 +#include "test_tools.h"
1.33 +
1.34 +using namespace lemon;
1.35 +
1.36 +void checkDijkstraCompile()
1.37 +{
1.38 + typedef int VType;
1.39 + typedef concepts::Digraph Digraph;
1.40 + typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
1.41 + typedef Dijkstra<Digraph, LengthMap> DType;
1.42 +
1.43 + Digraph G;
1.44 + Digraph::Node n;
1.45 + Digraph::Arc e;
1.46 + VType l;
1.47 + bool b;
1.48 + DType::DistMap d(G);
1.49 + DType::PredMap p(G);
1.50 + // DType::PredNodeMap pn(G);
1.51 + LengthMap length;
1.52 +
1.53 + DType dijkstra_test(G,length);
1.54 +
1.55 + dijkstra_test.run(n);
1.56 +
1.57 + l = dijkstra_test.dist(n);
1.58 + e = dijkstra_test.predArc(n);
1.59 + n = dijkstra_test.predNode(n);
1.60 + d = dijkstra_test.distMap();
1.61 + p = dijkstra_test.predMap();
1.62 + // pn = dijkstra_test.predNodeMap();
1.63 + b = dijkstra_test.reached(n);
1.64 +
1.65 + Path<Digraph> pp = dijkstra_test.path(n);
1.66 +}
1.67 +
1.68 +void checkDijkstraFunctionCompile()
1.69 +{
1.70 + typedef int VType;
1.71 + typedef concepts::Digraph Digraph;
1.72 + typedef Digraph::Arc Arc;
1.73 + typedef Digraph::Node Node;
1.74 + typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
1.75 +
1.76 + Digraph g;
1.77 + dijkstra(g,LengthMap(),Node()).run();
1.78 + dijkstra(g,LengthMap()).source(Node()).run();
1.79 + dijkstra(g,LengthMap())
1.80 + .predMap(concepts::WriteMap<Node,Arc>())
1.81 + .distMap(concepts::WriteMap<Node,VType>())
1.82 + .run(Node());
1.83 +}
1.84 +
1.85 +template <class Digraph>
1.86 +void checkDijkstra() {
1.87 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.88 + typedef typename Digraph::template ArcMap<int> LengthMap;
1.89 +
1.90 + Digraph G;
1.91 + Node s, t;
1.92 + LengthMap length(G);
1.93 + PetStruct<Digraph> ps = addPetersen(G, 5);
1.94 +
1.95 + for(int i=0;i<5;i++) {
1.96 + length[ps.outcir[i]]=4;
1.97 + length[ps.incir[i]]=1;
1.98 + length[ps.chords[i]]=10;
1.99 + }
1.100 + s=ps.outer[0];
1.101 + t=ps.inner[1];
1.102 +
1.103 + Dijkstra<Digraph, LengthMap>
1.104 + dijkstra_test(G, length);
1.105 + dijkstra_test.run(s);
1.106 +
1.107 + check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
1.108 +
1.109 + Path<Digraph> p = dijkstra_test.path(t);
1.110 + check(p.length()==4,"getPath() found a wrong path.");
1.111 + check(checkPath(G, p),"path() found a wrong path.");
1.112 + check(pathSource(G, p) == s,"path() found a wrong path.");
1.113 + check(pathTarget(G, p) == t,"path() found a wrong path.");
1.114 +
1.115 + for(ArcIt e(G); e!=INVALID; ++e) {
1.116 + Node u=G.source(e);
1.117 + Node v=G.target(e);
1.118 + check( !dijkstra_test.reached(u) || (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]),
1.119 + "dist(target)-dist(source)-arc_length= " << dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
1.120 + }
1.121 +
1.122 + for(NodeIt v(G); v!=INVALID; ++v){
1.123 + check(dijkstra_test.reached(v),"Each node should be reached.");
1.124 + if ( dijkstra_test.predArc(v)!=INVALID ) {
1.125 + Arc e=dijkstra_test.predArc(v);
1.126 + Node u=G.source(e);
1.127 + check(u==dijkstra_test.predNode(v),"Wrong tree.");
1.128 + check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
1.129 + "Wrong distance! Difference: " << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]));
1.130 + }
1.131 + }
1.132 +
1.133 + {
1.134 + NullMap<Node,Arc> myPredMap;
1.135 + dijkstra(G,length).predMap(myPredMap).run(s);
1.136 + }
1.137 +}
1.138 +
1.139 +int main() {
1.140 + checkDijkstra<ListDigraph>();
1.141 + checkDijkstra<SmartDigraph>();
1.142 + return 0;
1.143 +}