1 // Copyright (C) 2004-2008 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: Nick Edmonds
8 // Douglas Gregor
9 // Andrew Lumsdaine
10
11 // SCC won't work with CSR currently due to the way the reverse graph
12 // is constructed in the SCC algorithm
13
14 #include <boost/graph/use_mpi.hpp>
15
16 // #define CSR
17
18 #ifdef CSR
19 # include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
20 #else
21 # include <boost/graph/distributed/adjacency_list.hpp>
22 #endif
23
24 #include <boost/config.hpp>
25 #include <boost/throw_exception.hpp>
26 #include <boost/graph/strong_components.hpp>
27 #include <boost/graph/random.hpp>
28 #include <boost/property_map/parallel/distributed_property_map.hpp>
29 #include <boost/graph/distributed/mpi_process_group.hpp>
30 #include <boost/graph/parallel/distribution.hpp>
31 #include <boost/graph/erdos_renyi_generator.hpp>
32 #include <boost/test/minimal.hpp>
33 #include <boost/graph/distributed/graphviz.hpp>
34 #include <iostream>
35 #include <cstdlib>
36 #include <iomanip>
37 #include <boost/random.hpp>
38 #include <boost/test/minimal.hpp>
39
40 #ifdef BOOST_NO_EXCEPTIONS
41 void
throw_exception(std::exception const & ex)42 boost::throw_exception(std::exception const& ex)
43 {
44 std::cout << ex.what() << std::endl;
45 abort();
46 }
47 #endif
48
49 typedef double time_type;
50
get_time()51 inline time_type get_time()
52 {
53 return MPI_Wtime();
54 }
55
print_time(time_type t)56 std::string print_time(time_type t)
57 {
58 std::ostringstream out;
59 out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
60 return out.str();
61 }
62
63 using namespace boost;
64 using boost::graph::distributed::mpi_process_group;
65
66 void
test_distributed_strong_components(int n,double _p,bool verify,bool emit_dot_file,int seed)67 test_distributed_strong_components(int n, double _p, bool verify, bool emit_dot_file, int seed)
68 {
69 #ifdef CSR
70 typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property,
71 distributedS<mpi_process_group> > Graph;
72 #else
73 typedef adjacency_list<listS,
74 distributedS<mpi_process_group, vecS>,
75 bidirectionalS > Graph;
76 #endif
77
78 minstd_rand gen;
79
80 gen.seed(seed);
81
82 mpi_process_group pg;
83 parallel::variant_distribution<mpi_process_group> distrib
84 = parallel::block(pg, n);
85
86 #ifdef CSR
87 Graph g(sorted_erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2),
88 sorted_erdos_renyi_iterator<minstd_rand, Graph>(),
89 n, pg, distrib);
90 #else
91 Graph g(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2),
92 erdos_renyi_iterator<minstd_rand, Graph>(),
93 n, pg, distrib);
94 #endif
95
96 synchronize(g);
97
98 std::vector<int> local_components_vec(num_vertices(g));
99 typedef iterator_property_map<std::vector<int>::iterator, property_map<Graph, vertex_index_t>::type> ComponentMap;
100 ComponentMap component(local_components_vec.begin(), get(vertex_index, g));
101
102 int num_components = 0;
103
104 time_type start = get_time();
105 num_components = strong_components(g, component);
106 time_type end = get_time();
107 if (process_id(g.process_group()) == 0)
108 std::cerr << "Erdos-Reyni graph:\n" << n << " Vertices " << _p << " Edge probability "
109 << num_processes(pg) << " Processors\n"
110 << "Strong Components time = " << print_time(end - start) << " seconds.\n"
111 << num_components << " components identified\n";
112
113
114 if ( verify )
115 {
116 if ( process_id(g.process_group()) == 0 )
117 {
118 for (int i = 0; i < n; ++i)
119 get(component, vertex(i, g));
120 synchronize(component);
121
122 // Check against the sequential version
123 typedef adjacency_list<listS, vecS, directedS> Graph2;
124
125 gen.seed(seed);
126
127 Graph2 g2(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2),
128 erdos_renyi_iterator<minstd_rand, Graph>(),
129 n);
130
131 std::vector<int> component2(n);
132 int seq_num_components = strong_components(g2, make_iterator_property_map(component2.begin(), get(vertex_index, g2)));
133
134 assert(num_components == seq_num_components);
135
136 // Make sure components and component2 match
137 std::map<int, int> c2c;
138 int i;
139 for ( i = 0; i < n; i++ )
140 if ( c2c.find( get(component, vertex(i, g)) ) == c2c.end() )
141 c2c[get(component, vertex(i, g))] = component2[i];
142 else
143 if ( c2c[get(component, vertex(i, g))] != component2[i] )
144 break;
145
146 if ( i < n )
147 std::cerr << "Unable to verify SCC result...\n";
148 else
149 std::cerr << "Passed verification... " << seq_num_components << " strong components\n";
150 }
151 else
152 {
153 synchronize(component);
154 }
155 if ( emit_dot_file )
156 write_graphviz("scc.dot", g, paint_by_number(component));
157 }
158 }
159
test_main(int argc,char * argv[])160 int test_main(int argc, char* argv[])
161 {
162 mpi::environment env(argc, argv);
163
164 if (argc == 1)
165 test_distributed_strong_components(10000, 0.0005, true, false, 1);
166 else if ( argc < 5 )
167 std::cerr << "usage: test_distributed_strong_components <int num_vertices> <double p> <bool verify?> <bool emit_dotfile?> [seed]\n";
168 else
169 test_distributed_strong_components
170 (atoi(argv[1]), atof(argv[2]),
171 argv[3]==std::string("true"), argv[4]==std::string("true"),
172 argc == 5? 1 : atoi(argv[5]));
173
174 return 0;
175 }
176