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

indices1	A set of indices, assumed sorted.
indices2	A 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]	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.

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]	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.

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.