# Vertex colouring with backtracking in C

The vertex colouring problem is to colour the vertices of a graph in such a way that no two adjacent vertices are the same colour. The decision problem of whether a graph can be coloured in m or fewer colours is NP-complete.

Although the problem is intractable, a bactracking algorithm can be used to reduce the number of colourings that need to be tried. The algorithm works by colouring the vertices one at a time, and backtracking if at any point it becomes impossible to colour the next vertex differently from all of its neighbours.

typedef void(*vertex_colouringfn)(const unsigned int *, size_t);

static unsigned int promising(int i, const unsigned int **adjmat, const unsigned int *colours)
{
int j;
unsigned int ok = 1;

for (j = 0; j < i && ok; j++) {
if (adjmat[i][j] && colours[i] == colours[j]) {
/* Adjacent vertex is the same colour */
ok = 0;
}
}
return ok;
}

static void vertex_colouring_recursive(int i, const unsigned int **adjmat, size_t len,
unsigned int *colours, unsigned int m, vertex_colouringfn fun)
{
unsigned int colour;

if (promising(i, adjmat, colours)) {
if (i == len - 1) {
/* Coloured every vertex successfully */
fun(colours, len);
}
else if (i < (int)len - 1) {
/* Try every colour for the next vertex */
for (colour = 0; colour < m; colour++) {
colours[i + 1] = colour;
vertex_colouring_recursive(i + 1, adjmat, len, colours, m, fun);
}
}
}
}

void vertex_colouring(const unsigned int **adjmat, size_t len, unsigned int m,
vertex_colouringfn fun)
{
unsigned int *colours = calloc(len, sizeof(unsigned int));
if (colours == NULL) {
return;
}
vertex_colouring_recursive(-1, adjmat, len, colours, m, fun);
free(colours);
}


This is an example program with a small graph and m = 3:

static void print_colouring(const unsigned int *colours, size_t len)
{
unsigned int i;
for (i = 0; i < len; i++) {
printf("%d ", colours[i]);
}
printf("\n");
}

int main(void)
{
unsigned int v0[] = {0, 1, 1, 1, 0};
unsigned int v1[] = {1, 0, 1, 0, 1};
unsigned int v2[] = {1, 1, 0, 1, 1};
unsigned int v3[] = {1, 0, 1, 0, 1};
unsigned int v4[] = {0, 1, 1, 1, 0};
const unsigned int *adjmat[] = {v0, v1, v2, v3, v4};
const size_t len = sizeof(adjmat) / sizeof(unsigned int*);
const unsigned int m = 3; /* Number of colours */
vertex_colouring(adjmat, len, m, print_colouring);
return 0;
}