| //======================================================================= |
| // 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> |
| |
| #define DIMENSIONS 3 |
| |
| 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 < DIMENSIONS; |
| ++dimension_index) { |
| std::cout << vertex_to_print[dimension_index]; |
| |
| if (dimension_index != (DIMENSIONS - 1)) { |
| std::cout << ", "; |
| } |
| } |
| |
| std::cout << ")"; |
| } |
| |
| 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); |
| |
| typedef grid_graph<DIMENSIONS> Graph; |
| typedef graph_traits<Graph>::vertices_size_type vertices_size_type; |
| typedef graph_traits<Graph>::edges_size_type edges_size_type; |
| |
| typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor; |
| typedef graph_traits<Graph>::edge_descriptor edge_descriptor; |
| |
| std::cout << "Dimensions: " << DIMENSIONS << ", lengths: "; |
| |
| // Randomly generate the dimension lengths (3-10) and wrapping |
| array<Graph::vertices_size_type, DIMENSIONS> lengths; |
| array<bool, DIMENSIONS> wrapped; |
| |
| for (int dimension_index = 0; |
| dimension_index < DIMENSIONS; |
| ++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 (int dimension_index = 0; |
| dimension_index < DIMENSIONS; |
| ++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 (int dimension_index = 0; |
| dimension_index < DIMENSIONS; |
| ++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)); |
| |
| return (0); |
| } |
| |