boost_1_45_0/libs/graph_parallel/test/distributed_strong_components_test.cpp

// Copyright (C) 2004-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: Nick Edmonds
//           Douglas Gregor
//           Andrew Lumsdaine

// SCC won't work with CSR currently due to the way the reverse graph 
// is constructed in the SCC algorithm

#include <boost/graph/use_mpi.hpp>

// #define CSR

#ifdef CSR
#  include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
#else
#  include <boost/graph/distributed/adjacency_list.hpp>
#endif

#include <boost/config.hpp>
#include <boost/throw_exception.hpp>
#include <boost/graph/strong_components.hpp>
#include <boost/graph/random.hpp>
#include <boost/property_map/parallel/distributed_property_map.hpp>
#include <boost/graph/distributed/mpi_process_group.hpp>
#include <boost/graph/parallel/distribution.hpp>
#include <boost/graph/erdos_renyi_generator.hpp>
#include <boost/test/minimal.hpp>
#include <boost/graph/distributed/graphviz.hpp>
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <boost/random.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

typedef double time_type;

inline time_type get_time()
{
  return MPI_Wtime();
}

std::string print_time(time_type t)
{
  std::ostringstream out;
  out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
  return out.str();
}

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

void 
test_distributed_strong_components(int n, double _p, bool verify, bool emit_dot_file, int seed)
{
#ifdef CSR
  typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property,
    distributedS<mpi_process_group> > Graph;
#else
  typedef adjacency_list<listS, 
                         distributedS<mpi_process_group, vecS>,
                         bidirectionalS > Graph;
#endif

  typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
  typedef graph_traits<Graph>::vertex_iterator vertex_iterator;
  typedef iterator_property_map<std::vector<vertex_descriptor>::iterator, property_map<Graph, vertex_index_t>::type> ParentMap;
  typedef std::pair<int, int> Edge;

  minstd_rand gen;

  gen.seed(seed);

  mpi_process_group pg;
  parallel::variant_distribution<mpi_process_group> distrib 
    = parallel::block(pg, n);

#ifdef CSR
  Graph g(sorted_erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2),
          sorted_erdos_renyi_iterator<minstd_rand, Graph>(),
          n, pg, distrib);
#else
  Graph g(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2),
          erdos_renyi_iterator<minstd_rand, Graph>(),
          n, pg, distrib);
#endif

  synchronize(g);

  std::vector<int> local_components_vec(num_vertices(g));
  typedef iterator_property_map<std::vector<int>::iterator, property_map<Graph, vertex_index_t>::type> ComponentMap;
  ComponentMap component(local_components_vec.begin(), get(vertex_index, g));

  int num_components = 0;

  time_type start = get_time();
  num_components = strong_components(g, component);
  time_type end = get_time();
  if (process_id(g.process_group()) == 0)
    std::cerr << "Erdos-Reyni graph:\n" << n << " Vertices   " << _p << " Edge probability  " 
              << num_processes(pg) << " Processors\n"
              << "Strong Components time = " << print_time(end - start) << " seconds.\n"
              << num_components << " components identified\n";
  

  if ( verify )
    {
      if ( process_id(g.process_group()) == 0 )
        {
          for (int i = 0; i < n; ++i)
            get(component, vertex(i, g));
          synchronize(component);

          // Check against the sequential version
          typedef adjacency_list<listS, vecS, directedS> Graph2;
          
          gen.seed(seed);
          
          Graph2 g2(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2),
                    erdos_renyi_iterator<minstd_rand, Graph>(),
                    n);

          std::vector<int> component2(n);
          int seq_num_components = strong_components(g2, make_iterator_property_map(component2.begin(), get(vertex_index, g2)));

          assert(num_components == seq_num_components);

          // Make sure components and component2 match
          std::map<int, int> c2c;
          int i;
          for ( i = 0; i < n; i++ )
            if ( c2c.find( get(component, vertex(i, g)) ) == c2c.end() )
              c2c[get(component, vertex(i, g))] = component2[i];
            else
              if ( c2c[get(component, vertex(i, g))] != component2[i] )
                break;
          
          if ( i < n )
            std::cerr << "Unable to verify SCC result...\n";
          else
            std::cerr << "Passed verification... " << seq_num_components << " strong components\n"; 
        }
      else 
        {
          synchronize(component);
        }
      if ( emit_dot_file )
        write_graphviz("scc.dot", g, paint_by_number(component));
    }
}

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

  if (argc == 1)
    test_distributed_strong_components(10000, 0.0005, true, false, 1);
  else if ( argc < 5 )
    std::cerr << "usage: test_distributed_strong_components <int num_vertices> <double p> <bool verify?> <bool emit_dotfile?> [seed]\n";
  else
    test_distributed_strong_components
      (atoi(argv[1]), atof(argv[2]), 
       argv[3]==std::string("true"), argv[4]==std::string("true"),
       argc == 5? 1 : atoi(argv[5]));

  return 0;
}