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

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