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.
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.