boost_1_45_0/libs/graph_parallel/test/distributed_graph_coloring_test.cpp

// Copyright (C) 2005, 2006 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
#define PBGL_ACCOUNTING

#include <boost/graph/use_mpi.hpp>
#include <boost/config.hpp>
#include <boost/throw_exception.hpp>
#include <boost/graph/distributed/boman_et_al_graph_coloring.hpp>
#include <boost/graph/distributed/mpi_process_group.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/graph/parallel/distribution.hpp>
#include <boost/graph/erdos_renyi_generator.hpp>
#include <boost/graph/distributed/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <iostream>
#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

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

void 
test_distributed_graph_coloring(int n, double p, int s,
                                int seed, bool emit_dot_file)
{
  typedef adjacency_list<listS, 
                         distributedS<mpi_process_group, vecS>,
                         undirectedS> Graph;

  typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
  typedef graph_traits<Graph>::vertex_iterator vertex_iterator;
  typedef property_map<Graph, vertex_index_t>::type vertex_index_map;

  // Build a random number generator
  minstd_rand gen;
  gen.seed(seed);

  // Build a random graph
  Graph g(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, p),
          erdos_renyi_iterator<minstd_rand, Graph>(),
          n);

  // Set up color map
  std::vector<int> colors_vec(num_vertices(g));
  iterator_property_map<int*, vertex_index_map> color(&colors_vec[0],
                                                      get(vertex_index, g));

  // Run the graph coloring algorithm
  graph::boman_et_al_graph_coloring(g, color, s);

  if (process_id(g.process_group()) == 0) {
    graph::distributed::boman_et_al_graph_coloring_stats.print(std::cout);
  }

  if ( emit_dot_file ) {
    if ( process_id(g.process_group()) == 0 ) {
      for (int i = 0; i < n; ++i)
        get(color, vertex(i, g));
      synchronize(color);
    } else {
      synchronize(color);
    }
    
    write_graphviz("coloring.dot", g, paint_by_number(color));
  }
}

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

  int n = 1000;
  double p = 0.01;
  int s = 100;
  int seed = 1;
  bool emit_dot_file = false;

  if (argc > 1) n             = lexical_cast<int>(argv[1]);
  if (argc > 2) p             = lexical_cast<double>(argv[2]);
  if (argc > 3) s             = lexical_cast<int>(argv[3]);
  if (argc > 4) seed          = lexical_cast<int>(argv[4]);
  if (argc > 5) emit_dot_file = lexical_cast<bool>(argv[5]);

  test_distributed_graph_coloring(n, p, s, seed, emit_dot_file);

  return 0;
}