Overview of canonization algorithms

The following table presents an overview of found canonization algorithms so far.

Algorithm Canonization Edge Labels Directed Graph Vertex Labels Self Loops Parallel Edges Language
Scott Yes Yes3 No?1 Yes Yes Yes Python
nauty Yes No Yes Yes2 Yes No C
traces Yes No No Yes2 Yes No C
bliss Yes No Yes Yes Yes No C++, Java, Python
Arnborg et al. Yes No4 No4 No4 No4 No4 -
Grohe et al. Yes No No No No No -
Arvind et al. Yes No No Yes No No -
Wiebking Yes No? No? No? Yes? No? -
nishe Yes No Yes Yes Yes No C++
conauto No No Yes Yes? No? No? C
saucy No No? No? - - - ?
GI-EXT No No? No? - - - C++

Note that some algorithms (e.g. bliss & nauty) work with a coloured graph, introducing an extra function assigning a colour to each vertex. This is essentially the same as assigning vertex labels and does not seem to refer to a graph colouring.

Note that it is possible to rewrite a graph with edge labels into a graph without. This will typically increase the size of the graph, but technically means that the algorithm can deal with labelled input graphs. For the comparison table we do not count this way of dealing with labels as it will likely be less performant.

Note that if we keep our key CPQ core apart we might be able to just test for isomorphism directly against this key CPQ core essentially using the CPQ as the canonical representation key. Algorithms marked with a “No” for canonization only do isomorphism testing.

Footnotes:

  1. Extending the approach to directed graphs is an open research question in the original paper, but the codebase has support for directed edges already it seems.
  2. See the manual or this mailing list.
  3. Under the assumption that modality is just the named used in the Scott codebase for edge labels.
  4. Extending the approach to support these seems fairly easy as they are already used internally by the algorithm.