Practical graph isomorphism, II (2014)
Link: https://www.sciencedirect.com/science/article/pii/S0747717113001193
Abstract: We report the current state of the graph isomorphism problem from the practical point of view. After describing the general principles of the refinement-individualization paradigm and proving its validity, we explain how it is implemented in several of the key implementations. In particular, we bring the description of the best known program nauty up to date and describe an innovative approach called Traces that outperforms the competitors for many difficult graph classes. Detailed comparisons against saucy, Bliss and conauto are presented.
This is the most recent paper for the combination of the nauty and traces papers. The manual for the software can be found here: nauty and Traces User’s Guide (Version 2.7). Nauty is the software that is used internally by popular larger packages such as Magma, Sage and GAP.
Nauty has a mailing list with a lot of potentially useful information. Some potentially relevant threads are listed below:
- digraph–>graph
- labelg with coloured graphs
- Labeled graphs
- Can we do colored edges in nauty?
- canonical label for directed graphs
- Re: nauty-list digest, Vol 1 #116 - 3 msgs
It is worth noting that a lot of people in the mailing list state that running nauty on directed graph directly is slower than converting your graph to an undirected graph and then running nauty on that. A lot of these statements are over a decade old at this point however so this might not apply to the current version anymore. But this is worth keeping in mind when experimenting with nauty.
The following wordpress page by Derrick Stolee has some useful tips for working with nauty.