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.

This algorithm often creates less colors than the Greedy algorithm. The colors are not guaranteed to be balanced.

Usage example

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=DSATUR())

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 1302 elements
Color 2 has 1152 elements
Color 3 has 748 elements
Color 4 has 12 elements