1 //=======================================================================
2 // Copyright 2002 Indiana University.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
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 //=======================================================================
10 #ifndef BOOST_GRAPH_TEST_HPP
11 #define BOOST_GRAPH_TEST_HPP
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
26 template <typename Graph>
30 typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
31 typedef typename graph_traits<Graph>::edge_descriptor edge_t;
32 typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
33 typedef typename graph_traits<Graph>::degree_size_type deg_size_t;
34 typedef typename graph_traits<Graph>::edges_size_type e_size_t;
35 typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iter;
36 typedef typename property_map<Graph, vertex_index_t>::type index_map_t;
37 typedef iterator_property_map<typename std::vector<vertex_t>::iterator,
38 index_map_t,vertex_t,vertex_t&> IsoMap;
40 struct ignore_vertex {
42 ignore_vertex(vertex_t v) : v(v) { }
43 bool operator()(vertex_t x) const { return x != v; }
48 ignore_edge(edge_t e) : e(e) { }
49 bool operator()(edge_t x) const { return x != e; }
53 ignore_edges(vertex_t s, vertex_t t, const Graph& g)
54 : s(s), t(t), g(g) { }
55 bool operator()(edge_t x) const {
56 return !(source(x, g) == s && target(x, g) == t);
58 vertex_t s; vertex_t t; const Graph& g;
61 //=========================================================================
62 // Traversal Operations
64 void test_incidence_graph
65 (const std::vector<vertex_t>& vertex_set,
66 const std::vector< std::pair<vertex_t, vertex_t> >& edge_set,
69 typedef typename std::vector<vertex_t>::const_iterator vertex_iter;
70 typedef typename std::vector< std::pair<vertex_t, vertex_t> >
71 ::const_iterator edge_iter;
72 typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iter;
74 for (vertex_iter ui = vertex_set.begin(); ui != vertex_set.end(); ++ui) {
76 std::vector<vertex_t> adj;
77 for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e)
79 adj.push_back(e->second);
81 std::pair<out_edge_iter, out_edge_iter> p = out_edges(u, g);
82 BOOST_CHECK(out_degree(u, g) == adj.size());
83 BOOST_CHECK(deg_size_t(std::distance(p.first, p.second))
85 for (; p.first != p.second; ++p.first) {
87 BOOST_CHECK(source(e, g) == u);
88 BOOST_CHECK(contains(adj, target(e, g)) == true);
93 void test_bidirectional_graph
94 (const std::vector<vertex_t>& vertex_set,
95 const std::vector< std::pair<vertex_t, vertex_t> >& edge_set,
98 typedef typename std::vector<vertex_t>::const_iterator vertex_iter;
99 typedef typename std::vector< std::pair<vertex_t, vertex_t> >
100 ::const_iterator edge_iter;
101 typedef typename graph_traits<Graph>::in_edge_iterator in_edge_iter;
103 for (vertex_iter vi = vertex_set.begin(); vi != vertex_set.end(); ++vi) {
105 std::vector<vertex_t> inv_adj;
106 for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e)
108 inv_adj.push_back(e->first);
110 std::pair<in_edge_iter, in_edge_iter> p = in_edges(v, g);
111 BOOST_CHECK(in_degree(v, g) == inv_adj.size());
112 BOOST_CHECK(deg_size_t(std::distance(p.first, p.second))
114 for (; p.first != p.second; ++p.first) {
116 BOOST_CHECK(target(e, g) == v);
117 BOOST_CHECK(contains(inv_adj, source(e, g)) == true);
122 void test_adjacency_graph
123 (const std::vector<vertex_t>& vertex_set,
124 const std::vector< std::pair<vertex_t,vertex_t> >& edge_set,
127 typedef typename std::vector<vertex_t>::const_iterator vertex_iter;
128 typedef typename std::vector<std::pair<vertex_t,vertex_t> >
129 ::const_iterator edge_iter;
130 typedef typename graph_traits<Graph>::adjacency_iterator adj_iter;
132 for (vertex_iter ui = vertex_set.begin(); ui != vertex_set.end(); ++ui) {
134 std::vector<vertex_t> adj;
135 for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e)
137 adj.push_back(e->second);
139 std::pair<adj_iter, adj_iter> p = adjacent_vertices(u, g);
140 BOOST_CHECK(deg_size_t(std::distance(p.first, p.second)) == adj.size());
141 for (; p.first != p.second; ++p.first) {
142 vertex_t v = *p.first;
143 BOOST_CHECK(contains(adj, v) == true);
148 void test_vertex_list_graph
149 (const std::vector<vertex_t>& vertex_set, const Graph& g)
151 typedef typename graph_traits<Graph>::vertex_iterator v_iter;
152 std::pair<v_iter, v_iter> p = vertices(g);
153 BOOST_CHECK(num_vertices(g) == vertex_set.size());
154 v_size_t n = std::distance(p.first, p.second);
155 BOOST_CHECK(n == num_vertices(g));
156 for (; p.first != p.second; ++p.first) {
157 vertex_t v = *p.first;
158 BOOST_CHECK(contains(vertex_set, v) == true);
162 void test_edge_list_graph
163 (const std::vector<vertex_t>& vertex_set,
164 const std::vector< std::pair<vertex_t, vertex_t> >& edge_set,
167 typedef typename graph_traits<Graph>::edge_iterator e_iter;
168 std::pair<e_iter, e_iter> p = edges(g);
169 BOOST_CHECK(num_edges(g) == edge_set.size());
170 e_size_t m = std::distance(p.first, p.second);
171 BOOST_CHECK(m == num_edges(g));
172 for (; p.first != p.second; ++p.first) {
174 BOOST_CHECK(any_if(edge_set, connects(source(e, g), target(e, g), g)));
175 BOOST_CHECK(contains(vertex_set, source(e, g)) == true);
176 BOOST_CHECK(contains(vertex_set, target(e, g)) == true);
180 void test_adjacency_matrix
181 (const std::vector<vertex_t>& vertex_set,
182 const std::vector< std::pair<vertex_t, vertex_t> >& edge_set,
185 std::pair<edge_t, bool> p;
186 for (typename std::vector<std::pair<vertex_t, vertex_t> >
187 ::const_iterator i = edge_set.begin();
188 i != edge_set.end(); ++i) {
189 p = edge(i->first, i->second, g);
190 BOOST_CHECK(p.second == true);
191 BOOST_CHECK(source(p.first, g) == i->first);
192 BOOST_CHECK(target(p.first, g) == i->second);
194 typename std::vector<vertex_t>::const_iterator j, k;
195 for (j = vertex_set.begin(); j != vertex_set.end(); ++j)
196 for (k = vertex_set.begin(); k != vertex_set.end(); ++k) {
198 if (p.second == true)
199 BOOST_CHECK(any_if(edge_set,
200 connects(source(p.first, g), target(p.first, g), g)) == true);
204 //=========================================================================
205 // Mutating Operations
207 void test_add_vertex(Graph& g)
210 std::vector<vertex_t> iso_vec(num_vertices(g));
211 IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
212 copy_graph(g, cpy, orig_to_copy(iso_map));
214 assert((verify_isomorphism(g, cpy, iso_map)));
216 vertex_t v = add_vertex(g);
218 BOOST_CHECK(num_vertices(g) == num_vertices(cpy) + 1);
220 BOOST_CHECK(out_degree(v, g) == 0);
222 // Make sure the rest of the graph stayed the same
223 BOOST_CHECK((verify_isomorphism
224 (make_filtered_graph(g, keep_all(), ignore_vertex(v)), cpy,
228 void test_add_edge(vertex_t u, vertex_t v, Graph& g)
231 std::vector<vertex_t> iso_vec(num_vertices(g));
232 IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
233 copy_graph(g, cpy, orig_to_copy(iso_map));
235 bool parallel_edge_exists = contains(adjacent_vertices(u, g), v);
237 std::pair<edge_t, bool> p = add_edge(u, v, g);
239 bool added = p.second;
241 if (is_undirected(g) && u == v) // self edge
242 BOOST_CHECK(added == false);
243 else if (parallel_edge_exists)
244 BOOST_CHECK(allows_parallel_edges(g) && added == true
245 || !allows_parallel_edges(g) && added == false);
247 BOOST_CHECK(added == true);
249 if (p.second == true) { // edge added
250 BOOST_CHECK(num_edges(g) == num_edges(cpy) + 1);
252 BOOST_CHECK(contains(out_edges(u, g), e) == true);
254 BOOST_CHECK((verify_isomorphism
255 (make_filtered_graph(g, ignore_edge(e)), cpy, iso_map)));
257 else { // edge not added
258 if (! (is_undirected(g) && u == v)) {
259 // e should be a parallel edge
260 BOOST_CHECK(source(e, g) == u);
261 BOOST_CHECK(target(e, g) == v);
263 // The graph should not be changed.
264 BOOST_CHECK((verify_isomorphism(g, cpy, iso_map)));
269 void test_remove_edge(vertex_t u, vertex_t v, Graph& g)
272 std::vector<vertex_t> iso_vec(num_vertices(g));
273 IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
274 copy_graph(g, cpy, orig_to_copy(iso_map));
276 deg_size_t occurances = count(adjacent_vertices(u, g), v);
278 remove_edge(u, v, g);
280 BOOST_CHECK(num_edges(g) + occurances == num_edges(cpy));
281 BOOST_CHECK((verify_isomorphism
282 (g, make_filtered_graph(cpy, ignore_edges(u,v,cpy)),
286 void test_remove_edge(edge_t e, Graph& g)
289 std::vector<vertex_t> iso_vec(num_vertices(g));
290 IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
291 copy_graph(g, cpy, orig_to_copy(iso_map));
293 vertex_t u = source(e, g), v = target(e, g);
294 deg_size_t occurances = count(adjacent_vertices(u, g), v);
298 BOOST_CHECK(num_edges(g) + 1 == num_edges(cpy));
299 BOOST_CHECK(count(adjacent_vertices(u, g), v) + 1 == occurances);
300 BOOST_CHECK((verify_isomorphism
301 (g, make_filtered_graph(cpy, ignore_edge(e)),
305 void test_clear_vertex(vertex_t v, Graph& g)
308 std::vector<vertex_t> iso_vec(num_vertices(g));
309 IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
310 copy_graph(g, cpy, orig_to_copy(iso_map));
314 BOOST_CHECK(out_degree(v, g) == 0);
315 BOOST_CHECK(num_vertices(g) == num_vertices(cpy));
316 BOOST_CHECK((verify_isomorphism
317 (g, make_filtered_graph(cpy, keep_all(), ignore_vertex(v)),
321 //=========================================================================
324 template <typename PropVal, typename PropertyTag>
325 void test_readable_vertex_property_graph
326 (const std::vector<PropVal>& vertex_prop, PropertyTag, const Graph& g)
328 typedef typename property_map<Graph, PropertyTag>::const_type const_Map;
329 const_Map pmap = get(PropertyTag(), g);
330 typename std::vector<PropVal>::const_iterator i = vertex_prop.begin();
332 for (typename boost::graph_traits<Graph>::vertex_iterator
333 bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second;
334 bgl_first_9 != bgl_last_9; bgl_first_9 = bgl_last_9)
335 for (typename boost::graph_traits<Graph>::vertex_descriptor v;
336 bgl_first_9 != bgl_last_9 ? (v = *bgl_first_9, true) : false;
338 //BGL_FORALL_VERTICES_T(v, g, Graph) {
339 typename property_traits<const_Map>::value_type
340 pval1 = get(pmap, v), pval2 = get(PropertyTag(), g, v);
341 BOOST_CHECK(pval1 == pval2);
342 BOOST_CHECK(pval1 == *i++);
346 template <typename PropVal, typename PropertyTag>
347 void test_vertex_property_graph
348 (const std::vector<PropVal>& vertex_prop, PropertyTag tag, Graph& g)
350 typedef typename property_map<Graph, PropertyTag>::type PMap;
351 PMap pmap = get(PropertyTag(), g);
352 typename std::vector<PropVal>::const_iterator i = vertex_prop.begin();
353 for (typename boost::graph_traits<Graph>::vertex_iterator
354 bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second;
355 bgl_first_9 != bgl_last_9; bgl_first_9 = bgl_last_9)
356 for (typename boost::graph_traits<Graph>::vertex_descriptor v;
357 bgl_first_9 != bgl_last_9 ? (v = *bgl_first_9, true) : false;
359 // BGL_FORALL_VERTICES_T(v, g, Graph)
362 test_readable_vertex_property_graph(vertex_prop, tag, g);
364 BGL_FORALL_VERTICES_T(v, g, Graph)
365 put(pmap, v, vertex_prop[0]);
367 typename std::vector<PropVal>::const_iterator j = vertex_prop.begin();
368 BGL_FORALL_VERTICES_T(v, g, Graph)
369 put(PropertyTag(), g, v, *j++);
371 test_readable_vertex_property_graph(vertex_prop, tag, g);
380 #include <boost/graph/iteration_macros_undef.hpp>
382 #endif // BOOST_GRAPH_TEST_HPP