Simple wrapper for using
nauty, a graph isomorphism package, with
LightGraphs in Julia. Requires
gcc and a POSIX style build environment.
Currently under development. Interface may change / break by the day.
Check if two graphs are isomorphs of each other:
baked_canonical_form(g1).canong == baked_canonical_form(g2).canong
using Nauty BenchmarkTools.@btime LightGraphs.Experimental.has_isomorph(g1,g2,alg=NautyAlg())
If you need to provide custom options to nauty, use
densenauty(g, optionblk(optionblk_mutable(DEFAULTOPTIONS_GRAPH))), but be aware that it is around 2-4x slower than using baked in options as Julia cannot optimise across the
C boundary. Consider baking your own.
- Friendlier return types
- NautyGraph -> LightGraph
- MetaGraph -> (NautyGraph, labels, partition)
- isomorphOf() / congruence operator
- Documentation (documenter.jl)
- Pick a licence
- More comprehensive tests if we feel like it
- Build options
MAXN=WORDSIZEoptimisation effect. Build nauty twice if it matters, once with MAXN=0 if not
- Use baked_canonical_form automatically
canonical_isomorph(g: LightGraph) -> g' canonical_isomorph(g: ColouredGraph) -> g' - We'll have to use the relabelling information to make g'
isisomorph(g1, g2) -> bool operator overload (congruence sign?)
nauty(g, options) -> all the stuff nauty gives