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