1 | //======================================================================= |
2 | // Copyright 2009 Trustees of Indiana University. |
3 | // Authors: Michael Hansen |
4 | // |
5 | // Distributed under the Boost Software License, Version 1.0. (See |
6 | // accompanying file LICENSE_1_0.txt or copy at |
7 | // http://www.boost.org/LICENSE_1_0.txt) |
8 | //======================================================================= |
9 | |
10 | #include <iostream> |
11 | #include <map> |
12 | #include <vector> |
13 | #include <ctime> |
14 | #include <boost/config.hpp> |
15 | |
16 | #ifdef BOOST_MSVC |
17 | // Without disabling this we get hard errors about initialialized pointers: |
18 | #pragma warning(disable : 4703) |
19 | #endif |
20 | |
21 | #include <boost/lexical_cast.hpp> |
22 | #include <boost/random.hpp> |
23 | #include <boost/graph/adjacency_list.hpp> |
24 | #include <boost/graph/dijkstra_shortest_paths.hpp> |
25 | #include <boost/graph/dijkstra_shortest_paths_no_color_map.hpp> |
26 | #include <boost/graph/properties.hpp> |
27 | #include <boost/graph/random.hpp> |
28 | #include <boost/core/lightweight_test.hpp> |
29 | #include <boost/graph/iteration_macros.hpp> |
30 | |
31 | #define INITIALIZE_VERTEX 0 |
32 | #define DISCOVER_VERTEX 1 |
33 | #define EXAMINE_VERTEX 2 |
34 | #define EXAMINE_EDGE 3 |
35 | #define EDGE_RELAXED 4 |
36 | #define EDGE_NOT_RELAXED 5 |
37 | #define FINISH_VERTEX 6 |
38 | |
39 | template < typename Graph > void run_dijkstra_test(const Graph& graph) |
40 | { |
41 | using namespace boost; |
42 | |
43 | // Set up property maps |
44 | typedef typename graph_traits< Graph >::vertex_descriptor vertex_t; |
45 | |
46 | typedef typename std::map< vertex_t, vertex_t > vertex_map_t; |
47 | typedef associative_property_map< vertex_map_t > predecessor_map_t; |
48 | vertex_map_t default_vertex_map, no_color_map_vertex_map; |
49 | predecessor_map_t default_predecessor_map(default_vertex_map), |
50 | no_color_map_predecessor_map(no_color_map_vertex_map); |
51 | |
52 | typedef typename std::map< vertex_t, double > vertex_double_map_t; |
53 | typedef associative_property_map< vertex_double_map_t > distance_map_t; |
54 | vertex_double_map_t default_vertex_double_map, |
55 | no_color_map_vertex_double_map; |
56 | distance_map_t default_distance_map(default_vertex_double_map), |
57 | no_color_map_distance_map(no_color_map_vertex_double_map); |
58 | |
59 | // Run dijkstra algoirthms |
60 | dijkstra_shortest_paths(graph, vertex(0, graph), |
61 | predecessor_map(default_predecessor_map) |
62 | .distance_map(default_distance_map)); |
63 | |
64 | dijkstra_shortest_paths_no_color_map(graph, vertex(0, graph), |
65 | predecessor_map(no_color_map_predecessor_map) |
66 | .distance_map(no_color_map_distance_map)); |
67 | |
68 | // Verify that predecessor maps are equal |
69 | BOOST_TEST(std::equal(default_vertex_map.begin(), default_vertex_map.end(), |
70 | no_color_map_vertex_map.begin())); |
71 | |
72 | // Verify that distance maps are equal |
73 | BOOST_TEST(std::equal(default_vertex_double_map.begin(), |
74 | default_vertex_double_map.end(), |
75 | no_color_map_vertex_double_map.begin())); |
76 | } |
77 | |
78 | int main(int argc, char* argv[]) |
79 | { |
80 | using namespace boost; |
81 | |
82 | int vertices_to_create = 10; |
83 | int edges_to_create = 500; |
84 | std::size_t random_seed = std::time(timer: 0); |
85 | |
86 | if (argc > 1) |
87 | { |
88 | vertices_to_create = lexical_cast< int >(arg: argv[1]); |
89 | } |
90 | |
91 | if (argc > 2) |
92 | { |
93 | edges_to_create = lexical_cast< int >(arg: argv[2]); |
94 | } |
95 | |
96 | if (argc > 3) |
97 | { |
98 | random_seed = lexical_cast< std::size_t >(arg: argv[3]); |
99 | } |
100 | |
101 | minstd_rand generator(random_seed); |
102 | |
103 | // Set up graph |
104 | typedef adjacency_list< listS, listS, directedS, |
105 | property< vertex_index_t, int >, property< edge_weight_t, double > > |
106 | graph_t; |
107 | |
108 | graph_t graph; |
109 | generate_random_graph( |
110 | g&: graph, V: vertices_to_create, E: edges_to_create, gen&: generator); |
111 | |
112 | // Set up property maps |
113 | typedef property_map< graph_t, vertex_index_t >::type index_map_t; |
114 | index_map_t index_map = get(p: vertex_index, g&: graph); |
115 | int vertex_index = 0; |
116 | |
117 | BGL_FORALL_VERTICES(current_vertex, graph, graph_t) |
118 | { |
119 | put(pa: index_map, k: current_vertex, v: vertex_index++); |
120 | } |
121 | |
122 | randomize_property< edge_weight_t >(g&: graph, rg&: generator); |
123 | |
124 | // Run comparison test with original dijkstra_shortest_paths |
125 | std::cout << "Running dijkstra shortest paths test with " |
126 | << num_vertices(g_: graph) << " vertices and " << num_edges(g_: graph) |
127 | << " edges " << std::endl; |
128 | |
129 | run_dijkstra_test(graph); |
130 | |
131 | return boost::report_errors(); |
132 | } |
133 | |