Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Isomorphism testing of wiring diagrams #57

Closed
epatters opened this issue Nov 23, 2019 · 2 comments · Fixed by #413
Closed

Isomorphism testing of wiring diagrams #57

epatters opened this issue Nov 23, 2019 · 2 comments · Fixed by #413

Comments

@epatters
Copy link
Member

epatters commented Nov 23, 2019

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
Copy link
Member Author

epatters commented Jan 15, 2020

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
Copy link
Member Author

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant