1 //=======================================================================
2 // Copyright 2009 Trustees of Indiana University.
3 // Authors: Michael Hansen, Andrew Lumsdaine
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 <fstream>
11 #include <iostream>
12 #include <set>
13
14 #include <boost/foreach.hpp>
15 #include <boost/lexical_cast.hpp>
16 #include <boost/graph/grid_graph.hpp>
17 #include <boost/random.hpp>
18 #include <boost/core/lightweight_test.hpp>
19
20 using namespace boost;
21
22 // Function that prints a vertex to std::cout
print_vertex(Vertex vertex_to_print)23 template < typename Vertex > void print_vertex(Vertex vertex_to_print)
24 {
25
26 std::cout << "(";
27
28 for (std::size_t dimension_index = 0;
29 dimension_index < vertex_to_print.size(); ++dimension_index)
30 {
31 std::cout << vertex_to_print[dimension_index];
32
33 if (dimension_index != (vertex_to_print.size() - 1))
34 {
35 std::cout << ", ";
36 }
37 }
38
39 std::cout << ")";
40 }
41
do_test(minstd_rand & generator)42 template < unsigned int Dims > void do_test(minstd_rand& generator)
43 {
44 typedef grid_graph< Dims > Graph;
45 typedef
46 typename graph_traits< Graph >::vertices_size_type vertices_size_type;
47 typedef typename graph_traits< Graph >::edges_size_type edges_size_type;
48
49 typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor;
50 typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor;
51
52 std::cout << "Dimensions: " << Dims << ", lengths: ";
53
54 // Randomly generate the dimension lengths (3-10) and wrapping
55 boost::array< vertices_size_type, Dims > lengths;
56 boost::array< bool, Dims > wrapped;
57
58 for (unsigned int dimension_index = 0; dimension_index < Dims;
59 ++dimension_index)
60 {
61 lengths[dimension_index] = 3 + (generator() % 8);
62 wrapped[dimension_index] = ((generator() % 2) == 0);
63
64 std::cout << lengths[dimension_index]
65 << (wrapped[dimension_index] ? " [W]" : " [U]") << ", ";
66 }
67
68 std::cout << std::endl;
69
70 Graph graph(lengths, wrapped);
71
72 // Verify dimension lengths and wrapping
73 for (unsigned int dimension_index = 0; dimension_index < Dims;
74 ++dimension_index)
75 {
76 BOOST_TEST(
77 graph.length(dimension_index) == lengths[dimension_index]);
78 BOOST_TEST(
79 graph.wrapped(dimension_index) == wrapped[dimension_index]);
80 }
81
82 // Verify matching indices
83 for (vertices_size_type vertex_index = 0;
84 vertex_index < num_vertices(graph); ++vertex_index)
85 {
86 BOOST_TEST(
87 get(boost::vertex_index, graph, vertex(vertex_index, graph))
88 == vertex_index);
89 }
90
91 for (edges_size_type edge_index = 0; edge_index < num_edges(graph);
92 ++edge_index)
93 {
94
95 edge_descriptor current_edge = edge_at(edge_index, graph);
96 BOOST_TEST(
97 get(boost::edge_index, graph, current_edge) == edge_index);
98 }
99
100 // Verify all vertices are within bounds
101 vertices_size_type vertex_count = 0;
102 BOOST_FOREACH (vertex_descriptor current_vertex, vertices(graph))
103 {
104
105 vertices_size_type current_index
106 = get(boost::vertex_index, graph, current_vertex);
107
108 for (unsigned int dimension_index = 0; dimension_index < Dims;
109 ++dimension_index)
110 {
111 BOOST_TEST(
112 /*(current_vertex[dimension_index] >= 0) && */ // Always true
113 (current_vertex[dimension_index] < lengths[dimension_index]));
114 }
115
116 // Verify out-edges of this vertex
117 edges_size_type out_edge_count = 0;
118 std::set< vertices_size_type > target_vertices;
119
120 BOOST_FOREACH (
121 edge_descriptor out_edge, out_edges(current_vertex, graph))
122 {
123
124 target_vertices.insert(
125 get(boost::vertex_index, graph, target(out_edge, graph)));
126
127 ++out_edge_count;
128 }
129
130 BOOST_TEST(out_edge_count == out_degree(current_vertex, graph));
131
132 // Verify in-edges of this vertex
133 edges_size_type in_edge_count = 0;
134
135 BOOST_FOREACH (edge_descriptor in_edge, in_edges(current_vertex, graph))
136 {
137
138 BOOST_TEST(target_vertices.count(get(boost::vertex_index, graph,
139 source(in_edge, graph)))
140 > 0);
141
142 ++in_edge_count;
143 }
144
145 BOOST_TEST(in_edge_count == in_degree(current_vertex, graph));
146
147 // The number of out-edges and in-edges should be the same
148 BOOST_TEST(degree(current_vertex, graph)
149 == out_degree(current_vertex, graph)
150 + in_degree(current_vertex, graph));
151
152 // Verify adjacent vertices to this vertex
153 vertices_size_type adjacent_count = 0;
154
155 BOOST_FOREACH (vertex_descriptor adjacent_vertex,
156 adjacent_vertices(current_vertex, graph))
157 {
158
159 BOOST_TEST(target_vertices.count(
160 get(boost::vertex_index, graph, adjacent_vertex))
161 > 0);
162
163 ++adjacent_count;
164 }
165
166 BOOST_TEST(adjacent_count == out_degree(current_vertex, graph));
167
168 // Verify that this vertex is not listed as connected to any
169 // vertices outside of its adjacent vertices.
170 BOOST_FOREACH (vertex_descriptor unconnected_vertex, vertices(graph))
171 {
172
173 vertices_size_type unconnected_index
174 = get(boost::vertex_index, graph, unconnected_vertex);
175
176 if ((unconnected_index == current_index)
177 || (target_vertices.count(unconnected_index) > 0))
178 {
179 continue;
180 }
181
182 BOOST_TEST(
183 !edge(current_vertex, unconnected_vertex, graph).second);
184 BOOST_TEST(
185 !edge(unconnected_vertex, current_vertex, graph).second);
186 }
187
188 ++vertex_count;
189 }
190
191 BOOST_TEST(vertex_count == num_vertices(graph));
192
193 // Verify all edges are within bounds
194 edges_size_type edge_count = 0;
195 BOOST_FOREACH (edge_descriptor current_edge, edges(graph))
196 {
197
198 vertices_size_type source_index
199 = get(boost::vertex_index, graph, source(current_edge, graph));
200
201 vertices_size_type target_index
202 = get(boost::vertex_index, graph, target(current_edge, graph));
203
204 BOOST_TEST(source_index != target_index);
205 BOOST_TEST(/* (source_index >= 0) : always true && */ (
206 source_index < num_vertices(graph)));
207 BOOST_TEST(/* (target_index >= 0) : always true && */ (
208 target_index < num_vertices(graph)));
209
210 // Verify that the edge is listed as existing in both directions
211 BOOST_TEST(edge(
212 source(current_edge, graph), target(current_edge, graph), graph)
213 .second);
214 BOOST_TEST(edge(
215 target(current_edge, graph), source(current_edge, graph), graph)
216 .second);
217
218 ++edge_count;
219 }
220
221 BOOST_TEST(edge_count == num_edges(graph));
222 }
223
main(int argc,char * argv[])224 int main(int argc, char* argv[])
225 {
226
227 std::size_t random_seed = time(0);
228
229 if (argc > 1)
230 {
231 random_seed = lexical_cast< std::size_t >(argv[1]);
232 }
233
234 minstd_rand generator(random_seed);
235
236 do_test< 0 >(generator);
237 do_test< 1 >(generator);
238 do_test< 2 >(generator);
239 do_test< 3 >(generator);
240 do_test< 4 >(generator);
241
242 return boost::report_errors();
243 }
244