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 25 namespace boost 26 { 27 28 template < 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 { ignore_vertexboost::graph_test::ignore_vertex44 ignore_vertex() {} ignore_vertexboost::graph_test::ignore_vertex45 ignore_vertex(vertex_t v) : v(v) {} operator ()boost::graph_test::ignore_vertex46 bool operator()(vertex_t x) const { return x != v; } 47 vertex_t v; 48 }; 49 struct ignore_edge 50 { ignore_edgeboost::graph_test::ignore_edge51 ignore_edge() {} ignore_edgeboost::graph_test::ignore_edge52 ignore_edge(edge_t e) : e(e) {} operator ()boost::graph_test::ignore_edge53 bool operator()(edge_t x) const { return x != e; } 54 edge_t e; 55 }; 56 struct ignore_edges 57 { ignore_edgesboost::graph_test::ignore_edges58 ignore_edges(vertex_t s, vertex_t t, const Graph& g) : s(s), t(t), g(g) 59 { 60 } operator ()boost::graph_test::ignore_edges61 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 test_incidence_graphboost::graph_test73 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 test_bidirectional_graphboost::graph_test103 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 test_adjacency_graphboost::graph_test133 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 test_vertex_list_graphboost::graph_test161 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 test_edge_list_graphboost::graph_test176 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 test_adjacency_matrixboost::graph_test196 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 test_add_vertexboost::graph_test227 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 test_add_edgeboost::graph_test248 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 test_remove_edgeboost::graph_test292 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 test_remove_edgeboost::graph_test308 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 test_clear_vertexboost::graph_test326 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 > test_readable_vertex_property_graphboost::graph_test345 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 > test_vertex_property_graphboost::graph_test372 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