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 >
discover_vertexshow_events_visitor39 void discover_vertex(Vertex v, const Graph&)
40 {
41 std::cerr << "on_discover_vertex(" << v << ")\n";
42 }
43
44 template < typename Vertex, typename Graph >
examine_vertexshow_events_visitor45 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 >
run_test(const Graph & g,const char * name,Kind kind,const std::vector<double> & correct_distances)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
main(int argc,char * argv[])83 int main(int argc, char* argv[])
84 {
85 unsigned n = (argc > 1 ? lexical_cast< unsigned >(argv[1]) : 10000u);
86 unsigned m = (argc > 2 ? lexical_cast< unsigned >(argv[2]) : 10 * n);
87 int seed = (argc > 3 ? lexical_cast< int >(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) << " edges.\n";
100 uniform_real< double > rand01(0.0, 1.0);
101 graph_traits< Graph >::edge_iterator ei, ei_end;
102 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
103 put(edge_weight, g, *ei, 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, vertex(0, g),
116 distance_map(boost::make_iterator_property_map(
117 binary_heap_distances.begin(), get(boost::vertex_index, g))));
118 t.stop();
119 boost::timer::cpu_times binary_heap_time = t.elapsed();
120 std::cout << boost::timer::format(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, vertex(0, g),
127 distance_map(boost::make_iterator_property_map(
128 relaxed_heap_distances.begin(), get(boost::vertex_index, g))));
129 boost::timer::cpu_times relaxed_heap_time = t.elapsed();
130 std::cout << boost::timer::format(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(g, vertex(0, g),
144 boost::dummy_property_map(),
145 boost::make_iterator_property_map(
146 no_color_map_distances.begin(), get(boost::vertex_index, g), 0.),
147 get(boost::edge_weight, g), get(boost::vertex_index, g),
148 std::less< double >(), boost::closed_plus< double >(),
149 (std::numeric_limits< double >::max)(), 0,
150 make_dijkstra_visitor(null_visitor()));
151 boost::timer::cpu_times no_color_map_time = t.elapsed();
152 std::cout << boost::timer::format(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