Currently I am looking into register allocation using graph colouring
(also see Chaitin’s paper on the subject). The graph colouring problem also occurs when
trying to colour countries in a political world map where adjacent countries must have different colours.
I thought it would be interesting to try a minimal implementation in Scheme.
Feel free to suggest improvements in the comment section below .
A (undirected) graph is usually represented by a list of nodes (vertices) and a list of edges.
If there are no insular nodes, a list of edges is sufficient.
In Scheme (here GNU Guile implementation) one can do this as follows.
The graph can be visualised on the command line using Graphviz and ImageMagick as follows.
The following helper function graphviz uses a system call to display a graph from within the REPL.
One can get the nodes of the graph by extracting all elements and
suppressing any duplicates. The definition of delete-duplicates is part of SRFI-1
(Scheme Request for Implementation 1).
The adjacency list of a node is simply the list of nodes of the sub-graph obtained by filtering
for edges connecting to this node.
Chaitin’s graph coloring algorithm works by successively removing nodes with a low adjacency count from the graph. Removing a node from our graph can be done as follows.
Using the argument of the minimum one can determine the node with lowest adjacency count.
Now one can recursively remove the node with lowest adjacency count and then assign colours starting with the last node and working backwards.
If an adjacent node has a colour already, another colour must be used.
And here is an example of coloring a graph with a few more nodes.