]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
20effc67 | 13 | #include <ctime> |
92f5a8d4 TL |
14 | #include <boost/config.hpp> |
15 | ||
16 | #ifdef BOOST_MSVC | |
17 | // Without disabling this we get hard errors about initialialized pointers: | |
f67539c2 | 18 | #pragma warning(disable : 4703) |
92f5a8d4 | 19 | #endif |
7c673cae FG |
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> | |
f67539c2 | 28 | #include <boost/core/lightweight_test.hpp> |
7c673cae FG |
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 | ||
f67539c2 | 39 | template < typename Graph > void run_dijkstra_test(const Graph& graph) |
7c673cae | 40 | { |
f67539c2 TL |
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())); | |
7c673cae FG |
76 | } |
77 | ||
f67539c2 | 78 | int main(int argc, char* argv[]) |
7c673cae | 79 | { |
f67539c2 TL |
80 | using namespace boost; |
81 | ||
82 | int vertices_to_create = 10; | |
83 | int edges_to_create = 500; | |
20effc67 | 84 | std::size_t random_seed = std::time(0); |
f67539c2 TL |
85 | |
86 | if (argc > 1) | |
87 | { | |
88 | vertices_to_create = lexical_cast< int >(argv[1]); | |
89 | } | |
90 | ||
91 | if (argc > 2) | |
92 | { | |
93 | edges_to_create = lexical_cast< int >(argv[2]); | |
94 | } | |
95 | ||
96 | if (argc > 3) | |
97 | { | |
98 | random_seed = lexical_cast< std::size_t >(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; | |
7c673cae | 107 | |
f67539c2 TL |
108 | graph_t graph; |
109 | generate_random_graph( | |
110 | graph, vertices_to_create, edges_to_create, 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(vertex_index, graph); | |
115 | int vertex_index = 0; | |
116 | ||
117 | BGL_FORALL_VERTICES(current_vertex, graph, graph_t) | |
118 | { | |
119 | put(index_map, current_vertex, vertex_index++); | |
120 | } | |
121 | ||
122 | randomize_property< edge_weight_t >(graph, generator); | |
123 | ||
124 | // Run comparison test with original dijkstra_shortest_paths | |
125 | std::cout << "Running dijkstra shortest paths test with " | |
126 | << num_vertices(graph) << " vertices and " << num_edges(graph) | |
127 | << " edges " << std::endl; | |
128 | ||
129 | run_dijkstra_test(graph); | |
130 | ||
131 | return boost::report_errors(); | |
132 | } |