Patch #1

I submitted a patch to trac today. In it, there is a new module, sage.groups.perm_gps.partn_ref, which has a module for generic partition backtrack, tree_traversal, and a module for graph isomorphism/automorphism groups, refinement_graphs. The function search_tree in refinement_graphs is meant to ultimately replace the function of the same name in graph_isom, which should eventually become obsolete and removed. All tests that the original passes, the replacement now also passes. This is my first Google sponsored patch!

I'd like to add two notes. There were two places in graph_isom.pyx where I wasn't exactly sure what was going on, and I now have explanations for both of them:

# TODO: investigate the following line
if nu.k == -1: nu.k = 0 # not in BDM,
# broke at G = Graph({0:[], 1:[]}),
# Pi = [[0,1]], lab=False

Resolved! In fact, k should never be -1 here, and this was a false fix for a different bug (since squished). I've verified in the new version that this never ever happens.

# TODO: investigate why, in practice, the
# same does not seem to be true for hzf < k...
# BDM had !=, not <, and this broke at
# G = Graph({0:[],1:[],2:[]}), Pi = [[0,1,2]]
if nu.k < hzf: state = 8; continue

Resolved! This is similar to the last "fix"- the comments in graph_isom.pyx are wrong. hzf is the length for which indicator values line up, so for there to be an automorphism, nu must line up with zeta all the way, exactly. I've verified in the new version that != here instead does work.

Graph Isomorphism

I have just reproduced some of the graph isomorphism doctests with the new partition refinement code. Of the two files meant to replace graph_isom.pyx, one is over a thousand lines and one is around 300 lines. The graph-specific parts become the 300 lines, and the generic stuff is most of it. I'm currently scraping graph_isom.pyx for useful tests of this new software. In a day or two, I should have a complete replacement for the current graph isomorphism code, which will show up on trac as a patch. I'm particularly excited to demonstrate some nontrivial calculations using the new software, such as the sizes of the automorphism groups of the dodecahedron and the cube (search_tree_old is a function with the same signature as the function in graph_isom.pyx which uses the new architecture):

sage: import sage.groups.perm_gps.partn_ref.refinement_graphs
sage: st = sage.groups.perm_gps.partn_ref.refinement_graphs.search_tree_old

sage: G = graphs.DodecahedralGraph()
sage: Pi = [range(20)]
sage: st(G, Pi, order=True)[2]
120

sage: G = graphs.CubeGraph(3)
sage: G.relabel()
sage: Pi = [G.vertices()]
sage: st(G, Pi, order=True)[2]
48

Phase 1 Complete

Again, grateful thanks to Google for funding my summer work.

"Phase 1," by which I mean rewriting the common parts of sage.graphs.graph_isom and sage.coding.binary_code, is now finished. All of the variable names are logically labeled, so that in fact many of the comments in the original sage.graphs.graph_isom code have been simply removed. Now, reading the code itself is much like reading the comments in the original.

I have also tested the code written so far with valgrind, and fixed the errors that were found. For each of the problem specific functions, I have implemented a trivial version, which essentially does nothing. The first, which refines partitions, returns the partition given. The second, which allows for determining that all the nodes below the current position, always returns false. The third, which compares structures under a permutation, always returns true, i.e. that the permutation is an isomorphism of the structure in question. Basically, this means that given a partition with blocks of size n(1), ..., n(k), the algorithm just computes S_n(1) x ... x S_n(k).

In theory, this should be ready for arbitrary refinement functions and structures, so Phase 2 of my project will be to implement as many specific such things as possible. I'd like to try graphs, block designs (including binary codes), computing the automorphism group of a matrix (permuting columns such that the set of rows is preserved), reflexive polytopes (perhaps using some of the functionality of PALP, perhaps not...), Adinkras, and certain kinds of combinatorial species.

On a side note, I've said a few times to people that it's nice to be getting funding for "what I'd be doing anyway," but I have to admit that it has been making me much more productive in my work than I might have been otherwise. Thanks again, Google!

Partition Refinement Snapshot

I've just passed the thousand line mark on the partition backtrack code I'm writing this summer (thanks to the support of Google!), so I thought I'd take a snapshot of the work done so far and post it. As you can see, I've taken care of the datastructures, supporting functions, memory management, and I'm through the main loop itself. The naming conventions are better, the code is much more self-explanatory, and the loop is structured in a logical way, instead of a mazelike circuit of GOTOs. You can continue to watch my progress through the guts of NICE here, as I am trying to keep it current with what I am doing.

Variable names, people!

Once again thanks go to Google for funding my summer work!

If you've ever been frustrated with unhelpful variable names, perhaps you'll appreciate the planned changes for the partition backtrack algorithm I'm working on currently:

Theta -> orbits_of_subgroup
index -> subgroup_primary_orbit_size
size -> subgroup_size
L -> max_len_of_fp_and_mcr
l -> index_in_fp_and_mcr
Phi -> fixed_points_of_generators
Omega -> minimal_cell_reps_of_generators
W -> vertices_to_split
nu -> current_ps
zeta -> first_ps
rho -> label_ps
h -> first_meets_current
hb -> label_meets_current
hh -> current_kids_are_same
ht -> first_kids_are_same
Lambda -> current_indicators
zf -> first_indicators
zb -> label_indicators
hzf -> first_and_current_indicator_same
hzb -> label_and_current_indicator_same

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.

Fast sparse graphs

From the hotel room at Sage Days 7: Combinatorics

When I discussed the base implementation of graph datatypes with the NetworkX developers, I was surprised when they told me that they found the current Python dict-of-dict's approach faster than even any C implementations. Perhaps the missing ingredient was Cython, which allowed me to beat out the dicts in under twenty four hours. The underlying implementation is an adjacency list, achieved by an array of custom made hash tables, whose buckets are rudimentary binary trees. There is an option to specify at run time the expected degree of the graph-- these tests were done on random cubic graphs. The vertical axis is number of vertices, the horizontal is a single edge access, in secs x 10000000.

sage: G = graphs.RandomRegular(3,100)