libs/graph_parallel/test/distributed_graph_coloring_test.cpp

   1 // Copyright (C) 2005, 2006 The Trustees of Indiana University.
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Authors: Douglas Gregor
   8 //           Andrew Lumsdaine
   9 #define PBGL_ACCOUNTING
  10
  11 #include <boost/graph/use_mpi.hpp>
  12 #include <boost/config.hpp>
  13 #include <boost/throw_exception.hpp>
  14 #include <boost/graph/distributed/boman_et_al_graph_coloring.hpp>
  15 #include <boost/graph/distributed/mpi_process_group.hpp>
  16 #include <boost/lexical_cast.hpp>
  17 #include <boost/graph/parallel/distribution.hpp>
  18 #include <boost/graph/erdos_renyi_generator.hpp>
  19 #include <boost/graph/distributed/adjacency_list.hpp>
  20 #include <boost/graph/graphviz.hpp>
  21 #include <iostream>
  22 #include <boost/random.hpp>
  23 #include <boost/test/minimal.hpp>
  24
  25 #ifdef BOOST_NO_EXCEPTIONS
  26 void
  27 boost::throw_exception(std::exception const& ex)
  28 {
  29     std::cout << ex.what() << std::endl;
  30     abort();
  31 }
  32 #endif
  33
  34 using namespace boost;
  35 using boost::graph::distributed::mpi_process_group;
  36
  37 void
  38 test_distributed_graph_coloring(int n, double p, int s,
  39                                 int seed, bool emit_dot_file)
  40 {
  41   typedef adjacency_list<listS,
  42                          distributedS<mpi_process_group, vecS>,
  43                          undirectedS> Graph;
  44
  45   typedef property_map<Graph, vertex_index_t>::type vertex_index_map;
  46
  47   // Build a random number generator
  48   minstd_rand gen;
  49   gen.seed(seed);
  50
  51   // Build a random graph
  52   Graph g(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, p),
  53           erdos_renyi_iterator<minstd_rand, Graph>(),
  54           n);
  55
  56   // Set up color map
  57   std::vector<int> colors_vec(num_vertices(g));
  58   iterator_property_map<int*, vertex_index_map> color(&colors_vec[0],
  59                                                       get(vertex_index, g));
  60
  61   // Run the graph coloring algorithm
  62   graph::boman_et_al_graph_coloring(g, color, s);
  63
  64   if (process_id(g.process_group()) == 0) {
  65     graph::distributed::boman_et_al_graph_coloring_stats.print(std::cout);
  66   }
  67
  68   if ( emit_dot_file ) {
  69     if ( process_id(g.process_group()) == 0 ) {
  70       for (int i = 0; i < n; ++i)
  71         get(color, vertex(i, g));
  72       synchronize(color);
  73     } else {
  74       synchronize(color);
  75     }
  76
  77     write_graphviz("coloring.dot", g, paint_by_number(color));
  78   }
  79 }
  80
  81 int test_main(int argc, char* argv[])
  82 {
  83   mpi::environment env(argc, argv);
  84
  85   int n = 1000;
  86   double p = 0.01;
  87   int s = 100;
  88   int seed = 1;
  89   bool emit_dot_file = false;
  90
  91   if (argc > 1) n             = lexical_cast<int>(argv[1]);
  92   if (argc > 2) p             = lexical_cast<double>(argv[2]);
  93   if (argc > 3) s             = lexical_cast<int>(argv[3]);
  94   if (argc > 4) seed          = lexical_cast<int>(argv[4]);
  95   if (argc > 5) emit_dot_file = lexical_cast<bool>(argv[5]);
  96
  97   test_distributed_graph_coloring(n, p, s, seed, emit_dot_file);
  98
  99   return 0;
 100 }