![]() |
Reference documentation for deal.II version 9.6.0
|
Functions | |
bool | have_nonempty_intersection (const std::vector< types::global_dof_index > &indices1, const std::vector< types::global_dof_index > &indices2) |
template<typename Iterator > | |
std::vector< std::vector< Iterator > > | create_partitioning (const Iterator &begin, const std_cxx20::type_identity_t< Iterator > &end, const std::function< std::vector< types::global_dof_index >(const Iterator &)> &get_conflict_indices) |
template<typename Iterator > | |
void | make_dsatur_coloring (std::vector< Iterator > &partition, const std::function< std::vector< types::global_dof_index >(const Iterator &)> &get_conflict_indices, std::vector< std::vector< Iterator > > &partition_coloring) |
template<typename Iterator > | |
std::vector< std::vector< Iterator > > | gather_colors (const std::vector< std::vector< std::vector< Iterator > > > &partition_coloring) |
|
inline |
Given two sets of indices that are assumed to be sorted, determine whether they will have a nonempty intersection. The actual intersection is not computed.
indices1 | A set of indices, assumed sorted. |
indices2 | A set of indices, assumed sorted. |
Definition at line 53 of file graph_coloring.h.
std::vector< std::vector< Iterator > > GraphColoring::internal::create_partitioning | ( | const Iterator & | begin, |
const std_cxx20::type_identity_t< Iterator > & | end, | ||
const std::function< std::vector< types::global_dof_index >(const Iterator &)> & | get_conflict_indices ) |
Create a partitioning of the given range of iterators using a simplified version of the Cuthill-McKee algorithm (Breadth First Search algorithm). The function creates partitions that contain "zones" of iterators where the first partition contains the first iterator, the second zone contains all those iterators that have conflicts with the single element in the first zone, the third zone contains those iterators that have conflicts with the iterators of the second zone and have not previously been assigned to a zone, etc. If the iterators represent cells, then this generates partitions that are like onion shells around the very first cell. Note that elements in each zone may conflict with other elements in the same zone.
The question whether two iterators conflict is determined by a user-provided function. The meaning of this function is discussed in the documentation of the GraphColoring::make_graph_coloring() function.
[in] | begin | The first element of a range of iterators for which a partitioning is sought. |
[in] | end | The element past the end of the range of iterators. |
[in] | get_conflict_indices | A user defined function object returning a set of indicators that are descriptive of what represents a conflict. See above for a more thorough discussion. |
Definition at line 109 of file graph_coloring.h.
void GraphColoring::internal::make_dsatur_coloring | ( | std::vector< Iterator > & | partition, |
const std::function< std::vector< types::global_dof_index >(const Iterator &)> & | get_conflict_indices, | ||
std::vector< std::vector< Iterator > > & | partition_coloring ) |
This function uses DSATUR (Degree SATURation) to color the elements of a set. DSATUR works as follows:
[in] | partition | The set of iterators that should be colored. |
[in] | get_conflict_indices | A user defined function object returning a set of indicators that are descriptive of what represents a conflict. See above for a more thorough discussion. |
[out] | partition_coloring | A set of sets of iterators (where sets are represented by std::vector for efficiency). Each element of the outermost set corresponds to the iterators pointing to objects that are in the same partition (have the same color) and consequently do not conflict. The elements of different sets may conflict. |
Definition at line 222 of file graph_coloring.h.
std::vector< std::vector< Iterator > > GraphColoring::internal::gather_colors | ( | const std::vector< std::vector< std::vector< Iterator > > > & | partition_coloring | ) |
Given a partition-coloring graph, i.e., a set of zones (partitions) each of which is colored, produce a combined coloring for the entire set of iterators. This is possible because any color on an even (resp. odd) zone does not conflict with any color of any other even (resp. odd) zone. Consequently, we can combine colors from all even and all odd zones. This function tries to create colors of similar number of elements.
Definition at line 327 of file graph_coloring.h.