Workstream

The Workstream coloring algorithm is presented in [1].

The Workstream coloring algorithm does not have the goal to create the minimal amount of colors, but is very good at creating balanced colors. Balanced colors are important for load balancing in parallel computing. The algorithm consists of the following steps:

partition
The elements are partitioned into two sets of zones: even and odd 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.
color
The colorzones colors the elements within each zone using a specified algorithm.
gather
For the even and odd zones, respectively, the gather step selects the zone with the most colors (the "master zone") and uses its colors as the initial set. It then iterates over the remaining zones, appending their colors to the corresponding colors in the master zone to create larger colors. Finally, the colors are sorted in decreasing order by the number of their members.

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

Usage example I

using PlotlyJS
using CompScienceMeshes
using BEAST
using GraphsColoring

m = meshsphere(1.0, 0.1)
X = raviartthomas(m)

conflicts = GraphsColoring.conflictmatrix(X)

colors = GraphsColoring.color(conflicts; algorithm=WorkstreamDSATUR)

facecolors = zeros(size(conflicts, 1))

for color in eachindex(colors)
    println("Color $color has $(length(colors[color])) elements")
    for element in colors[color]
        facecolors[element] = color
    end
end

p = PlotlyJS.plot(
    patch(m, facecolors; showscale=false),
    Layout(;
        scene=attr(;
            xaxis=attr(; visible=false),
            yaxis=attr(; visible=false),
            zaxis=attr(; visible=false),
        ),
    );
)

Color 1 has 810 elements
Color 2 has 809 elements
Color 3 has 801 elements
Color 4 has 794 elements

Usage example II

Instead of the DSATUR algorithm we can also use the Greedy algorithm in the color step.

colors = GraphsColoring.color(conflicts; algorithm=WorkstreamGreedy)

Color 1 has 810 elements
Color 2 has 809 elements
Color 3 has 801 elements
Color 4 has 794 elements