31
|
1 |
// Copyright 2002 Rensselaer Polytechnic Institute
|
|
2 |
|
|
3 |
// Use, modification and distribution is subject to the Boost Software
|
|
4 |
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
|
|
5 |
// http://www.boost.org/LICENSE_1_0.txt)
|
|
6 |
|
|
7 |
// Authors: Lauren Foutz
|
|
8 |
// Scott Hill
|
|
9 |
/*
|
|
10 |
* © Portions copyright (c) 2006-2007 Nokia Corporation. All rights reserved.
|
|
11 |
*/
|
|
12 |
|
|
13 |
#include <boost/graph/floyd_warshall_shortest.hpp>
|
|
14 |
#include <map>
|
|
15 |
#include <algorithm>
|
|
16 |
#include <iostream>
|
|
17 |
#include <boost/random/linear_congruential.hpp>
|
|
18 |
#include <boost/graph/graph_utility.hpp>
|
|
19 |
#include <boost/graph/properties.hpp>
|
|
20 |
#include <boost/graph/bellman_ford_shortest_paths.hpp>
|
|
21 |
#include <boost/graph/random.hpp>
|
|
22 |
#include <boost/graph/adjacency_list.hpp>
|
|
23 |
#include <boost/graph/adjacency_matrix.hpp>
|
|
24 |
#include <boost/test/minimal.hpp>
|
|
25 |
#include <algorithm>
|
|
26 |
|
|
27 |
#ifdef __SYMBIAN32__
|
|
28 |
#include "std_log_result.h"
|
|
29 |
#define LOG_FILENAME_LINE __FILE__, __LINE__
|
|
30 |
#endif
|
|
31 |
using namespace boost;
|
|
32 |
|
|
33 |
template <typename T>
|
|
34 |
struct inf_plus{
|
|
35 |
T operator()(const T& a, const T& b) const {
|
|
36 |
T inf = std::numeric_limits<T>::max BOOST_PREVENT_MACRO_SUBSTITUTION();
|
|
37 |
if (a == inf || b == inf){
|
|
38 |
return inf;
|
|
39 |
}
|
|
40 |
return a + b;
|
|
41 |
}
|
|
42 |
};
|
|
43 |
|
|
44 |
template<typename T>
|
|
45 |
inline const T& my_min(const T& x, const T& y)
|
|
46 |
{ return x < y? x : y; }
|
|
47 |
|
|
48 |
template<typename Graph>
|
|
49 |
bool acceptance_test(Graph& g, int vec, int e)
|
|
50 |
{
|
|
51 |
boost::minstd_rand ran(vec);
|
|
52 |
|
|
53 |
{
|
|
54 |
typename boost::property_map<Graph, boost::vertex_name_t>::type index =
|
|
55 |
boost::get(boost::vertex_name, g);
|
|
56 |
typename boost::graph_traits<Graph>::vertex_iterator firstv, lastv,
|
|
57 |
firstv2, lastv2;
|
|
58 |
int x = 0;
|
|
59 |
for(boost::tie(firstv, lastv) = boost::vertices(g); firstv != lastv;
|
|
60 |
firstv++){
|
|
61 |
boost::put(index, *firstv, x);
|
|
62 |
x++;
|
|
63 |
}
|
|
64 |
|
|
65 |
|
|
66 |
for(int i = 0; i < e; i++){
|
|
67 |
boost::add_edge(index[ran() % vec], index[ran() % vec], g);
|
|
68 |
}
|
|
69 |
|
|
70 |
|
|
71 |
typename boost::graph_traits<Graph>::edge_iterator first, last;
|
|
72 |
typename boost::property_map<Graph, boost::edge_weight_t>::type
|
|
73 |
local_edge_map = boost::get(boost::edge_weight, g);
|
|
74 |
for(boost::tie(first, last) = boost::edges(g); first != last; first++){
|
|
75 |
if (ran() % vec != 0){
|
|
76 |
boost::put(local_edge_map, *first, ran() % 100);
|
|
77 |
} else {
|
|
78 |
boost::put(local_edge_map, *first, 0 - (ran() % 100));
|
|
79 |
}
|
|
80 |
}
|
|
81 |
|
|
82 |
int int_inf =
|
|
83 |
std::numeric_limits<int>::max BOOST_PREVENT_MACRO_SUBSTITUTION();
|
|
84 |
typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_des;
|
|
85 |
std::map<vertex_des,int> matrixRow;
|
|
86 |
std::map<vertex_des, std::map<vertex_des ,int> > matrix;
|
|
87 |
typedef typename boost::property_map<Graph, boost::vertex_distance_t>::type
|
|
88 |
distance_type;
|
|
89 |
distance_type distance_row = boost::get(boost::vertex_distance, g);
|
|
90 |
for(boost::tie(firstv, lastv) = boost::vertices(g); firstv != lastv;
|
|
91 |
firstv++){
|
|
92 |
boost::put(distance_row, *firstv, int_inf);
|
|
93 |
matrixRow[*firstv] = int_inf;
|
|
94 |
}
|
|
95 |
for(boost::tie(firstv, lastv) = boost::vertices(g); firstv != lastv;
|
|
96 |
firstv++){
|
|
97 |
matrix[*firstv] = matrixRow;
|
|
98 |
}
|
|
99 |
for(boost::tie(firstv, lastv) = boost::vertices(g); firstv != lastv;
|
|
100 |
firstv++){
|
|
101 |
matrix[*firstv][*firstv] = 0;
|
|
102 |
}
|
|
103 |
std::map<vertex_des, std::map<vertex_des, int> > matrix3(matrix);
|
|
104 |
std::map<vertex_des, std::map<vertex_des, int> > matrix4(matrix);
|
|
105 |
for(boost::tie(first, last) = boost::edges(g); first != last; first++){
|
|
106 |
if (matrix[boost::source(*first, g)][boost::target(*first, g)] != int_inf)
|
|
107 |
{
|
|
108 |
matrix[boost::source(*first, g)][boost::target(*first, g)] =
|
|
109 |
my_min
|
|
110 |
(boost::get(local_edge_map, *first),
|
|
111 |
matrix[boost::source(*first, g)][boost::target(*first, g)]);
|
|
112 |
} else {
|
|
113 |
matrix[boost::source(*first, g)][boost::target(*first, g)] =
|
|
114 |
boost::get(local_edge_map, *first);
|
|
115 |
}
|
|
116 |
}
|
|
117 |
bool is_undirected =
|
|
118 |
boost::is_same<typename boost::graph_traits<Graph>::directed_category,
|
|
119 |
boost::undirected_tag>::value;
|
|
120 |
if (is_undirected){
|
|
121 |
for(boost::tie(first, last) = boost::edges(g); first != last; first++){
|
|
122 |
if (matrix[boost::target(*first, g)][boost::source(*first, g)] != int_inf)
|
|
123 |
{
|
|
124 |
matrix[boost::target(*first, g)][boost::source(*first, g)] =
|
|
125 |
my_min
|
|
126 |
(boost::get(local_edge_map, *first),
|
|
127 |
matrix[boost::target(*first, g)][boost::source(*first, g)]);
|
|
128 |
} else {
|
|
129 |
matrix[boost::target(*first, g)][boost::source(*first, g)] =
|
|
130 |
boost::get(local_edge_map, *first);
|
|
131 |
}
|
|
132 |
}
|
|
133 |
}
|
|
134 |
|
|
135 |
|
|
136 |
bool bellman = true, floyd1 = true, floyd2 = true, floyd3 = true;
|
|
137 |
std::less<int> compare;
|
|
138 |
inf_plus<int> combine;
|
|
139 |
floyd1 =
|
|
140 |
boost::floyd_warshall_initialized_all_pairs_shortest_paths
|
|
141 |
(g,
|
|
142 |
matrix, weight_map(boost::get(boost::edge_weight, g)).
|
|
143 |
distance_compare(compare). distance_combine(combine).
|
|
144 |
distance_inf(int_inf). distance_zero(0));
|
|
145 |
|
|
146 |
floyd2 =
|
|
147 |
boost::floyd_warshall_all_pairs_shortest_paths
|
|
148 |
(g, matrix3,
|
|
149 |
weight_map(local_edge_map). distance_compare(compare).
|
|
150 |
distance_combine(combine).
|
|
151 |
distance_inf(int_inf). distance_zero(0));
|
|
152 |
|
|
153 |
floyd3 = boost::floyd_warshall_all_pairs_shortest_paths(g, matrix4);
|
|
154 |
|
|
155 |
|
|
156 |
boost::dummy_property_map dummy_map;
|
|
157 |
std::map<vertex_des, std::map<vertex_des, int> > matrix2;
|
|
158 |
for(boost::tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++){
|
|
159 |
boost::put(distance_row, *firstv, 0);
|
|
160 |
bellman =
|
|
161 |
boost::bellman_ford_shortest_paths
|
|
162 |
(g, vec,
|
|
163 |
weight_map(boost::get(boost::edge_weight, g)).
|
|
164 |
distance_map(boost::get(boost::vertex_distance, g)).
|
|
165 |
predecessor_map(dummy_map).distance_compare(compare).
|
|
166 |
distance_combine(combine));
|
|
167 |
distance_row = boost::get(boost::vertex_distance, g);
|
|
168 |
for(boost::tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2;
|
|
169 |
firstv2++){
|
|
170 |
matrix2[*firstv][*firstv2] = boost::get(distance_row, *firstv2);
|
|
171 |
boost::put(distance_row, *firstv2, int_inf);
|
|
172 |
}
|
|
173 |
if(bellman == false){
|
|
174 |
break;
|
|
175 |
}
|
|
176 |
}
|
|
177 |
|
|
178 |
|
|
179 |
if (bellman != floyd1 || bellman != floyd2 || bellman != floyd3){
|
|
180 |
std::cout <<
|
|
181 |
"A negative cycle was detected in one algorithm but not the others. "
|
|
182 |
<< std::endl;
|
|
183 |
return false;
|
|
184 |
}
|
|
185 |
else if (bellman == false && floyd1 == false && floyd2 == false &&
|
|
186 |
floyd3 == false){
|
|
187 |
return true;
|
|
188 |
}
|
|
189 |
else {
|
|
190 |
typename boost::graph_traits<Graph>::vertex_iterator first1, first2,
|
|
191 |
last1, last2;
|
|
192 |
for (boost::tie(first1, last1) = boost::vertices(g); first1 != last1;
|
|
193 |
first1++){
|
|
194 |
for (boost::tie(first2, last2) = boost::vertices(g); first2 != last2;
|
|
195 |
first2++){
|
|
196 |
if (matrix2[*first1][*first2] != matrix[*first1][*first2]){
|
|
197 |
std::cout << "Algorithms do not match at matrix point "
|
|
198 |
<< index[*first1] << " " << index[*first2]
|
|
199 |
<< " Bellman results: " << matrix2[*first1][*first2]
|
|
200 |
<< " floyd 1 results " << matrix[*first1][*first2]
|
|
201 |
<< std::endl;
|
|
202 |
return false;
|
|
203 |
}
|
|
204 |
if (matrix2[*first1][*first2] != matrix3[*first1][*first2]){
|
|
205 |
std::cout << "Algorithms do not match at matrix point "
|
|
206 |
<< index[*first1] << " " << index[*first2]
|
|
207 |
<< " Bellman results: " << matrix2[*first1][*first2]
|
|
208 |
<< " floyd 2 results " << matrix3[*first1][*first2]
|
|
209 |
<< std::endl;
|
|
210 |
return false;
|
|
211 |
}
|
|
212 |
if (matrix2[*first1][*first2] != matrix4[*first1][*first2]){
|
|
213 |
std::cout << "Algorithms do not match at matrix point "
|
|
214 |
<< index[*first1] << " " << index[*first2]
|
|
215 |
<< " Bellman results: " << matrix2[*first1][*first2]
|
|
216 |
<< " floyd 3 results " << matrix4[*first1][*first2]
|
|
217 |
<< std::endl;
|
|
218 |
return false;
|
|
219 |
}
|
|
220 |
}
|
|
221 |
}
|
|
222 |
}
|
|
223 |
|
|
224 |
}
|
|
225 |
return true;
|
|
226 |
}
|
|
227 |
|
|
228 |
template<typename Graph>
|
|
229 |
bool acceptance_test2(Graph& g, int vec, int e)
|
|
230 |
{
|
|
231 |
boost::minstd_rand ran(vec);
|
|
232 |
|
|
233 |
{
|
|
234 |
|
|
235 |
typename boost::property_map<Graph, boost::vertex_name_t>::type index =
|
|
236 |
boost::get(boost::vertex_name, g);
|
|
237 |
typename boost::graph_traits<Graph>::vertex_iterator firstv, lastv,
|
|
238 |
firstv2, lastv2;
|
|
239 |
int x = 0;
|
|
240 |
for(boost::tie(firstv, lastv) = boost::vertices(g); firstv != lastv;
|
|
241 |
firstv++){
|
|
242 |
boost::put(index, *firstv, x);
|
|
243 |
x++;
|
|
244 |
}
|
|
245 |
|
|
246 |
boost::generate_random_graph(g, vec, e, ran, true);
|
|
247 |
|
|
248 |
typename boost::graph_traits<Graph>::edge_iterator first, last;
|
|
249 |
typename boost::property_map<Graph, boost::edge_weight_t>::type
|
|
250 |
local_edge_map = boost::get(boost::edge_weight, g);
|
|
251 |
for(boost::tie(first, last) = boost::edges(g); first != last; first++){
|
|
252 |
if (ran() % vec != 0){
|
|
253 |
boost::put(local_edge_map, *first, ran() % 100);
|
|
254 |
} else {
|
|
255 |
boost::put(local_edge_map, *first, 0 - (ran() % 100));
|
|
256 |
}
|
|
257 |
}
|
|
258 |
|
|
259 |
int int_inf =
|
|
260 |
std::numeric_limits<int>::max BOOST_PREVENT_MACRO_SUBSTITUTION();
|
|
261 |
typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_des;
|
|
262 |
std::map<vertex_des,int> matrixRow;
|
|
263 |
std::map<vertex_des, std::map<vertex_des ,int> > matrix;
|
|
264 |
typedef typename boost::property_map<Graph, boost::vertex_distance_t>::type
|
|
265 |
distance_type;
|
|
266 |
distance_type distance_row = boost::get(boost::vertex_distance, g);
|
|
267 |
for(boost::tie(firstv, lastv) = boost::vertices(g); firstv != lastv;
|
|
268 |
firstv++){
|
|
269 |
boost::put(distance_row, *firstv, int_inf);
|
|
270 |
matrixRow[*firstv] = int_inf;
|
|
271 |
}
|
|
272 |
for(boost::tie(firstv, lastv) = boost::vertices(g); firstv != lastv;
|
|
273 |
firstv++){
|
|
274 |
matrix[*firstv] = matrixRow;
|
|
275 |
}
|
|
276 |
for(boost::tie(firstv, lastv) = boost::vertices(g); firstv != lastv;
|
|
277 |
firstv++){
|
|
278 |
matrix[*firstv][*firstv] = 0;
|
|
279 |
}
|
|
280 |
std::map<vertex_des, std::map<vertex_des, int> > matrix3(matrix);
|
|
281 |
std::map<vertex_des, std::map<vertex_des, int> > matrix4(matrix);
|
|
282 |
for(boost::tie(first, last) = boost::edges(g); first != last; first++){
|
|
283 |
if (matrix[boost::source(*first, g)][boost::target(*first, g)] != int_inf)
|
|
284 |
{
|
|
285 |
matrix[boost::source(*first, g)][boost::target(*first, g)] =
|
|
286 |
my_min
|
|
287 |
(boost::get(local_edge_map, *first),
|
|
288 |
matrix[boost::source(*first, g)][boost::target(*first, g)]);
|
|
289 |
} else {
|
|
290 |
matrix[boost::source(*first, g)][boost::target(*first, g)] =
|
|
291 |
boost::get(local_edge_map, *first);
|
|
292 |
}
|
|
293 |
}
|
|
294 |
bool is_undirected =
|
|
295 |
boost::is_same<typename boost::graph_traits<Graph>::directed_category,
|
|
296 |
boost::undirected_tag>::value;
|
|
297 |
if (is_undirected){
|
|
298 |
for(boost::tie(first, last) = boost::edges(g); first != last; first++){
|
|
299 |
if (matrix[boost::target(*first, g)][boost::source(*first, g)]
|
|
300 |
!= int_inf){
|
|
301 |
matrix[boost::target(*first, g)][boost::source(*first, g)] =
|
|
302 |
my_min
|
|
303 |
(boost::get(local_edge_map, *first),
|
|
304 |
matrix[boost::target(*first, g)][boost::source(*first, g)]);
|
|
305 |
} else {
|
|
306 |
matrix[boost::target(*first, g)][boost::source(*first, g)] =
|
|
307 |
boost::get(local_edge_map, *first);
|
|
308 |
}
|
|
309 |
}
|
|
310 |
}
|
|
311 |
|
|
312 |
|
|
313 |
bool bellman = true, floyd1 = true, floyd2 = true, floyd3 = true;
|
|
314 |
std::less<int> compare;
|
|
315 |
inf_plus<int> combine;
|
|
316 |
floyd1 =
|
|
317 |
boost::floyd_warshall_initialized_all_pairs_shortest_paths
|
|
318 |
(g,
|
|
319 |
matrix, weight_map(boost::get(boost::edge_weight, g)).
|
|
320 |
distance_compare(compare). distance_combine(combine).
|
|
321 |
distance_inf(int_inf). distance_zero(0));
|
|
322 |
|
|
323 |
floyd2 =
|
|
324 |
boost::floyd_warshall_all_pairs_shortest_paths
|
|
325 |
(g, matrix3,
|
|
326 |
weight_map(local_edge_map). distance_compare(compare).
|
|
327 |
distance_combine(combine).
|
|
328 |
distance_inf(int_inf). distance_zero(0));
|
|
329 |
|
|
330 |
floyd3 = boost::floyd_warshall_all_pairs_shortest_paths(g, matrix4);
|
|
331 |
|
|
332 |
|
|
333 |
boost::dummy_property_map dummy_map;
|
|
334 |
std::map<vertex_des, std::map<vertex_des, int> > matrix2;
|
|
335 |
for(boost::tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++){
|
|
336 |
boost::put(distance_row, *firstv, 0);
|
|
337 |
bellman =
|
|
338 |
boost::bellman_ford_shortest_paths
|
|
339 |
(g, vec,
|
|
340 |
weight_map(boost::get(boost::edge_weight, g)).
|
|
341 |
distance_map(boost::get(boost::vertex_distance, g)).
|
|
342 |
predecessor_map(dummy_map).distance_compare(compare).
|
|
343 |
distance_combine(combine));
|
|
344 |
distance_row = boost::get(boost::vertex_distance, g);
|
|
345 |
for(boost::tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2;
|
|
346 |
firstv2++){
|
|
347 |
matrix2[*firstv][*firstv2] = boost::get(distance_row, *firstv2);
|
|
348 |
boost::put(distance_row, *firstv2, int_inf);
|
|
349 |
}
|
|
350 |
if(bellman == false){
|
|
351 |
break;
|
|
352 |
}
|
|
353 |
}
|
|
354 |
|
|
355 |
|
|
356 |
if (bellman != floyd1 || bellman != floyd2 || bellman != floyd3){
|
|
357 |
std::cout <<
|
|
358 |
"A negative cycle was detected in one algorithm but not the others. "
|
|
359 |
<< std::endl;
|
|
360 |
return false;
|
|
361 |
}
|
|
362 |
else if (bellman == false && floyd1 == false && floyd2 == false &&
|
|
363 |
floyd3 == false){
|
|
364 |
return true;
|
|
365 |
}
|
|
366 |
else {
|
|
367 |
typename boost::graph_traits<Graph>::vertex_iterator first1, first2,
|
|
368 |
last1, last2;
|
|
369 |
for (boost::tie(first1, last1) = boost::vertices(g); first1 != last1;
|
|
370 |
first1++){
|
|
371 |
for (boost::tie(first2, last2) = boost::vertices(g); first2 != last2;
|
|
372 |
first2++){
|
|
373 |
if (matrix2[*first1][*first2] != matrix[*first1][*first2]){
|
|
374 |
std::cout << "Algorithms do not match at matrix point "
|
|
375 |
<< index[*first1] << " " << index[*first2]
|
|
376 |
<< " Bellman results: " << matrix2[*first1][*first2]
|
|
377 |
<< " floyd 1 results " << matrix[*first1][*first2]
|
|
378 |
<< std::endl;
|
|
379 |
return false;
|
|
380 |
}
|
|
381 |
if (matrix2[*first1][*first2] != matrix3[*first1][*first2]){
|
|
382 |
std::cout << "Algorithms do not match at matrix point "
|
|
383 |
<< index[*first1] << " " << index[*first2]
|
|
384 |
<< " Bellman results: " << matrix2[*first1][*first2]
|
|
385 |
<< " floyd 2 results " << matrix3[*first1][*first2]
|
|
386 |
<< std::endl;
|
|
387 |
return false;
|
|
388 |
}
|
|
389 |
if (matrix2[*first1][*first2] != matrix4[*first1][*first2]){
|
|
390 |
std::cout << "Algorithms do not match at matrix point "
|
|
391 |
<< index[*first1] << " " << index[*first2]
|
|
392 |
<< " Bellman results: " << matrix2[*first1][*first2]
|
|
393 |
<< " floyd 3 results " << matrix4[*first1][*first2]
|
|
394 |
<< std::endl;
|
|
395 |
return false;
|
|
396 |
}
|
|
397 |
}
|
|
398 |
}
|
|
399 |
}
|
|
400 |
|
|
401 |
}
|
|
402 |
return true;
|
|
403 |
}
|
|
404 |
|
|
405 |
int test_main(int, char*[])
|
|
406 |
{
|
|
407 |
typedef boost::adjacency_list<boost::listS, boost::listS, boost::directedS,
|
|
408 |
boost::property<boost::vertex_distance_t, int,
|
|
409 |
boost::property<boost::vertex_name_t, int> > ,
|
|
410 |
boost::property<boost::edge_weight_t, int> > Digraph;
|
|
411 |
Digraph adjlist_digraph;
|
|
412 |
BOOST_CHECK(acceptance_test2(adjlist_digraph, 100, 2000));
|
|
413 |
|
|
414 |
typedef boost::adjacency_matrix<boost::undirectedS,
|
|
415 |
boost::property<boost::vertex_distance_t, int,
|
|
416 |
boost::property<boost::vertex_name_t, int> > ,
|
|
417 |
boost::property<boost::edge_weight_t, int> > Graph;
|
|
418 |
Graph matrix_graph(100);
|
|
419 |
BOOST_CHECK(acceptance_test(matrix_graph, 100, 2000));
|
|
420 |
|
|
421 |
|
|
422 |
#ifdef __SYMBIAN32__
|
|
423 |
|
|
424 |
std_log(LOG_FILENAME_LINE,"[End Test Case ]");
|
|
425 |
|
|
426 |
testResultXml("floyd_warshall_test");
|
|
427 |
close_log_file();
|
|
428 |
#endif
|
|
429 |
return 0;
|
|
430 |
}
|