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
39template < 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
78int 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

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