Implement colour refinement

[Joseph-Edwards]

Colour refinement is an algorithm that takes a graph $G = (V, E)$, and returns a colouring $C \colon V \to \mathbb{N}$ of the vertices such that, for any pair of vertices $u, v \in V$ with the same colour (i.e. $C(u) = C(v)$ ), the neighbours of $u$ are coloured in the same way as the colours of $v$.

This algorithm has many applications, notably relating to graph isomorphism testing. It would be good to have an implementation in the Digraphs package.

Useful references

• The ideas are presented very nicely in sections 15.1 and 15.2 of this book chapter by Grohe et al.
• The colour refinement algorithm was the main focus of this master's dissertation. In particular, there is a pseudocode implementation of colour refinement in Algorithm 2.2.1, and an accompanying Python implementation available here.
• There is a JavaScript implementation in this repository. To see it in action, go here.