API Reference

const WorkstreamDSATUR = Workstream(DSATUR())

A workstream that uses the DSATUR coloring algorithm.

const WorkstreamGreedy = Workstream(Greedy())

A workstream that uses the Greedy coloring algorithm.

struct ConflictFunctor{T}
    conflictindices::T

A functor that can be used to return conflict indices.

Type Parameters

• T: The type of the conflict indices.

Fields

• conflictindices::T: The conflict indices.

This functor represents a mapping from element indices to conflict indices. Two elements that have the same conflict index are considered to be in conflict. An element can have multiple conflict indices, indicating that it is in conflict with multiple other elements.

function (f::ConflictFunctor)(i::Int)

Returns the conflict indices for the given element index.

Arguments

• f::ConflictFunctor: The conflict functor.
• i::Int: The element index.

Returns

The conflict indices for the given element index.

struct DSATUR

Represents the DSATUR (Degree SATURated) coloring algorithm, which makes use of two key concepts:

• Degree of a node: The number of neighbors a node has.
• Saturation of a node: The number of colors already assigned to its neighbors.

The next node to be colored is chosen based on the following criteria:

1. Highest saturation degree: The node with the highest saturation degree is chosen first.
2. Largest degree: In case of a tie, the node with the largest degree is chosen.
3. Largest element ID: If there is still a tie, the node with the largest element ID is chosen.

struct DSATURNode
    elementid::Int
    degree::Int
    saturation::Int

Represents a node in the context of the DSATUR coloring algorithm.

Fields

• elementid::Int: The unique identifier of the element.
• degree::Int: The number of neighbors the element has.
• saturation::Int: The number of colors already assigned to the neighboring elements.

This node is used in a RBTree from DataStructures.jl to efficiently manage and prioritize nodes during the coloring process.

GroupedColors

A trait that indicates that a coloring operation should return results as a Graphs.Coloring.

struct Greedy

Represents the Greedy coloring algorithm, where the next node to be colored is chosen as the node with the largest element ID.

struct GreedyNode

Represents a node in the context of the Greedy coloring algorithm.

Fields

• elementid::Int: The unique identifier of the element.

This node type is used by the Greedy algorithm to make coloring decisions, where the next node to be colored is chosen based on its element ID.

GroupedColoring{I}

A data structure that represents a coloring of elements as a vector of vectors, where each inner vector contains the indices of elements assigned to a particular color.

This representation is optimized for efficiently retrieving all elements belonging to a specific color group, making it ideal for operations that frequently access elements by color.

Type Parameters

• I: The integer type used to represent element indices (e.g., Int, Int64, UInt32).

Fields

• colors: A vector of vectors, where colors[i] contains the indices of all elements assigned to color i. The vector is sorted by group size in descending order (largest groups first) for consistency.

Notes

The constructor automatically sorts the color groups by size in descending order using `sort!`
with `by=length, rev=true`.

GroupedColors

A trait that indicates that a coloring operation should return results as a GroupedColoring.

struct PassThroughConflictFunctor{E,C1,C2}

A functor that passes through elements, conflicts, and conflict IDs for the conflicts function.

Fields

• elements::E: The elements to be passed through.
• conflicts::C1: The conflicts to be passed through.
• conflictids::C2: The conflict IDs to be passed through.

struct Workstream{T}
    algorithm::T

Represents the workstream coloring algorithm presented in [1].

Type Parameters

• T: The type of the coloring algorithm.

Fields

• algorithm::T: The coloring algorithm used by the workstream.

This struct represents the workstream coloring algorithm, which does not create the minimal amount of colors, but is very good at creating balanced colors. Balanced colors are important for load balancing in parallel computing. It uses the partition, color, and gather steps to perform coloring. In the color step, the algorithm is used for internal coloring. Only coloring all elements is supported.

See [1] for more information on the workstream design pattern.

[1] B. Turcksin, M. Kronbichler, and W. Bangerth, WorkStream – A Design Pattern for Multicore-Enabled Finite Element Computations, 2017

Base.eachindex(c::Union{GroupedColoring,Graphs.Coloring})

Return an iterator over the indices of the color groups in c.

Arguments

• c: An object representing a coloring.

Returns

• An iterator over the indices of the color groups (typically 1:numcolors(c))).

Notes

This method implements the eachindex interface for GroupedColoring and Graphs.Coloring, making it compatible with Julia's standard iteration patterns.

Base.getindex(c::Union{GroupedColoring,Graphs.Coloring}, color)

Return the i-th color group from the coloring object c.

Arguments

• c: An object representing a coloring.
• color: An integer index specifying which color group to retrieve (must be within valid bounds).

Returns

• The i-th color group (typically a vector of elements assigned to that color).

function _neighbors(s::SparseMatrixCSC, element::Int)

Returns the neighbors of a given element, i.e. the elements that have a conflict with the element, in the sparse matrix, which is used as a conflict representation.

Arguments

• s::SparseMatrixCSC: The sparse matrix representing the graph.
• element::Int: The element for which to retrieve the neighbors.

Returns

A view of the row values in the sparse matrix that correspond to the neighbors of the given element.

function _numelements(s::SparseMatrixCSC)

Returns the number of elements in the given sparse matrix, which is used as a conflict representation.

Arguments

• s::SparseMatrixCSC: The sparse matrix.

Returns

The number of rows in the matrix, which represents the number of elements.

function color(conflicts, algorithm::Workstream, elements=1:_numelements(conflicts))

Performs workstream coloring on the given conflicts. It was presented in [1]. Workstream coloring does not create the minimal amount of colors, but is very good at creating balanced colors. Balanced colors are important for load balancing in parallel computing. It uses the partition, color, and gather steps to perform coloring.

Arguments

• conflicts: The conflict representation.
• algorithm::Workstream: The workstream coloring algorithm.
• elements=1:_numelements(conflicts): The elements to consider during coloring (default: all elements).

Returns

A vector of vectors, where each inner vector represents a color.

Note that workstream coloring only supports coloring all elements, so the elements argument must be equal to 1:_numelements(conflicts).

See [1] for more information on the workstream design pattern.

[1] B. Turcksin, M. Kronbichler, and W. Bangerth, WorkStream – A Design Pattern for Multicore-Enabled Finite Element Computations, 2017

function color(conflicts, algorithm, elements=1:_numelements(conflicts))

Performs graph coloring using the specified algorithm.

Arguments

• conflicts: The conflict representation.
• algorithm: The coloring algorithm to use (e.g., DSATUR, Greedy).
• elements: The elements to consider during coloring (default: all elements).

Returns

A vector of vectors, where each inner vector represents a color (i.e., a set of elements with the same color). Elements in the same color do not have any conflict. The colors are sorted such that the number of their members decrease.

This function implements a generic coloring workflow that can be used with different algorithms, such as DSATUR and Greedy.

color(conflicts; algorithm=Workstream(DSATUR()))

Colors the elements in the conflict representation such that elements in the same color do not have any conflicts.

Arguments

• conflicts: The conflict representation.
• algorithm: The coloring algorithm to use. Defaults to Workstream(DSATUR()).

Returns

• A Vector{Vector{Int}} where each inner Vector represents the elements of one color.

function colorzones(conflicts, zones, algorithm)

Colors the elements within each zone using the specified algorithm.

Arguments

• conflicts: The conflict representation.
• zones: A vector of sets, where each set represents a zone.
• algorithm: The coloring algorithm to use (e.g., DSATUR, Greedy).

Returns

A vector of vectors of vectors, where each innermost vector represents a color class within a zone.

This function applies the color function to each zone independently, using the specified algorithm to color the elements within that zone.

conflictgraph

function conflictmatrix(X; kwargs...)

Computes a sparse matrix as a conflict representation.

Arguments

• X: An object that supports the conflicts function.
• kwargs...: Additional keyword arguments that are passed to the conflicts function.

Returns

A sparse matrix representing the conflicts between elements, where each entry (i, j) represents a conflict between elements i and j. Note that this matrix is symmetric.

function conflicts

conflicts(f::PassThroughConflictFunctor; kwargs...)

Returns the elements, conflicts, and conflict IDs of the functor.

function gather(oddcoloredzones, evencoloredzones)

Gathers and combines the colors of the odd and even zones.

Arguments

• oddcoloredzones: A vector of vectors, where each inner vector represents a color class within an odd zone.
• evencoloredzones: A vector of vectors, where each inner vector represents a color class within an even zone.

Returns

A vector of vectors, where each inner vector represents a combined color with elements from both odd and even zones. The colors are sorted in decreasing order by the number of their members.

This function works by first gathering the colors within each set of zones (odd and even) using the gather function, and then combining the results. The combined colors are then sorted in decreasing order by the number of their members.

function gather(coloredzones)

Gathers elements from all zones to create larger colors.

Arguments

• coloredzones: A vector of vectors, where each inner vector represents a color class within a zone.

Returns

A vector of vectors, where each inner vector represents a color class with elements from all zones. The colors are sorted in decreasing order by the number of their members.

This function works by first selecting the zone with the most colors (the "master zone") and using its colors as the initial set. It then iterates over the remaining zones, appending their colors to the corresponding colors in the master zone. Finally, the colors are sorted in decreasing order by the number of their members.

function initializealgorithminfo(conflicts, elements, ::DSATUR)

Initializes the algorithm-specific information for the DSATUR coloring algorithm.

Arguments

• conflicts: The conflict representation.
• elements: The list of elements to be colored.
• ::DSATUR: The DSATUR algorithm specifier.

Returns

A named tuple containing the following fields:

• degrees: A vector of integers representing the degree of each element (i.e., the number of neighbors).
• saturations: A vector of integers representing the saturation of each element (i.e., the number of colors already assigned to its neighbors), initialized to zero.

This function is used to set up the initial state of the DSATUR algorithm, which relies on the degrees and saturations of the elements to make coloring decisions.

function initializealgorithminfo(::Any, ::Any, ::Greedy)

Initializes the algorithm-specific information for the Greedy coloring algorithm.

Arguments

• ::Any: Unused arguments (placeholders for other algorithms).
• ::Any: Unused arguments (placeholders for other algorithms).
• ::Greedy: The Greedy algorithm specifier.

Returns

nothing, indicating that no additional information is needed for the Greedy algorithm to make coloring decisions.

function noconflicts(s::SparseMatrixCSC)

Checks if there are no conflicts in the given sparse matrix, which is used as a conflict representation.

Arguments

• s::SparseMatrixCSC: The sparse matrix to check.

Returns

true if there are no conflicts (i.e., the matrix has no non-zero entries), and false otherwise.

function node(element, elementid, algorithminfo, ::DSATUR)

Creates a new node for the DSATUR coloring algorithm.

Arguments

• element: The element to be represented by the node.
• elementid: The local ID of the element.
• algorithminfo: The named tuple containing the algorithm-specific information (degrees and saturations).
• ::DSATUR: The DSATUR algorithm specifier.

Returns

A new DSATURNode instance with the following fields:

• elementid: The global ID of the element (note: this field is actually set to the element itself, not the elementid).
• degree: The current degree of the element.
• saturation: The current saturation of the element.

function node(element, ::Any, ::Any, ::Greedy)

Creates a new node for the Greedy coloring algorithm.

Arguments

• element: The element to be represented by the node.
• ::Any: Unused arguments (placeholders for other algorithms).
• ::Any: Unused arguments (placeholders for other algorithms).
• ::Greedy: The Greedy algorithm specifier.

Returns

A new node instance representing the element, which is used by the Greedy algorithm to make coloring decisions.

Note: The Greedy algorithm does not require any additional information beyond the element itself, so the node is created with only the element.

function nodetype(::DSATUR)

Returns the node type used by the DSATUR coloring algorithm.

Arguments

• ::DSATUR: The DSATUR algorithm specifier.

Returns

The DSATURNode type, which represents a node with an element ID, degree, and saturation.

function nodetype(::Greedy)

Returns the node type used by the Greedy coloring algorithm.

Arguments

• ::Greedy: The Greedy algorithm specifier.

Returns

The GreedyNode type, which represents a node used by the Greedy algorithm to make coloring decisions.

numcolors(c)

Return the number of distinct colors used in the coloring.

Arguments

• c: A coloring object representing a coloring of a graph or similar structure, where elements are grouped by color.

Returns

• An integer representing the number of distinct colors used in the coloring.

function partition(conflicts)

Partitions the elements into two sets of zones: even and odd zones.

Arguments

• conflicts: The conflict representation.

Returns

A tuple of two vectors of sets, where each set represents a zone. The first vector contains the odd zones, and the second vector contains the even zones.

The partitioning is done such that there are no conflicts between elements of an odd zone and elements of another odd zone (and similarly for even zones). However, there may be conflicts between elements within the same zone.

function reverseconflicts(elements, conflicts, conflictids)

Reverses the conflict indices and elements.

Arguments

• elements: The elements.
• conflicts: A function that takes an element and returns its conflict indices.
• conflictids: The conflict IDs.

Returns

A vector of vectors, where each inner vector represents the elements which have a certain conflict index.

function updateinfo!(::Any, elementid, algorithminfo, ::DSATUR)

Updates the algorithm-specific information for the DSATUR coloring algorithm after an element has been colored.

Arguments

• ::Any: Unused argument (a placeholder for other algorithms, that need the global elementid).
• elementid: The local ID of the element that has been colored.
• algorithminfo: The named tuple containing the algorithm-specific information (degrees and saturations).
• ::DSATUR: The DSATUR algorithm specifier.

Returns

The updated algorithminfo named tuple.

This function updates the degree and saturation of the colored element by:

• Decrementing its degree by 1, since once of its neighbors is no longer available for coloring.
• Incrementing its saturation by 1, since a color has been assigned to one of its neighbors.

function updateinfo!(::Any, ::Any, ::Any, ::Greedy)

Updates the algorithm-specific information for the Greedy coloring algorithm.

Arguments

• ::Any: Unused arguments (placeholders for other algorithms).
• ::Any: Unused arguments (placeholders for other algorithms).
• ::Any: Unused arguments (placeholders for other algorithms).
• ::Greedy: The Greedy algorithm specifier.

Returns

nothing, indicating that no update is needed for the Greedy algorithm, as it does not maintain any internal state.

function _neighbors(g::AbstractGraph, element::Int)

Returns the neighbors of a given element, i.e. the elements that have a conflict with the element, in the AbstractGraph, which is used as a conflict representation.

Arguments

• g::AbstractGraph: The graph.
• element::Int: The element for which to retrieve the neighbors.

Returns

The neighbors of the given element.

function _numelements(g::AbstractGraph)

Returns the number of elements in the graph.

Arguments

• g::AbstractGraph: The graph.

Returns

The number of elements in the graph.

function conflictgraph(X; kwargs...)

Creates a conflict graph as a SimpleGraph from Graphs.jl.

Arguments

• X: An object that supports the conflictmatrix function.
• kwargs...: Additional keyword arguments that are passed to the conflictmatrix function.

Returns

A SimpleGraph representing the conflict graph.

This function works by first computing the conflict matrix using the conflictmatrix function, and then creating a SimpleGraph from the matrix.

function noconflicts(g::AbstractGraph)

Checks if there are no conflicts in the given graph.

Arguments

• g::AbstractGraph: The graph to check.

Returns

true if there are no conflicts (i.e., there are no edges in the graph), and false otherwise.