| 1 |
|
| 2 |
// ------------------------------------------------------------------------ |
| 3 |
// |
| 4 |
// SPDX-License-Identifier: LGPL-2.1-or-later |
| 5 |
// Copyright (C) 2013 - 2025 by the deal.II authors |
| 6 |
// |
| 7 |
// This file is part of the deal.II library. |
| 8 |
// |
| 9 |
// Part of the source code is dual licensed under Apache-2.0 WITH |
| 10 |
// LLVM-exception OR LGPL-2.1-or-later. Detailed license information |
| 11 |
// governing the source code and code contributions can be found in |
| 12 |
// LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II. |
| 13 |
// |
| 14 |
// ------------------------------------------------------------------------ |
| 15 |
|
| 16 |
#ifndef dealii_graph_coloring_h |
| 17 |
# define dealii_graph_coloring_h |
| 18 |
|
| 19 |
|
| 20 |
# include <deal.II/base/config.h> |
| 21 |
|
| 22 |
# include <deal.II/base/std_cxx20/type_traits.h> |
| 23 |
# include <deal.II/base/thread_management.h> |
| 24 |
# include <deal.II/base/types.h> |
| 25 |
|
| 26 |
# include <algorithm> |
| 27 |
# include <functional> |
| 28 |
# include <set> |
| 29 |
# include <unordered_map> |
| 30 |
# include <unordered_set> |
| 31 |
# include <vector> |
| 32 |
|
| 33 |
|
| 34 |
DEAL_II_NAMESPACE_OPEN |
| 35 |
|
| 36 |
class SparsityPattern; |
| 37 |
|
| 38 |
/** |
| 39 |
* A namespace containing functions that can color graphs. |
| 40 |
*/ |
| 41 |
namespace GraphColoring |
| 42 |
{ |
| 43 |
namespace internal |
| 44 |
{ |
| 45 |
/** |
| 46 |
* Given two sets of indices that are assumed to be sorted, determine |
| 47 |
* whether they will have a nonempty intersection. The actual intersection |
| 48 |
* is not computed. |
| 49 |
* @param indices1 A set of indices, assumed sorted. |
| 50 |
* @param indices2 A set of indices, assumed sorted. |
| 51 |
* @return Whether the two sets of indices do have a nonempty |
| 52 |
* intersection. |
| 53 |
*/ |
| 54 |
inline bool |
| 55 |
have_nonempty_intersection( |
| 56 |
const std::vector<types::global_dof_index> &indices1, |
| 57 |
const std::vector<types::global_dof_index> &indices2) |
| 58 |
{ |
| 59 |
// we assume that both arrays are sorted, so we can walk |
| 60 |
// them in lockstep and see if we encounter an index that's |
| 61 |
// in both arrays. once we reach the end of either array, |
| 62 |
// we know that there is no intersection |
| 63 |
std::vector<types::global_dof_index>::const_iterator p = indices1.begin(), |
| 64 |
q = indices2.begin(); |
| 65 |
while ((p != indices1.end()) && (q != indices2.end())) |
| 66 |
{ |
| 67 |
if (*p < *q) |
| 68 |
++p; |
| 69 |
else if (*p > *q) |
| 70 |
++q; |
| 71 |
else |
| 72 |
// conflict found! |
| 73 |
return true; |
| 74 |
} |
| 75 |
|
| 76 |
// no conflict found! |
| 77 |
return false; |
| 78 |
} |
| 79 |
|
| 80 |
|
| 81 |
/** |
| 82 |
* Create a partitioning of the given range of iterators using a |
| 83 |
* simplified version of the Cuthill-McKee algorithm (Breadth First Search |
| 84 |
* algorithm). The function creates partitions that contain "zones" of |
| 85 |
* iterators where the first partition contains the first iterator, the |
| 86 |
* second zone contains all those iterators that have conflicts with the |
| 87 |
* single element in the first zone, the third zone contains those |
| 88 |
* iterators that have conflicts with the iterators of the second zone and |
| 89 |
* have not previously been assigned to a zone, etc. If the iterators |
| 90 |
* represent cells, then this generates partitions that are like onion |
| 91 |
* shells around the very first cell. Note that elements in each zone may |
| 92 |
* conflict with other elements in the same zone. |
| 93 |
* |
| 94 |
* The question whether two iterators conflict is determined by a |
| 95 |
* user-provided function. The meaning of this function is discussed in the |
| 96 |
* documentation of the GraphColoring::make_graph_coloring() function. |
| 97 |
* |
| 98 |
* @param[in] begin The first element of a range of iterators for which a |
| 99 |
* partitioning is sought. |
| 100 |
* @param[in] end The element past the end of the range of iterators. |
| 101 |
* @param[in] get_conflict_indices A user defined function object |
| 102 |
* returning a set of indicators that are descriptive of what represents a |
| 103 |
* conflict. See above for a more thorough discussion. |
| 104 |
* @return A set of sets of iterators (where sets are represented by |
| 105 |
* std::vector for efficiency). Each element of the outermost set |
| 106 |
* corresponds to the iterators pointing to objects that are in the same |
| 107 |
* partition (i.e., the same zone). |
| 108 |
*/ |
| 109 |
template <typename Iterator> |
| 110 |
std::vector<std::vector<Iterator>> |
| 111 |
create_partitioning( |
| 112 |
const Iterator &begin, |
| 113 |
const std_cxx20::type_identity_t<Iterator> &end, |
| 114 |
const std::function<std::vector<types::global_dof_index>( |
| 115 |
const Iterator &)> &get_conflict_indices) |
| 116 |
{ |
| 117 |
// Number of iterators. |
| 118 |
unsigned int n_iterators = 0; |
| 119 |
|
| 120 |
// Create a map from conflict indices to iterators |
| 121 |
std::unordered_map<types::global_dof_index, std::vector<Iterator>> |
| 122 |
indices_to_iterators; |
| 123 |
for (Iterator it = begin; it != end; ++it) |
| 124 |
{ |
| 125 |
const std::vector<types::global_dof_index> conflict_indices = |
| 126 |
get_conflict_indices(it); |
| 127 |
const unsigned int n_conflict_indices = conflict_indices.size(); |
| 128 |
for (unsigned int i = 0; i < n_conflict_indices; ++i) |
| 129 |
indices_to_iterators[conflict_indices[i]].push_back(it); |
| 130 |
++n_iterators; |
| 131 |
} |
| 132 |
|
| 133 |
// create the very first zone which contains only the first |
| 134 |
// iterator. then create the other zones. keep track of all the |
| 135 |
// iterators that have already been assigned to a zone |
| 136 |
std::vector<std::vector<Iterator>> zones(1, |
| 137 |
std::vector<Iterator>(1, begin)); |
| 138 |
std::set<Iterator> used_it; |
| 139 |
used_it.insert(begin); |
| 140 |
while (used_it.size() != n_iterators) |
| 141 |
{ |
| 142 |
// loop over the elements of the previous zone. for each element of |
| 143 |
// the previous zone, get the conflict indices and from there get |
| 144 |
// those iterators that are conflicting with the current element |
| 145 |
typename std::vector<Iterator>::iterator previous_zone_it( |
| 146 |
zones.back().begin()); |
| 147 |
typename std::vector<Iterator>::iterator previous_zone_end( |
| 148 |
zones.back().end()); |
| 149 |
std::vector<Iterator> new_zone; |
| 150 |
for (; previous_zone_it != previous_zone_end; ++previous_zone_it) |
| 151 |
{ |
| 152 |
const std::vector<types::global_dof_index> conflict_indices = |
| 153 |
get_conflict_indices(*previous_zone_it); |
| 154 |
|
| 155 |
const unsigned int n_conflict_indices(conflict_indices.size()); |
| 156 |
for (unsigned int i = 0; i < n_conflict_indices; ++i) |
| 157 |
{ |
| 158 |
const std::vector<Iterator> &conflicting_elements = |
| 159 |
indices_to_iterators[conflict_indices[i]]; |
| 160 |
for (unsigned int j = 0; j < conflicting_elements.size(); ++j) |
| 161 |
{ |
| 162 |
// check that the iterator conflicting with the current |
| 163 |
// one is not associated to a zone yet and if so, assign |
| 164 |
// it to the current zone. mark it as used |
| 165 |
// |
| 166 |
// we can shortcut this test if the conflicting iterator |
| 167 |
// is the current iterator |
| 168 |
if ((conflicting_elements[j] != *previous_zone_it) && |
| 169 |
(used_it.count(conflicting_elements[j]) == 0)) |
| 170 |
{ |
| 171 |
new_zone.push_back(conflicting_elements[j]); |
| 172 |
used_it.insert(conflicting_elements[j]); |
| 173 |
} |
| 174 |
} |
| 175 |
} |
| 176 |
} |
| 177 |
|
| 178 |
// If there are iterators in the new zone, then the zone is added to |
| 179 |
// the partition. Otherwise, the graph is disconnected and we need to |
| 180 |
// find an iterator on the other part of the graph. start the whole |
| 181 |
// process again with the first iterator that hasn't been assigned to |
| 182 |
// a zone yet |
| 183 |
if (new_zone.size() != 0) |
| 184 |
zones.push_back(new_zone); |
| 185 |
else |
| 186 |
for (Iterator it = begin; it != end; ++it) |
| 187 |
if (used_it.count(it) == 0) |
| 188 |
{ |
| 189 |
zones.push_back(std::vector<Iterator>(1, it)); |
| 190 |
used_it.insert(it); |
| 191 |
break; |
| 192 |
} |
| 193 |
} |
| 194 |
|
| 195 |
return zones; |
| 196 |
} |
| 197 |
|
| 198 |
|
| 199 |
|
| 200 |
/** |
| 201 |
* This function uses DSATUR (Degree SATURation) to color the elements of |
| 202 |
* a set. DSATUR works as follows: |
| 203 |
* -# Arrange the vertices by decreasing order of degrees. |
| 204 |
* -# Color a vertex of maximal degree with color 1. |
| 205 |
* -# Choose a vertex with a maximal saturation degree. If there is |
| 206 |
* equality, choose any vertex of maximal degree in the uncolored |
| 207 |
* subgraph. |
| 208 |
* -# Color the chosen vertex with the least possible (lowest numbered) |
| 209 |
* color. |
| 210 |
* -# If all the vertices are colored, stop. Otherwise, return to 3. |
| 211 |
* |
| 212 |
* @param[in] partition The set of iterators that should be colored. |
| 213 |
* @param[in] get_conflict_indices A user defined function object |
| 214 |
* returning a set of indicators that are descriptive of what represents a |
| 215 |
* conflict. See above for a more thorough discussion. |
| 216 |
* @param[out] partition_coloring A set of sets of iterators (where sets |
| 217 |
* are represented by std::vector for efficiency). Each element of the |
| 218 |
* outermost set corresponds to the iterators pointing to objects that are |
| 219 |
* in the same partition (have the same color) and consequently do not |
| 220 |
* conflict. The elements of different sets may conflict. |
| 221 |
*/ |
| 222 |
template <typename Iterator> |
| 223 |
void |
| 224 |
make_dsatur_coloring( |
| 225 |
std::vector<Iterator> &partition, |
| 226 |
const std::function<std::vector<types::global_dof_index>( |
| 227 |
const Iterator &)> &get_conflict_indices, |
| 228 |
std::vector<std::vector<Iterator>> &partition_coloring) |
| 229 |
{ |
| 230 |
partition_coloring.clear(); |
| 231 |
|
| 232 |
// Number of zones composing the partitioning. |
| 233 |
const unsigned int partition_size(partition.size()); |
| 234 |
std::vector<unsigned int> sorted_vertices(partition_size); |
| 235 |
std::vector<int> degrees(partition_size); |
| 236 |
std::vector<std::vector<types::global_dof_index>> conflict_indices( |
| 237 |
partition_size); |
| 238 |
std::vector<std::vector<unsigned int>> graph(partition_size); |
| 239 |
|
| 240 |
// Get the conflict indices associated to each iterator. The |
| 241 |
// conflict_indices have to be sorted so we can more easily find conflicts |
| 242 |
// later on |
| 243 |
for (unsigned int i = 0; i < partition_size; ++i) |
| 244 |
{ |
| 245 |
conflict_indices[i] = get_conflict_indices(partition[i]); |
| 246 |
std::sort(conflict_indices[i].begin(), conflict_indices[i].end()); |
| 247 |
} |
| 248 |
|
| 249 |
// Compute the degree of each vertex of the graph using the |
| 250 |
// intersection of the conflict indices. |
| 251 |
for (unsigned int i = 0; i < partition_size; ++i) |
| 252 |
for (unsigned int j = i + 1; j < partition_size; ++j) |
| 253 |
// If the two iterators share indices then we increase the degree of |
| 254 |
// the vertices and create an ''edge'' in the graph. |
| 255 |
if (have_nonempty_intersection(conflict_indices[i], |
| 256 |
conflict_indices[j])) |
| 257 |
{ |
| 258 |
++degrees[i]; |
| 259 |
++degrees[j]; |
| 260 |
graph[i].push_back(j); |
| 261 |
graph[j].push_back(i); |
| 262 |
} |
| 263 |
|
| 264 |
// Sort the vertices by decreasing degree. |
| 265 |
std::vector<int>::iterator degrees_it; |
| 266 |
for (unsigned int i = 0; i < partition_size; ++i) |
| 267 |
{ |
| 268 |
// Find the largest element. |
| 269 |
degrees_it = std::max_element(degrees.begin(), degrees.end()); |
| 270 |
sorted_vertices[i] = degrees_it - degrees.begin(); |
| 271 |
// Put the largest element to -1 so it cannot be chosen again. |
| 272 |
*degrees_it = -1; |
| 273 |
} |
| 274 |
|
| 275 |
// Color the graph. |
| 276 |
std::vector<std::unordered_set<unsigned int>> colors_used; |
| 277 |
for (unsigned int i = 0; i < partition_size; ++i) |
| 278 |
{ |
| 279 |
const unsigned int current_vertex(sorted_vertices[i]); |
| 280 |
bool new_color(true); |
| 281 |
// Try to use an existing color, i.e., try to find a color which is |
| 282 |
// not associated to one of the vertices linked to current_vertex. |
| 283 |
// Loop over the color. |
| 284 |
for (unsigned int j = 0; j < partition_coloring.size(); ++j) |
| 285 |
{ |
| 286 |
// Loop on the vertices linked to current_vertex. If one vertex |
| 287 |
// linked to current_vertex is already using the color j, this |
| 288 |
// color cannot be used anymore. |
| 289 |
bool unused_color(true); |
| 290 |
for (const auto adjacent_vertex : graph[current_vertex]) |
| 291 |
if (colors_used[j].count(adjacent_vertex) == 1) |
| 292 |
{ |
| 293 |
unused_color = false; |
| 294 |
break; |
| 295 |
} |
| 296 |
if (unused_color) |
| 297 |
{ |
| 298 |
partition_coloring[j].push_back(partition[current_vertex]); |
| 299 |
colors_used[j].insert(current_vertex); |
| 300 |
new_color = false; |
| 301 |
break; |
| 302 |
} |
| 303 |
} |
| 304 |
// Add a new color. |
| 305 |
if (new_color) |
| 306 |
{ |
| 307 |
partition_coloring.push_back( |
| 308 |
std::vector<Iterator>(1, partition[current_vertex])); |
| 309 |
std::unordered_set<unsigned int> tmp; |
| 310 |
tmp.insert(current_vertex); |
| 311 |
colors_used.push_back(tmp); |
| 312 |
} |
| 313 |
} |
| 314 |
} |
| 315 |
|
| 316 |
|
| 317 |
|
| 318 |
/** |
| 319 |
* Given a partition-coloring graph, i.e., a set of zones (partitions) |
| 320 |
* each of which is colored, produce a combined coloring for the entire |
| 321 |
* set of iterators. This is possible because any color on an even (resp. |
| 322 |
* odd) zone does not conflict with any color of any other even (resp. |
| 323 |
* odd) zone. Consequently, we can combine colors from all even and all |
| 324 |
* odd zones. This function tries to create colors of similar number of |
| 325 |
* elements. |
| 326 |
*/ |
| 327 |
template <typename Iterator> |
| 328 |
std::vector<std::vector<Iterator>> |
| 329 |
gather_colors( |
| 330 |
const std::vector<std::vector<std::vector<Iterator>>> &partition_coloring) |
| 331 |
{ |
| 332 |
std::vector<std::vector<Iterator>> coloring; |
| 333 |
|
| 334 |
// Count the number of iterators in each color. |
| 335 |
const unsigned int partition_size(partition_coloring.size()); |
| 336 |
std::vector<std::vector<unsigned int>> colors_counter(partition_size); |
| 337 |
for (unsigned int i = 0; i < partition_size; ++i) |
| 338 |
{ |
| 339 |
const unsigned int n_colors(partition_coloring[i].size()); |
| 340 |
colors_counter[i].resize(n_colors); |
| 341 |
for (unsigned int j = 0; j < n_colors; ++j) |
| 342 |
colors_counter[i][j] = partition_coloring[i][j].size(); |
| 343 |
} |
| 344 |
|
| 345 |
// Find the partition with the largest number of colors for the even |
| 346 |
// partition. |
| 347 |
unsigned int i_color(0); |
| 348 |
unsigned int max_even_n_colors(0); |
| 349 |
const unsigned int colors_size(colors_counter.size()); |
| 350 |
for (unsigned int i = 0; i < colors_size; i += 2) |
| 351 |
{ |
| 352 |
if (max_even_n_colors < colors_counter[i].size()) |
| 353 |
{ |
| 354 |
max_even_n_colors = colors_counter[i].size(); |
| 355 |
i_color = i; |
| 356 |
} |
| 357 |
} |
| 358 |
coloring.resize(max_even_n_colors); |
| 359 |
for (unsigned int j = 0; j < colors_counter[i_color].size(); ++j) |
| 360 |
coloring[j] = partition_coloring[i_color][j]; |
| 361 |
|
| 362 |
for (unsigned int i = 0; i < partition_size; i += 2) |
| 363 |
{ |
| 364 |
if (i != i_color) |
| 365 |
{ |
| 366 |
std::unordered_set<unsigned int> used_k; |
| 367 |
for (unsigned int j = 0; j < colors_counter[i].size(); ++j) |
| 368 |
{ |
| 369 |
// Find the color in the current partition with the largest |
| 370 |
// number of iterators. |
| 371 |
std::vector<unsigned int>::iterator it; |
| 372 |
it = std::max_element(colors_counter[i].begin(), |
| 373 |
colors_counter[i].end()); |
| 374 |
unsigned int min_iterators(static_cast<unsigned int>(-1)); |
| 375 |
unsigned int pos(0); |
| 376 |
// Find the color of coloring with the least number of colors |
| 377 |
// among the colors that have not been used yet. |
| 378 |
for (unsigned int k = 0; k < max_even_n_colors; ++k) |
| 379 |
if (used_k.count(k) == 0) |
| 380 |
if (colors_counter[i_color][k] < min_iterators) |
| 381 |
{ |
| 382 |
min_iterators = colors_counter[i_color][k]; |
| 383 |
pos = k; |
| 384 |
} |
| 385 |
colors_counter[i_color][pos] += *it; |
| 386 |
// Concatenate the current color with the existing coloring. |
| 387 |
coloring[pos].insert( |
| 388 |
coloring[pos].end(), |
| 389 |
partition_coloring[i][it - colors_counter[i].begin()] |
| 390 |
.begin(), |
| 391 |
partition_coloring[i][it - colors_counter[i].begin()] |
| 392 |
.end()); |
| 393 |
used_k.insert(pos); |
| 394 |
// Put the number of iterators to the current color to zero. |
| 395 |
*it = 0; |
| 396 |
} |
| 397 |
} |
| 398 |
} |
| 399 |
|
| 400 |
// If there is more than one partition, do the same thing that we did for |
| 401 |
// the even partitions to the odd partitions |
| 402 |
if (partition_size > 1) |
| 403 |
{ |
| 404 |
unsigned int max_odd_n_colors(0); |
| 405 |
for (unsigned int i = 1; i < partition_size; i += 2) |
| 406 |
{ |
| 407 |
if (max_odd_n_colors < colors_counter[i].size()) |
| 408 |
{ |
| 409 |
max_odd_n_colors = colors_counter[i].size(); |
| 410 |
i_color = i; |
| 411 |
} |
| 412 |
} |
| 413 |
coloring.resize(max_even_n_colors + max_odd_n_colors); |
| 414 |
for (unsigned int j = 0; j < colors_counter[i_color].size(); ++j) |
| 415 |
coloring[max_even_n_colors + j] = partition_coloring[i_color][j]; |
| 416 |
|
| 417 |
for (unsigned int i = 1; i < partition_size; i += 2) |
| 418 |
{ |
| 419 |
if (i != i_color) |
| 420 |
{ |
| 421 |
std::unordered_set<unsigned int> used_k; |
| 422 |
for (unsigned int j = 0; j < colors_counter[i].size(); ++j) |
| 423 |
{ |
| 424 |
// Find the color in the current partition with the |
| 425 |
// largest number of iterators. |
| 426 |
std::vector<unsigned int>::iterator it; |
| 427 |
it = std::max_element(colors_counter[i].begin(), |
| 428 |
colors_counter[i].end()); |
| 429 |
unsigned int min_iterators(static_cast<unsigned int>(-1)); |
| 430 |
unsigned int pos(0); |
| 431 |
// Find the color of coloring with the least number of |
| 432 |
// colors among the colors that have not been used yet. |
| 433 |
for (unsigned int k = 0; k < max_odd_n_colors; ++k) |
| 434 |
if (used_k.count(k) == 0) |
| 435 |
if (colors_counter[i_color][k] < min_iterators) |
| 436 |
{ |
| 437 |
min_iterators = colors_counter[i_color][k]; |
| 438 |
pos = k; |
| 439 |
} |
| 440 |
colors_counter[i_color][pos] += *it; |
| 441 |
// Concatenate the current color with the existing |
| 442 |
// coloring. |
| 443 |
coloring[max_even_n_colors + pos].insert( |
| 444 |
coloring[max_even_n_colors + pos].end(), |
| 445 |
partition_coloring[i][it - colors_counter[i].begin()] |
| 446 |
.begin(), |
| 447 |
partition_coloring[i][it - colors_counter[i].begin()] |
| 448 |
.end()); |
| 449 |
used_k.insert(pos); |
| 450 |
// Put the number of iterators to the current color to |
| 451 |
// zero. |
| 452 |
*it = 0; |
| 453 |
} |
| 454 |
} |
| 455 |
} |
| 456 |
} |
| 457 |
|
| 458 |
return coloring; |
| 459 |
} |
| 460 |
} // namespace internal |
| 461 |
|
| 462 |
|
| 463 |
/** |
| 464 |
* Create a partitioning of the given range of iterators so that iterators |
| 465 |
* that point to conflicting objects will be placed into different |
| 466 |
* partitions, where the question whether two objects conflict is determined |
| 467 |
* by a user-provided function. |
| 468 |
* |
| 469 |
* This function can also be considered as a graph coloring: each object |
| 470 |
* pointed to by an iterator is considered to be a node and there is an edge |
| 471 |
* between each two nodes that conflict. The graph coloring algorithm then |
| 472 |
* assigns a color to each node in such a way that two nodes connected by an |
| 473 |
* edge do not have the same color. |
| 474 |
* |
| 475 |
* A typical use case for this function is in assembling a matrix in |
| 476 |
* parallel. There, one would like to assemble local contributions on |
| 477 |
* different cells at the same time (an operation that is purely local and |
| 478 |
* so requires no synchronization) but then we need to add these local |
| 479 |
* contributions to the global matrix. In general, the contributions from |
| 480 |
* different cells may be to the same matrix entries if the cells share |
| 481 |
* degrees of freedom and, consequently, can not happen at the same time |
| 482 |
* unless we want to risk a race condition (see |
| 483 |
* http://en.wikipedia.org/wiki/Race_condition). Thus, we call these two |
| 484 |
* cells in conflict, and we can only allow operations in parallel from |
| 485 |
* cells that do not conflict. In other words, two cells are in conflict if |
| 486 |
* the set of matrix entries (for example characterized by the rows) have a |
| 487 |
* nonempty intersection. |
| 488 |
* |
| 489 |
* In this generality, computing the graph of conflicts would require |
| 490 |
* calling a function that determines whether two iterators (or the two |
| 491 |
* objects they represent) conflict, and calling it for every pair of |
| 492 |
* iterators, i.e., $\frac 12 N (N-1)$ times. This is too expensive in |
| 493 |
* general. A better approach is to require a user-defined function that |
| 494 |
* returns for every iterator it is called for a set of indicators of some |
| 495 |
* kind that characterize a conflict; two iterators are in conflict if their |
| 496 |
* conflict indicator sets have a nonempty intersection. In the example of |
| 497 |
* assembling a matrix, the conflict indicator set would contain the indices |
| 498 |
* of all degrees of freedom on the cell pointed to (in the case of |
| 499 |
* continuous Galerkin methods) or the union of indices of degree of freedom |
| 500 |
* on the current cell and all cells adjacent to the faces of the current |
| 501 |
* cell (in the case of discontinuous Galerkin methods, because there one |
| 502 |
* computes face integrals coupling the degrees of freedom connected by a |
| 503 |
* common face -- see step-12). |
| 504 |
* |
| 505 |
* @note The conflict set returned by the user defined function passed as |
| 506 |
* third argument needs to accurately describe <i>all</i> degrees of freedom |
| 507 |
* for which anything is written into the matrix or right hand side. In |
| 508 |
* other words, if the writing happens through a function like |
| 509 |
* AffineConstraints::copy_local_to_global(), then the set of conflict |
| 510 |
* indices must actually contain not only the degrees of freedom on the |
| 511 |
* current cell, but also those they are linked to by constraints such as |
| 512 |
* hanging nodes. |
| 513 |
* |
| 514 |
* In other situations, the conflict indicator sets may represent something |
| 515 |
* different altogether -- it is up to the caller of this function to |
| 516 |
* describe what it means for two iterators to conflict. Given this, |
| 517 |
* computing conflict graph edges can be done significantly more cheaply |
| 518 |
* than with ${\cal O}(N^2)$ operations. |
| 519 |
* |
| 520 |
* In any case, the result of the function will be so that iterators whose |
| 521 |
* conflict indicator sets have overlap will not be assigned to the same |
| 522 |
* color. |
| 523 |
* |
| 524 |
* @note The algorithm used in this function is described in a paper by |
| 525 |
* Turcksin, Kronbichler and Bangerth, see |
| 526 |
* @ref workstream_paper. |
| 527 |
* |
| 528 |
* @param[in] begin The first element of a range of iterators for which a |
| 529 |
* coloring is sought. |
| 530 |
* @param[in] end The element past the end of the range of iterators. |
| 531 |
* @param[in] get_conflict_indices A user defined function object returning |
| 532 |
* a set of indicators that are descriptive of what represents a conflict. |
| 533 |
* See above for a more thorough discussion. |
| 534 |
* @return A set of sets of iterators (where sets are represented by |
| 535 |
* std::vector for efficiency). Each element of the outermost set |
| 536 |
* corresponds to the iterators pointing to objects that are in the same |
| 537 |
* partition (have the same color) and consequently do not conflict. The |
| 538 |
* elements of different sets may conflict. |
| 539 |
*/ |
| 540 |
template <typename Iterator> |
| 541 |
std::vector<std::vector<Iterator>> |
| 542 |
make_graph_coloring( |
| 543 |
const Iterator &begin, |
| 544 |
const std_cxx20::type_identity_t<Iterator> &end, |
| 545 |
const std::function<std::vector<types::global_dof_index>( |
| 546 |
const std_cxx20::type_identity_t<Iterator> &)> &get_conflict_indices) |
| 547 |
{ |
| 548 |
Assert(begin != end, |
| 549 |
ExcMessage( |
| 550 |
"GraphColoring is not prepared to deal with empty ranges!")); |
| 551 |
|
| 552 |
// Create the partitioning. |
| 553 |
std::vector<std::vector<Iterator>> partitioning = |
| 554 |
internal::create_partitioning(begin, end, get_conflict_indices); |
| 555 |
|
| 556 |
// Color the iterators within each partition. |
| 557 |
// Run the coloring algorithm on each zone in parallel |
| 558 |
const unsigned int partitioning_size(partitioning.size()); |
| 559 |
std::vector<std::vector<std::vector<Iterator>>> partition_coloring( |
| 560 |
partitioning_size); |
| 561 |
|
| 562 |
Threads::TaskGroup<> tasks; |
| 563 |
for (unsigned int i = 0; i < partitioning_size; ++i) |
| 564 |
tasks += Threads::new_task(&internal::make_dsatur_coloring<Iterator>, |
| 565 |
partitioning[i], |
| 566 |
get_conflict_indices, |
| 567 |
partition_coloring[i]); |
| 568 |
tasks.join_all(); |
| 569 |
|
| 570 |
// Gather the colors together. |
| 571 |
return internal::gather_colors(partition_coloring); |
| 572 |
} |
| 573 |
|
| 574 |
/** |
| 575 |
* GraphColoring::color_sparsity_pattern, a wrapper function for |
| 576 |
* SparsityTools::color_sparsity_pattern, is an alternate method for |
| 577 |
* coloring using graph connections represented by SparsityPattern. |
| 578 |
* For further details, refer to SparsityTools::color_sparsity_pattern. |
| 579 |
*/ |
| 580 |
unsigned int |
| 581 |
color_sparsity_pattern(const SparsityPattern &sparsity_pattern, |
| 582 |
std::vector<unsigned int> &color_indices); |
| 583 |
|
| 584 |
} // namespace GraphColoring |
| 585 |
|
| 586 |
DEAL_II_NAMESPACE_CLOSE |
| 587 |
|
| 588 |
|
| 589 |
//---------------------------- graph_coloring.h --------------------------- |
| 590 |
// end of #ifndef dealii_graph_coloring_h |
| 591 |
#endif |
| 592 |
//---------------------------- graph_coloring.h --------------------------- |