Vertex Colour Respecting canonical labelling

[ChrisJefferson]

Hi,

The current CanonicalLabelling in Digraphs does support coloured vertices, but doesn't "respect" the colours (that is, it doesn't only permute colours inside their colour class).

This means, unlike finding the automorphisms, you can't restrict the permutation you get from CanonicalLabelling to one colour class, as it can map things out of the colour class.

I think this would be useful for various things, for example when people build a graph to represent some more complex object, (such as a matrix, or a multidigraph, for example), then we often have one colour class which represents the set $\Omega$ we are permuting, and we would like a permutation which just acts on that colour class, so we can interpret the canonical image on $\Omega$ (I can explain that more fully if that doesn't make sense).

[ChrisJefferson]

I've just thought about this a bit more.

It's possible the reason this isn't present is there isn't a published algorithm to do it (I don't know if Nauty or Bliss do this?). If there isn't an algorithm, then I'm fairly sure I know how to do it, but I probably don't have time to fully integrate it into Digraphs, so if there is interest on working on it, and it isn't published somewhere already, let me know and I'm happy to talk about how (I think!) to do it.