search

AlgebraicJulia / Catlab.jl

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

Isomorphism testing of wiring diagrams #57

Closed epatters closed 3 years ago

epatters commented 4 years ago

We should have a procedure to test for isomorphism of wiring diagrams and, when an isomorphism exists, exhibit the corresponding matchings of boxes and wires.

A possible approach is to first find an isomorphism of the underlying directed graphs, using existing software, and then check if the induced map on boxes is a wiring diagram isomorphism. At the time of this writing, LightGraphs has experimental support for isomorphism testing.

This would be a good first issue for someone who likes graph algorithms. It should require only a basic knowledge of Catlab's wiring diagram API.

epatters commented 4 years ago

We could also enlist the help of nauty, which has experimental Julia bindings via Nauty.jl. According to the manual, "nauty can also handle directed graphs and loops, but Traces currently only handles simple undirected graphs."

Besides checking isomorphism, nauty also produces canonical labelings, which could be used to put wiring diagrams into normal form.

epatters commented 3 years ago

Now that #401 is implemented and DWDs are ACSets, we basically get this one for free, although we should not expect performance anywhere near a specialized package like nauty.

To finish this issue, we should add a function is_isomorphic. IIRC, some of the DWD unit tests would benefit from having this function.