graph_parallel/test/hohberg_biconnected_components_test.cpp

// Copyright (C) 2005-2008 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: Douglas Gregor
//           Andrew Lumsdaine
//
// Test of Hohberg's distributed biconnected components algorithm.
#include <boost/graph/use_mpi.hpp>
#include <boost/config.hpp>
#include <boost/throw_exception.hpp>
#include <boost/graph/distributed/hohberg_biconnected_components.hpp>
#include <boost/graph/distributed/mpi_process_group.hpp>
#include <boost/graph/distributed/adjacency_list.hpp>
#include <boost/test/minimal.hpp>

#ifdef BOOST_NO_EXCEPTIONS
void
boost::throw_exception(std::exception const& ex)
{
    std::cout << ex.what() << std::endl;
    abort();
}
#endif

using boost::graph::distributed::mpi_process_group;

using namespace boost;

template<typename Graph>
void check_components(const Graph& g, std::size_t num_comps)
{
  std::size_t not_mapped = (std::numeric_limits<std::size_t>::max)();
  std::vector<std::size_t> color_to_name(num_comps, not_mapped);
  BGL_FORALL_EDGES_T(e, g, Graph) {
    BOOST_CHECK(get(edge_color, g, e) < num_comps);
    if (color_to_name[get(edge_color, g, e)] == not_mapped)
      color_to_name[get(edge_color, g, e)] = get(edge_name, g, e);
    BOOST_CHECK(color_to_name[get(edge_color,g,e)] == get(edge_name,g,e));

    if (color_to_name[get(edge_color,g,e)] != get(edge_name,g,e)) {
      for (std::size_t i = 0; i < color_to_name.size(); ++i)
        std::cerr << color_to_name[i] << ' ';

      std::cerr << std::endl;

      std::cerr << color_to_name[get(edge_color,g,e)] << " != "
                << get(edge_name,g,e) << " on edge "
                << local(source(e, g)) << " -> " << local(target(e, g))
                << std::endl;
    }
  }
}

template<typename Graph>
void
test_small_hohberg_biconnected_components(Graph& g, int n, int comps_expected,
                                          bool single_component = true)
{
  using boost::graph::distributed::hohberg_biconnected_components;

  bool is_root = (process_id(process_group(g)) == 0);

  if (single_component) {
    for (int i = 0; i < n; ++i) {
      if (is_root) std::cerr << "Testing with leader = " << i << std::endl;

      // Scramble edge_color_map
      BGL_FORALL_EDGES_T(e, g, Graph)
        put(edge_color, g, e, 17);

      typename graph_traits<Graph>::vertex_descriptor leader = vertex(i, g);
      int num_comps =
        hohberg_biconnected_components(g, get(edge_color, g), &leader,
                                       &leader + 1);

      BOOST_CHECK(num_comps == comps_expected);
      check_components(g, num_comps);
    }
  }

  if (is_root) std::cerr << "Testing simple interface." << std::endl;
  synchronize(g);

  // Scramble edge_color_map
  int i = 0;
  BGL_FORALL_EDGES_T(e, g, Graph) {
    ++i;
    put(edge_color, g, e, 17);
  }
  std::cerr << process_id(process_group(g)) << " has "
            << i << " edges.\n";

  int num_comps = hohberg_biconnected_components(g, get(edge_color, g));

  BOOST_CHECK(num_comps == comps_expected);
  check_components(g, num_comps);
}

int test_main(int argc, char* argv[])
{
  mpi::environment env(argc, argv);

  typedef adjacency_list<listS,
                         distributedS<mpi_process_group, vecS>,
                         undirectedS,
                         // Vertex properties
                         no_property,
                         // Edge properties
                         property<edge_name_t, std::size_t,
                         property<edge_color_t, std::size_t> > > Graph;

  typedef std::pair<int, int> E;

  {
    // Example 1: A single component with 2 bicomponents
    E edges_init[] = { E(0, 1), E(0, 2), E(1, 3), E(2, 4), E(3, 4), E(4, 5),
                       E(4, 6), E(5, 6) };
    const int m = sizeof(edges_init) / sizeof(E);
    std::size_t expected_components[m] = { 0, 0, 0, 0, 0, 1, 1, 1 };
    const int n = 7;
    Graph g(&edges_init[0], &edges_init[0] + m, &expected_components[0], n);

    int num_comps_expected =
      *std::max_element(&expected_components[0], &expected_components[0] + m)
      + 1;

    test_small_hohberg_biconnected_components(g, n, num_comps_expected);
  }

  {
    // Example 2: A single component with 4 bicomponents
    E edges_init[] = { E(0, 1), E(1, 2), E(2, 0), E(2, 3), E(3, 4), E(4, 5),
                       E(5, 2), E(3, 6), E(6, 7), E(7, 8), E(8, 6) };
    const int m = sizeof(edges_init) / sizeof(E);
    std::size_t expected_components[m] = { 0, 0, 0, 1, 1, 1, 1, 2, 3, 3, 3 };
    const int n = 9;
    Graph g(&edges_init[0], &edges_init[0] + m, &expected_components[0], n);

    int num_comps_expected =
      *std::max_element(&expected_components[0], &expected_components[0] + m)
      + 1;

    test_small_hohberg_biconnected_components(g, n, num_comps_expected);
  }

  {
    // Example 3: Two components, 6 bicomponents
    // This is just the concatenation of the two previous graphs.
    E edges_init[] = { /* Example 1 graph */
                       E(0, 1), E(0, 2), E(1, 3), E(2, 4), E(3, 4), E(4, 5),
                       E(4, 6), E(5, 6),
                       /* Example 2 graph */
                       E(7, 8), E(8, 9), E(9, 7), E(9, 10), E(10, 11),
                       E(11, 12), E(12, 9), E(10, 13), E(13, 14), E(14, 15),
                       E(15, 13) };
    const int m = sizeof(edges_init) / sizeof(E);
    std::size_t expected_components[m] =
      { /* Example 1 */0, 0, 0, 0, 0, 1, 1, 1,
        /* Example 2 */2, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5 };
    const int n = 16;
    Graph g(&edges_init[0], &edges_init[0] + m, &expected_components[0], n);

    int num_comps_expected =
      *std::max_element(&expected_components[0], &expected_components[0] + m)
      + 1;

    test_small_hohberg_biconnected_components(g, n, num_comps_expected,
                                              false);
  }

  return 0;
}