This C code below generates all $4$-colourings of a graph with <=31 vertices. It's a basic depth-first search, backtracking algorithm.
- It's not designed to be overly efficient, but some obvious improvements have been made. I believe there would be vastly better implementations out there (this problem screams SSE). (But my impression is that you're after a simple but effective solution.)
- It's restricted to graphs with at most 31 vertices since I use bitwise operations. On a 64-bit machine this could be increased. Otherwise, a more complicated version would be required (e.g. dividing the adjacency matrix into 4 smaller adjacency matrices).
- We can assume the vertex $0$ is coloured $0$ (this saves a run-time factor of $4$). [If you want to include the other colourings, add $+d$ too all colours, as $d$ runs over $0,1,2,3$.]
- It generates a random graph to work on initially. This will need to be edited to allow your own input.
Keep in mind that, depending on the density of your input graph, there might be gazillions of $4$-colourings, and, in such a case, no program would be able to run to completion, regardless of how good your algorithm is and how good your coding skills are. Merely iterating through all possible $4$-colourings, even with the aid of an oracle, would be too slow.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_NR_VERTICES 31
#define MAX_NR_EDGES MAX_NR_VERTICES*(MAX_NR_VERTICES-1)/2
#define VERBOSE 0
const int n=31;
/* the u-th bit of adjacency[v] is 1 whenever {u,v} is an edge in the graph */
int adjacency[MAX_NR_VERTICES];
/* colour[v] is the colour of vertex v */
int colour[MAX_NR_VERTICES];
/* a counter for the number of colourings */
int nr_colourings;
void generate_4_colourings_backtracking_algorithm(int v) {
/* attempts to use colour c for vertex v */
for(int c=0;c<4;c++) {
for(int u=0;u<v;u++) {
/* checks if there is a vertex u adjacent to v coloured c */
/* only the vertices before v have been coloured thusfar */
if((adjacency[v] & 1 << u) && colour[u]==c) { goto dont_use_this_colour; }
}
/* trying colour c for vertex v */
colour[v]=c;
if(v==n-1) {
/* found a proper colouring */
nr_colourings++;
/* if VERBOSE is set to 1, this will print the colouring to the screen */
if(VERBOSE) { printf("colouring %d: ",nr_colourings); for(int u=0;u<n;u++) { printf("%d ",colour[u]); } printf("\n"); }
}
else {
/* normal backtracking step */
generate_4_colourings_backtracking_algorithm(v+1);
}
dont_use_this_colour: ;
}
}
int main() {
if(n>MAX_NR_VERTICES) { return 0; }
/* generates a random list of edges for the graph */
srand(time(NULL));
int u;
for(int v=0;v<n;v++) {
int nr_edges=3;
for(int i=0;i<nr_edges;i++) {
do { u=rand()%n; } while (u==v);
adjacency[v] |= 1 << u;
adjacency[u] |= 1 << v;
}
}
printf("Adjacency matrix:\n"); for(int v=0;v<n;v++) { for(int u=0;u<n;u++) { printf("%d",(adjacency[v] >> u) & 1); } printf("\n"); } printf("\n");
/* finished generating random graph */
/* by symmetry, we can assume vertex 0 is coloured 0 */
colour[0]=0;
generate_4_colourings_backtracking_algorithm(1);
printf("Found %d canonical 4-colourings; %d total 4-colourings\n",nr_colourings,4*nr_colourings);
return 1;
}
