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

Optional visual trace of backtracking search tree #814

Open kris-brown opened 1 year ago

kris-brown commented 1 year ago

This PR makes three improvements to homomorphism search:

  1. The main one is that an optional BacktrackingTree data structure is added to the BacktrackingState. If debug_homomorphisms(...) is called rather than homomorphisms(...), then a list of homomorphisms in addition to a BacktrackingTree are returned as a pair. This can be viewed in graphviz (see below).

  2. find_mrv_elem picks which C-Set part to branch on, attempting to minimize the branching factor. It does this by finding, for each part, how many valid assignments there are. Previously it just counted how many valid assignments, rather than remembering what these were - this is fixed by just using filter rather than count. I would expect this to have a positive performance impact, but this hasn't been benchmarked.

  3. When a successful assignment is found, there is a bit of logic to extract an ACSetTransformation from the BacktrackingState. This has now been factored into a function get_hom.

kris-brown commented 1 year ago

Example of the search tree graphviz output on a schema with Triangles, Edges, and Vertices (note the hover text). The vertices are labeled by the parts of the domain ACSet, and the edges indicate the assigned part in the codomain ACSet.

Screenshot 2023-06-21 at 6 42 42 PM
kris-brown commented 1 year ago

(TODO: Rebase and then tag Evan as a reviewer)

github-actions[bot] commented 1 year ago

Review Checklist

Does this PR follow the development guidelines? Following is a partial checklist:

Tests

Documentation

Other