]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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/serialization/vector.hpp> | |
15 | #include <boost/graph/distributed/boman_et_al_graph_coloring.hpp> | |
16 | #include <boost/graph/distributed/mpi_process_group.hpp> | |
17 | #include <boost/lexical_cast.hpp> | |
18 | #include <boost/graph/parallel/distribution.hpp> | |
19 | #include <boost/graph/erdos_renyi_generator.hpp> | |
20 | #include <boost/graph/distributed/adjacency_list.hpp> | |
21 | #include <boost/graph/graphviz.hpp> | |
22 | #include <iostream> | |
23 | #include <boost/random.hpp> | |
1e59de90 | 24 | #include <boost/core/lightweight_test.hpp> |
7c673cae FG |
25 | |
26 | #ifdef BOOST_NO_EXCEPTIONS | |
27 | void | |
28 | boost::throw_exception(std::exception const& ex) | |
29 | { | |
30 | std::cout << ex.what() << std::endl; | |
31 | abort(); | |
32 | } | |
33 | #endif | |
34 | ||
35 | using namespace boost; | |
36 | using boost::graph::distributed::mpi_process_group; | |
37 | ||
38 | void | |
39 | test_distributed_graph_coloring(int n, double p, int s, | |
40 | int seed, bool emit_dot_file) | |
41 | { | |
42 | typedef adjacency_list<listS, | |
43 | distributedS<mpi_process_group, vecS>, | |
44 | undirectedS> Graph; | |
45 | ||
46 | typedef property_map<Graph, vertex_index_t>::type vertex_index_map; | |
47 | ||
48 | // Build a random number generator | |
49 | minstd_rand gen; | |
50 | gen.seed(seed); | |
51 | ||
52 | // Build a random graph | |
53 | Graph g(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, p), | |
54 | erdos_renyi_iterator<minstd_rand, Graph>(), | |
55 | n); | |
56 | ||
57 | // Set up color map | |
58 | std::vector<int> colors_vec(num_vertices(g)); | |
59 | iterator_property_map<int*, vertex_index_map> color(&colors_vec[0], | |
60 | get(vertex_index, g)); | |
61 | ||
62 | // Run the graph coloring algorithm | |
63 | graph::boman_et_al_graph_coloring(g, color, s); | |
64 | ||
65 | if (process_id(g.process_group()) == 0) { | |
66 | graph::distributed::boman_et_al_graph_coloring_stats.print(std::cout); | |
67 | } | |
68 | ||
69 | if ( emit_dot_file ) { | |
70 | if ( process_id(g.process_group()) == 0 ) { | |
71 | for (int i = 0; i < n; ++i) | |
72 | get(color, vertex(i, g)); | |
73 | synchronize(color); | |
74 | } else { | |
75 | synchronize(color); | |
76 | } | |
77 | ||
78 | write_graphviz("coloring.dot", g, paint_by_number(color)); | |
79 | } | |
80 | } | |
81 | ||
1e59de90 | 82 | int main(int argc, char* argv[]) |
7c673cae FG |
83 | { |
84 | mpi::environment env(argc, argv); | |
85 | ||
86 | int n = 1000; | |
87 | double p = 0.01; | |
88 | int s = 100; | |
89 | int seed = 1; | |
90 | bool emit_dot_file = false; | |
91 | ||
92 | if (argc > 1) n = lexical_cast<int>(argv[1]); | |
93 | if (argc > 2) p = lexical_cast<double>(argv[2]); | |
94 | if (argc > 3) s = lexical_cast<int>(argv[3]); | |
95 | if (argc > 4) seed = lexical_cast<int>(argv[4]); | |
96 | if (argc > 5) emit_dot_file = lexical_cast<bool>(argv[5]); | |
97 | ||
98 | test_distributed_graph_coloring(n, p, s, seed, emit_dot_file); | |
99 | ||
1e59de90 | 100 | return boost::report_errors(); |
7c673cae | 101 | } |