1 // Copyright (C) 2004-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
10 #include <boost/graph/use_mpi.hpp>
11 #include <boost/config.hpp>
12 #include <boost/throw_exception.hpp>
13 #include <boost/serialization/vector.hpp>
14 #include <boost/graph/distributed/adjacency_list.hpp>
15 #include <boost/graph/connected_components.hpp>
16 #include <boost/graph/distributed/connected_components_parallel_search.hpp>
17 #include <boost/graph/random.hpp>
18 #include <boost/property_map/parallel/distributed_property_map.hpp>
19 #include <boost/graph/distributed/mpi_process_group.hpp>
20 #include <boost/graph/parallel/distribution.hpp>
21 #include <boost/graph/erdos_renyi_generator.hpp>
22 #include <boost/graph/distributed/graphviz.hpp>
23 #include <iostream>
24 #include <cstdlib>
25 #include <iomanip>
26 #include <boost/random.hpp>
27 #include <boost/test/minimal.hpp>
28
29 #include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
30 #include <boost/graph/rmat_graph_generator.hpp>
31
32 #ifdef BOOST_NO_EXCEPTIONS
33 void
throw_exception(std::exception const & ex)34 boost::throw_exception(std::exception const& ex)
35 {
36 std::cout << ex.what() << std::endl;
37 abort();
38 }
39 #endif
40
41 using namespace boost;
42 using boost::graph::distributed::mpi_process_group;
43
44 typedef double time_type;
45
get_time()46 inline time_type get_time()
47 {
48 return MPI_Wtime();
49 }
50
print_time(time_type t)51 std::string print_time(time_type t)
52 {
53 std::ostringstream out;
54 out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
55 return out.str();
56 }
57
58 template<typename T>
59 class map_lt
60 {
61 public:
operator ()() const62 bool operator()() const { return false; }
operator ()(T x,T y) const63 bool operator()(T x, T y) const { return (owner(x) < owner(y) || (owner(x) == owner(y) && local(x) < local(y))); }
64 };
65
66 void
test_distributed_connected_components(int n,double _p,bool verify,bool emit_dot_file,int seed,bool parallel_search)67 test_distributed_connected_components(int n, double _p, bool verify, bool emit_dot_file, int seed, bool parallel_search)
68 {
69 // typedef adjacency_list<listS,
70 // distributedS<mpi_process_group, vecS>,
71 // undirectedS> Graph;
72
73 typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property,
74 distributedS<mpi_process_group> > Graph;
75
76 minstd_rand gen;
77
78 gen.seed(seed);
79
80 mpi_process_group pg;
81 parallel::variant_distribution<mpi_process_group> distrib
82 = parallel::block(pg, n);
83
84 minstd_rand dist_gen;
85 #if 0
86 if (false) {
87 distrib = parallel::random_distribution(pg, dist_gen, n);
88 } else if (true) {
89 distrib = parallel::oned_block_cyclic(pg, 13);
90 }
91 #endif
92
93 // Graph g(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2),
94 // erdos_renyi_iterator<minstd_rand, Graph>(),
95 // n, pg, distrib);
96
97 int m = int(n * n * _p/2);
98 double a = 0.57, b = 0.19, c = 0.19, d = 0.05;
99
100 // Last boolean parameter makes R-MAT bidirectional
101 Graph g(sorted_unique_rmat_iterator<minstd_rand, Graph>(gen, n, m, a, b, c, d, true),
102 sorted_unique_rmat_iterator<minstd_rand, Graph>(),
103 n, pg, distrib);
104
105 synchronize(g);
106
107 std::vector<int> local_components_vec(num_vertices(g));
108 typedef iterator_property_map<std::vector<int>::iterator, property_map<Graph, vertex_index_t>::type> ComponentMap;
109 ComponentMap component(local_components_vec.begin(), get(vertex_index, g));
110
111 int num_components = 0;
112
113 time_type start = get_time();
114 if (parallel_search) {
115 num_components = connected_components_ps(g, component);
116 } else {
117 num_components = connected_components(g, component);
118 }
119 time_type end = get_time();
120 if (process_id(g.process_group()) == 0)
121 std::cerr << "Connected Components time = " << print_time(end - start) << " seconds.\n"
122 << num_components << " components identified\n";
123
124 if ( verify )
125 {
126 if ( process_id(g.process_group()) == 0 )
127 {
128 component.set_max_ghost_cells(0);
129 for (int i = 0; i < n; ++i)
130 get(component, vertex(i, g));
131 synchronize(component);
132
133 // Check against the sequential version
134 typedef adjacency_list<listS,
135 vecS,
136 undirectedS,
137 // Vertex properties
138 no_property,
139 // Edge properties
140 no_property > Graph2;
141
142 gen.seed(seed);
143
144 // Graph2 g2(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2),
145 // erdos_renyi_iterator<minstd_rand, Graph>(),
146 // n);
147
148 Graph2 g2( sorted_unique_rmat_iterator<minstd_rand, Graph>(gen, n, m, a, b, c, d, true),
149 sorted_unique_rmat_iterator<minstd_rand, Graph>(),
150 n);
151
152 std::vector<int> component2 (n);
153 int tmp;
154 tmp = connected_components(g2, make_iterator_property_map(component2.begin(), get(vertex_index, g2)));
155 std::cerr << "Verifier found " << tmp << " components" << std::endl;
156
157 // Make sure components and component2 match
158 std::map<int, int> c2c;
159 int i;
160 // This fails if there are more components in 'component' than
161 // 'component2' because multiple components in 'component' may
162 // legitimately map to the same component number in 'component2'.
163 // We can either test the mapping in the opposite direction or
164 // just assert that the numbers of components found by both
165 // algorithms is the same
166 for ( i = 0; i < n; i++ )
167 if ( c2c.find( get(component, vertex(i, g)) ) == c2c.end() )
168 c2c[get(component, vertex(i, g))] = component2[i];
169 else
170 if ( c2c[get(component, vertex(i, g))] != component2[i] )
171 break;
172
173 if ( i < n || num_components != tmp) {
174 printf("Unable to verify CC result...\n");
175 } else
176 printf("Passed verification... %i connected components\n",
177 (int)c2c.size());
178 }
179 else
180 {
181 synchronize(component);
182 }
183 if ( emit_dot_file )
184 write_graphviz("cc.dot", g, paint_by_number(component));
185 }
186 }
187
test_main(int argc,char * argv[])188 int test_main(int argc, char* argv[])
189 {
190 mpi::environment env(argc, argv);
191
192 if ( argc < 6 ) {
193 test_distributed_connected_components(10000, 0.001, true, false, 1, false);
194 test_distributed_connected_components(10000, 0.001, true, false, 1, true);
195 }
196 else
197 test_distributed_connected_components
198 (atoi(argv[1]), atof(argv[2]),
199 argv[3]==std::string("true"), argv[4]==std::string("true"),
200 argc == 6? 1 : atoi(argv[6]),
201 argv[5]==std::string("true"));
202
203 return 0;
204 }
205