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

`refine_and_return_invariant`

:Signature:

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

`compare_structures`

:Signature:

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

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

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

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

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

.`free_aug`

:Signature:

`void free_aug(void *aug)`

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

`generate_children`

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

REFERENCE:

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