1 | // Copyright 2004 The Trustees of Indiana University. |
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: Douglas Gregor |
8 | // Andrew Lumsdaine |
9 | #ifndef BOOST_GRAPH_DIJKSTRA_TESTING_DIETMAR |
10 | #define BOOST_GRAPH_DIJKSTRA_TESTING |
11 | #endif |
12 | |
13 | #include <boost/graph/dijkstra_shortest_paths.hpp> |
14 | #include <boost/graph/dijkstra_shortest_paths_no_color_map.hpp> |
15 | #include <boost/graph/adjacency_list.hpp> |
16 | #include <boost/random/linear_congruential.hpp> |
17 | #include <boost/lexical_cast.hpp> |
18 | #include <boost/random/uniform_real.hpp> |
19 | #include <boost/timer/timer.hpp> |
20 | #include <vector> |
21 | #include <iostream> |
22 | |
23 | #include <iterator> |
24 | #include <utility> |
25 | #include <boost/random/uniform_int.hpp> |
26 | #include <boost/graph/graph_traits.hpp> |
27 | #include <boost/graph/erdos_renyi_generator.hpp> |
28 | #include <boost/type_traits/is_base_and_derived.hpp> |
29 | #include <boost/type_traits/is_same.hpp> |
30 | #include <boost/detail/lightweight_test.hpp> |
31 | |
32 | using namespace boost; |
33 | |
34 | #ifdef BOOST_GRAPH_DIJKSTRA_TESTING_DIETMAR |
35 | |
36 | struct show_events_visitor : dijkstra_visitor<> |
37 | { |
38 | template < typename Vertex, typename Graph > |
39 | void discover_vertex(Vertex v, const Graph&) |
40 | { |
41 | std::cerr << "on_discover_vertex(" << v << ")\n" ; |
42 | } |
43 | |
44 | template < typename Vertex, typename Graph > |
45 | void examine_vertex(Vertex v, const Graph&) |
46 | { |
47 | std::cerr << "on_discover_vertex(" << v << ")\n" ; |
48 | } |
49 | }; |
50 | |
51 | template < typename Graph, typename Kind > |
52 | void run_test(const Graph& g, const char* name, Kind kind, |
53 | const std::vector< double >& correct_distances) |
54 | { |
55 | std::vector< double > distances(num_vertices(g)); |
56 | |
57 | std::cout << "Running Dijkstra's with " << name << "..." ; |
58 | std::cout.flush(); |
59 | boost::timer::cpu_timer t; |
60 | t.start(); |
61 | dijkstra_heap_kind = kind; |
62 | |
63 | dijkstra_shortest_paths(g, vertex(0, g), |
64 | distance_map(&distances[0]).visitor(show_events_visitor())); |
65 | double run_time = t.stop(); |
66 | std::cout << t.format() << " seconds.\n" ; |
67 | |
68 | BOOST_TEST(distances == correct_distances); |
69 | |
70 | if (distances != correct_distances) |
71 | { |
72 | std::cout << "Expected: " ; |
73 | std::copy(correct_distances.begin(), correct_distances.end(), |
74 | std::ostream_iterator< double >(std::cout, " " )); |
75 | std::cout << "\nReceived: " ; |
76 | std::copy(distances.begin(), distances.end(), |
77 | std::ostream_iterator< double >(std::cout, " " )); |
78 | std::cout << std::endl; |
79 | } |
80 | } |
81 | #endif |
82 | |
83 | int main(int argc, char* argv[]) |
84 | { |
85 | unsigned n = (argc > 1 ? lexical_cast< unsigned >(arg: argv[1]) : 10000u); |
86 | unsigned m = (argc > 2 ? lexical_cast< unsigned >(arg: argv[2]) : 10 * n); |
87 | int seed = (argc > 3 ? lexical_cast< int >(arg: argv[3]) : 1); |
88 | |
89 | // Build random graph |
90 | typedef adjacency_list< vecS, vecS, directedS, no_property, |
91 | property< edge_weight_t, double > > |
92 | Graph; |
93 | std::cout << "Generating graph..." ; |
94 | std::cout.flush(); |
95 | minstd_rand gen(seed); |
96 | double p = double(m) / (double(n) * double(n)); |
97 | Graph g(erdos_renyi_iterator< minstd_rand, Graph >(gen, n, p), |
98 | erdos_renyi_iterator< minstd_rand, Graph >(), n); |
99 | std::cout << n << " vertices, " << num_edges(g_: g) << " edges.\n" ; |
100 | uniform_real< double > rand01(0.0, 1.0); |
101 | graph_traits< Graph >::edge_iterator ei, ei_end; |
102 | for (boost::tie(t0&: ei, t1&: ei_end) = edges(g_: g); ei != ei_end; ++ei) |
103 | put(p: edge_weight, g, key: *ei, value: rand01(gen)); |
104 | |
105 | std::vector< double > binary_heap_distances(n); |
106 | std::vector< double > relaxed_heap_distances(n); |
107 | std::vector< double > no_color_map_distances(n); |
108 | |
109 | // Run binary or d-ary heap version |
110 | std::cout << "Running Dijkstra's with binary heap..." ; |
111 | std::cout.flush(); |
112 | boost::timer::cpu_timer t; |
113 | t.start(); |
114 | |
115 | dijkstra_shortest_paths(g, s: vertex(n: 0, g), |
116 | params: distance_map(p: boost::make_iterator_property_map( |
117 | iter: binary_heap_distances.begin(), id: get(p: boost::vertex_index, g)))); |
118 | t.stop(); |
119 | boost::timer::cpu_times binary_heap_time = t.elapsed(); |
120 | std::cout << boost::timer::format(times: binary_heap_time) << " seconds.\n" ; |
121 | |
122 | std::cout << "Running Dijkstra's with d-ary heap (d=4)..." ; |
123 | std::cout.flush(); |
124 | t.start(); |
125 | |
126 | dijkstra_shortest_paths(g, s: vertex(n: 0, g), |
127 | params: distance_map(p: boost::make_iterator_property_map( |
128 | iter: relaxed_heap_distances.begin(), id: get(p: boost::vertex_index, g)))); |
129 | boost::timer::cpu_times relaxed_heap_time = t.elapsed(); |
130 | std::cout << boost::timer::format(times: relaxed_heap_time) << " seconds.\n" |
131 | << "Speedup = " << (binary_heap_time.user / relaxed_heap_time.user) |
132 | << ".\n" ; |
133 | |
134 | // Verify that the results are equivalent |
135 | BOOST_TEST(binary_heap_distances == relaxed_heap_distances); |
136 | |
137 | // Run Michael's no-color-map version |
138 | |
139 | std::cout << "Running Dijkstra's (no color map) with d-ary heap (d=4)..." ; |
140 | std::cout.flush(); |
141 | |
142 | t.start(); |
143 | dijkstra_shortest_paths_no_color_map(graph: g, start_vertex: vertex(n: 0, g), |
144 | predecessor_map: boost::dummy_property_map(), |
145 | distance_map: boost::make_iterator_property_map( |
146 | iter: no_color_map_distances.begin(), id: get(p: boost::vertex_index, g), 0.), |
147 | weight_map: get(p: boost::edge_weight, g), index_map: get(p: boost::vertex_index, g), |
148 | distance_compare: std::less< double >(), distance_weight_combine: boost::closed_plus< double >(), |
149 | distance_infinity: (std::numeric_limits< double >::max)(), distance_zero: 0, |
150 | visitor: make_dijkstra_visitor(vis: null_visitor())); |
151 | boost::timer::cpu_times no_color_map_time = t.elapsed(); |
152 | std::cout << boost::timer::format(times: no_color_map_time) << " seconds.\n" |
153 | << "Speedup = " << (binary_heap_time.user / no_color_map_time.user) |
154 | << ".\n" ; |
155 | |
156 | // Verify that the results are equivalent |
157 | BOOST_TEST(binary_heap_distances == no_color_map_distances); |
158 | |
159 | #ifdef BOOST_GRAPH_DIJKSTRA_TESTING_DIETMAR |
160 | run_test(g, "d-ary heap (d=2)" , dijkstra_d_heap_2, binary_heap_distances); |
161 | run_test(g, "d-ary heap (d=3)" , dijkstra_d_heap_3, binary_heap_distances); |
162 | run_test( |
163 | g, "Fibonacci heap" , dijkstra_fibonacci_heap, binary_heap_distances); |
164 | run_test(g, "Lazy Fibonacci heap" , dijkstra_lazy_fibonacci_heap, |
165 | binary_heap_distances); |
166 | run_test(g, "Pairing heap" , dijkstra_pairing_heap, binary_heap_distances); |
167 | run_test(g, "Splay heap" , dijkstra_splay_heap, binary_heap_distances); |
168 | #endif |
169 | return boost::report_errors(); |
170 | } |
171 | |