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
26namespace 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

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