solver_dsatur: DSatur Solver
In caranha/EvoGCP: Evolutionary Computation Tools for the Graph Coloring Problem

Description Usage Arguments Details Value Examples

Solves the 3-GCP problem using DSatur heuristic

1	solver_dsatur(G, nfe, args)

G

the graph to be solved, represented by a list where G$V is the number of nodes, G$E is a |E|x2 edge matrix, G$adj is the adjacency list.

nfe

the number of iterations allowed

args

a list with arguments for the method. The list must contain the following names:

weight: List of weights, which will be used to build a permutation of vertices.
return_satur: Boolean, if the final saturation degrees should be returned (used by some methods like heuristical swap)

DSatur heuristic function, adapted from the description by Daniel Brelaz, "New methods to Color the Vertices of a Graph" Communications of the ACM. 22(4): 251?..256 (1979).

The algorithm follows 5 steps: 1. Arrange the vertices by decreasing order of degrees (or any given permutation). 2. Color a vertex of maximal degree with color 1. 3. Choose a vertex with a maximal saturation degree. 4. Color the chosen vertex with the least possible (lowest numbered) color. 5. If all the vertices are colored, stop. Otherwise, return to 3.

a list containing the total number of violations of the best coloring, the best coloring (a V vector of 1:3) and the total number of evaluations spent