A reliable idiomatic nauty wrapper

[mxhbl]

A reliable idiomatic nauty wrapper

The C library nauty provides advanced and efficient implementations of graph canonization and isomorphism algorithms. The NautyGraphs.jl package already exists and provides a barebones wrapper for nauty. A lot of this work probably will not be directly in the Graphs.jl repository.

• Fast conversion and/or views between NautyGraphs.jl types and the C structures of nauty, including both dense (bit vector) and sparse (adjacency list) graph formats.
• Complete Graph API support for the NautyGraphs.jl types (so that NautyGraphs.jl types can be used in all already existing Graph.jl algorithms that do not peek behind the API)
• User-friendly handling of graph information computed by nauty, including properties of the graph automorphism group and detection of graph isomorphisms
• use GraphsInterfaceChecker.jl in the test suite
• Dispatch from operations defined in Graphs/GraphsMatching/GraphsOptim to nauty implementation. For instance if there is a pre-existing Graphs.some_interesting_property(::AbstractGraph) there should now be a new method defined in NautyGraphs some_interesting_property(g::AbstractGraph, ::NautyAlgorithm) that dispatches to the C implementation. It should convert the g argument to NautyGraph if necessary.
• If there is an algorithm defined in nauty that does not exist yet in Graphs.jl, it should be declared in Graphs.jl (just a function with docs but no methods), together with an error hint that NautyGraphs.jl is necessary.
• Proper tests and documentation.
• PRs on this topic have to be submitted with clean git histories and well compartmentalized for ease of review.

Required skills: familiarity with the Graphs.jl API, the nauty API, and understanding of the Julia-C interface

Reviewer: any Graphs.jl member with merge rights

Duration: 3 months

[BenraouaneSoufiane]

Hello, can I work on this?

[Krastanov]

Hi, @BenraouaneSoufiane
This is already reserved and assigned to mxhbl. But there are a few similar bounties for other packages (igraph, very_nauty, networkx). If you are interested, just ping me on the corresponding issues. If you do so, make sure to describe a bit of your background to vet that you have been exposed to the necessary skills.

[BenraouaneSoufiane]

Hi, @BenraouaneSoufiane This is already reserved and assigned to mxhbl. But there are a few similar bounties for other packages (igraph, very_nauty, networkx). If you are interested, just ping me on the corresponding issues. If you do so, make sure to describe a bit of your background to vet that you have been exposed to the necessary skills.

Hello again, thank you for your reply, I didn't found open issues in igraph & very_nauty

[Krastanov]

see here https://github.com/JuliaGraphs/Graphs.jl/issues?q=is%3Aissue%20state%3Aopen%20label%3Abounty%20-label%3Abounty%3Areserved

[Gutopro]

Hi @mxhbl is this still open? And can it be Assigned to me?

[mxhbl]

Hi, thanks for leaving a comment; a status update on this is long overdue.

I believe this issue can be closed in the very near future. Basic functionality of NautyGraphs.jl (https://github.com/JuliaGraphs/NautyGraphs.jl) has been complete since last summer (JuliaGraphs/NautyGraphs.jl#25). Support for the sparse graph format was a bit trickier than I injtially thought; but I finished most work on this last week and that should be merged in the coming days (JuliaGraphs/NautyGraphs.jl#48). Regard the declaration of algorithms in Graphs.jl I am actually not sure what should be done. Since NautyGraphs.jl depens on Graphs.jl the extra algorithms will be available upon loading the wrapper anyway (see also #418)

It would be good if @Krastanov could weigh in on what remains to be done or if this issue can be closed.

[Krastanov]

The main outstanding thing is making the NautyGraphs.jl algorithms available to Graphs.jl. Check the README of IGraphs.jl for an example https://github.com/JuliaGraphs/IGraphs.jl/?tab=readme-ov-file#alternatives-to-graphsjl-algorithms

Semi-arbitrarily, let's say the following is necessary:

• Create a NautyGraphs.NautyAlg type (probably without any fields).
• Create a NautyGraphs.nautyalg_methods function that returns all Graphs.jl function names for which NautyGraphs provides custom methods.
• For all these functions create a new method like Graphs.diameter(g::AbstractSimpleGraph, ::NautyAlg) = diameter(NautyGraph(g)) that provide a dispatch to the NautyGraphs algorithm for any graph type. Depending on the situation, the signature might not be AbstractSimpleGraph, it might be something else.