123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218 |
- //=======================================================================
- // Copyright 2009 Trustees of Indiana University.
- // Authors: Michael Hansen, Andrew Lumsdaine
- //
- // Distributed under the Boost Software License, Version 1.0. (See
- // accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- //=======================================================================
- #include <fstream>
- #include <iostream>
- #include <set>
- #include <boost/foreach.hpp>
- #include <boost/lexical_cast.hpp>
- #include <boost/graph/grid_graph.hpp>
- #include <boost/random.hpp>
- #include <boost/test/minimal.hpp>
- using namespace boost;
- // Function that prints a vertex to std::cout
- template <typename Vertex>
- void print_vertex(Vertex vertex_to_print) {
- std::cout << "(";
- for (std::size_t dimension_index = 0;
- dimension_index < vertex_to_print.size();
- ++dimension_index) {
- std::cout << vertex_to_print[dimension_index];
- if (dimension_index != (vertex_to_print.size() - 1)) {
- std::cout << ", ";
- }
- }
- std::cout << ")";
- }
- template <unsigned int Dims>
- void do_test(minstd_rand& generator) {
- typedef grid_graph<Dims> Graph;
- typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
- typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
- std::cout << "Dimensions: " << Dims << ", lengths: ";
- // Randomly generate the dimension lengths (3-10) and wrapping
- boost::array<vertices_size_type, Dims> lengths;
- boost::array<bool, Dims> wrapped;
- for (unsigned int dimension_index = 0;
- dimension_index < Dims;
- ++dimension_index) {
- lengths[dimension_index] = 3 + (generator() % 8);
- wrapped[dimension_index] = ((generator() % 2) == 0);
- std::cout << lengths[dimension_index] <<
- (wrapped[dimension_index] ? " [W]" : " [U]") << ", ";
- }
- std::cout << std::endl;
- Graph graph(lengths, wrapped);
- // Verify dimension lengths and wrapping
- for (unsigned int dimension_index = 0;
- dimension_index < Dims;
- ++dimension_index) {
- BOOST_REQUIRE(graph.length(dimension_index) == lengths[dimension_index]);
- BOOST_REQUIRE(graph.wrapped(dimension_index) == wrapped[dimension_index]);
- }
- // Verify matching indices
- for (vertices_size_type vertex_index = 0;
- vertex_index < num_vertices(graph);
- ++vertex_index) {
- BOOST_REQUIRE(get(boost::vertex_index, graph, vertex(vertex_index, graph)) == vertex_index);
- }
- for (edges_size_type edge_index = 0;
- edge_index < num_edges(graph);
- ++edge_index) {
- edge_descriptor current_edge = edge_at(edge_index, graph);
- BOOST_REQUIRE(get(boost::edge_index, graph, current_edge) == edge_index);
- }
- // Verify all vertices are within bounds
- vertices_size_type vertex_count = 0;
- BOOST_FOREACH(vertex_descriptor current_vertex, vertices(graph)) {
- vertices_size_type current_index =
- get(boost::vertex_index, graph, current_vertex);
- for (unsigned int dimension_index = 0;
- dimension_index < Dims;
- ++dimension_index) {
- BOOST_REQUIRE(/*(current_vertex[dimension_index] >= 0) && */ // Always true
- (current_vertex[dimension_index] < lengths[dimension_index]));
- }
- // Verify out-edges of this vertex
- edges_size_type out_edge_count = 0;
- std::set<vertices_size_type> target_vertices;
- BOOST_FOREACH(edge_descriptor out_edge,
- out_edges(current_vertex, graph)) {
- target_vertices.insert
- (get(boost::vertex_index, graph, target(out_edge, graph)));
- ++out_edge_count;
- }
- BOOST_REQUIRE(out_edge_count == out_degree(current_vertex, graph));
- // Verify in-edges of this vertex
- edges_size_type in_edge_count = 0;
- BOOST_FOREACH(edge_descriptor in_edge,
- in_edges(current_vertex, graph)) {
- BOOST_REQUIRE(target_vertices.count
- (get(boost::vertex_index, graph, source(in_edge, graph))) > 0);
- ++in_edge_count;
- }
- BOOST_REQUIRE(in_edge_count == in_degree(current_vertex, graph));
- // The number of out-edges and in-edges should be the same
- BOOST_REQUIRE(degree(current_vertex, graph) ==
- out_degree(current_vertex, graph) +
- in_degree(current_vertex, graph));
- // Verify adjacent vertices to this vertex
- vertices_size_type adjacent_count = 0;
- BOOST_FOREACH(vertex_descriptor adjacent_vertex,
- adjacent_vertices(current_vertex, graph)) {
- BOOST_REQUIRE(target_vertices.count
- (get(boost::vertex_index, graph, adjacent_vertex)) > 0);
- ++adjacent_count;
- }
- BOOST_REQUIRE(adjacent_count == out_degree(current_vertex, graph));
- // Verify that this vertex is not listed as connected to any
- // vertices outside of its adjacent vertices.
- BOOST_FOREACH(vertex_descriptor unconnected_vertex, vertices(graph)) {
-
- vertices_size_type unconnected_index =
- get(boost::vertex_index, graph, unconnected_vertex);
- if ((unconnected_index == current_index) ||
- (target_vertices.count(unconnected_index) > 0)) {
- continue;
- }
- BOOST_REQUIRE(!edge(current_vertex, unconnected_vertex, graph).second);
- BOOST_REQUIRE(!edge(unconnected_vertex, current_vertex, graph).second);
- }
- ++vertex_count;
- }
- BOOST_REQUIRE(vertex_count == num_vertices(graph));
- // Verify all edges are within bounds
- edges_size_type edge_count = 0;
- BOOST_FOREACH(edge_descriptor current_edge, edges(graph)) {
- vertices_size_type source_index =
- get(boost::vertex_index, graph, source(current_edge, graph));
- vertices_size_type target_index =
- get(boost::vertex_index, graph, target(current_edge, graph));
- BOOST_REQUIRE(source_index != target_index);
- BOOST_REQUIRE(/* (source_index >= 0) : always true && */ (source_index < num_vertices(graph)));
- BOOST_REQUIRE(/* (target_index >= 0) : always true && */ (target_index < num_vertices(graph)));
- // Verify that the edge is listed as existing in both directions
- BOOST_REQUIRE(edge(source(current_edge, graph), target(current_edge, graph), graph).second);
- BOOST_REQUIRE(edge(target(current_edge, graph), source(current_edge, graph), graph).second);
- ++edge_count;
- }
- BOOST_REQUIRE(edge_count == num_edges(graph));
- }
- int test_main(int argc, char* argv[]) {
- std::size_t random_seed = time(0);
- if (argc > 1) {
- random_seed = lexical_cast<std::size_t>(argv[1]);
- }
- minstd_rand generator(random_seed);
- do_test<0>(generator);
- do_test<1>(generator);
- do_test<2>(generator);
- do_test<3>(generator);
- do_test<4>(generator);
- return (0);
- }
|