Google Summer and Partition Backtrack

First of all I would like to thank Google for funding my summer work on Sage.

The algorithm used in sage.coding.binary_code and sage.graphs.graph_isom is based on Brendan McKay's masters thesis. The algorithm computes, amongst other things, the automorphism group of the combinatorial structure in question. The method of the algorithm is to traverse a tree consisting of successively finer partitions (e.g. ({0,1},{2,3},{4}) is finer than ({0,1,2,3},{4})...) whose leaves are discrete partitions (such as ({1},{0},{3},{2},{4})). The two key steps are refinement and pruning. Refinement is how you get from one node in the tree to any of its successors (i.e. how to go from a given partition to one finer). For example, one way (what we do in the above modules) would be to pick a vertex of the graph, put it in its own partition, and use the number of edges between cells in the partition to further refine the partition. Pruning is making use of the observation that symmetries of the object being studied translate into symmetries of the tree being traversed, so that large chunks of the tree need not be searched, being equivalent to parts already searched.

My first goal is to generalize this algorithm by making the refinement method one of the arguments to the function. This would replace two copies of the same algorithm in different places with one copy that would be much easier to plug other questions into. For example, the algorithm would work with any "subgroup type problem," in which one has a permutation group G, and a property P of permutations of G such that the permutations in G satisfying P are a subgroup (for the automorphism group of a graph, G = S_n and P is obvious). This would allow us to find set stabilizers, centralizers and normalizers of elements, upper central series, group intersections, and automorphism groups. The algorithm would also work with "canonical representative type problems," such as finding a unique representative of a conjugacy class or an orbit of some group action.

Once the algorithm is generalized, other refinement procedures can also be implemented, even for the same familiar problem of graphs. For example, the technique described in this paper always chooses the optimal refinement, which makes the actual refinement process much longer at each step, but the search tree exponentially smaller for certain classes of sparse graphs for which nauty's performance is bad. The strategy described here works well when the symmetries themselves are sparse, which is to "check for the condition that all the differences between partitions exist... only in the singletons, and [to] short-circuit... paths to leaf nodes when the condition" holds, which it does frequently for graphs with sparse symmetry.