1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2009
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #include <lemon/concepts/digraph.h>
20 #include <lemon/smart_graph.h>
21 #include <lemon/list_graph.h>
22 #include <lemon/lgf_reader.h>
23 #include <lemon/bellman_ford.h>
24 #include <lemon/path.h>
26 #include "graph_test.h"
27 #include "test_tools.h"
29 using namespace lemon;
55 void checkBellmanFordCompile()
58 typedef concepts::Digraph Digraph;
59 typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;
60 typedef BellmanFord<Digraph, LengthMap> BF;
61 typedef Digraph::Node Node;
62 typedef Digraph::Arc Arc;
73 concepts::Path<Digraph> pp;
76 BF bf_test(gr,length);
77 const BF& const_bf_test = bf_test;
84 bf_test.addSource(s, 1);
85 b = bf_test.processNextRound();
86 b = bf_test.processNextWeakRound();
89 bf_test.checkedStart();
90 bf_test.limitedStart(k);
92 l = const_bf_test.dist(t);
93 e = const_bf_test.predArc(t);
94 s = const_bf_test.predNode(t);
95 b = const_bf_test.reached(t);
96 d = const_bf_test.distMap();
97 p = const_bf_test.predMap();
98 pp = const_bf_test.path(t);
100 for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
103 BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
104 ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
105 ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
106 ::Create bf_test(gr,length);
108 LengthMap length_map;
109 concepts::ReadWriteMap<Node,Arc> pred_map;
110 concepts::ReadWriteMap<Node,Value> dist_map;
113 .lengthMap(length_map)
121 bf_test.addSource(s);
122 bf_test.addSource(s, 1);
123 b = bf_test.processNextRound();
124 b = bf_test.processNextWeakRound();
127 bf_test.checkedStart();
128 bf_test.limitedStart(k);
131 e = bf_test.predArc(t);
132 s = bf_test.predNode(t);
133 b = bf_test.reached(t);
134 pp = bf_test.path(t);
138 void checkBellmanFordFunctionCompile()
141 typedef concepts::Digraph Digraph;
142 typedef Digraph::Arc Arc;
143 typedef Digraph::Node Node;
144 typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;
148 bellmanFord(g,LengthMap()).run(Node());
149 b = bellmanFord(g,LengthMap()).run(Node(),Node());
150 bellmanFord(g,LengthMap())
151 .predMap(concepts::ReadWriteMap<Node,Arc>())
152 .distMap(concepts::ReadWriteMap<Node,Value>())
154 b=bellmanFord(g,LengthMap())
155 .predMap(concepts::ReadWriteMap<Node,Arc>())
156 .distMap(concepts::ReadWriteMap<Node,Value>())
157 .path(concepts::Path<Digraph>())
163 template <typename Digraph, typename Value>
164 void checkBellmanFord() {
165 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
166 typedef typename Digraph::template ArcMap<Value> LengthMap;
170 LengthMap length(gr);
172 std::istringstream input(test_lgf);
173 digraphReader(gr, input).
174 arcMap("length", length).
179 BellmanFord<Digraph, LengthMap>
182 Path<Digraph> p = bf.path(t);
184 check(bf.reached(t) && bf.dist(t) == -1, "Bellman-Ford found a wrong path.");
185 check(p.length() == 3, "path() found a wrong path.");
186 check(checkPath(gr, p), "path() found a wrong path.");
187 check(pathSource(gr, p) == s, "path() found a wrong path.");
188 check(pathTarget(gr, p) == t, "path() found a wrong path.");
190 ListPath<Digraph> path;
192 bool reached = bellmanFord(gr,length).path(path).dist(dist).run(s,t);
194 check(reached && dist == -1, "Bellman-Ford found a wrong path.");
195 check(path.length() == 3, "path() found a wrong path.");
196 check(checkPath(gr, path), "path() found a wrong path.");
197 check(pathSource(gr, path) == s, "path() found a wrong path.");
198 check(pathTarget(gr, path) == t, "path() found a wrong path.");
200 for(ArcIt e(gr); e!=INVALID; ++e) {
203 check(!bf.reached(u) || (bf.dist(v) - bf.dist(u) <= length[e]),
204 "Wrong output. dist(target)-dist(source)-arc_length=" <<
205 bf.dist(v) - bf.dist(u) - length[e]);
208 for(NodeIt v(gr); v!=INVALID; ++v) {
210 check(v==s || bf.predArc(v)!=INVALID, "Wrong tree.");
211 if (bf.predArc(v)!=INVALID ) {
214 check(u==bf.predNode(v),"Wrong tree.");
215 check(bf.dist(v) - bf.dist(u) == length[e],
216 "Wrong distance! Difference: " <<
217 bf.dist(v) - bf.dist(u) - length[e]);
224 checkBellmanFord<ListDigraph, int>();
225 checkBellmanFord<SmartDigraph, double>();