# 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 | Yes^{3} |
No?^{1} |
Yes | Yes | Yes | Python |

nauty | Yes | No | Yes | Yes^{2} |
Yes | No | C |

traces | Yes | No | No | Yes^{2} |
Yes | No | C |

bliss | Yes | No | Yes | Yes | Yes | No | C++, Java, Python |

Arnborg et al. | Yes | No^{4} |
No^{4} |
No^{4} |
No^{4} |
No^{4} |
- |

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:**

- 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.
- See the manual or this mailing list.
- Under the assumption that modality is just the named used in the Scott codebase for edge labels.
- Extending the approach to support these seems fairly easy as they are already used internally by the algorithm.