17 #ifndef dealii_graph_coloring_h 18 # define dealii_graph_coloring_h 21 # include <deal.II/base/config.h> 23 # include <deal.II/base/thread_management.h> 25 # include <deal.II/lac/sparsity_tools.h> 27 # include <boost/unordered_map.hpp> 28 # include <boost/unordered_set.hpp> 30 # include <functional> 35 DEAL_II_NAMESPACE_OPEN
54 have_nonempty_intersection(
55 const std::vector<types::global_dof_index> &indices1,
56 const std::vector<types::global_dof_index> &indices2)
62 std::vector<types::global_dof_index>::const_iterator p = indices1.begin(),
64 while ((p != indices1.end()) && (q != indices2.end()))
110 template <
typename Iterator>
111 std::vector<std::vector<Iterator>>
113 const Iterator & begin,
114 const typename identity<Iterator>::type &end,
115 const std::function<std::vector<types::global_dof_index>(
116 const Iterator &)> & get_conflict_indices)
119 unsigned int n_iterators = 0;
122 boost::unordered_map<types::global_dof_index, std::vector<Iterator>>
123 indices_to_iterators;
124 for (Iterator it = begin; it != end; ++it)
126 const std::vector<types::global_dof_index> conflict_indices =
127 get_conflict_indices(it);
128 const unsigned int n_conflict_indices = conflict_indices.size();
129 for (
unsigned int i = 0; i < n_conflict_indices; ++i)
130 indices_to_iterators[conflict_indices[i]].push_back(it);
137 std::vector<std::vector<Iterator>> zones(1,
138 std::vector<Iterator>(1, begin));
139 std::set<Iterator> used_it;
140 used_it.insert(begin);
141 while (used_it.size() != n_iterators)
146 typename std::vector<Iterator>::iterator previous_zone_it(
147 zones.back().begin());
148 typename std::vector<Iterator>::iterator previous_zone_end(
150 std::vector<Iterator> new_zone;
151 for (; previous_zone_it != previous_zone_end; ++previous_zone_it)
153 const std::vector<types::global_dof_index> conflict_indices =
154 get_conflict_indices(*previous_zone_it);
156 const unsigned int n_conflict_indices(conflict_indices.size());
157 for (
unsigned int i = 0; i < n_conflict_indices; ++i)
159 const std::vector<Iterator> &conflicting_elements =
160 indices_to_iterators[conflict_indices[i]];
161 for (
unsigned int j = 0; j < conflicting_elements.size(); ++j)
169 if ((conflicting_elements[j] != *previous_zone_it) &&
170 (used_it.count(conflicting_elements[j]) == 0))
172 new_zone.push_back(conflicting_elements[j]);
173 used_it.insert(conflicting_elements[j]);
184 if (new_zone.size() != 0)
185 zones.push_back(new_zone);
187 for (Iterator it = begin; it != end; ++it)
188 if (used_it.count(it) == 0)
190 zones.push_back(std::vector<Iterator>(1, it));
220 template <
typename Iterator>
222 make_dsatur_coloring(
223 std::vector<Iterator> & partition,
224 const std::function<std::vector<types::global_dof_index>(
225 const Iterator &)> & get_conflict_indices,
226 std::vector<std::vector<Iterator>> &partition_coloring)
228 partition_coloring.clear();
231 const unsigned int partition_size(partition.size());
232 std::vector<unsigned int> sorted_vertices(partition_size);
233 std::vector<int> degrees(partition_size);
234 std::vector<std::vector<types::global_dof_index>> conflict_indices(
236 std::vector<std::vector<unsigned int>> graph(partition_size);
241 for (
unsigned int i = 0; i < partition_size; ++i)
243 conflict_indices[i] = get_conflict_indices(partition[i]);
244 std::sort(conflict_indices[i].begin(), conflict_indices[i].end());
249 for (
unsigned int i = 0; i < partition_size; ++i)
250 for (
unsigned int j = i + 1; j < partition_size; ++j)
253 if (have_nonempty_intersection(conflict_indices[i],
254 conflict_indices[j]))
258 graph[i].push_back(j);
259 graph[j].push_back(i);
263 std::vector<int>::iterator degrees_it;
264 for (
unsigned int i = 0; i < partition_size; ++i)
267 degrees_it = std::max_element(degrees.begin(), degrees.end());
268 sorted_vertices[i] = degrees_it - degrees.begin();
274 std::vector<boost::unordered_set<unsigned int>> colors_used;
275 for (
unsigned int i = 0; i < partition_size; ++i)
277 const unsigned int current_vertex(sorted_vertices[i]);
278 bool new_color(
true);
282 for (
unsigned int j = 0; j < partition_coloring.size(); ++j)
287 bool unused_color(
true);
288 for (
unsigned int k = 0; k < graph[current_vertex].size(); ++k)
289 if (colors_used[j].count(graph[current_vertex][k]) == 1)
291 unused_color =
false;
296 partition_coloring[j].push_back(partition[current_vertex]);
297 colors_used[j].insert(current_vertex);
305 partition_coloring.push_back(
306 std::vector<Iterator>(1, partition[current_vertex]));
307 boost::unordered_set<unsigned int> tmp;
308 tmp.insert(current_vertex);
309 colors_used.push_back(tmp);
325 template <
typename Iterator>
326 std::vector<std::vector<Iterator>>
328 const std::vector<std::vector<std::vector<Iterator>>> &partition_coloring)
330 std::vector<std::vector<Iterator>> coloring;
333 const unsigned int partition_size(partition_coloring.size());
334 std::vector<std::vector<unsigned int>> colors_counter(partition_size);
335 for (
unsigned int i = 0; i < partition_size; ++i)
337 const unsigned int n_colors(partition_coloring[i].size());
338 colors_counter[i].resize(n_colors);
339 for (
unsigned int j = 0; j < n_colors; ++j)
340 colors_counter[i][j] = partition_coloring[i][j].size();
345 unsigned int i_color(0);
346 unsigned int max_even_n_colors(0);
347 const unsigned int colors_size(colors_counter.size());
348 for (
unsigned int i = 0; i < colors_size; i += 2)
350 if (max_even_n_colors < colors_counter[i].size())
352 max_even_n_colors = colors_counter[i].size();
356 coloring.resize(max_even_n_colors);
357 for (
unsigned int j = 0; j < colors_counter[i_color].size(); ++j)
358 coloring[j] = partition_coloring[i_color][j];
360 for (
unsigned int i = 0; i < partition_size; i += 2)
364 boost::unordered_set<unsigned int> used_k;
365 for (
unsigned int j = 0; j < colors_counter[i].size(); ++j)
369 std::vector<unsigned int>::iterator it;
370 it = std::max_element(colors_counter[i].begin(),
371 colors_counter[i].end());
372 unsigned int min_iterators(static_cast<unsigned int>(-1));
376 for (
unsigned int k = 0; k < max_even_n_colors; ++k)
377 if (used_k.count(k) == 0)
378 if (colors_counter[i_color][k] < min_iterators)
380 min_iterators = colors_counter[i_color][k];
383 colors_counter[i_color][pos] += *it;
385 coloring[pos].insert(
387 partition_coloring[i][it - colors_counter[i].begin()]
389 partition_coloring[i][it - colors_counter[i].begin()]
400 if (partition_size > 1)
402 unsigned int max_odd_n_colors(0);
403 for (
unsigned int i = 1; i < partition_size; i += 2)
405 if (max_odd_n_colors < colors_counter[i].size())
407 max_odd_n_colors = colors_counter[i].size();
411 coloring.resize(max_even_n_colors + max_odd_n_colors);
412 for (
unsigned int j = 0; j < colors_counter[i_color].size(); ++j)
413 coloring[max_even_n_colors + j] = partition_coloring[i_color][j];
415 for (
unsigned int i = 1; i < partition_size; i += 2)
419 boost::unordered_set<unsigned int> used_k;
420 for (
unsigned int j = 0; j < colors_counter[i].size(); ++j)
424 std::vector<unsigned int>::iterator it;
425 it = std::max_element(colors_counter[i].begin(),
426 colors_counter[i].end());
427 unsigned int min_iterators(static_cast<unsigned int>(-1));
431 for (
unsigned int k = 0; k < max_odd_n_colors; ++k)
432 if (used_k.count(k) == 0)
433 if (colors_counter[i_color][k] < min_iterators)
435 min_iterators = colors_counter[i_color][k];
438 colors_counter[i_color][pos] += *it;
441 coloring[max_even_n_colors + pos].insert(
442 coloring[max_even_n_colors + pos].end(),
443 partition_coloring[i][it - colors_counter[i].begin()]
445 partition_coloring[i][it - colors_counter[i].begin()]
540 template <
typename Iterator>
541 std::vector<std::vector<Iterator>>
543 const Iterator & begin,
544 const typename identity<Iterator>::type & end,
545 const std::function<std::vector<types::global_dof_index>(
546 const typename identity<Iterator>::type &)> &get_conflict_indices)
550 "GraphColoring is not prepared to deal with empty ranges!"));
553 std::vector<std::vector<Iterator>> partitioning =
554 internal::create_partitioning(begin, end, get_conflict_indices);
558 const unsigned int partitioning_size(partitioning.size());
559 std::vector<std::vector<std::vector<Iterator>>> partition_coloring(
563 for (
unsigned int i = 0; i < partitioning_size; ++i)
566 get_conflict_indices,
567 partition_coloring[i]);
571 return internal::gather_colors(partition_coloring);
582 std::vector<unsigned int> &color_indices);
586 DEAL_II_NAMESPACE_CLOSE
Task< RT > new_task(const std::function< RT()> &function)
std::vector< std::vector< Iterator > > make_graph_coloring(const Iterator &begin, const typename identity< Iterator >::type &end, const std::function< std::vector< types::global_dof_index >(const typename identity< Iterator >::type &)> &get_conflict_indices)
static::ExceptionBase & ExcMessage(std::string arg1)
#define Assert(cond, exc)
unsigned int color_sparsity_pattern(const SparsityPattern &sparsity_pattern, std::vector< unsigned int > &color_indices)