## NautyGraphs.jl

I am excited to announce my first package NautyGraphs.jl, which is now available through the general registry.

NautyGraphs is a Julia interface to the famous graph isomorphism library *nauty* by Brendan McKay. NautyGraphs can be used to perform efficient isomorphism checking, canonical labeling, and hashing of vertex-labeled graphs.

Moreover, NautyGraphs is fully compatible with the Graphs.jl API. This makes it easy to create and modify NautyGraphs through familiar syntax, convert between the graph formats, or use NautyGraphs with a large library of existing graph algorithms. NautyGraphs.jl has been partly inspired by the (now dormant) Nauty.jl package.

### How it Works

NautyGraphs exports two main types: `NautyGraph`

and `NautyDiGraph`

. These graph types can be created, accessed, and modified through the Graphs.jl API, but they represent their underlying graphs in bit array form, the format required by nauty. Therefore, a NautyGraph can be passed directly to nauty, without any conversion overhead. Through nautyâ€™s canonical labeling procedure, NautyGraphs can be hashed, which makes it possible to efficiently filter large collections of graphs for isomorphism.

There are two main methods exported by NautyGraphs:

`is_isomorphic(g1, g2)`

checks two NautyGraphs for isomorphism`ghash(g)`

hashes the canonical version of a graph, so that (up to hash collisions)`ghash(g1) == ghash(g2)`

is true if and only if`is_isomorphic(g1, g2)`

.

It is also possible to use `nauty(g)`

directly to get more information about a graphâ€™s automorphism group.

For more information, please check out NautyGraphs on GitHub.

### Rough Edges

NautyGraphsâ€™ biggest open issue is that it is currently not available on Windows. This should hopefully be fixed someday by making Windows binaries for nauty available through nauty_jll.

There are a number of other minor issues or missing features, from detailed documentation, supporting nautyâ€™s sparse graphs format, handling of automorphism group information, or simply improving the performance of basic graph methods. I welcome any raised issues or pull requests!

### Alternatives

NautyGraphs is designed to be a lightweight interface to nauty that works with Graphs.jl. There are other ways to access nauty, or perform graph isomorphism checks from within Julia. Some examples I know of:

- Nauty.jl: An older wrapper for nauty. Has baked-in options for nauty to increase performance. Can convert LightGraphs to nauty format.
- VF2 algorithm in Graphs.Experimental. Can perform graph isomorphism, subgraph matching and more. No graph hashing (as far as I know). Performs better than nauty on some graphs, but worse on others. NautyGraphs.jl comes with a benchmark file to compare against VF2. NautyGraphs usually performs much better on larger graphs, while VF2 is faster on small and sparse graphs. Additional optimizations and support for nautyâ€™s sparse graph format should lead to even better performance in the future.

Since this is my first Julia package, Iâ€™d be very grateful for any comments or feedback!