1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/graph_test.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,382 @@
1.4 +//=======================================================================
1.5 +// Copyright 2002 Indiana University.
1.6 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
1.7 +//
1.8 +// Distributed under the Boost Software License, Version 1.0. (See
1.9 +// accompanying file LICENSE_1_0.txt or copy at
1.10 +// http://www.boost.org/LICENSE_1_0.txt)
1.11 +//=======================================================================
1.12 +
1.13 +#ifndef BOOST_GRAPH_TEST_HPP
1.14 +#define BOOST_GRAPH_TEST_HPP
1.15 +
1.16 +#include <vector>
1.17 +#include <boost/test/minimal.hpp>
1.18 +#include <boost/graph/filtered_graph.hpp>
1.19 +#include <boost/graph/iteration_macros.hpp>
1.20 +#include <boost/graph/isomorphism.hpp>
1.21 +#include <boost/graph/copy.hpp>
1.22 +#include <boost/graph/graph_utility.hpp> // for connects
1.23 +
1.24 +
1.25 +// UNDER CONSTRUCTION
1.26 +
1.27 +namespace boost {
1.28 +
1.29 + template <typename Graph>
1.30 + struct graph_test
1.31 + {
1.32 +
1.33 + typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
1.34 + typedef typename graph_traits<Graph>::edge_descriptor edge_t;
1.35 + typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
1.36 + typedef typename graph_traits<Graph>::degree_size_type deg_size_t;
1.37 + typedef typename graph_traits<Graph>::edges_size_type e_size_t;
1.38 + typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iter;
1.39 + typedef typename property_map<Graph, vertex_index_t>::type index_map_t;
1.40 + typedef iterator_property_map<typename std::vector<vertex_t>::iterator,
1.41 + index_map_t,vertex_t,vertex_t&> IsoMap;
1.42 +
1.43 + struct ignore_vertex {
1.44 + ignore_vertex() { }
1.45 + ignore_vertex(vertex_t v) : v(v) { }
1.46 + bool operator()(vertex_t x) const { return x != v; }
1.47 + vertex_t v;
1.48 + };
1.49 + struct ignore_edge {
1.50 + ignore_edge() { }
1.51 + ignore_edge(edge_t e) : e(e) { }
1.52 + bool operator()(edge_t x) const { return x != e; }
1.53 + edge_t e;
1.54 + };
1.55 + struct ignore_edges {
1.56 + ignore_edges(vertex_t s, vertex_t t, const Graph& g)
1.57 + : s(s), t(t), g(g) { }
1.58 + bool operator()(edge_t x) const {
1.59 + return !(source(x, g) == s && target(x, g) == t);
1.60 + }
1.61 + vertex_t s; vertex_t t; const Graph& g;
1.62 + };
1.63 +
1.64 + //=========================================================================
1.65 + // Traversal Operations
1.66 +
1.67 + void test_incidence_graph
1.68 + (const std::vector<vertex_t>& vertex_set,
1.69 + const std::vector< std::pair<vertex_t, vertex_t> >& edge_set,
1.70 + const Graph& g)
1.71 + {
1.72 + typedef typename std::vector<vertex_t>::const_iterator vertex_iter;
1.73 + typedef typename std::vector< std::pair<vertex_t, vertex_t> >
1.74 + ::const_iterator edge_iter;
1.75 + typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iter;
1.76 +
1.77 + for (vertex_iter ui = vertex_set.begin(); ui != vertex_set.end(); ++ui) {
1.78 + vertex_t u = *ui;
1.79 + std::vector<vertex_t> adj;
1.80 + for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e)
1.81 + if (e->first == u)
1.82 + adj.push_back(e->second);
1.83 +
1.84 + std::pair<out_edge_iter, out_edge_iter> p = out_edges(u, g);
1.85 + BOOST_CHECK(out_degree(u, g) == adj.size());
1.86 + BOOST_CHECK(deg_size_t(std::distance(p.first, p.second))
1.87 + == out_degree(u, g));
1.88 + for (; p.first != p.second; ++p.first) {
1.89 + edge_t e = *p.first;
1.90 + BOOST_CHECK(source(e, g) == u);
1.91 + BOOST_CHECK(contains(adj, target(e, g)) == true);
1.92 + }
1.93 + }
1.94 + }
1.95 +
1.96 + void test_bidirectional_graph
1.97 + (const std::vector<vertex_t>& vertex_set,
1.98 + const std::vector< std::pair<vertex_t, vertex_t> >& edge_set,
1.99 + const Graph& g)
1.100 + {
1.101 + typedef typename std::vector<vertex_t>::const_iterator vertex_iter;
1.102 + typedef typename std::vector< std::pair<vertex_t, vertex_t> >
1.103 + ::const_iterator edge_iter;
1.104 + typedef typename graph_traits<Graph>::in_edge_iterator in_edge_iter;
1.105 +
1.106 + for (vertex_iter vi = vertex_set.begin(); vi != vertex_set.end(); ++vi) {
1.107 + vertex_t v = *vi;
1.108 + std::vector<vertex_t> inv_adj;
1.109 + for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e)
1.110 + if (e->second == v)
1.111 + inv_adj.push_back(e->first);
1.112 +
1.113 + std::pair<in_edge_iter, in_edge_iter> p = in_edges(v, g);
1.114 + BOOST_CHECK(in_degree(v, g) == inv_adj.size());
1.115 + BOOST_CHECK(deg_size_t(std::distance(p.first, p.second))
1.116 + == in_degree(v, g));
1.117 + for (; p.first != p.second; ++p.first) {
1.118 + edge_t e = *p.first;
1.119 + BOOST_CHECK(target(e, g) == v);
1.120 + BOOST_CHECK(contains(inv_adj, source(e, g)) == true);
1.121 + }
1.122 + }
1.123 + }
1.124 +
1.125 + void test_adjacency_graph
1.126 + (const std::vector<vertex_t>& vertex_set,
1.127 + const std::vector< std::pair<vertex_t,vertex_t> >& edge_set,
1.128 + const Graph& g)
1.129 + {
1.130 + typedef typename std::vector<vertex_t>::const_iterator vertex_iter;
1.131 + typedef typename std::vector<std::pair<vertex_t,vertex_t> >
1.132 + ::const_iterator edge_iter;
1.133 + typedef typename graph_traits<Graph>::adjacency_iterator adj_iter;
1.134 +
1.135 + for (vertex_iter ui = vertex_set.begin(); ui != vertex_set.end(); ++ui) {
1.136 + vertex_t u = *ui;
1.137 + std::vector<vertex_t> adj;
1.138 + for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e)
1.139 + if (e->first == u)
1.140 + adj.push_back(e->second);
1.141 +
1.142 + std::pair<adj_iter, adj_iter> p = adjacent_vertices(u, g);
1.143 + BOOST_CHECK(deg_size_t(std::distance(p.first, p.second)) == adj.size());
1.144 + for (; p.first != p.second; ++p.first) {
1.145 + vertex_t v = *p.first;
1.146 + BOOST_CHECK(contains(adj, v) == true);
1.147 + }
1.148 + }
1.149 + }
1.150 +
1.151 + void test_vertex_list_graph
1.152 + (const std::vector<vertex_t>& vertex_set, const Graph& g)
1.153 + {
1.154 + typedef typename graph_traits<Graph>::vertex_iterator v_iter;
1.155 + std::pair<v_iter, v_iter> p = vertices(g);
1.156 + BOOST_CHECK(num_vertices(g) == vertex_set.size());
1.157 + v_size_t n = std::distance(p.first, p.second);
1.158 + BOOST_CHECK(n == num_vertices(g));
1.159 + for (; p.first != p.second; ++p.first) {
1.160 + vertex_t v = *p.first;
1.161 + BOOST_CHECK(contains(vertex_set, v) == true);
1.162 + }
1.163 + }
1.164 +
1.165 + void test_edge_list_graph
1.166 + (const std::vector<vertex_t>& vertex_set,
1.167 + const std::vector< std::pair<vertex_t, vertex_t> >& edge_set,
1.168 + const Graph& g)
1.169 + {
1.170 + typedef typename graph_traits<Graph>::edge_iterator e_iter;
1.171 + std::pair<e_iter, e_iter> p = edges(g);
1.172 + BOOST_CHECK(num_edges(g) == edge_set.size());
1.173 + e_size_t m = std::distance(p.first, p.second);
1.174 + BOOST_CHECK(m == num_edges(g));
1.175 + for (; p.first != p.second; ++p.first) {
1.176 + edge_t e = *p.first;
1.177 + BOOST_CHECK(any_if(edge_set, connects(source(e, g), target(e, g), g)));
1.178 + BOOST_CHECK(contains(vertex_set, source(e, g)) == true);
1.179 + BOOST_CHECK(contains(vertex_set, target(e, g)) == true);
1.180 + }
1.181 + }
1.182 +
1.183 + void test_adjacency_matrix
1.184 + (const std::vector<vertex_t>& vertex_set,
1.185 + const std::vector< std::pair<vertex_t, vertex_t> >& edge_set,
1.186 + const Graph& g)
1.187 + {
1.188 + std::pair<edge_t, bool> p;
1.189 + for (typename std::vector<std::pair<vertex_t, vertex_t> >
1.190 + ::const_iterator i = edge_set.begin();
1.191 + i != edge_set.end(); ++i) {
1.192 + p = edge(i->first, i->second, g);
1.193 + BOOST_CHECK(p.second == true);
1.194 + BOOST_CHECK(source(p.first, g) == i->first);
1.195 + BOOST_CHECK(target(p.first, g) == i->second);
1.196 + }
1.197 + typename std::vector<vertex_t>::const_iterator j, k;
1.198 + for (j = vertex_set.begin(); j != vertex_set.end(); ++j)
1.199 + for (k = vertex_set.begin(); k != vertex_set.end(); ++k) {
1.200 + p = edge(*j, *k, g);
1.201 + if (p.second == true)
1.202 + BOOST_CHECK(any_if(edge_set,
1.203 + connects(source(p.first, g), target(p.first, g), g)) == true);
1.204 + }
1.205 + }
1.206 +
1.207 + //=========================================================================
1.208 + // Mutating Operations
1.209 +
1.210 + void test_add_vertex(Graph& g)
1.211 + {
1.212 + Graph cpy;
1.213 + std::vector<vertex_t> iso_vec(num_vertices(g));
1.214 + IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
1.215 + copy_graph(g, cpy, orig_to_copy(iso_map));
1.216 +
1.217 + assert((verify_isomorphism(g, cpy, iso_map)));
1.218 +
1.219 + vertex_t v = add_vertex(g);
1.220 +
1.221 + BOOST_CHECK(num_vertices(g) == num_vertices(cpy) + 1);
1.222 +
1.223 + BOOST_CHECK(out_degree(v, g) == 0);
1.224 +
1.225 + // Make sure the rest of the graph stayed the same
1.226 + BOOST_CHECK((verify_isomorphism
1.227 + (make_filtered_graph(g, keep_all(), ignore_vertex(v)), cpy,
1.228 + iso_map)));
1.229 + }
1.230 +
1.231 + void test_add_edge(vertex_t u, vertex_t v, Graph& g)
1.232 + {
1.233 + Graph cpy;
1.234 + std::vector<vertex_t> iso_vec(num_vertices(g));
1.235 + IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
1.236 + copy_graph(g, cpy, orig_to_copy(iso_map));
1.237 +
1.238 + bool parallel_edge_exists = contains(adjacent_vertices(u, g), v);
1.239 +
1.240 + std::pair<edge_t, bool> p = add_edge(u, v, g);
1.241 + edge_t e = p.first;
1.242 + bool added = p.second;
1.243 +
1.244 + if (is_undirected(g) && u == v) // self edge
1.245 + BOOST_CHECK(added == false);
1.246 + else if (parallel_edge_exists)
1.247 + BOOST_CHECK(allows_parallel_edges(g) && added == true
1.248 + || !allows_parallel_edges(g) && added == false);
1.249 + else
1.250 + BOOST_CHECK(added == true);
1.251 +
1.252 + if (p.second == true) { // edge added
1.253 + BOOST_CHECK(num_edges(g) == num_edges(cpy) + 1);
1.254 +
1.255 + BOOST_CHECK(contains(out_edges(u, g), e) == true);
1.256 +
1.257 + BOOST_CHECK((verify_isomorphism
1.258 + (make_filtered_graph(g, ignore_edge(e)), cpy, iso_map)));
1.259 + }
1.260 + else { // edge not added
1.261 + if (! (is_undirected(g) && u == v)) {
1.262 + // e should be a parallel edge
1.263 + BOOST_CHECK(source(e, g) == u);
1.264 + BOOST_CHECK(target(e, g) == v);
1.265 + }
1.266 + // The graph should not be changed.
1.267 + BOOST_CHECK((verify_isomorphism(g, cpy, iso_map)));
1.268 + }
1.269 + } // test_add_edge()
1.270 +
1.271 +
1.272 + void test_remove_edge(vertex_t u, vertex_t v, Graph& g)
1.273 + {
1.274 + Graph cpy;
1.275 + std::vector<vertex_t> iso_vec(num_vertices(g));
1.276 + IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
1.277 + copy_graph(g, cpy, orig_to_copy(iso_map));
1.278 +
1.279 + deg_size_t occurances = count(adjacent_vertices(u, g), v);
1.280 +
1.281 + remove_edge(u, v, g);
1.282 +
1.283 + BOOST_CHECK(num_edges(g) + occurances == num_edges(cpy));
1.284 + BOOST_CHECK((verify_isomorphism
1.285 + (g, make_filtered_graph(cpy, ignore_edges(u,v,cpy)),
1.286 + iso_map)));
1.287 + }
1.288 +
1.289 + void test_remove_edge(edge_t e, Graph& g)
1.290 + {
1.291 + Graph cpy;
1.292 + std::vector<vertex_t> iso_vec(num_vertices(g));
1.293 + IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
1.294 + copy_graph(g, cpy, orig_to_copy(iso_map));
1.295 +
1.296 + vertex_t u = source(e, g), v = target(e, g);
1.297 + deg_size_t occurances = count(adjacent_vertices(u, g), v);
1.298 +
1.299 + remove_edge(e, g);
1.300 +
1.301 + BOOST_CHECK(num_edges(g) + 1 == num_edges(cpy));
1.302 + BOOST_CHECK(count(adjacent_vertices(u, g), v) + 1 == occurances);
1.303 + BOOST_CHECK((verify_isomorphism
1.304 + (g, make_filtered_graph(cpy, ignore_edge(e)),
1.305 + iso_map)));
1.306 + }
1.307 +
1.308 + void test_clear_vertex(vertex_t v, Graph& g)
1.309 + {
1.310 + Graph cpy;
1.311 + std::vector<vertex_t> iso_vec(num_vertices(g));
1.312 + IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
1.313 + copy_graph(g, cpy, orig_to_copy(iso_map));
1.314 +
1.315 + clear_vertex(v, g);
1.316 +
1.317 + BOOST_CHECK(out_degree(v, g) == 0);
1.318 + BOOST_CHECK(num_vertices(g) == num_vertices(cpy));
1.319 + BOOST_CHECK((verify_isomorphism
1.320 + (g, make_filtered_graph(cpy, keep_all(), ignore_vertex(v)),
1.321 + iso_map)));
1.322 + }
1.323 +
1.324 + //=========================================================================
1.325 + // Property Map
1.326 +
1.327 + template <typename PropVal, typename PropertyTag>
1.328 + void test_readable_vertex_property_graph
1.329 + (const std::vector<PropVal>& vertex_prop, PropertyTag, const Graph& g)
1.330 + {
1.331 + typedef typename property_map<Graph, PropertyTag>::const_type const_Map;
1.332 + const_Map pmap = get(PropertyTag(), g);
1.333 + typename std::vector<PropVal>::const_iterator i = vertex_prop.begin();
1.334 +
1.335 + for (typename boost::graph_traits<Graph>::vertex_iterator
1.336 + bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second;
1.337 + bgl_first_9 != bgl_last_9; bgl_first_9 = bgl_last_9)
1.338 + for (typename boost::graph_traits<Graph>::vertex_descriptor v;
1.339 + bgl_first_9 != bgl_last_9 ? (v = *bgl_first_9, true) : false;
1.340 + ++bgl_first_9) {
1.341 + //BGL_FORALL_VERTICES_T(v, g, Graph) {
1.342 + typename property_traits<const_Map>::value_type
1.343 + pval1 = get(pmap, v), pval2 = get(PropertyTag(), g, v);
1.344 + BOOST_CHECK(pval1 == pval2);
1.345 + BOOST_CHECK(pval1 == *i++);
1.346 + }
1.347 + }
1.348 +
1.349 + template <typename PropVal, typename PropertyTag>
1.350 + void test_vertex_property_graph
1.351 + (const std::vector<PropVal>& vertex_prop, PropertyTag tag, Graph& g)
1.352 + {
1.353 + typedef typename property_map<Graph, PropertyTag>::type PMap;
1.354 + PMap pmap = get(PropertyTag(), g);
1.355 + typename std::vector<PropVal>::const_iterator i = vertex_prop.begin();
1.356 + for (typename boost::graph_traits<Graph>::vertex_iterator
1.357 + bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second;
1.358 + bgl_first_9 != bgl_last_9; bgl_first_9 = bgl_last_9)
1.359 + for (typename boost::graph_traits<Graph>::vertex_descriptor v;
1.360 + bgl_first_9 != bgl_last_9 ? (v = *bgl_first_9, true) : false;
1.361 + ++bgl_first_9)
1.362 + // BGL_FORALL_VERTICES_T(v, g, Graph)
1.363 + put(pmap, v, *i++);
1.364 +
1.365 + test_readable_vertex_property_graph(vertex_prop, tag, g);
1.366 +
1.367 + BGL_FORALL_VERTICES_T(v, g, Graph)
1.368 + put(pmap, v, vertex_prop[0]);
1.369 +
1.370 + typename std::vector<PropVal>::const_iterator j = vertex_prop.begin();
1.371 + BGL_FORALL_VERTICES_T(v, g, Graph)
1.372 + put(PropertyTag(), g, v, *j++);
1.373 +
1.374 + test_readable_vertex_property_graph(vertex_prop, tag, g);
1.375 + }
1.376 +
1.377 +
1.378 + };
1.379 +
1.380 +
1.381 +} // namespace boost
1.382 +
1.383 +#include <boost/graph/iteration_macros_undef.hpp>
1.384 +
1.385 +#endif // BOOST_GRAPH_TEST_HPP