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.