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