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