Debian Codegraph @

include/deal.II/base/graph_coloring.h

raw
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 ---------------------------