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 { ignore_vertexboost::graph_test::ignore_vertex43 ignore_vertex() { } ignore_vertexboost::graph_test::ignore_vertex44 ignore_vertex(vertex_t v) : v(v) { } operator ()boost::graph_test::ignore_vertex45 bool operator()(vertex_t x) const { return x != v; } 46 vertex_t v; 47 }; 48 struct ignore_edge { ignore_edgeboost::graph_test::ignore_edge49 ignore_edge() { } ignore_edgeboost::graph_test::ignore_edge50 ignore_edge(edge_t e) : e(e) { } operator ()boost::graph_test::ignore_edge51 bool operator()(edge_t x) const { return x != e; } 52 edge_t e; 53 }; 54 struct ignore_edges { ignore_edgesboost::graph_test::ignore_edges55 ignore_edges(vertex_t s, vertex_t t, const Graph& g) 56 : s(s), t(t), g(g) { } operator ()boost::graph_test::ignore_edges57 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 test_incidence_graphboost::graph_test66 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 test_bidirectional_graphboost::graph_test95 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 test_adjacency_graphboost::graph_test124 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 test_vertex_list_graphboost::graph_test150 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 test_edge_list_graphboost::graph_test164 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 test_adjacency_matrixboost::graph_test182 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 test_add_vertexboost::graph_test209 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 test_add_edgeboost::graph_test230 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 test_remove_edgeboost::graph_test271 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 test_remove_edgeboost::graph_test288 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 test_clear_vertexboost::graph_test307 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> test_readable_vertex_property_graphboost::graph_test327 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> test_vertex_property_graphboost::graph_test349 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