graph/test/grid_graph_test.cpp

//=======================================================================
// 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 <ctime>

#include <boost/foreach.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/graph/grid_graph.hpp>
#include <boost/random.hpp>
#include <boost/core/lightweight_test.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_TEST(
            graph.length(dimension_index) == lengths[dimension_index]);
        BOOST_TEST(
            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_TEST(
            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_TEST(
            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_TEST(
                /*(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_TEST(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_TEST(target_vertices.count(get(boost::vertex_index, graph,
                              source(in_edge, graph)))
                > 0);

            ++in_edge_count;
        }

        BOOST_TEST(in_edge_count == in_degree(current_vertex, graph));

        // The number of out-edges and in-edges should be the same
        BOOST_TEST(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_TEST(target_vertices.count(
                              get(boost::vertex_index, graph, adjacent_vertex))
                > 0);

            ++adjacent_count;
        }

        BOOST_TEST(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_TEST(
                !edge(current_vertex, unconnected_vertex, graph).second);
            BOOST_TEST(
                !edge(unconnected_vertex, current_vertex, graph).second);
        }

        ++vertex_count;
    }

    BOOST_TEST(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_TEST(source_index != target_index);
        BOOST_TEST(/* (source_index >= 0) : always true && */ (
            source_index < num_vertices(graph)));
        BOOST_TEST(/* (target_index >= 0) : always true && */ (
            target_index < num_vertices(graph)));

        // Verify that the edge is listed as existing in both directions
        BOOST_TEST(edge(
            source(current_edge, graph), target(current_edge, graph), graph)
                          .second);
        BOOST_TEST(edge(
            target(current_edge, graph), source(current_edge, graph), graph)
                          .second);

        ++edge_count;
    }

    BOOST_TEST(edge_count == num_edges(graph));
}

int main(int argc, char* argv[])
{

    std::size_t random_seed = std::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 boost::report_errors();
}