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 21 22 // UNDER CONSTRUCTION 23 24 namespace boost { 25 26 template <typename Graph> 27 struct graph_test 28 { 29 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; 39 40 struct ignore_vertex { ignore_vertexboost::graph_test::ignore_vertex41 ignore_vertex() { } ignore_vertexboost::graph_test::ignore_vertex42 ignore_vertex(vertex_t v) : v(v) { } operator ()boost::graph_test::ignore_vertex43 bool operator()(vertex_t x) const { return x != v; } 44 vertex_t v; 45 }; 46 struct ignore_edge { ignore_edgeboost::graph_test::ignore_edge47 ignore_edge() { } ignore_edgeboost::graph_test::ignore_edge48 ignore_edge(edge_t e) : e(e) { } operator ()boost::graph_test::ignore_edge49 bool operator()(edge_t x) const { return x != e; } 50 edge_t e; 51 }; 52 struct ignore_edges { ignore_edgesboost::graph_test::ignore_edges53 ignore_edges(vertex_t s, vertex_t t, const Graph& g) 54 : s(s), t(t), g(g) { } operator ()boost::graph_test::ignore_edges55 bool operator()(edge_t x) const { 56 return !(source(x, g) == s && target(x, g) == t); 57 } 58 vertex_t s; vertex_t t; const Graph& g; 59 }; 60 61 //========================================================================= 62 // Traversal Operations 63 test_incidence_graphboost::graph_test64 void test_incidence_graph 65 (const std::vector<vertex_t>& vertex_set, 66 const std::vector< std::pair<vertex_t, vertex_t> >& edge_set, 67 const Graph& g) 68 { 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; 73 74 for (vertex_iter ui = vertex_set.begin(); ui != vertex_set.end(); ++ui) { 75 vertex_t u = *ui; 76 std::vector<vertex_t> adj; 77 for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e) 78 if (e->first == u) 79 adj.push_back(e->second); 80 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)) 84 == out_degree(u, g)); 85 for (; p.first != p.second; ++p.first) { 86 edge_t e = *p.first; 87 BOOST_CHECK(source(e, g) == u); 88 BOOST_CHECK(contains(adj, target(e, g)) == true); 89 } 90 } 91 } 92 test_bidirectional_graphboost::graph_test93 void test_bidirectional_graph 94 (const std::vector<vertex_t>& vertex_set, 95 const std::vector< std::pair<vertex_t, vertex_t> >& edge_set, 96 const Graph& g) 97 { 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; 102 103 for (vertex_iter vi = vertex_set.begin(); vi != vertex_set.end(); ++vi) { 104 vertex_t v = *vi; 105 std::vector<vertex_t> inv_adj; 106 for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e) 107 if (e->second == v) 108 inv_adj.push_back(e->first); 109 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)) 113 == in_degree(v, g)); 114 for (; p.first != p.second; ++p.first) { 115 edge_t e = *p.first; 116 BOOST_CHECK(target(e, g) == v); 117 BOOST_CHECK(contains(inv_adj, source(e, g)) == true); 118 } 119 } 120 } 121 test_adjacency_graphboost::graph_test122 void test_adjacency_graph 123 (const std::vector<vertex_t>& vertex_set, 124 const std::vector< std::pair<vertex_t,vertex_t> >& edge_set, 125 const Graph& g) 126 { 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; 131 132 for (vertex_iter ui = vertex_set.begin(); ui != vertex_set.end(); ++ui) { 133 vertex_t u = *ui; 134 std::vector<vertex_t> adj; 135 for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e) 136 if (e->first == u) 137 adj.push_back(e->second); 138 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); 144 } 145 } 146 } 147 test_vertex_list_graphboost::graph_test148 void test_vertex_list_graph 149 (const std::vector<vertex_t>& vertex_set, const Graph& g) 150 { 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); 159 } 160 } 161 test_edge_list_graphboost::graph_test162 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, 165 const Graph& g) 166 { 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) { 173 edge_t e = *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); 177 } 178 } 179 test_adjacency_matrixboost::graph_test180 void test_adjacency_matrix 181 (const std::vector<vertex_t>& vertex_set, 182 const std::vector< std::pair<vertex_t, vertex_t> >& edge_set, 183 const Graph& g) 184 { 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); 193 } 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) { 197 p = edge(*j, *k, g); 198 if (p.second == true) 199 BOOST_CHECK(any_if(edge_set, 200 connects(source(p.first, g), target(p.first, g), g)) == true); 201 } 202 } 203 204 //========================================================================= 205 // Mutating Operations 206 test_add_vertexboost::graph_test207 void test_add_vertex(Graph& g) 208 { 209 Graph cpy; 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)); 213 214 assert((verify_isomorphism(g, cpy, iso_map))); 215 216 vertex_t v = add_vertex(g); 217 218 BOOST_CHECK(num_vertices(g) == num_vertices(cpy) + 1); 219 220 BOOST_CHECK(out_degree(v, g) == 0); 221 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, 225 iso_map))); 226 } 227 test_add_edgeboost::graph_test228 void test_add_edge(vertex_t u, vertex_t v, Graph& g) 229 { 230 Graph cpy; 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)); 234 235 bool parallel_edge_exists = contains(adjacent_vertices(u, g), v); 236 237 std::pair<edge_t, bool> p = add_edge(u, v, g); 238 edge_t e = p.first; 239 bool added = p.second; 240 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); 246 else 247 BOOST_CHECK(added == true); 248 249 if (p.second == true) { // edge added 250 BOOST_CHECK(num_edges(g) == num_edges(cpy) + 1); 251 252 BOOST_CHECK(contains(out_edges(u, g), e) == true); 253 254 BOOST_CHECK((verify_isomorphism 255 (make_filtered_graph(g, ignore_edge(e)), cpy, iso_map))); 256 } 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); 262 } 263 // The graph should not be changed. 264 BOOST_CHECK((verify_isomorphism(g, cpy, iso_map))); 265 } 266 } // test_add_edge() 267 268 test_remove_edgeboost::graph_test269 void test_remove_edge(vertex_t u, vertex_t v, Graph& g) 270 { 271 Graph cpy; 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)); 275 276 deg_size_t occurances = count(adjacent_vertices(u, g), v); 277 278 remove_edge(u, v, g); 279 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)), 283 iso_map))); 284 } 285 test_remove_edgeboost::graph_test286 void test_remove_edge(edge_t e, Graph& g) 287 { 288 Graph cpy; 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)); 292 293 vertex_t u = source(e, g), v = target(e, g); 294 deg_size_t occurances = count(adjacent_vertices(u, g), v); 295 296 remove_edge(e, g); 297 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)), 302 iso_map))); 303 } 304 test_clear_vertexboost::graph_test305 void test_clear_vertex(vertex_t v, Graph& g) 306 { 307 Graph cpy; 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)); 311 312 clear_vertex(v, g); 313 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)), 318 iso_map))); 319 } 320 321 //========================================================================= 322 // Property Map 323 324 template <typename PropVal, typename PropertyTag> test_readable_vertex_property_graphboost::graph_test325 void test_readable_vertex_property_graph 326 (const std::vector<PropVal>& vertex_prop, PropertyTag, const Graph& g) 327 { 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(); 331 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; 337 ++bgl_first_9) { 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++); 343 } 344 } 345 346 template <typename PropVal, typename PropertyTag> test_vertex_property_graphboost::graph_test347 void test_vertex_property_graph 348 (const std::vector<PropVal>& vertex_prop, PropertyTag tag, Graph& g) 349 { 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; 358 ++bgl_first_9) 359 // BGL_FORALL_VERTICES_T(v, g, Graph) 360 put(pmap, v, *i++); 361 362 test_readable_vertex_property_graph(vertex_prop, tag, g); 363 364 BGL_FORALL_VERTICES_T(v, g, Graph) 365 put(pmap, v, vertex_prop[0]); 366 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++); 370 371 test_readable_vertex_property_graph(vertex_prop, tag, g); 372 } 373 374 375 }; 376 377 378 } // namespace boost 379 380 #include <boost/graph/iteration_macros_undef.hpp> 381 382 #endif // BOOST_GRAPH_TEST_HPP 383