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
32using namespace boost;
33
34#ifdef BOOST_GRAPH_DIJKSTRA_TESTING_DIETMAR
35
36struct 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
51template < typename Graph, typename Kind >
52void 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
83int 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

source code of boost/libs/graph/test/dijkstra_heap_performance.cpp