(basically speaking) no-one does Graph Isomorphism with VF2, they use (as you say) Nauty, or some system which derives from that.

Things like VF2 can be used for sub-graph isomorphism (and various variants of that problem). Nauty (and this paper) are useless for solving that problem.

I work in this area, and it's interesting (to me at least) that you would imagine the algorithms for graph isomorphism and sub-graph isomorphism would be quite similar and they really aren't.

Still, the more well known graph libraries seem to avoid Nauty, probably because it is not that easy to implement. From a quick search: - NetworkX: VF2 - JGraphT: VF2 and some newer algorithm called "color refinement algorithm" - seems to resemble Nauty - BGL: VF2 - SnapGraph: Does not seem to contain graph isomporphism - Igaph: Bliss and VF2

So are you convinced that Nauty is still the best thing that we have nowadays? I was looking at the paper last summer with the intention to implement it for Julia, but then got sidetracked with other stuff. Maybe I should resume that.

Nauty is I think the best trade-off. The improvements in Saucy and Bliss (which have mostly been added to Nauty now) are useful.

The basic algorithm isn't that hard -- I have a few implementations lying around (nothing in Julia). Traces is better, but is much harder to implement and it isn't clear the improvement is worth it for someone implementing from scratch.

There are some improvements, particularly for graph isomorphism (as opposed to automorphism), but the basic algorithm framework is the same.

As you work in this area, is there any such thing as a clique bestiary? I spend a lot of time looking at large-ish graphs in Gephi but it's hard to find tools/code about shapes/structures rather than quantitative analysis of degree or betweenness. Not a scientist, it's a means to an end for domain exploration for me.