1 | //======================================================================= |
2 | // Copyright 2002 Indiana University. |
3 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek |
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 | #ifndef BOOST_GRAPH_TEST_HPP |
11 | #define BOOST_GRAPH_TEST_HPP |
12 | |
13 | #include <vector> |
14 | #include <boost/core/lightweight_test.hpp> |
15 | #include <boost/graph/filtered_graph.hpp> |
16 | #include <boost/graph/iteration_macros.hpp> |
17 | #include <boost/graph/isomorphism.hpp> |
18 | #include <boost/graph/copy.hpp> |
19 | #include <boost/graph/graph_utility.hpp> // for connects |
20 | #include <boost/range.hpp> |
21 | #include <boost/range/algorithm/find_if.hpp> |
22 | |
23 | // UNDER CONSTRUCTION |
24 | |
25 | namespace boost |
26 | { |
27 | |
28 | template < typename Graph > struct graph_test |
29 | { |
30 | |
31 | typedef typename graph_traits< Graph >::vertex_descriptor vertex_t; |
32 | typedef typename graph_traits< Graph >::edge_descriptor edge_t; |
33 | typedef typename graph_traits< Graph >::vertices_size_type v_size_t; |
34 | typedef typename graph_traits< Graph >::degree_size_type deg_size_t; |
35 | typedef typename graph_traits< Graph >::edges_size_type e_size_t; |
36 | typedef typename graph_traits< Graph >::out_edge_iterator out_edge_iter; |
37 | typedef typename property_map< Graph, vertex_index_t >::type index_map_t; |
38 | typedef iterator_property_map< typename std::vector< vertex_t >::iterator, |
39 | index_map_t, vertex_t, vertex_t& > |
40 | IsoMap; |
41 | |
42 | struct ignore_vertex |
43 | { |
44 | ignore_vertex() {} |
45 | ignore_vertex(vertex_t v) : v(v) {} |
46 | bool operator()(vertex_t x) const { return x != v; } |
47 | vertex_t v; |
48 | }; |
49 | struct ignore_edge |
50 | { |
51 | ignore_edge() {} |
52 | ignore_edge(edge_t e) : e(e) {} |
53 | bool operator()(edge_t x) const { return x != e; } |
54 | edge_t e; |
55 | }; |
56 | struct ignore_edges |
57 | { |
58 | ignore_edges(vertex_t s, vertex_t t, const Graph& g) : s(s), t(t), g(g) |
59 | { |
60 | } |
61 | bool operator()(edge_t x) const |
62 | { |
63 | return !(source(x, g) == s && target(x, g) == t); |
64 | } |
65 | vertex_t s; |
66 | vertex_t t; |
67 | const Graph& g; |
68 | }; |
69 | |
70 | //========================================================================= |
71 | // Traversal Operations |
72 | |
73 | void test_incidence_graph(const std::vector< vertex_t >& vertex_set, |
74 | const std::vector< std::pair< vertex_t, vertex_t > >& edge_set, |
75 | const Graph& g) |
76 | { |
77 | typedef typename std::vector< vertex_t >::const_iterator vertex_iter; |
78 | typedef typename std::vector< |
79 | std::pair< vertex_t, vertex_t > >::const_iterator edge_iter; |
80 | typedef typename graph_traits< Graph >::out_edge_iterator out_edge_iter; |
81 | |
82 | for (vertex_iter ui = vertex_set.begin(); ui != vertex_set.end(); ++ui) |
83 | { |
84 | vertex_t u = *ui; |
85 | std::vector< vertex_t > adj; |
86 | for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e) |
87 | if (e->first == u) |
88 | adj.push_back(e->second); |
89 | |
90 | std::pair< out_edge_iter, out_edge_iter > p = out_edges(u, g); |
91 | BOOST_TEST(out_degree(u, g) == adj.size()); |
92 | BOOST_TEST(deg_size_t(std::distance(p.first, p.second)) |
93 | == out_degree(u, g)); |
94 | for (; p.first != p.second; ++p.first) |
95 | { |
96 | edge_t e = *p.first; |
97 | BOOST_TEST(source(e, g) == u); |
98 | BOOST_TEST(container_contains(adj, target(e, g)) == true); |
99 | } |
100 | } |
101 | } |
102 | |
103 | void test_bidirectional_graph(const std::vector< vertex_t >& vertex_set, |
104 | const std::vector< std::pair< vertex_t, vertex_t > >& edge_set, |
105 | const Graph& g) |
106 | { |
107 | typedef typename std::vector< vertex_t >::const_iterator vertex_iter; |
108 | typedef typename std::vector< |
109 | std::pair< vertex_t, vertex_t > >::const_iterator edge_iter; |
110 | typedef typename graph_traits< Graph >::in_edge_iterator in_edge_iter; |
111 | |
112 | for (vertex_iter vi = vertex_set.begin(); vi != vertex_set.end(); ++vi) |
113 | { |
114 | vertex_t v = *vi; |
115 | std::vector< vertex_t > inv_adj; |
116 | for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e) |
117 | if (e->second == v) |
118 | inv_adj.push_back(e->first); |
119 | |
120 | std::pair< in_edge_iter, in_edge_iter > p = in_edges(v, g); |
121 | BOOST_TEST(in_degree(v, g) == inv_adj.size()); |
122 | BOOST_TEST(deg_size_t(std::distance(p.first, p.second)) |
123 | == in_degree(v, g)); |
124 | for (; p.first != p.second; ++p.first) |
125 | { |
126 | edge_t e = *p.first; |
127 | BOOST_TEST(target(e, g) == v); |
128 | BOOST_TEST(container_contains(inv_adj, source(e, g)) == true); |
129 | } |
130 | } |
131 | } |
132 | |
133 | void test_adjacency_graph(const std::vector< vertex_t >& vertex_set, |
134 | const std::vector< std::pair< vertex_t, vertex_t > >& edge_set, |
135 | const Graph& g) |
136 | { |
137 | typedef typename std::vector< vertex_t >::const_iterator vertex_iter; |
138 | typedef typename std::vector< |
139 | std::pair< vertex_t, vertex_t > >::const_iterator edge_iter; |
140 | typedef typename graph_traits< Graph >::adjacency_iterator adj_iter; |
141 | |
142 | for (vertex_iter ui = vertex_set.begin(); ui != vertex_set.end(); ++ui) |
143 | { |
144 | vertex_t u = *ui; |
145 | std::vector< vertex_t > adj; |
146 | for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e) |
147 | if (e->first == u) |
148 | adj.push_back(e->second); |
149 | |
150 | std::pair< adj_iter, adj_iter > p = adjacent_vertices(u, g); |
151 | BOOST_TEST( |
152 | deg_size_t(std::distance(p.first, p.second)) == adj.size()); |
153 | for (; p.first != p.second; ++p.first) |
154 | { |
155 | vertex_t v = *p.first; |
156 | BOOST_TEST(container_contains(adj, v) == true); |
157 | } |
158 | } |
159 | } |
160 | |
161 | void test_vertex_list_graph( |
162 | const std::vector< vertex_t >& vertex_set, const Graph& g) |
163 | { |
164 | typedef typename graph_traits< Graph >::vertex_iterator v_iter; |
165 | std::pair< v_iter, v_iter > p = vertices(g); |
166 | BOOST_TEST(num_vertices(g) == vertex_set.size()); |
167 | v_size_t n = (size_t)std::distance(p.first, p.second); |
168 | BOOST_TEST(n == num_vertices(g)); |
169 | for (; p.first != p.second; ++p.first) |
170 | { |
171 | vertex_t v = *p.first; |
172 | BOOST_TEST(container_contains(vertex_set, v) == true); |
173 | } |
174 | } |
175 | |
176 | void test_edge_list_graph(const std::vector< vertex_t >& vertex_set, |
177 | const std::vector< std::pair< vertex_t, vertex_t > >& edge_set, |
178 | const Graph& g) |
179 | { |
180 | typedef typename graph_traits< Graph >::edge_iterator e_iter; |
181 | std::pair< e_iter, e_iter > p = edges(g); |
182 | BOOST_TEST(num_edges(g) == edge_set.size()); |
183 | e_size_t m = std::distance(p.first, p.second); |
184 | BOOST_TEST(m == num_edges(g)); |
185 | for (; p.first != p.second; ++p.first) |
186 | { |
187 | edge_t e = *p.first; |
188 | BOOST_TEST( |
189 | find_if(edge_set, connects(source(e, g), target(e, g), g)) |
190 | != boost::end(edge_set)); |
191 | BOOST_TEST(container_contains(vertex_set, source(e, g)) == true); |
192 | BOOST_TEST(container_contains(vertex_set, target(e, g)) == true); |
193 | } |
194 | } |
195 | |
196 | void test_adjacency_matrix(const std::vector< vertex_t >& vertex_set, |
197 | const std::vector< std::pair< vertex_t, vertex_t > >& edge_set, |
198 | const Graph& g) |
199 | { |
200 | std::pair< edge_t, bool > p; |
201 | for (typename std::vector< |
202 | std::pair< vertex_t, vertex_t > >::const_iterator i |
203 | = edge_set.begin(); |
204 | i != edge_set.end(); ++i) |
205 | { |
206 | p = edge(i->first, i->second, g); |
207 | BOOST_TEST(p.second == true); |
208 | BOOST_TEST(source(p.first, g) == i->first); |
209 | BOOST_TEST(target(p.first, g) == i->second); |
210 | } |
211 | typename std::vector< vertex_t >::const_iterator j, k; |
212 | for (j = vertex_set.begin(); j != vertex_set.end(); ++j) |
213 | for (k = vertex_set.begin(); k != vertex_set.end(); ++k) |
214 | { |
215 | p = edge(*j, *k, g); |
216 | if (p.second == true) |
217 | BOOST_TEST( |
218 | find_if(edge_set, |
219 | connects(source(p.first, g), target(p.first, g), g)) |
220 | != boost::end(edge_set)); |
221 | } |
222 | } |
223 | |
224 | //========================================================================= |
225 | // Mutating Operations |
226 | |
227 | void test_add_vertex(Graph& g) |
228 | { |
229 | Graph cpy; |
230 | std::vector< vertex_t > iso_vec(num_vertices(g)); |
231 | IsoMap iso_map(iso_vec.begin(), get(vertex_index, g)); |
232 | copy_graph(g, cpy, orig_to_copy(iso_map)); |
233 | |
234 | BOOST_TEST((verify_isomorphism(g, cpy, iso_map))); |
235 | |
236 | vertex_t v = add_vertex(g); |
237 | |
238 | BOOST_TEST(num_vertices(g) == num_vertices(cpy) + 1); |
239 | |
240 | BOOST_TEST(out_degree(v, g) == 0); |
241 | |
242 | // Make sure the rest of the graph stayed the same |
243 | BOOST_TEST((verify_isomorphism( |
244 | make_filtered_graph(g, keep_all(), ignore_vertex(v)), cpy, |
245 | iso_map))); |
246 | } |
247 | |
248 | void test_add_edge(vertex_t u, vertex_t v, Graph& g) |
249 | { |
250 | Graph cpy; |
251 | std::vector< vertex_t > iso_vec(num_vertices(g)); |
252 | IsoMap iso_map(iso_vec.begin(), get(vertex_index, g)); |
253 | copy_graph(g, cpy, orig_to_copy(iso_map)); |
254 | |
255 | bool parallel_edge_exists |
256 | = container_contains(adjacent_vertices(u, g), v); |
257 | |
258 | std::pair< edge_t, bool > p = add_edge(u, v, g); |
259 | edge_t e = p.first; |
260 | bool added = p.second; |
261 | |
262 | if (is_undirected(g) && u == v) // self edge |
263 | BOOST_TEST(added == false); |
264 | else if (parallel_edge_exists) |
265 | BOOST_TEST(allows_parallel_edges(g) && added == true |
266 | || !allows_parallel_edges(g) && added == false); |
267 | else |
268 | BOOST_TEST(added == true); |
269 | |
270 | if (p.second == true) |
271 | { // edge added |
272 | BOOST_TEST(num_edges(g) == num_edges(cpy) + 1); |
273 | |
274 | BOOST_TEST(container_contains(out_edges(u, g), e) == true); |
275 | |
276 | BOOST_TEST((verify_isomorphism( |
277 | make_filtered_graph(g, ignore_edge(e)), cpy, iso_map))); |
278 | } |
279 | else |
280 | { // edge not added |
281 | if (!(is_undirected(g) && u == v)) |
282 | { |
283 | // e should be a parallel edge |
284 | BOOST_TEST(source(e, g) == u); |
285 | BOOST_TEST(target(e, g) == v); |
286 | } |
287 | // The graph should not be changed. |
288 | BOOST_TEST((verify_isomorphism(g, cpy, iso_map))); |
289 | } |
290 | } // test_add_edge() |
291 | |
292 | void test_remove_edge(vertex_t u, vertex_t v, Graph& g) |
293 | { |
294 | Graph cpy; |
295 | std::vector< vertex_t > iso_vec(num_vertices(g)); |
296 | IsoMap iso_map(iso_vec.begin(), get(vertex_index, g)); |
297 | copy_graph(g, cpy, orig_to_copy(iso_map)); |
298 | |
299 | deg_size_t occurances = count(adjacent_vertices(u, g), v); |
300 | |
301 | remove_edge(u, v, g); |
302 | |
303 | BOOST_TEST(num_edges(g) + occurances == num_edges(cpy)); |
304 | BOOST_TEST((verify_isomorphism( |
305 | g, make_filtered_graph(cpy, ignore_edges(u, v, cpy)), iso_map))); |
306 | } |
307 | |
308 | void test_remove_edge(edge_t e, Graph& g) |
309 | { |
310 | Graph cpy; |
311 | std::vector< vertex_t > iso_vec(num_vertices(g)); |
312 | IsoMap iso_map(iso_vec.begin(), get(vertex_index, g)); |
313 | copy_graph(g, cpy, orig_to_copy(iso_map)); |
314 | |
315 | vertex_t u = source(e, g), v = target(e, g); |
316 | deg_size_t occurances = count(adjacent_vertices(u, g), v); |
317 | |
318 | remove_edge(e, g); |
319 | |
320 | BOOST_TEST(num_edges(g) + 1 == num_edges(cpy)); |
321 | BOOST_TEST(count(adjacent_vertices(u, g), v) + 1 == occurances); |
322 | BOOST_TEST((verify_isomorphism( |
323 | g, make_filtered_graph(cpy, ignore_edge(e)), iso_map))); |
324 | } |
325 | |
326 | void test_clear_vertex(vertex_t v, Graph& g) |
327 | { |
328 | Graph cpy; |
329 | std::vector< vertex_t > iso_vec(num_vertices(g)); |
330 | IsoMap iso_map(iso_vec.begin(), get(vertex_index, g)); |
331 | copy_graph(g, cpy, orig_to_copy(iso_map)); |
332 | |
333 | clear_vertex(v, g); |
334 | |
335 | BOOST_TEST(out_degree(v, g) == 0); |
336 | BOOST_TEST(num_vertices(g) == num_vertices(cpy)); |
337 | BOOST_TEST((verify_isomorphism(g, |
338 | make_filtered_graph(cpy, keep_all(), ignore_vertex(v)), iso_map))); |
339 | } |
340 | |
341 | //========================================================================= |
342 | // Property Map |
343 | |
344 | template < typename PropVal, typename PropertyTag > |
345 | void test_readable_vertex_property_graph( |
346 | const std::vector< PropVal >& vertex_prop, PropertyTag tag, |
347 | const Graph& g) |
348 | { |
349 | typedef |
350 | typename property_map< Graph, PropertyTag >::const_type const_Map; |
351 | const_Map pmap = get(tag, g); |
352 | typename std::vector< PropVal >::const_iterator i = vertex_prop.begin(); |
353 | |
354 | for (typename boost::graph_traits< Graph >::vertex_iterator bgl_first_9 |
355 | = vertices(g).first, |
356 | bgl_last_9 = vertices(g).second; |
357 | bgl_first_9 != bgl_last_9; bgl_first_9 = bgl_last_9) |
358 | for (typename boost::graph_traits< Graph >::vertex_descriptor v; |
359 | bgl_first_9 != bgl_last_9 ? (v = *bgl_first_9, true) : false; |
360 | ++bgl_first_9) |
361 | { |
362 | // BGL_FORALL_VERTICES_T(v, g, Graph) { |
363 | typename property_traits< const_Map >::value_type pval1 |
364 | = get(pmap, v), |
365 | pval2 = get(tag, g, v); |
366 | BOOST_TEST(pval1 == pval2); |
367 | BOOST_TEST(pval1 == *i++); |
368 | } |
369 | } |
370 | |
371 | template < typename PropVal, typename PropertyTag > |
372 | void test_vertex_property_graph( |
373 | const std::vector< PropVal >& vertex_prop, PropertyTag tag, Graph& g) |
374 | { |
375 | typedef typename property_map< Graph, PropertyTag >::type PMap; |
376 | PMap pmap = get(tag, g); |
377 | typename std::vector< PropVal >::const_iterator i = vertex_prop.begin(); |
378 | for (typename boost::graph_traits< Graph >::vertex_iterator bgl_first_9 |
379 | = vertices(g).first, |
380 | bgl_last_9 = vertices(g).second; |
381 | bgl_first_9 != bgl_last_9; bgl_first_9 = bgl_last_9) |
382 | for (typename boost::graph_traits< Graph >::vertex_descriptor v; |
383 | bgl_first_9 != bgl_last_9 ? (v = *bgl_first_9, true) : false; |
384 | ++bgl_first_9) |
385 | // BGL_FORALL_VERTICES_T(v, g, Graph) |
386 | put(pmap, v, *i++); |
387 | |
388 | test_readable_vertex_property_graph(vertex_prop, tag, g); |
389 | |
390 | BGL_FORALL_VERTICES_T(v, g, Graph) |
391 | put(pmap, v, vertex_prop[0]); |
392 | |
393 | typename std::vector< PropVal >::const_iterator j = vertex_prop.begin(); |
394 | BGL_FORALL_VERTICES_T(v, g, Graph) |
395 | put(tag, g, v, *j++); |
396 | |
397 | test_readable_vertex_property_graph(vertex_prop, tag, g); |
398 | } |
399 | }; |
400 | |
401 | } // namespace boost |
402 | |
403 | #include <boost/graph/iteration_macros_undef.hpp> |
404 | |
405 | #endif // BOOST_GRAPH_TEST_HPP |
406 | |