1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/bellman_ford_test.cc Thu Nov 05 15:48:01 2009 +0100
1.3 @@ -0,0 +1,285 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2009
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 +#include <lemon/concepts/digraph.h>
1.23 +#include <lemon/smart_graph.h>
1.24 +#include <lemon/list_graph.h>
1.25 +#include <lemon/lgf_reader.h>
1.26 +#include <lemon/bellman_ford.h>
1.27 +#include <lemon/path.h>
1.28 +
1.29 +#include "graph_test.h"
1.30 +#include "test_tools.h"
1.31 +
1.32 +using namespace lemon;
1.33 +
1.34 +char test_lgf[] =
1.35 + "@nodes\n"
1.36 + "label\n"
1.37 + "0\n"
1.38 + "1\n"
1.39 + "2\n"
1.40 + "3\n"
1.41 + "4\n"
1.42 + "@arcs\n"
1.43 + " length\n"
1.44 + "0 1 3\n"
1.45 + "1 2 -3\n"
1.46 + "1 2 -5\n"
1.47 + "1 3 -2\n"
1.48 + "0 2 -1\n"
1.49 + "1 2 -4\n"
1.50 + "0 3 2\n"
1.51 + "4 2 -5\n"
1.52 + "2 3 1\n"
1.53 + "@attributes\n"
1.54 + "source 0\n"
1.55 + "target 3\n";
1.56 +
1.57 +
1.58 +void checkBellmanFordCompile()
1.59 +{
1.60 + typedef int Value;
1.61 + typedef concepts::Digraph Digraph;
1.62 + typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;
1.63 + typedef BellmanFord<Digraph, LengthMap> BF;
1.64 + typedef Digraph::Node Node;
1.65 + typedef Digraph::Arc Arc;
1.66 +
1.67 + Digraph gr;
1.68 + Node s, t, n;
1.69 + Arc e;
1.70 + Value l;
1.71 + int k;
1.72 + bool b;
1.73 + BF::DistMap d(gr);
1.74 + BF::PredMap p(gr);
1.75 + LengthMap length;
1.76 + concepts::Path<Digraph> pp;
1.77 +
1.78 + {
1.79 + BF bf_test(gr,length);
1.80 + const BF& const_bf_test = bf_test;
1.81 +
1.82 + bf_test.run(s);
1.83 + bf_test.run(s,k);
1.84 +
1.85 + bf_test.init();
1.86 + bf_test.addSource(s);
1.87 + bf_test.addSource(s, 1);
1.88 + b = bf_test.processNextRound();
1.89 + b = bf_test.processNextWeakRound();
1.90 +
1.91 + bf_test.start();
1.92 + bf_test.checkedStart();
1.93 + bf_test.limitedStart(k);
1.94 +
1.95 + l = const_bf_test.dist(t);
1.96 + e = const_bf_test.predArc(t);
1.97 + s = const_bf_test.predNode(t);
1.98 + b = const_bf_test.reached(t);
1.99 + d = const_bf_test.distMap();
1.100 + p = const_bf_test.predMap();
1.101 + pp = const_bf_test.path(t);
1.102 + pp = const_bf_test.negativeCycle();
1.103 +
1.104 + for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
1.105 + }
1.106 + {
1.107 + BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
1.108 + ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
1.109 + ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
1.110 + ::Create bf_test(gr,length);
1.111 +
1.112 + LengthMap length_map;
1.113 + concepts::ReadWriteMap<Node,Arc> pred_map;
1.114 + concepts::ReadWriteMap<Node,Value> dist_map;
1.115 +
1.116 + bf_test
1.117 + .lengthMap(length_map)
1.118 + .predMap(pred_map)
1.119 + .distMap(dist_map);
1.120 +
1.121 + bf_test.run(s);
1.122 + bf_test.run(s,k);
1.123 +
1.124 + bf_test.init();
1.125 + bf_test.addSource(s);
1.126 + bf_test.addSource(s, 1);
1.127 + b = bf_test.processNextRound();
1.128 + b = bf_test.processNextWeakRound();
1.129 +
1.130 + bf_test.start();
1.131 + bf_test.checkedStart();
1.132 + bf_test.limitedStart(k);
1.133 +
1.134 + l = bf_test.dist(t);
1.135 + e = bf_test.predArc(t);
1.136 + s = bf_test.predNode(t);
1.137 + b = bf_test.reached(t);
1.138 + pp = bf_test.path(t);
1.139 + pp = bf_test.negativeCycle();
1.140 + }
1.141 +}
1.142 +
1.143 +void checkBellmanFordFunctionCompile()
1.144 +{
1.145 + typedef int Value;
1.146 + typedef concepts::Digraph Digraph;
1.147 + typedef Digraph::Arc Arc;
1.148 + typedef Digraph::Node Node;
1.149 + typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;
1.150 +
1.151 + Digraph g;
1.152 + bool b;
1.153 + bellmanFord(g,LengthMap()).run(Node());
1.154 + b = bellmanFord(g,LengthMap()).run(Node(),Node());
1.155 + bellmanFord(g,LengthMap())
1.156 + .predMap(concepts::ReadWriteMap<Node,Arc>())
1.157 + .distMap(concepts::ReadWriteMap<Node,Value>())
1.158 + .run(Node());
1.159 + b=bellmanFord(g,LengthMap())
1.160 + .predMap(concepts::ReadWriteMap<Node,Arc>())
1.161 + .distMap(concepts::ReadWriteMap<Node,Value>())
1.162 + .path(concepts::Path<Digraph>())
1.163 + .dist(Value())
1.164 + .run(Node(),Node());
1.165 +}
1.166 +
1.167 +
1.168 +template <typename Digraph, typename Value>
1.169 +void checkBellmanFord() {
1.170 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.171 + typedef typename Digraph::template ArcMap<Value> LengthMap;
1.172 +
1.173 + Digraph gr;
1.174 + Node s, t;
1.175 + LengthMap length(gr);
1.176 +
1.177 + std::istringstream input(test_lgf);
1.178 + digraphReader(gr, input).
1.179 + arcMap("length", length).
1.180 + node("source", s).
1.181 + node("target", t).
1.182 + run();
1.183 +
1.184 + BellmanFord<Digraph, LengthMap>
1.185 + bf(gr, length);
1.186 + bf.run(s);
1.187 + Path<Digraph> p = bf.path(t);
1.188 +
1.189 + check(bf.reached(t) && bf.dist(t) == -1, "Bellman-Ford found a wrong path.");
1.190 + check(p.length() == 3, "path() found a wrong path.");
1.191 + check(checkPath(gr, p), "path() found a wrong path.");
1.192 + check(pathSource(gr, p) == s, "path() found a wrong path.");
1.193 + check(pathTarget(gr, p) == t, "path() found a wrong path.");
1.194 +
1.195 + ListPath<Digraph> path;
1.196 + Value dist;
1.197 + bool reached = bellmanFord(gr,length).path(path).dist(dist).run(s,t);
1.198 +
1.199 + check(reached && dist == -1, "Bellman-Ford found a wrong path.");
1.200 + check(path.length() == 3, "path() found a wrong path.");
1.201 + check(checkPath(gr, path), "path() found a wrong path.");
1.202 + check(pathSource(gr, path) == s, "path() found a wrong path.");
1.203 + check(pathTarget(gr, path) == t, "path() found a wrong path.");
1.204 +
1.205 + for(ArcIt e(gr); e!=INVALID; ++e) {
1.206 + Node u=gr.source(e);
1.207 + Node v=gr.target(e);
1.208 + check(!bf.reached(u) || (bf.dist(v) - bf.dist(u) <= length[e]),
1.209 + "Wrong output. dist(target)-dist(source)-arc_length=" <<
1.210 + bf.dist(v) - bf.dist(u) - length[e]);
1.211 + }
1.212 +
1.213 + for(NodeIt v(gr); v!=INVALID; ++v) {
1.214 + if (bf.reached(v)) {
1.215 + check(v==s || bf.predArc(v)!=INVALID, "Wrong tree.");
1.216 + if (bf.predArc(v)!=INVALID ) {
1.217 + Arc e=bf.predArc(v);
1.218 + Node u=gr.source(e);
1.219 + check(u==bf.predNode(v),"Wrong tree.");
1.220 + check(bf.dist(v) - bf.dist(u) == length[e],
1.221 + "Wrong distance! Difference: " <<
1.222 + bf.dist(v) - bf.dist(u) - length[e]);
1.223 + }
1.224 + }
1.225 + }
1.226 +}
1.227 +
1.228 +void checkBellmanFordNegativeCycle() {
1.229 + DIGRAPH_TYPEDEFS(SmartDigraph);
1.230 +
1.231 + SmartDigraph gr;
1.232 + IntArcMap length(gr);
1.233 +
1.234 + Node n1 = gr.addNode();
1.235 + Node n2 = gr.addNode();
1.236 + Node n3 = gr.addNode();
1.237 + Node n4 = gr.addNode();
1.238 +
1.239 + Arc a1 = gr.addArc(n1, n2);
1.240 + Arc a2 = gr.addArc(n2, n2);
1.241 +
1.242 + length[a1] = 2;
1.243 + length[a2] = -1;
1.244 +
1.245 + {
1.246 + BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
1.247 + bf.run(n1);
1.248 + StaticPath<SmartDigraph> p = bf.negativeCycle();
1.249 + check(p.length() == 1 && p.front() == p.back() && p.front() == a2,
1.250 + "Wrong negative cycle.");
1.251 + }
1.252 +
1.253 + length[a2] = 0;
1.254 +
1.255 + {
1.256 + BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
1.257 + bf.run(n1);
1.258 + check(bf.negativeCycle().empty(),
1.259 + "Negative cycle should not be found.");
1.260 + }
1.261 +
1.262 + length[gr.addArc(n1, n3)] = 5;
1.263 + length[gr.addArc(n4, n3)] = 1;
1.264 + length[gr.addArc(n2, n4)] = 2;
1.265 + length[gr.addArc(n3, n2)] = -4;
1.266 +
1.267 + {
1.268 + BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
1.269 + bf.init();
1.270 + bf.addSource(n1);
1.271 + for (int i = 0; i < 4; ++i) {
1.272 + check(bf.negativeCycle().empty(),
1.273 + "Negative cycle should not be found.");
1.274 + bf.processNextRound();
1.275 + }
1.276 + StaticPath<SmartDigraph> p = bf.negativeCycle();
1.277 + check(p.length() == 3, "Wrong negative cycle.");
1.278 + check(length[p.nth(0)] + length[p.nth(1)] + length[p.nth(2)] == -1,
1.279 + "Wrong negative cycle.");
1.280 + }
1.281 +}
1.282 +
1.283 +int main() {
1.284 + checkBellmanFord<ListDigraph, int>();
1.285 + checkBellmanFord<SmartDigraph, double>();
1.286 + checkBellmanFordNegativeCycle();
1.287 + return 0;
1.288 +}