Documentation

HexGraphIso.Nauty.Policy.Canon.Scatter

theorem Hex.GraphIso.Nauty.canonVerdict_map {n : Nat} {ctx : Ctx n} {level : Nat} {st : Search n} (he : (canonVerdict ctx level st).fst = Generic.Leaf.autoCanon) (hw : st.workperm.size = n) (hs : st.canonlab.size = n) (hp : st.canonlab.toList.Perm (List.range n)) (i : Nat) :
i < n → (canonVerdict ctx level st).snd.workperm[st.canonlab[i]!]! = st.lab[i]!

A canonical automorphism verdict stores the scatter from the canonical labelling to the current labelling.

theorem Hex.GraphIso.Nauty.classify_canon_map {n : Nat} {ctx : Ctx n} {level numcells : Nat} {st : Search n} (he : (classify ctx level numcells st).fst = Generic.Leaf.autoCanon) (hw : st.workperm.size = n) (hs : st.canonlab.size = n) (hp : st.canonlab.toList.Perm (List.range n)) (i : Nat) :
i < n → (classify ctx level numcells st).snd.workperm[st.canonlab[i]!]! = st.lab[i]!

The full classifier's canonical verdict has the same scatter relation, even when it first attempted an unsuccessful first-reference admission.

theorem Hex.GraphIso.Nauty.classify_canon_out {n : Nat} {ctx : Ctx n} {level numcells : Nat} {st : Search n} (he : (classify ctx level numcells st).fst = Generic.Leaf.autoCanon) :
have out := (classify ctx level numcells st).snd; out.workperm.size = n → out.canonlab.size = n → out.canonlab.toList.Perm (List.range n) → ∀ (i : Nat), i < n → out.workperm[out.canonlab[i]!]! = out.lab[i]!

The scatter relation is readable entirely from the classified state; its scratch allocation and canonical reference are the only size premises.