search

kris-brown / CombinatorialEnumeration.jl

Enumerate models of finite limit sketches up to isomorphism
MIT License
4 stars 0 forks source link

Take advantage of nauty's orbits #4

Open kris-brown opened 2 years ago

kris-brown commented 2 years ago

There are many points where we consider all possible assignments of a foreign key (such as branching on an unassigned one, or at many points in the colimit code e.g. detecting if two components are connectable via some assignment).

However, many of these assignments are equal up to symmetry, captured by the orbits produced by CSetAutomorphisms.jl. We could greatly reduce some branching factors by only considering distinct orbits.

It would be helpful to address this issue though.

kris-brown commented 2 years ago

As a makeshift solution, this being addressed by creating a premodel after each branching (but before the constraints are then propagated) and quotienting by nauty. This is less than ideal because it requires running nauty many more times, when in theory it just needs to be run once before branching.