1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/bellman_ford_test.cc Sun Aug 11 15:28:12 2013 +0200
1.3 @@ -0,0 +1,289 @@
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-2010
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 + ::lemon::ignore_unused_variable_warning(l);
1.72 + int k=3;
1.73 + bool b;
1.74 + ::lemon::ignore_unused_variable_warning(b);
1.75 + BF::DistMap d(gr);
1.76 + BF::PredMap p(gr);
1.77 + LengthMap length;
1.78 + concepts::Path<Digraph> pp;
1.79 +
1.80 + {
1.81 + BF bf_test(gr,length);
1.82 + const BF& const_bf_test = bf_test;
1.83 +
1.84 + bf_test.run(s);
1.85 + bf_test.run(s,k);
1.86 +
1.87 + bf_test.init();
1.88 + bf_test.addSource(s);
1.89 + bf_test.addSource(s, 1);
1.90 + b = bf_test.processNextRound();
1.91 + b = bf_test.processNextWeakRound();
1.92 +
1.93 + bf_test.start();
1.94 + bf_test.checkedStart();
1.95 + bf_test.limitedStart(k);
1.96 +
1.97 + l = const_bf_test.dist(t);
1.98 + e = const_bf_test.predArc(t);
1.99 + s = const_bf_test.predNode(t);
1.100 + b = const_bf_test.reached(t);
1.101 + d = const_bf_test.distMap();
1.102 + p = const_bf_test.predMap();
1.103 + pp = const_bf_test.path(t);
1.104 + pp = const_bf_test.negativeCycle();
1.105 +
1.106 + for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
1.107 + }
1.108 + {
1.109 + BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
1.110 + ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
1.111 + ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
1.112 + ::Create bf_test(gr,length);
1.113 +
1.114 + LengthMap length_map;
1.115 + concepts::ReadWriteMap<Node,Arc> pred_map;
1.116 + concepts::ReadWriteMap<Node,Value> dist_map;
1.117 +
1.118 + bf_test
1.119 + .lengthMap(length_map)
1.120 + .predMap(pred_map)
1.121 + .distMap(dist_map);
1.122 +
1.123 + bf_test.run(s);
1.124 + bf_test.run(s,k);
1.125 +
1.126 + bf_test.init();
1.127 + bf_test.addSource(s);
1.128 + bf_test.addSource(s, 1);
1.129 + b = bf_test.processNextRound();
1.130 + b = bf_test.processNextWeakRound();
1.131 +
1.132 + bf_test.start();
1.133 + bf_test.checkedStart();
1.134 + bf_test.limitedStart(k);
1.135 +
1.136 + l = bf_test.dist(t);
1.137 + e = bf_test.predArc(t);
1.138 + s = bf_test.predNode(t);
1.139 + b = bf_test.reached(t);
1.140 + pp = bf_test.path(t);
1.141 + pp = bf_test.negativeCycle();
1.142 + }
1.143 +}
1.144 +
1.145 +void checkBellmanFordFunctionCompile()
1.146 +{
1.147 + typedef int Value;
1.148 + typedef concepts::Digraph Digraph;
1.149 + typedef Digraph::Arc Arc;
1.150 + typedef Digraph::Node Node;
1.151 + typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;
1.152 +
1.153 + Digraph g;
1.154 + bool b;
1.155 + ::lemon::ignore_unused_variable_warning(b);
1.156 +
1.157 + bellmanFord(g,LengthMap()).run(Node());
1.158 + b = bellmanFord(g,LengthMap()).run(Node(),Node());
1.159 + bellmanFord(g,LengthMap())
1.160 + .predMap(concepts::ReadWriteMap<Node,Arc>())
1.161 + .distMap(concepts::ReadWriteMap<Node,Value>())
1.162 + .run(Node());
1.163 + b=bellmanFord(g,LengthMap())
1.164 + .predMap(concepts::ReadWriteMap<Node,Arc>())
1.165 + .distMap(concepts::ReadWriteMap<Node,Value>())
1.166 + .path(concepts::Path<Digraph>())
1.167 + .dist(Value())
1.168 + .run(Node(),Node());
1.169 +}
1.170 +
1.171 +
1.172 +template <typename Digraph, typename Value>
1.173 +void checkBellmanFord() {
1.174 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.175 + typedef typename Digraph::template ArcMap<Value> LengthMap;
1.176 +
1.177 + Digraph gr;
1.178 + Node s, t;
1.179 + LengthMap length(gr);
1.180 +
1.181 + std::istringstream input(test_lgf);
1.182 + digraphReader(gr, input).
1.183 + arcMap("length", length).
1.184 + node("source", s).
1.185 + node("target", t).
1.186 + run();
1.187 +
1.188 + BellmanFord<Digraph, LengthMap>
1.189 + bf(gr, length);
1.190 + bf.run(s);
1.191 + Path<Digraph> p = bf.path(t);
1.192 +
1.193 + check(bf.reached(t) && bf.dist(t) == -1, "Bellman-Ford found a wrong path.");
1.194 + check(p.length() == 3, "path() found a wrong path.");
1.195 + check(checkPath(gr, p), "path() found a wrong path.");
1.196 + check(pathSource(gr, p) == s, "path() found a wrong path.");
1.197 + check(pathTarget(gr, p) == t, "path() found a wrong path.");
1.198 +
1.199 + ListPath<Digraph> path;
1.200 + Value dist = 0;
1.201 + bool reached = bellmanFord(gr,length).path(path).dist(dist).run(s,t);
1.202 +
1.203 + check(reached && dist == -1, "Bellman-Ford found a wrong path.");
1.204 + check(path.length() == 3, "path() found a wrong path.");
1.205 + check(checkPath(gr, path), "path() found a wrong path.");
1.206 + check(pathSource(gr, path) == s, "path() found a wrong path.");
1.207 + check(pathTarget(gr, path) == t, "path() found a wrong path.");
1.208 +
1.209 + for(ArcIt e(gr); e!=INVALID; ++e) {
1.210 + Node u=gr.source(e);
1.211 + Node v=gr.target(e);
1.212 + check(!bf.reached(u) || (bf.dist(v) - bf.dist(u) <= length[e]),
1.213 + "Wrong output. dist(target)-dist(source)-arc_length=" <<
1.214 + bf.dist(v) - bf.dist(u) - length[e]);
1.215 + }
1.216 +
1.217 + for(NodeIt v(gr); v!=INVALID; ++v) {
1.218 + if (bf.reached(v)) {
1.219 + check(v==s || bf.predArc(v)!=INVALID, "Wrong tree.");
1.220 + if (bf.predArc(v)!=INVALID ) {
1.221 + Arc e=bf.predArc(v);
1.222 + Node u=gr.source(e);
1.223 + check(u==bf.predNode(v),"Wrong tree.");
1.224 + check(bf.dist(v) - bf.dist(u) == length[e],
1.225 + "Wrong distance! Difference: " <<
1.226 + bf.dist(v) - bf.dist(u) - length[e]);
1.227 + }
1.228 + }
1.229 + }
1.230 +}
1.231 +
1.232 +void checkBellmanFordNegativeCycle() {
1.233 + DIGRAPH_TYPEDEFS(SmartDigraph);
1.234 +
1.235 + SmartDigraph gr;
1.236 + IntArcMap length(gr);
1.237 +
1.238 + Node n1 = gr.addNode();
1.239 + Node n2 = gr.addNode();
1.240 + Node n3 = gr.addNode();
1.241 + Node n4 = gr.addNode();
1.242 +
1.243 + Arc a1 = gr.addArc(n1, n2);
1.244 + Arc a2 = gr.addArc(n2, n2);
1.245 +
1.246 + length[a1] = 2;
1.247 + length[a2] = -1;
1.248 +
1.249 + {
1.250 + BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
1.251 + bf.run(n1);
1.252 + StaticPath<SmartDigraph> p = bf.negativeCycle();
1.253 + check(p.length() == 1 && p.front() == p.back() && p.front() == a2,
1.254 + "Wrong negative cycle.");
1.255 + }
1.256 +
1.257 + length[a2] = 0;
1.258 +
1.259 + {
1.260 + BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
1.261 + bf.run(n1);
1.262 + check(bf.negativeCycle().empty(),
1.263 + "Negative cycle should not be found.");
1.264 + }
1.265 +
1.266 + length[gr.addArc(n1, n3)] = 5;
1.267 + length[gr.addArc(n4, n3)] = 1;
1.268 + length[gr.addArc(n2, n4)] = 2;
1.269 + length[gr.addArc(n3, n2)] = -4;
1.270 +
1.271 + {
1.272 + BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
1.273 + bf.init();
1.274 + bf.addSource(n1);
1.275 + for (int i = 0; i < 4; ++i) {
1.276 + check(bf.negativeCycle().empty(),
1.277 + "Negative cycle should not be found.");
1.278 + bf.processNextRound();
1.279 + }
1.280 + StaticPath<SmartDigraph> p = bf.negativeCycle();
1.281 + check(p.length() == 3, "Wrong negative cycle.");
1.282 + check(length[p.nth(0)] + length[p.nth(1)] + length[p.nth(2)] == -1,
1.283 + "Wrong negative cycle.");
1.284 + }
1.285 +}
1.286 +
1.287 +int main() {
1.288 + checkBellmanFord<ListDigraph, int>();
1.289 + checkBellmanFord<SmartDigraph, double>();
1.290 + checkBellmanFordNegativeCycle();
1.291 + return 0;
1.292 +}