• PartitionRefinement
• Refactor

Refactor existing code in Sage

Currently there are two almost duplicate algorithms in sage.coding.binary_code and sage.graphs.graph_isom which need to be refactored into a more general purpose "subgroup-type problem" and "canonical labeling-type problem" algorithm. Steps:

Phase 1 (DONE): refactor the common parts of aut. group and canonical label stuff

• here

Phase 2: refactor the problem-specific parts of aut. group and canonical label stuff

• Graph isomorphism (DONE).

  • Elimination - In McKay's "Practical Graph Isomorphism", there is Lemma 2.25 (and a corresponding variable, hh) which allows you to recognize a situation in which all of the refinements below the current one will be equivalent. The hypotheses for Lemma 2.25 could be different for different structures. Anything having to do with Lemma 2.25 needs to be pulled out, since it is specific to graphs. Instead, this will be a problem-specific black-box opportunity to conclude that the part of the tree underneath the current node need not be searched (for whatever reasons).

  • Refinement - The process for refining the partitions from one node to the next on the search tree is problem-specific, and any invariants for the tree should be specified at this time.

  • Comparison - A function which takes an object G and a permutation \gamma, and returns whether \gamma(G) < G, = G or > G, such that the resulting ordering is total, i.e. for every G, H, one of the previous three holds.

    • Note - the total ordering requirement rules out relations like G \leq H meaning G is a sub-structure of H.

• Adinkras (DONE for now)

• Linear binary codes (DONE)
  • fresh implementation using bitsets instead of machine words, to allow for arbitrary degree/dimension.
  • part of the object passed around will actually be another partition stack, to keep track of the words.
  • The initial partition of the words can be part of the input to the algorithm - for now just assumes unit partition.
  • Elimination (DONE) -- essentially just BDM's Lemma 2.25 on the bipartite graph
  • Refinement (DONE) -- same
  • Comparison (DONE) -- use row reduction
• incidence structures
  • essentially just nonlinear binary codes
• matrix automorphism groups

Phase 3: refactor the common parts of canonical augmentation stuff

• part 1: for a given object P, (*)generate all possible children (in some form)

• part 2: (*)compute the action of a permutation on a child (to give another)
  • this should give unique representatives of the orbits of children

• part 3: for a given child C, (*)compute its canonical relabeling \gamma, and compute the canonical label's (*)canonical parent \gamma(M), which gives the child's canonical parent M.

• part 4: now you have two groups, G and H. G is the aut gp. of the parent P, and H is the aut gp. of the child C. Let \gamma denote the canonical relabeling of the child, which will represent some coset of H. We want to check if (P,C) \cong (M,C), that is whether there is a permutation \rho \in H such that \rho(P) = M.

  • First, we can (*)easily eliminate some cases when P \not\cong M.

  • Then, we can ask the hard problem of whether P \cong M, rejecting if it is not, otherwise we will have \delta(P) = M.

  • Now we have boiled it down to a question of whether the coset \delta G intersects H.

  • Thus the "hard part" of canonical augmentation boils down to a double coset question.

Phase 4: refactor the problem-specific parts of canonical augmentation stuff

• Graphs
• Binary codes

• Use techniques described by Leon to allow a group G as input, so that the entire traversal happens inside G (this will trivially provide group intersections, stabilizers and normalizers of elements, etc.).