`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

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

# 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.

## No comments:

Post a Comment