1 // Copyright (C) 2005-2008 The Trustees of Indiana University.
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)
7 // Authors: Douglas Gregor
9 #ifndef BOOST_GRAPH_DISTRIBUTED_BOMAN_ET_AL_GRAPH_COLORING_HPP
10 #define BOOST_GRAPH_DISTRIBUTED_BOMAN_ET_AL_GRAPH_COLORING_HPP
12 #ifndef BOOST_GRAPH_USE_MPI
13 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
16 #include <boost/graph/graph_traits.hpp>
17 #include <boost/graph/parallel/algorithm.hpp>
18 #include <boost/property_map/property_map.hpp>
19 #include <boost/graph/parallel/process_group.hpp>
23 #include <boost/graph/iteration_macros.hpp>
24 #include <boost/optional.hpp>
25 #include <boost/assert.hpp>
26 #include <boost/graph/parallel/container_traits.hpp>
27 #include <boost/graph/properties.hpp>
29 #ifdef PBGL_ACCOUNTING
30 # include <boost/graph/accounting.hpp>
31 #endif // PBGL_ACCOUNTING
33 namespace boost { namespace graph { namespace distributed {
35 /**************************************************************************
36 * This source file implements the distributed graph coloring algorithm *
37 * by Boman et al in: *
39 * Erik G. Boman, Doruk Bozdag, Umit Catalyurek, Assefaw H. Gebremedhin,*
40 * and Fredrik Manne. A Scalable Parallel Graph Coloring Algorithm for *
41 * Distributed Memory Computers. [unpublished preprint?] *
43 **************************************************************************/
45 #ifdef PBGL_ACCOUNTING
46 struct boman_et_al_graph_coloring_stats_t
48 /* The size of the blocks to step through (i.e., the parameter s). */
49 std::size_t block_size;
51 /* Total wall-clock time used by the algorithm.*/
52 accounting::time_type execution_time;
54 /* The number of conflicts that occurred during execution. */
55 std::size_t conflicts;
57 /* The number of supersteps. */
58 std::size_t supersteps;
60 /* The number of colors used. */
61 std::size_t num_colors;
63 template<typename OutputStream>
64 void print(OutputStream& out)
66 out << "Problem = \"Coloring\"\n"
67 << "Algorithm = \"Boman et al\"\n"
68 << "Function = boman_et_al_graph_coloring\n"
69 << "(P) Block size = " << block_size << "\n"
70 << "Wall clock time = " << accounting::print_time(execution_time)
71 << "\nConflicts = " << conflicts << "\n"
72 << "Supersteps = " << supersteps << "\n"
73 << "(R) Colors = " << num_colors << "\n";
77 static boman_et_al_graph_coloring_stats_t boman_et_al_graph_coloring_stats;
82 struct graph_coloring_reduce
84 BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);
86 template<typename Key>
87 T operator()(const Key&) const { return (std::numeric_limits<T>::max)(); }
89 template<typename Key> T operator()(const Key&, T, T y) const { return y; }
93 template<typename Color>
94 struct first_fit_color
97 Color operator()(const std::vector<T>& marked, T marked_true)
100 while (k < (Color)marked.size() && marked[k] == marked_true)
106 template<typename DistributedGraph, typename ColorMap, typename ChooseColor,
107 typename VertexOrdering, typename VertexIndexMap>
108 typename property_traits<ColorMap>::value_type
109 boman_et_al_graph_coloring
110 (const DistributedGraph& g,
112 typename graph_traits<DistributedGraph>::vertices_size_type s,
113 ChooseColor choose_color,
114 VertexOrdering ordering, VertexIndexMap vertex_index)
116 using namespace boost::graph::parallel;
117 using boost::parallel::all_reduce;
119 typename property_map<DistributedGraph, vertex_owner_t>::const_type
120 owner = get(vertex_owner, g);
122 typedef typename process_group_type<DistributedGraph>::type
124 typedef typename process_group_type::process_id_type process_id_type;
125 typedef typename graph_traits<DistributedGraph>::vertex_descriptor Vertex;
126 typedef typename graph_traits<DistributedGraph>::vertices_size_type
128 typedef typename property_traits<ColorMap>::value_type color_type;
129 typedef unsigned long long iterations_type;
130 typedef typename std::vector<Vertex>::iterator vertex_set_iterator;
131 typedef std::pair<Vertex, color_type> message_type;
133 #ifdef PBGL_ACCOUNTING
134 boman_et_al_graph_coloring_stats.block_size = s;
135 boman_et_al_graph_coloring_stats.execution_time = accounting::get_time();
136 boman_et_al_graph_coloring_stats.conflicts = 0;
137 boman_et_al_graph_coloring_stats.supersteps = 0;
140 // Initialize color map
141 color_type no_color = (std::numeric_limits<color_type>::max)();
142 BGL_FORALL_VERTICES_T(v, g, DistributedGraph)
143 put(color, v, no_color);
144 color.set_reduce(detail::graph_coloring_reduce<color_type>());
146 // Determine if we'll be using synchronous or asynchronous communication.
147 typedef typename process_group_type::communication_category
148 communication_category;
149 static const bool asynchronous =
150 is_convertible<communication_category, boost::parallel::immediate_process_group_tag>::value;
151 process_group_type pg = process_group(g);
154 std::vector<Vertex> vertices_to_color(vertices(g).first, vertices(g).second);
156 iterations_type iter_num = 1, outer_iter_num = 1;
157 std::vector<iterations_type> marked;
158 std::vector<iterations_type> marked_conflicting(num_vertices(g), 0);
159 std::vector<bool> sent_to_processors;
161 std::size_t rounds = vertices_to_color.size() / s
162 + (vertices_to_color.size() % s == 0? 0 : 1);
163 rounds = all_reduce(pg, rounds, boost::parallel::maximum<std::size_t>());
165 #ifdef PBGL_GRAPH_COLORING_DEBUG
166 std::cerr << "Number of rounds = " << rounds << std::endl;
170 if (!vertices_to_color.empty()) {
171 // Set of conflicting vertices
172 std::vector<Vertex> conflicting_vertices;
174 vertex_set_iterator first = vertices_to_color.begin();
175 while (first != vertices_to_color.end()) {
176 // For each subset of size s (or smaller for the last subset)
177 vertex_set_iterator start = first;
178 for (vertices_size_type counter = s;
179 first != vertices_to_color.end() && counter > 0;
180 ++first, --counter) {
181 // This vertex hasn't been sent to anyone yet
182 sent_to_processors.assign(num_processes(pg), false);
183 sent_to_processors[process_id(pg)] = true;
185 // Mark all of the colors that we see
186 BGL_FORALL_OUTEDGES_T(*first, e, g, DistributedGraph) {
187 color_type k = get(color, target(e, g));
189 if (k >= (color_type)marked.size()) marked.resize(k + 1, 0);
190 marked[k] = iter_num;
194 // Find a color for this vertex
195 put(color, *first, choose_color(marked, iter_num));
197 #ifdef PBGL_GRAPH_COLORING_DEBUG
198 std::cerr << "Chose color " << get(color, *first) << " for vertex "
199 << *first << std::endl;
202 // Send this vertex's color to the owner of the edge target.
203 BGL_FORALL_OUTEDGES_T(*first, e, g, DistributedGraph) {
204 if (!sent_to_processors[get(owner, target(e, g))]) {
205 send(pg, get(owner, target(e, g)), 17,
206 message_type(source(e, g), get(color, source(e, g))));
207 sent_to_processors[get(owner, target(e, g))] = true;
214 // Synchronize for non-immediate process groups.
220 // Receive boundary colors from other processors
221 while (optional<std::pair<process_id_type, int> > stp = probe(pg)) {
222 BOOST_ASSERT(stp->second == 17);
224 receive(pg, stp->first, stp->second, msg);
225 cache(color, msg.first, msg.second);
226 #ifdef PBGL_GRAPH_COLORING_DEBUG
227 std::cerr << "Cached color " << msg.second << " for vertex "
228 << msg.first << std::endl;
232 // Compute the set of conflicting vertices
233 // [start, first) contains all vertices in this subset
234 for (vertex_set_iterator vi = start; vi != first; ++vi) {
236 BGL_FORALL_OUTEDGES_T(v, e, g, DistributedGraph) {
237 Vertex w = target(e, g);
238 if (get(owner, w) != process_id(pg) // boundary vertex
239 && marked_conflicting[get(vertex_index, v)] != outer_iter_num
240 && get(color, v) == get(color, w)
242 conflicting_vertices.push_back(v);
243 marked_conflicting[get(vertex_index, v)] = outer_iter_num;
244 put(color, v, no_color);
245 #ifdef PBGL_GRAPH_COLORING_DEBUG
246 std::cerr << "Vertex " << v << " has a conflict with vertex "
254 #ifdef PBGL_ACCOUNTING
255 boman_et_al_graph_coloring_stats.conflicts +=
256 conflicting_vertices.size();
260 if (asynchronous) synchronize(pg);
267 conflicting_vertices.swap(vertices_to_color);
270 if (asynchronous) synchronize(pg);
279 // Receive boundary colors from other processors
280 while (optional<std::pair<process_id_type, int> > stp = probe(pg)) {
281 BOOST_ASSERT(stp->second == 17);
283 receive(pg, stp->first, stp->second, msg);
284 cache(color, msg.first, msg.second);
287 rounds = vertices_to_color.size() / s
288 + (vertices_to_color.size() % s == 0? 0 : 1);
289 rounds = all_reduce(pg, rounds, boost::parallel::maximum<std::size_t>());
291 #ifdef PBGL_ACCOUNTING
292 ++boman_et_al_graph_coloring_stats.supersteps;
296 // Determine the number of colors used.
297 color_type num_colors = 0;
298 BGL_FORALL_VERTICES_T(v, g, DistributedGraph) {
299 color_type k = get(color, v);
300 BOOST_ASSERT(k != no_color);
302 if (k >= (color_type)marked.size()) marked.resize(k + 1, 0); // TBD: perf?
303 if (marked[k] != iter_num) {
304 marked[k] = iter_num;
311 all_reduce(pg, num_colors, boost::parallel::maximum<color_type>());
314 #ifdef PBGL_ACCOUNTING
315 boman_et_al_graph_coloring_stats.execution_time =
316 accounting::get_time() - boman_et_al_graph_coloring_stats.execution_time;
318 boman_et_al_graph_coloring_stats.conflicts =
319 all_reduce(pg, boman_et_al_graph_coloring_stats.conflicts,
320 std::plus<color_type>());
321 boman_et_al_graph_coloring_stats.num_colors = num_colors;
328 template<typename DistributedGraph, typename ColorMap, typename ChooseColor,
329 typename VertexOrdering>
330 inline typename property_traits<ColorMap>::value_type
331 boman_et_al_graph_coloring
332 (const DistributedGraph& g, ColorMap color,
333 typename graph_traits<DistributedGraph>::vertices_size_type s,
334 ChooseColor choose_color, VertexOrdering ordering)
336 return boman_et_al_graph_coloring(g, color, s, choose_color, ordering,
337 get(vertex_index, g));
340 template<typename DistributedGraph, typename ColorMap, typename ChooseColor>
341 inline typename property_traits<ColorMap>::value_type
342 boman_et_al_graph_coloring
343 (const DistributedGraph& g,
345 typename graph_traits<DistributedGraph>::vertices_size_type s,
346 ChooseColor choose_color)
348 typedef typename graph_traits<DistributedGraph>::vertex_descriptor
350 return boman_et_al_graph_coloring(g, color, s, choose_color,
351 std::less<vertex_descriptor>());
354 template<typename DistributedGraph, typename ColorMap>
355 inline typename property_traits<ColorMap>::value_type
356 boman_et_al_graph_coloring
357 (const DistributedGraph& g,
359 typename graph_traits<DistributedGraph>::vertices_size_type s = 100)
361 typedef typename property_traits<ColorMap>::value_type Color;
362 return boman_et_al_graph_coloring(g, color, s, first_fit_color<Color>());
365 } } } // end namespace boost::graph::distributed
367 namespace boost { namespace graph {
368 using distributed::boman_et_al_graph_coloring;
369 } } // end namespace boost::graph
371 #endif // BOOST_GRAPH_DISTRIBUTED_BOMAN_ET_AL_GRAPH_COLORING_HPP