112 const Iterator &begin,
114 const std::function<std::vector<types::global_dof_index>(
115 const Iterator &)> &get_conflict_indices)
118 unsigned int n_iterators = 0;
121 std::unordered_map<types::global_dof_index, std::vector<Iterator>>
122 indices_to_iterators;
123 for (Iterator it = begin; it != end; ++it)
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);
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)
145 typename std::vector<Iterator>::iterator previous_zone_it(
146 zones.back().begin());
147 typename std::vector<Iterator>::iterator previous_zone_end(
149 std::vector<Iterator> new_zone;
150 for (; previous_zone_it != previous_zone_end; ++previous_zone_it)
152 const std::vector<types::global_dof_index> conflict_indices =
153 get_conflict_indices(*previous_zone_it);
155 const unsigned int n_conflict_indices(conflict_indices.size());
156 for (
unsigned int i = 0; i < n_conflict_indices; ++i)
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)
168 if ((conflicting_elements[j] != *previous_zone_it) &&
169 (used_it.count(conflicting_elements[j]) == 0))
171 new_zone.push_back(conflicting_elements[j]);
172 used_it.insert(conflicting_elements[j]);
183 if (new_zone.size() != 0)
184 zones.push_back(new_zone);
186 for (Iterator it = begin; it != end; ++it)
187 if (used_it.count(it) == 0)
189 zones.push_back(std::vector<Iterator>(1, it));
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)
230 partition_coloring.clear();
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(
238 std::vector<std::vector<unsigned int>> graph(partition_size);
243 for (
unsigned int i = 0; i < partition_size; ++i)
245 conflict_indices[i] = get_conflict_indices(partition[i]);
246 std::sort(conflict_indices[i].begin(), conflict_indices[i].end());
251 for (
unsigned int i = 0; i < partition_size; ++i)
252 for (
unsigned int j = i + 1; j < partition_size; ++j)
256 conflict_indices[j]))
260 graph[i].push_back(j);
261 graph[j].push_back(i);
265 std::vector<int>::iterator degrees_it;
266 for (
unsigned int i = 0; i < partition_size; ++i)
269 degrees_it = std::max_element(degrees.begin(), degrees.end());
270 sorted_vertices[i] = degrees_it - degrees.begin();
276 std::vector<std::unordered_set<unsigned int>> colors_used;
277 for (
unsigned int i = 0; i < partition_size; ++i)
279 const unsigned int current_vertex(sorted_vertices[i]);
280 bool new_color(
true);
284 for (
unsigned int j = 0; j < partition_coloring.size(); ++j)
289 bool unused_color(
true);
290 for (
const auto adjacent_vertex : graph[current_vertex])
291 if (colors_used[j].count(adjacent_vertex) == 1)
293 unused_color =
false;
298 partition_coloring[j].push_back(partition[current_vertex]);
299 colors_used[j].insert(current_vertex);
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);
330 const std::vector<std::vector<std::vector<Iterator>>> &partition_coloring)
332 std::vector<std::vector<Iterator>> coloring;
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)
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();
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)
352 if (max_even_n_colors < colors_counter[i].
size())
354 max_even_n_colors = colors_counter[i].size();
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];
362 for (
unsigned int i = 0; i < partition_size; i += 2)
366 std::unordered_set<unsigned int> used_k;
367 for (
unsigned int j = 0; j < colors_counter[i].size(); ++j)
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));
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)
382 min_iterators = colors_counter[i_color][k];
385 colors_counter[i_color][pos] += *it;
387 coloring[pos].insert(
389 partition_coloring[i][it - colors_counter[i].begin()]
391 partition_coloring[i][it - colors_counter[i].begin()]
402 if (partition_size > 1)
404 unsigned int max_odd_n_colors(0);
405 for (
unsigned int i = 1; i < partition_size; i += 2)
407 if (max_odd_n_colors < colors_counter[i].
size())
409 max_odd_n_colors = colors_counter[i].size();
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];
417 for (
unsigned int i = 1; i < partition_size; i += 2)
421 std::unordered_set<unsigned int> used_k;
422 for (
unsigned int j = 0; j < colors_counter[i].size(); ++j)
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));
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)
437 min_iterators = colors_counter[i_color][k];
440 colors_counter[i_color][pos] += *it;
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()]
447 partition_coloring[i][it - colors_counter[i].begin()]