[Nauty-list] labelg with coloured graphs

Matthew Skala mskala at cs.umanitoba.ca
Sat May 5 01:53:23 EST 2012

I'm processing collections of coloured graphs, in the range of tens to
hundreds of millions of them at a time.  The graphs are small, typically
between 9 and 14 vertices each; the vertices have at most four colours.
I'd like to use labelg or something like it to canonically label them
while respecting the colours.

I'm aware of the -f option to labelg, which sets a partition of the point
set, but it appears to allow setting a single colouring that will be
global to the entire run of labelg.  I have in principle a different
colouring for every graph, with a currently-unknown amount of duplication
of colourings between different input graphs in any given collection.

Running labelg separately for every graph seems like it would cost too
much in process invocation/termination.  It seems like a reasonable thing
to do would be to separate my input graphs into slices based on the
colourings, run labelg once for each distinct colouring, and then merge
the results again; but that seems like it will be cumbersome and
error-prone.  A more ambitious approach, which may well be what I end up
doing, would be to invent my own extension of graph6 format with both the
graph and the colouring specified on each line, and write my own
labelg-like program that would process that format.

I suppose another option might be to manually relabel my graphs, and
insert extra isolated vertices, such that I end up with the same -f string
being applicable to every graph in the file.  That will drastically
increase the number of vertices in the graphs, but in a simple enough way
that maybe it won't slow nauty down very much, and because of involving
less splitting and joining of "slice" files, it might actually be worth it
in terms of human labour and the opportunity for making mistakes.

Do list readers have any suggestions on dealing with this situation?
Matthew Skala
Postdoctoral Fellow, University of Manitoba
mskala at cs.umanitoba.ca

More information about the Nauty mailing list