search

AlgebraicJulia / Catlab.jl

A framework for applied category theory in the Julia language
https://www.algebraicjulia.org
MIT License
608 stars 58 forks source link

Integrate ACSets.NautyInterface #860

Open kris-brown opened 11 months ago

kris-brown commented 11 months ago

ACSets now has integration with nauty.c - allowing for very fast (if you're not on Windows) computation of representatives of the isomorphism class for an ACSet.

Catlab should extend this functionality to have canonical representatives for other derivative data structures, e.g. ACSetTransformations, Diagrams, Slices. It might also be the case that this is faster at computing isomorphisms between two ACSets than backtracking search.

This would be a big algorithmic speedup in algorithms like maximum common subacset and enumerating subobjects. Another place to use this is in the tests. E.g. right now we have:

colim = pushout(α, β)
@test src(ob(colim)) == [1,1]
@test tgt(ob(colim)) == [2,1]
@test subpart(ob(colim), :vlabel) == [:u, :v]
@test subpart(ob(colim), :elabel) == [:e, :f]

This is a bit evil because the pushout is defined only up to isomorphism. Rather the resulting Span of the pushout should be compared (up to isomorphism) with some expected Span.