Canonical augmentation#

This module implements a general algorithm for generating isomorphism classes of objects. The class of objects in question must be some kind of structure which can be built up out of smaller objects by a process of augmentation, and for which an automorphism is a permutation in \(S_n\) for some \(n\). This process consists of starting with a finite number of “seed objects” and building up to more complicated objects by a sequence of “augmentations.” It should be noted that the word “canonical” in the term canonical augmentation is used loosely. Given an object \(X\), one must define a canonical parent \(M(X)\), which is essentially an arbitrary choice.

The class of objects in question must satisfy the assumptions made in the module automorphism_group_canonical_label, in particular the three custom functions mentioned there must be implemented:

  1. refine_and_return_invariant:

    Signature:

    int refine_and_return_invariant(PartitionStack *PS, void *S, int *cells_to_refine_by, int ctrb_len)

  2. compare_structures:

    Signature:

    int compare_structures(int *gamma_1, int *gamma_2, void *S1, void *S2, int degree)

  3. all_children_are_equivalent:

    Signature:

    bint all_children_are_equivalent(PartitionStack *PS, void *S)

In the following functions there is frequently a mem_err input. This is a pointer to an integer which must be set to a nonzero value in case of an allocation failure. Other functions have an int return value which serves the same purpose. The idea is that if a memory error occurs, the canonical generator should still be able to iterate over the objects already generated before it terminates.

More details about these functions can be found in that module. In addition, several other functions must be implemented, which will make use of the following:

ctypedef struct iterator:
    void *data
    void *(*next)(void *data, int *degree, int *mem_err)

The following functions must be implemented for each specific type of object to be generated. Each function following which takes a mem_err variable as input should make use of this variable.

  1. generate_children:

    Signature:

    int generate_children(void *S, aut_gp_and_can_lab *group, iterator *it)

    This function receives a pointer to an iterator it. The iterator has two fields: data and next. The function generate_children should set these two fields, returning 1 to indicate a memory error, or 0 for no error.

    The function that next points to takes data as an argument, and should return a (void *) pointer to the next object to be iterated. It also takes a pointer to an int, and must update that int to reflect the degree of each generated object. The objects to be iterated over should satisfy the property that if \(\gamma\) is an automorphism of the parent object \(S\), then for any two child objects \(C_1, C_2\) given by the iterator, it is not the case that \(\gamma(C_1) = C_2\), where in the latter \(\gamma\) is appropriately extended if necessary to operate on \(C_1\) and \(C_2\). It is essential for this iterator to handle its own data. If the next function is called and no suitable object is yielded, a NULL pointer indicates a termination of the iteration. At this point, the data pointed to by the data variable should be cleared by the next function, because the iterator struct itself will be deallocated.

    The next function must check mem_err[0] before proceeding. If it is nonzero then the function should deallocate the iterator right away and return NULL to end the iteration. This ensures that the canonical augmentation software will finish iterating over the objects found before finishing, and the mem_err attribute of the canonical_generator_data will reflect this.

    The objects which the iterator generates can be thought of as augmentations, which the following function must turn into objects.

  2. apply_augmentation:

    Signature:

    void *apply_augmentation(void *parent, void *aug, void *child, int *degree, bint *mem_err)

    This function takes the parent, applies the augmentation aug and returns a pointer to the corresponding child object (freeing aug if necessary). Should also update degree[0] to be the degree of the new child.

  3. free_object:

    Signature:

    void free_object(void *child)

    This function is a simple deallocation function for children which are not canonically generated, and therefore rejected in the canonical augmentation process. They should deallocate the contents of child.

  4. free_iter_data:

    Signature:

    void free_iter_data(void *data)

    This function deallocates the data part of the iterator which is set up by generate_children.

  5. free_aug:

    Signature:

    void free_aug(void *aug)

    This function frees an augmentation as generated by the iterator returned by generate_children.

  6. canonical_parent:

    Signature:

    void *canonical_parent(void *child, void *parent, int *permutation, int *degree, bint *mem_err)

    Apply the permutation to the child, determine an arbitrary but fixed parent, apply the inverse of permutation to that parent, and return the resulting object. Must also set the integer degree points to the degree of the returned object.

Note

It is a good idea to try to implement an augmentation scheme where the degree of objects on each level of the augmentation tree is constant. The iteration will be more efficient in this case, as the relevant work spaces will never need to be reallocated. Otherwise, one should at least strive to iterate over augmentations in such a way that all children of the same degree are given in the same segment of iteration.

EXAMPLES:

sage: import sage.groups.perm_gps.partn_ref.canonical_augmentation

>>> from sage.all import *
>>> import sage.groups.perm_gps.partn_ref.canonical_augmentation

REFERENCE:

  • [1] McKay, Brendan D. Isomorph-free exhaustive generation. J Algorithms, Vol. 26 (1998), pp. 306-324.