GB Con recordGraphBacktracking provides its refiners through the global record GB_Con, in the same spirit as the BTKit_Refiner record of BacktrackKit. Each field of GB_Con is a function that constructs a refiner; the resulting refiner can be placed in the conlist argument of the search functions in 2, freely mixed with BacktrackKit refiners. For the general notion of a refiner and the constraint it refines for, see BacktrackKit: Refiners and BacktrackKit: Constraints. What is specific to this package is that these refiners may additionally push graphs onto the graph stack, as described in 1.
The descriptions below cover the refiners intended for ordinary use. Several of them have a family of experimental variants (used for benchmarking the different graph constructions); those are listed in 3.5.
GB_Con.InGroup(G)refines for the permutations lying in the group G. Placing two such refiners in a search computes a group intersection.
GB_Con.InCoset(G, x)refines for the permutations lying in the right coset G * x.
GB_Con.InGroupSimple and GB_Con.InCosetSimple are alternative implementations of the same two constraints that push a different (simpler) set of graphs; they exist for comparison and compute the same answers.
gap> LoadPackage("graphbacktracking", false);; gap> G := SymmetricGroup(4);; gap> H := DihedralGroup(IsPermGroup, 8);; gap> GB_SimpleSearch(PartitionStack(4), > [GB_Con.InGroup(G), GB_Con.InGroup(H)]) = Intersection(G, H); true
GB_Con.PermConjugacy(a, b)refines for the permutations p with a ^ p = b, i.e. that conjugate the permutation a to b.
GB_Con.TransformationConjugacy(a, b)likewise for transformations a, b: refines for the permutations p with a ^ p = b (conjugation), via the functional digraph of each transformation.
GB_Con.PartialPermConjugacy(a, b)likewise for partial permutations a, b.
GB_Con.SetDigraphs(setL, setR)refines for the permutations mapping the set of digraphs setL to the set of digraphs setR (under OnSetsDigraphs). With setL = setR this is the setwise stabiliser of a set of digraphs.
These are the refiners that motivate graph backtracking, and the main addition in this release. To compute the normaliser of G inside some group U, combine the normaliser refiner with a BTKit_Refiner.InGroup(U) (or GB_Con.InGroup) refiner.
GB_Con.NormaliserOrbital(G)the recommended refiner for the normaliser of G. It pushes the orbital graphs of the relevant stabilisers (encoded as a set of graphs the normaliser may permute), together with orbit colourings and root-level block systems.
GB_Con.GroupConjugacyOrbital(L, R)the transporter version: refines for the permutations conjugating the group L to the group R (group conjugacy under OnPoints). GB_Con.NormaliserOrbital(G) is exactly GB_Con.GroupConjugacyOrbital(G, G).
gap> G := Group((1,2,3,4,5));; gap> N := GB_SimpleSearch(PartitionStack(5), > [BTKit_Refiner.InGroup(SymmetricGroup(5)), > GB_Con.NormaliserOrbital(G)]);; gap> N = Normaliser(SymmetricGroup(5), G); true
For experimenting with the different graph constructions, several other normaliser refiners are provided. They all compute the same normaliser as GB_Con.NormaliserOrbital (and the corresponding GroupConjugacy* two-argument forms exist as well), but differ in which graphs and deductions they push, and hence in speed: NormaliserSimple, NormaliserSimple2, NormaliserOrbitalRoot, NormaliserOrbitalNone, NormaliserOrbitalDeep, NormaliserOrbitalSmall, NormaliserOrbitalRegOrbit and NormaliserOrbitalRegOrbitChar. The trade-offs of each are documented in the comments of gap/constraints/normaliser.g.
Warning. The two regular-orbit variants (NormaliserOrbitalRegOrbit and NormaliserOrbitalRegOrbitChar) are not canonical-safe: they are correct for testing normaliser/conjugacy equality, but must not be used for canonical-image computations. Use GB_Con.NormaliserOrbital when a canonical image is required.
generated by GAPDoc2HTML