Reference documentation for deal.II version 9.6.0
\(\newcommand{\dealvcentcolon}{\mathrel{\mathop{:}}}\) \(\newcommand{\dealcoloneq}{\dealvcentcolon\mathrel{\mkern-1.2mu}=}\) \(\newcommand{\jump}[1]{\left[\!\left[ #1 \right]\!\right]}\) \(\newcommand{\average}[1]{\left\{\!\left\{ #1 \right\}\!\right\}}\)
Loading...
Searching...
No Matches
GraphColoring::internal Namespace Reference

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)
 

Function Documentation

◆ have_nonempty_intersection()

bool GraphColoring::internal::have_nonempty_intersection ( const std::vector< types::global_dof_index > & indices1,
const std::vector< types::global_dof_index > & indices2 )
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.

Parameters
indices1A set of indices, assumed sorted.
indices2A set of indices, assumed sorted.
Returns
Whether the two sets of indices do have a nonempty intersection.

Definition at line 53 of file graph_coloring.h.

◆ create_partitioning()

template<typename Iterator >
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.

Parameters
[in]beginThe first element of a range of iterators for which a partitioning is sought.
[in]endThe element past the end of the range of iterators.
[in]get_conflict_indicesA user defined function object returning a set of indicators that are descriptive of what represents a conflict. See above for a more thorough discussion.
Returns
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 (i.e., the same zone).

Definition at line 109 of file graph_coloring.h.

◆ make_dsatur_coloring()

template<typename Iterator >
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:

  1. Arrange the vertices by decreasing order of degrees.
  2. Color a vertex of maximal degree with color 1.
  3. Choose a vertex with a maximal saturation degree. If there is equality, choose any vertex of maximal degree in the uncolored subgraph.
  4. Color the chosen vertex with the least possible (lowest numbered) color.
  5. If all the vertices are colored, stop. Otherwise, return to 3.
Parameters
[in]partitionThe set of iterators that should be colored.
[in]get_conflict_indicesA 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_coloringA 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.

◆ gather_colors()

template<typename Iterator >
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.