1.1 --- a/test/CMakeLists.txt Sun Aug 02 13:24:46 2009 +0200
1.2 +++ b/test/CMakeLists.txt Mon Aug 03 00:52:45 2009 +0200
1.3 @@ -9,6 +9,7 @@
1.4
1.5 SET(TESTS
1.6 adaptors_test
1.7 + bellman_ford_test
1.8 bfs_test
1.9 circulation_test
1.10 connectivity_test
2.1 --- a/test/Makefile.am Sun Aug 02 13:24:46 2009 +0200
2.2 +++ b/test/Makefile.am Mon Aug 03 00:52:45 2009 +0200
2.3 @@ -7,6 +7,7 @@
2.4
2.5 check_PROGRAMS += \
2.6 test/adaptors_test \
2.7 + test/bellman_ford_test \
2.8 test/bfs_test \
2.9 test/circulation_test \
2.10 test/connectivity_test \
2.11 @@ -52,6 +53,7 @@
2.12 XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
2.13
2.14 test_adaptors_test_SOURCES = test/adaptors_test.cc
2.15 +test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc
2.16 test_bfs_test_SOURCES = test/bfs_test.cc
2.17 test_circulation_test_SOURCES = test/circulation_test.cc
2.18 test_counter_test_SOURCES = test/counter_test.cc
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/test/bellman_ford_test.cc Mon Aug 03 00:52:45 2009 +0200
3.3 @@ -0,0 +1,227 @@
3.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library.
3.7 + *
3.8 + * Copyright (C) 2003-2009
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 +#include <lemon/concepts/digraph.h>
3.23 +#include <lemon/smart_graph.h>
3.24 +#include <lemon/list_graph.h>
3.25 +#include <lemon/lgf_reader.h>
3.26 +#include <lemon/bellman_ford.h>
3.27 +#include <lemon/path.h>
3.28 +
3.29 +#include "graph_test.h"
3.30 +#include "test_tools.h"
3.31 +
3.32 +using namespace lemon;
3.33 +
3.34 +char test_lgf[] =
3.35 + "@nodes\n"
3.36 + "label\n"
3.37 + "0\n"
3.38 + "1\n"
3.39 + "2\n"
3.40 + "3\n"
3.41 + "4\n"
3.42 + "@arcs\n"
3.43 + " length\n"
3.44 + "0 1 3\n"
3.45 + "1 2 -3\n"
3.46 + "1 2 -5\n"
3.47 + "1 3 -2\n"
3.48 + "0 2 -1\n"
3.49 + "1 2 -4\n"
3.50 + "0 3 2\n"
3.51 + "4 2 -5\n"
3.52 + "2 3 1\n"
3.53 + "@attributes\n"
3.54 + "source 0\n"
3.55 + "target 3\n";
3.56 +
3.57 +
3.58 +void checkBellmanFordCompile()
3.59 +{
3.60 + typedef int Value;
3.61 + typedef concepts::Digraph Digraph;
3.62 + typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;
3.63 + typedef BellmanFord<Digraph, LengthMap> BF;
3.64 + typedef Digraph::Node Node;
3.65 + typedef Digraph::Arc Arc;
3.66 +
3.67 + Digraph gr;
3.68 + Node s, t, n;
3.69 + Arc e;
3.70 + Value l;
3.71 + int k;
3.72 + bool b;
3.73 + BF::DistMap d(gr);
3.74 + BF::PredMap p(gr);
3.75 + LengthMap length;
3.76 + concepts::Path<Digraph> pp;
3.77 +
3.78 + {
3.79 + BF bf_test(gr,length);
3.80 + const BF& const_bf_test = bf_test;
3.81 +
3.82 + bf_test.run(s);
3.83 + bf_test.run(s,k);
3.84 +
3.85 + bf_test.init();
3.86 + bf_test.addSource(s);
3.87 + bf_test.addSource(s, 1);
3.88 + b = bf_test.processNextRound();
3.89 + b = bf_test.processNextWeakRound();
3.90 +
3.91 + bf_test.start();
3.92 + bf_test.checkedStart();
3.93 + bf_test.limitedStart(k);
3.94 +
3.95 + l = const_bf_test.dist(t);
3.96 + e = const_bf_test.predArc(t);
3.97 + s = const_bf_test.predNode(t);
3.98 + b = const_bf_test.reached(t);
3.99 + d = const_bf_test.distMap();
3.100 + p = const_bf_test.predMap();
3.101 + pp = const_bf_test.path(t);
3.102 +
3.103 + for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
3.104 + }
3.105 + {
3.106 + BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
3.107 + ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
3.108 + ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
3.109 + ::Create bf_test(gr,length);
3.110 +
3.111 + LengthMap length_map;
3.112 + concepts::ReadWriteMap<Node,Arc> pred_map;
3.113 + concepts::ReadWriteMap<Node,Value> dist_map;
3.114 +
3.115 + bf_test
3.116 + .lengthMap(length_map)
3.117 + .predMap(pred_map)
3.118 + .distMap(dist_map);
3.119 +
3.120 + bf_test.run(s);
3.121 + bf_test.run(s,k);
3.122 +
3.123 + bf_test.init();
3.124 + bf_test.addSource(s);
3.125 + bf_test.addSource(s, 1);
3.126 + b = bf_test.processNextRound();
3.127 + b = bf_test.processNextWeakRound();
3.128 +
3.129 + bf_test.start();
3.130 + bf_test.checkedStart();
3.131 + bf_test.limitedStart(k);
3.132 +
3.133 + l = bf_test.dist(t);
3.134 + e = bf_test.predArc(t);
3.135 + s = bf_test.predNode(t);
3.136 + b = bf_test.reached(t);
3.137 + pp = bf_test.path(t);
3.138 + }
3.139 +}
3.140 +
3.141 +void checkBellmanFordFunctionCompile()
3.142 +{
3.143 + typedef int Value;
3.144 + typedef concepts::Digraph Digraph;
3.145 + typedef Digraph::Arc Arc;
3.146 + typedef Digraph::Node Node;
3.147 + typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;
3.148 +
3.149 + Digraph g;
3.150 + bool b;
3.151 + bellmanFord(g,LengthMap()).run(Node());
3.152 + b = bellmanFord(g,LengthMap()).run(Node(),Node());
3.153 + bellmanFord(g,LengthMap())
3.154 + .predMap(concepts::ReadWriteMap<Node,Arc>())
3.155 + .distMap(concepts::ReadWriteMap<Node,Value>())
3.156 + .run(Node());
3.157 + b=bellmanFord(g,LengthMap())
3.158 + .predMap(concepts::ReadWriteMap<Node,Arc>())
3.159 + .distMap(concepts::ReadWriteMap<Node,Value>())
3.160 + .path(concepts::Path<Digraph>())
3.161 + .dist(Value())
3.162 + .run(Node(),Node());
3.163 +}
3.164 +
3.165 +
3.166 +template <typename Digraph, typename Value>
3.167 +void checkBellmanFord() {
3.168 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
3.169 + typedef typename Digraph::template ArcMap<Value> LengthMap;
3.170 +
3.171 + Digraph gr;
3.172 + Node s, t;
3.173 + LengthMap length(gr);
3.174 +
3.175 + std::istringstream input(test_lgf);
3.176 + digraphReader(gr, input).
3.177 + arcMap("length", length).
3.178 + node("source", s).
3.179 + node("target", t).
3.180 + run();
3.181 +
3.182 + BellmanFord<Digraph, LengthMap>
3.183 + bf(gr, length);
3.184 + bf.run(s);
3.185 + Path<Digraph> p = bf.path(t);
3.186 +
3.187 + check(bf.reached(t) && bf.dist(t) == -1, "Bellman-Ford found a wrong path.");
3.188 + check(p.length() == 3, "path() found a wrong path.");
3.189 + check(checkPath(gr, p), "path() found a wrong path.");
3.190 + check(pathSource(gr, p) == s, "path() found a wrong path.");
3.191 + check(pathTarget(gr, p) == t, "path() found a wrong path.");
3.192 +
3.193 + ListPath<Digraph> path;
3.194 + Value dist;
3.195 + bool reached = bellmanFord(gr,length).path(path).dist(dist).run(s,t);
3.196 +
3.197 + check(reached && dist == -1, "Bellman-Ford found a wrong path.");
3.198 + check(path.length() == 3, "path() found a wrong path.");
3.199 + check(checkPath(gr, path), "path() found a wrong path.");
3.200 + check(pathSource(gr, path) == s, "path() found a wrong path.");
3.201 + check(pathTarget(gr, path) == t, "path() found a wrong path.");
3.202 +
3.203 + for(ArcIt e(gr); e!=INVALID; ++e) {
3.204 + Node u=gr.source(e);
3.205 + Node v=gr.target(e);
3.206 + check(!bf.reached(u) || (bf.dist(v) - bf.dist(u) <= length[e]),
3.207 + "Wrong output. dist(target)-dist(source)-arc_length=" <<
3.208 + bf.dist(v) - bf.dist(u) - length[e]);
3.209 + }
3.210 +
3.211 + for(NodeIt v(gr); v!=INVALID; ++v) {
3.212 + if (bf.reached(v)) {
3.213 + check(v==s || bf.predArc(v)!=INVALID, "Wrong tree.");
3.214 + if (bf.predArc(v)!=INVALID ) {
3.215 + Arc e=bf.predArc(v);
3.216 + Node u=gr.source(e);
3.217 + check(u==bf.predNode(v),"Wrong tree.");
3.218 + check(bf.dist(v) - bf.dist(u) == length[e],
3.219 + "Wrong distance! Difference: " <<
3.220 + bf.dist(v) - bf.dist(u) - length[e]);
3.221 + }
3.222 + }
3.223 + }
3.224 +}
3.225 +
3.226 +int main() {
3.227 + checkBellmanFord<ListDigraph, int>();
3.228 + checkBellmanFord<SmartDigraph, double>();
3.229 + return 0;
3.230 +}