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