graph/test/csr_graph_test.cpp

// Copyright 2005 The Trustees of Indiana University.

// Use, modification and distribution is subject to 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)

//  Authors: Jeremiah Willcock
//           Douglas Gregor
//           Andrew Lumsdaine

// The libstdc++ debug mode makes this test run for hours...
#ifdef _GLIBCXX_DEBUG
#undef _GLIBCXX_DEBUG
#endif

// Test for the compressed sparse row graph type
#include <boost/graph/compressed_sparse_row_graph.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/erdos_renyi_generator.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/random/linear_congruential.hpp>
#include <boost/concept_check.hpp> // for ignore_unused_variable_warning
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <boost/lexical_cast.hpp>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/limits.hpp>
#include <string>
#include <boost/graph/iteration_macros.hpp>
#include <boost/core/lightweight_test.hpp>

// Algorithms to test against
#include <boost/graph/betweenness_centrality.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>

typedef boost::adjacency_list<> GraphT;
typedef boost::erdos_renyi_iterator< boost::minstd_rand, GraphT > ERGen;

struct VertexData
{
    int index;
};

struct EdgeData
{
    int index_e;
};

typedef boost::compressed_sparse_row_graph< boost::directedS, VertexData,
    EdgeData >
    CSRGraphT;

typedef boost::compressed_sparse_row_graph< boost::bidirectionalS, VertexData,
    EdgeData >
    BidirCSRGraphT;

template < class G1, class VI1, class G2, class VI2, class IsomorphismMap >
void assert_graphs_equal(const G1& g1, const VI1& vi1, const G2& g2,
    const VI2& vi2, const IsomorphismMap& iso)
{
    using boost::out_degree;

    BOOST_TEST(num_vertices(g1) == num_vertices(g2));
    BOOST_TEST(num_edges(g1) == num_edges(g2));

    typedef typename boost::graph_traits< G1 >::vertex_iterator vertiter1;
    {
        vertiter1 i, iend;
        for (boost::tie(i, iend) = vertices(g1); i != iend; ++i)
        {
            typename boost::graph_traits< G1 >::vertex_descriptor v1 = *i;
            typename boost::graph_traits< G2 >::vertex_descriptor v2 = iso[v1];

            BOOST_TEST(vi1[v1] == vi2[v2]);

            BOOST_TEST(out_degree(v1, g1) == out_degree(v2, g2));
            std::vector< std::size_t > edges1(out_degree(v1, g1));
            typename boost::graph_traits< G1 >::out_edge_iterator oe1, oe1end;
            for (boost::tie(oe1, oe1end) = out_edges(v1, g1); oe1 != oe1end;
                 ++oe1)
            {
                BOOST_TEST(source(*oe1, g1) == v1);
                edges1.push_back(vi1[target(*oe1, g1)]);
            }
            std::vector< std::size_t > edges2(out_degree(v2, g2));
            typename boost::graph_traits< G2 >::out_edge_iterator oe2, oe2end;
            for (boost::tie(oe2, oe2end) = out_edges(v2, g2); oe2 != oe2end;
                 ++oe2)
            {
                BOOST_TEST(source(*oe2, g2) == v2);
                edges2.push_back(vi2[target(*oe2, g2)]);
            }

            std::sort(edges1.begin(), edges1.end());
            std::sort(edges2.begin(), edges2.end());
            if (edges1 != edges2)
            {
                std::cerr << "For vertex " << v1 << std::endl;
                std::cerr << "edges1:";
                for (size_t i = 0; i < edges1.size(); ++i)
                    std::cerr << " " << edges1[i];
                std::cerr << std::endl;
                std::cerr << "edges2:";
                for (size_t i = 0; i < edges2.size(); ++i)
                    std::cerr << " " << edges2[i];
                std::cerr << std::endl;
            }
            BOOST_TEST(edges1 == edges2);
        }
    }

    {
        std::vector< std::pair< std::size_t, std::size_t > > all_edges1;
        std::vector< std::pair< std::size_t, std::size_t > > all_edges2;
        typename boost::graph_traits< G1 >::edge_iterator ei1, ei1end;
        for (boost::tie(ei1, ei1end) = edges(g1); ei1 != ei1end; ++ei1)
            all_edges1.push_back(
                std::make_pair(vi1[source(*ei1, g1)], vi1[target(*ei1, g1)]));
        typename boost::graph_traits< G2 >::edge_iterator ei2, ei2end;
        for (boost::tie(ei2, ei2end) = edges(g2); ei2 != ei2end; ++ei2)
            all_edges2.push_back(
                std::make_pair(vi2[source(*ei2, g2)], vi2[target(*ei2, g2)]));
        std::sort(all_edges1.begin(), all_edges1.end());
        std::sort(all_edges2.begin(), all_edges2.end());
        BOOST_TEST(all_edges1 == all_edges2);
    }
}

template < typename Structure > void check_consistency_one(const Structure& g)
{
    // Do a bunch of tests on the graph internal data
    // Check that m_rowstart entries are valid, and that entries after
    // m_last_source + 1 are all zero
    BOOST_TEST(g.m_rowstart[0] == 0);
    for (size_t i = 0; i < g.m_rowstart.size() - 1; ++i)
    {
        BOOST_TEST(g.m_rowstart[i + 1] >= g.m_rowstart[i]);
        BOOST_TEST(g.m_rowstart[i + 1] <= g.m_rowstart.back());
    }
    // Check that m_column entries are within range
    for (size_t i = 0; i < g.m_rowstart.back(); ++i)
    {
        BOOST_TEST(g.m_column[i] < g.m_rowstart.size() - 1);
    }
}

template < typename Graph >
void check_consistency_dispatch(const Graph& g, boost::incidence_graph_tag)
{
    check_consistency_one(g.m_forward);
}

template < class G > void assert_bidir_equal_in_both_dirs(const G& g)
{
    BOOST_TEST(
        g.m_forward.m_rowstart.size() == g.m_backward.m_rowstart.size());
    BOOST_TEST(g.m_forward.m_column.size() == g.m_backward.m_column.size());
    typedef typename boost::graph_traits< G >::vertex_descriptor Vertex;
    typedef typename boost::graph_traits< G >::edges_size_type EdgeIndex;
    std::vector< boost::tuple< EdgeIndex, Vertex, Vertex > > edges_forward,
        edges_backward;
    for (Vertex i = 0; i < g.m_forward.m_rowstart.size() - 1; ++i)
    {
        for (EdgeIndex j = g.m_forward.m_rowstart[i];
             j < g.m_forward.m_rowstart[i + 1]; ++j)
        {
            edges_forward.push_back(
                boost::make_tuple(j, i, g.m_forward.m_column[j]));
        }
    }
    for (Vertex i = 0; i < g.m_backward.m_rowstart.size() - 1; ++i)
    {
        for (EdgeIndex j = g.m_backward.m_rowstart[i];
             j < g.m_backward.m_rowstart[i + 1]; ++j)
        {
            edges_backward.push_back(
                boost::make_tuple(g.m_backward.m_edge_properties[j],
                    g.m_backward.m_column[j], i));
        }
    }
    std::sort(edges_forward.begin(), edges_forward.end());
    std::sort(edges_backward.begin(), edges_backward.end());
    BOOST_TEST(edges_forward == edges_backward);
}

template < typename Graph >
void check_consistency_dispatch(const Graph& g, boost::bidirectional_graph_tag)
{
    check_consistency_one(g.m_forward);
    check_consistency_one(g.m_backward);
    assert_bidir_equal_in_both_dirs(g);
}

template < typename Graph > void check_consistency(const Graph& g)
{
    check_consistency_dispatch(
        g, typename boost::graph_traits< Graph >::traversal_category());
}

template < typename OrigGraph > void graph_test(const OrigGraph& g)
{
    // Check copying of a graph
    CSRGraphT g2(g);
    check_consistency(g2);
    BOOST_TEST((std::size_t)std::distance(edges(g2).first, edges(g2).second)
        == num_edges(g2));
    assert_graphs_equal(g, boost::identity_property_map(), g2,
        boost::identity_property_map(), boost::identity_property_map());

    // Check constructing a graph from iterators
    CSRGraphT g3(boost::edges_are_sorted,
        boost::make_transform_iterator(
            edges(g2).first, boost::detail::make_edge_to_index_pair(g2)),
        boost::make_transform_iterator(
            edges(g2).second, boost::detail::make_edge_to_index_pair(g2)),
        num_vertices(g));
    check_consistency(g3);
    BOOST_TEST((std::size_t)std::distance(edges(g3).first, edges(g3).second)
        == num_edges(g3));
    assert_graphs_equal(g2, boost::identity_property_map(), g3,
        boost::identity_property_map(), boost::identity_property_map());

    // Check constructing a graph using in-place modification of vectors
    {
        std::vector< std::size_t > sources(num_edges(g2));
        std::vector< std::size_t > targets(num_edges(g2));
        std::size_t idx = 0;
        // Edges actually sorted
        BGL_FORALL_EDGES(e, g2, CSRGraphT)
        {
            sources[idx] = source(e, g2);
            targets[idx] = target(e, g2);
            ++idx;
        }
        CSRGraphT g3a(boost::construct_inplace_from_sources_and_targets,
            sources, targets, num_vertices(g2));
        check_consistency(g3a);
        assert_graphs_equal(g2, boost::identity_property_map(), g3a,
            boost::identity_property_map(), boost::identity_property_map());
    }
    {
        std::vector< std::size_t > sources(num_edges(g2));
        std::vector< std::size_t > targets(num_edges(g2));
        std::size_t idx = 0;
        // Edges reverse-sorted
        BGL_FORALL_EDGES(e, g2, CSRGraphT)
        {
            sources[num_edges(g2) - 1 - idx] = source(e, g2);
            targets[num_edges(g2) - 1 - idx] = target(e, g2);
            ++idx;
        }
        CSRGraphT g3a(boost::construct_inplace_from_sources_and_targets,
            sources, targets, num_vertices(g2));
        check_consistency(g3a);
        assert_graphs_equal(g2, boost::identity_property_map(), g3a,
            boost::identity_property_map(), boost::identity_property_map());
    }
    {
        std::vector< std::size_t > sources(num_edges(g2));
        std::vector< std::size_t > targets(num_edges(g2));
        std::size_t idx = 0;
        // Edges scrambled using Fisher-Yates shuffle (Durstenfeld variant) from
        // Wikipedia
        BGL_FORALL_EDGES(e, g2, CSRGraphT)
        {
            sources[idx] = source(e, g2);
            targets[idx] = target(e, g2);
            ++idx;
        }
        boost::minstd_rand gen(1);
        if (num_edges(g) != 0)
        {
            for (std::size_t i = num_edges(g) - 1; i > 0; --i)
            {
                std::size_t scrambled = boost::uniform_int<>(0, i)(gen);
                if (scrambled == i)
                    continue;
                using std::swap;
                swap(sources[i], sources[scrambled]);
                swap(targets[i], targets[scrambled]);
            }
        }
        CSRGraphT g3a(boost::construct_inplace_from_sources_and_targets,
            sources, targets, num_vertices(g2));
        check_consistency(g3a);
        assert_graphs_equal(g2, boost::identity_property_map(), g3a,
            boost::identity_property_map(), boost::identity_property_map());
    }

    CSRGraphT::edge_iterator ei, ei_end;

    // Check edge_from_index (and implicitly the edge_index property map) for
    // each edge in g2
    std::size_t last_src = 0;
    for (boost::tie(ei, ei_end) = edges(g2); ei != ei_end; ++ei)
    {
        BOOST_TEST(
            edge_from_index(get(boost::edge_index, g2, *ei), g2) == *ei);
        std::size_t src = get(boost::vertex_index, g2, source(*ei, g2));
        (void)(std::size_t) get(boost::vertex_index, g2, target(*ei, g2));
        BOOST_TEST(src >= last_src);
        last_src = src;
    }

    // Check out edge iteration and vertex iteration for sortedness
    CSRGraphT::vertex_iterator vi, vi_end;
    std::size_t last_vertex = 0;
    bool first_iter = true;
    for (boost::tie(vi, vi_end) = vertices(g2); vi != vi_end; ++vi)
    {
        std::size_t v = get(boost::vertex_index, g2, *vi);
        BOOST_TEST(first_iter || v > last_vertex);
        last_vertex = v;
        first_iter = false;

        CSRGraphT::out_edge_iterator oei, oei_end;
        for (boost::tie(oei, oei_end) = out_edges(*vi, g2); oei != oei_end;
             ++oei)
        {
            BOOST_TEST(source(*oei, g2) == *vi);
        }

        // Find a vertex for testing
        CSRGraphT::vertex_descriptor test_vertex
            = vertex(num_vertices(g2) / 2, g2);
        int edge_count = 0;
        CSRGraphT::out_edge_iterator oei2, oei2_end;
        for (boost::tie(oei2, oei_end) = out_edges(*vi, g2); oei2 != oei_end;
             ++oei2)
        {
            if (target(*oei2, g2) == test_vertex)
                ++edge_count;
        }
    }

    // Run brandes_betweenness_centrality, which touches on a whole lot
    // of things, including VertexListGraph and IncidenceGraph
    using namespace boost;
    std::vector< double > vertex_centralities(num_vertices(g3));
    std::vector< double > edge_centralities(num_edges(g3));
    brandes_betweenness_centrality(g3,
        make_iterator_property_map(
            vertex_centralities.begin(), get(boost::vertex_index, g3)),
        make_iterator_property_map(
            edge_centralities.begin(), get(boost::edge_index, g3)));
    // Extra qualifications for aCC

    // Invert the edge centralities and use these as weights to
    // Kruskal's MST algorithm, which will test the EdgeListGraph
    // capabilities.
    double max_val = (std::numeric_limits< double >::max)();
    for (std::size_t i = 0; i < num_edges(g3); ++i)
        edge_centralities[i] = edge_centralities[i] == 0.0
            ? max_val
            : 1.0 / edge_centralities[i];

    typedef boost::graph_traits< CSRGraphT >::edge_descriptor edge_descriptor;
    std::vector< edge_descriptor > mst_edges;
    mst_edges.reserve(num_vertices(g3));
    kruskal_minimum_spanning_tree(g3, std::back_inserter(mst_edges),
        weight_map(make_iterator_property_map(
            edge_centralities.begin(), get(boost::edge_index, g3))));
}

void graph_test(int nnodes, double density, int seed)
{
    boost::minstd_rand gen(seed);
    std::cout << "Testing " << nnodes << " density " << density << std::endl;
    GraphT g(ERGen(gen, nnodes, density), ERGen(), nnodes);
    graph_test(g);
}

void test_graph_properties()
{
    using namespace boost;

    typedef compressed_sparse_row_graph< directedS, no_property, no_property,
        property< graph_name_t, std::string > >
        CSRGraphT;

    CSRGraphT g;
    BOOST_TEST(get_property(g, graph_name) == "");
    set_property(g, graph_name, "beep");
    BOOST_TEST(get_property(g, graph_name) == "beep");
}

struct Vertex
{
    double centrality;
};

struct Edge
{
    Edge(double weight) : weight(weight), centrality(0.0) {}

    double weight;
    double centrality;
};

void test_vertex_and_edge_properties()
{
    using namespace boost;
    typedef compressed_sparse_row_graph< directedS, Vertex, Edge >
        CSRGraphWithPropsT;

    typedef std::pair< int, int > E;
    E edges_init[6] = { E(0, 1), E(0, 3), E(1, 2), E(3, 1), E(3, 4), E(4, 2) };
    double weights[6] = { 1.0, 1.0, 0.5, 1.0, 1.0, 0.5 };
    double centrality[5] = { 0.0, 1.5, 0.0, 1.0, 0.5 };

    CSRGraphWithPropsT g(boost::edges_are_sorted, &edges_init[0],
        &edges_init[0] + 6, &weights[0], 5, 6);
    brandes_betweenness_centrality(g,
        centrality_map(get(&Vertex::centrality, g))
            .weight_map(get(&Edge::weight, g))
            .edge_centrality_map(get(&Edge::centrality, g)));

    BGL_FORALL_VERTICES(v, g, CSRGraphWithPropsT)
    BOOST_TEST(g[v].centrality == centrality[v]);
}

int main(int argc, char* argv[])
{
    // Optionally accept a seed value
    int seed = int(std::time(0));
    if (argc > 1)
        seed = boost::lexical_cast< int >(argv[1]);

    std::cout << "Seed = " << seed << std::endl;
    {
        std::cout << "Testing empty graph" << std::endl;
        CSRGraphT g;
        graph_test(g);
    }
    //  graph_test(1000, 0.05, seed);
    //  graph_test(1000, 0.0, seed);
    //  graph_test(1000, 0.1, seed);
    graph_test(1000, 0.001, seed);
    graph_test(1000, 0.0005, seed);

    test_graph_properties();
    test_vertex_and_edge_properties();

    {
        std::cout << "Testing CSR graph built from unsorted edges" << std::endl;
        std::pair< int, int > unsorted_edges[] = { std::make_pair(5, 0),
            std::make_pair(3, 2), std::make_pair(4, 1), std::make_pair(4, 0),
            std::make_pair(0, 2), std::make_pair(5, 2) };
        CSRGraphT g(boost::edges_are_unsorted, unsorted_edges,
            unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges),
            6);

        // Test vertex and edge bundle access
        boost::ignore_unused_variable_warning(
            (VertexData&)get(get(boost::vertex_bundle, g), vertex(0, g)));
        boost::ignore_unused_variable_warning((const VertexData&)get(
            get(boost::vertex_bundle, (const CSRGraphT&)g), vertex(0, g)));
        boost::ignore_unused_variable_warning(
            (VertexData&)get(boost::vertex_bundle, g, vertex(0, g)));
        boost::ignore_unused_variable_warning((const VertexData&)get(
            boost::vertex_bundle, (const CSRGraphT&)g, vertex(0, g)));
        put(boost::vertex_bundle, g, vertex(0, g), VertexData());
        boost::ignore_unused_variable_warning(
            (EdgeData&)get(get(boost::edge_bundle, g), *edges(g).first));
        boost::ignore_unused_variable_warning((const EdgeData&)get(
            get(boost::edge_bundle, (const CSRGraphT&)g), *edges(g).first));
        boost::ignore_unused_variable_warning(
            (EdgeData&)get(boost::edge_bundle, g, *edges(g).first));
        boost::ignore_unused_variable_warning((const EdgeData&)get(
            boost::edge_bundle, (const CSRGraphT&)g, *edges(g).first));
        put(boost::edge_bundle, g, *edges(g).first, EdgeData());

        CSRGraphT g2(boost::edges_are_unsorted_multi_pass, unsorted_edges,
            unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges),
            6);
        graph_test(g);
        graph_test(g2);
        assert_graphs_equal(g, boost::identity_property_map(), g2,
            boost::identity_property_map(), boost::identity_property_map());
        std::cout << "Testing bidir CSR graph built from unsorted edges"
                  << std::endl;
        BidirCSRGraphT g2b(boost::edges_are_unsorted_multi_pass, unsorted_edges,
            unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges),
            6);
        graph_test(g2b);
        assert_graphs_equal(g, boost::identity_property_map(), g2b,
            boost::identity_property_map(), boost::identity_property_map());
        // Check in edge access
        typedef boost::graph_traits< BidirCSRGraphT >::in_edge_iterator
            in_edge_iterator;
        std::pair< in_edge_iterator, in_edge_iterator > ie(
            in_edges(vertex(0, g2b), g2b));
        // quiet unused variable warning
        ie.first = ie.second;

        std::cout << "Testing CSR graph built using add_edges" << std::endl;
        // Test building a graph using add_edges on unsorted lists
        CSRGraphT g3(boost::edges_are_unsorted, unsorted_edges, unsorted_edges,
            6); // Empty range
        add_edges(unsorted_edges, unsorted_edges + 3, g3);
        EdgeData edge_data[3];
        add_edges(unsorted_edges + 3, unsorted_edges + 6, edge_data,
            edge_data + 3, g3);
        graph_test(g3);
        assert_graphs_equal(g, boost::identity_property_map(), g3,
            boost::identity_property_map(), boost::identity_property_map());
    }

    return boost::report_errors();
}