1 //=======================================================================
2 // Copyright 2009 Trustees of Indiana University.
3 // Authors: Michael Hansen
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 //=======================================================================
14 #include <boost/lexical_cast.hpp>
15 #include <boost/random.hpp>
16 #include <boost/graph/adjacency_list.hpp>
17 #include <boost/graph/dijkstra_shortest_paths.hpp>
18 #include <boost/graph/dijkstra_shortest_paths_no_color_map.hpp>
19 #include <boost/graph/properties.hpp>
20 #include <boost/graph/random.hpp>
21 #include <boost/test/minimal.hpp>
22 #include <boost/graph/iteration_macros.hpp>
24 #define INITIALIZE_VERTEX 0
25 #define DISCOVER_VERTEX 1
26 #define EXAMINE_VERTEX 2
27 #define EXAMINE_EDGE 3
28 #define EDGE_RELAXED 4
29 #define EDGE_NOT_RELAXED 5
30 #define FINISH_VERTEX 6
32 template <typename Graph
>
33 void run_dijkstra_test(const Graph
& graph
)
35 using namespace boost
;
37 // Set up property maps
38 typedef typename graph_traits
<Graph
>::vertex_descriptor vertex_t
;
40 typedef typename
std::map
<vertex_t
, vertex_t
> vertex_map_t
;
41 typedef associative_property_map
<vertex_map_t
> predecessor_map_t
;
42 vertex_map_t default_vertex_map
, no_color_map_vertex_map
;
43 predecessor_map_t
default_predecessor_map(default_vertex_map
),
44 no_color_map_predecessor_map(no_color_map_vertex_map
);
46 typedef typename
std::map
<vertex_t
, double> vertex_double_map_t
;
47 typedef associative_property_map
<vertex_double_map_t
> distance_map_t
;
48 vertex_double_map_t default_vertex_double_map
, no_color_map_vertex_double_map
;
49 distance_map_t
default_distance_map(default_vertex_double_map
),
50 no_color_map_distance_map(no_color_map_vertex_double_map
);
52 // Run dijkstra algoirthms
53 dijkstra_shortest_paths(graph
, vertex(0, graph
),
54 predecessor_map(default_predecessor_map
)
55 .distance_map(default_distance_map
));
57 dijkstra_shortest_paths_no_color_map(graph
, vertex(0, graph
),
58 predecessor_map(no_color_map_predecessor_map
)
59 .distance_map(no_color_map_distance_map
));
61 // Verify that predecessor maps are equal
62 BOOST_CHECK(std::equal(default_vertex_map
.begin(), default_vertex_map
.end(),
63 no_color_map_vertex_map
.begin()));
65 // Verify that distance maps are equal
66 BOOST_CHECK(std::equal(default_vertex_double_map
.begin(), default_vertex_double_map
.end(),
67 no_color_map_vertex_double_map
.begin()));
70 int test_main(int argc
, char* argv
[])
72 using namespace boost
;
74 int vertices_to_create
= 10;
75 int edges_to_create
= 500;
76 std::size_t random_seed
= time(0);
79 vertices_to_create
= lexical_cast
<int>(argv
[1]);
83 edges_to_create
= lexical_cast
<int>(argv
[2]);
87 random_seed
= lexical_cast
<std::size_t>(argv
[3]);
90 minstd_rand
generator(random_seed
);
93 typedef adjacency_list
<listS
, listS
, directedS
,
94 property
<vertex_index_t
, int >,
95 property
<edge_weight_t
, double> > graph_t
;
98 generate_random_graph(graph
, vertices_to_create
, edges_to_create
, generator
);
100 // Set up property maps
101 typedef property_map
<graph_t
, vertex_index_t
>::type index_map_t
;
102 index_map_t index_map
= get(vertex_index
, graph
);
103 int vertex_index
= 0;
105 BGL_FORALL_VERTICES(current_vertex
, graph
, graph_t
) {
106 put(index_map
, current_vertex
, vertex_index
++);
109 randomize_property
<edge_weight_t
>(graph
, generator
);
111 // Run comparison test with original dijkstra_shortest_paths
112 std::cout
<< "Running dijkstra shortest paths test with " << num_vertices(graph
) <<
113 " vertices and " << num_edges(graph
) << " edges " << std::endl
;
115 run_dijkstra_test(graph
);