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
25namespace boost
26{
27
28template < 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

source code of boost/libs/graph/test/graph_test.hpp