Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" 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:
A. ``refine_and_return_invariant``:
Signature:
``int refine_and_return_invariant(PartitionStack *PS, void *S, int *cells_to_refine_by, int ctrb_len)``
B. ``compare_structures``:
Signature:
``int compare_structures(int *gamma_1, int *gamma_2, void *S1, void *S2, int degree)``
C. ``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.
D. ``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.
E. ``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.
F. ``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``.
G. ``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``.
H. ``free_aug``:
Signature:
``void free_aug(void *aug)``
This function frees an augmentation as generated by the iterator returned by ``generate_children``.
I. ``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.
"""
#***************************************************************************** # Copyright (C) 2010 - 2011 Robert L. Miller <rlmillster@gmail.com> # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 2 of the License, or # (at your option) any later version. # http://www.gnu.org/licenses/ #*****************************************************************************
from cysignals.memory cimport sig_malloc, sig_free
from .data_structures cimport*
cdef void *canonical_generator_next(void *can_gen_data, int *degree, bint *mem_err): r""" This function is part of the iterator struct which will iterate over objects. Return value of ``NULL`` indicates termination. """ # degree ignored! cdef iterator *cur_iter cdef void *next_candidate cdef void *parent_cand cdef void *aug cdef int i, next_cand_deg, parent_cand_deg cdef int *isom cdef PartitionStack *part cdef bint augmentation_is_canonical cdef aut_gp_and_can_lab *output cdef agcl_work_space *agcl_ws cdef dc_work_space *dc_ws
mem_err[0] = 1 deallocate_cgd(cgd)
# getting next candidate at level cgd.level # cur_iter has run out: backtrack by one, return the parent else: aug, cgd.object_stack[cgd.level], &cgd.degree_stack[cgd.level], # allocate a work space if it hasn't been allocated already # in case the degree has changed, we need to reallocate the work # space: this is why one should do augmentations in order of degree deallocate_agcl_work_space(cgd.agcl_work_spaces[cgd.level]) deallocate_agcl_output(cgd.aut_gp_stack[cgd.level]) cgd.aut_gp_stack[cgd.level] = NULL PS_dealloc(cgd.ps_stack[cgd.level]) cgd.agcl_work_spaces[cgd.level] = allocate_agcl_work_space(next_cand_deg) cgd.ps_stack[cgd.level] = PS_new(next_cand_deg, 0) cgd.mem_err = 1 continue # see if next_candidate is canonically augmented part, next_cand_deg, cgd.all_children_are_equivalent, cgd.refine_and_return_invariant, cgd.compare_structures, 1, cgd.group, cgd.agcl_work_spaces[cgd.level], cgd.aut_gp_stack[cgd.level]) except MemoryError: cgd.mem_err = 1 continue cgd.aut_gp_stack[cgd.level].relabeling, &parent_cand_deg, &cgd.mem_err) continue augmentation_is_canonical = 0 else: # allocate a work space if it hasn't been allocated already # in case the degree has changed, we need to reallocate the work # space: this is why one should do augmentations in order of degree deallocate_dc_work_space(cgd.dc_work_spaces[cgd.level-1]) cgd.dc_work_spaces[cgd.level-1] = allocate_dc_work_space(next_cand_deg) cgd.mem_err = 1 continue parent_cand, part, NULL, next_cand_deg, cgd.all_children_are_equivalent, cgd.refine_and_return_invariant, cgd.compare_structures, cgd.aut_gp_stack[cgd.level].group, cgd.dc_work_spaces[cgd.level-1], NULL) except MemoryError: cgd.mem_err = 1 continue # the object is canonically augmented, so we add it to the chain cgd.aut_gp_stack[cgd.level], cgd.iterator_stack+cgd.level) continue
# we're at the end of the chain, so just give the object
cdef canonical_generator_data *allocate_cgd(int max_depth, int degree): r""" Allocate the data part of the canonical generation iterator struct. """ cdef PartitionStack *part sig_free(cgd) return NULL sig_free(cgd.object_stack) sig_free(cgd.degree_stack) sig_free(cgd.iterator_stack) sig_free(cgd.aut_gp_stack) sig_free(cgd.agcl_work_spaces) sig_free(cgd.dc_work_spaces) sig_free(cgd.ps_stack) sig_free(cgd.aug_stack) sig_free(cgd.parent_stack) sig_free(cgd) PS_dealloc(part) deallocate_agcl_work_space(agclws) deallocate_agcl_output(output) return NULL
cdef int i
cdef void deallocate_cgd(canonical_generator_data *cgd): r""" Deallocate the data part of the canonical generation iterator struct. """ return cdef int i cdef void *thingy cdef void (*clearer)(void*) cgd.free_aug(cgd.aug_stack[i])
cdef iterator *setup_canonical_generator(int degree, bint (*all_children_are_equivalent)(PartitionStack *PS, void *S), int (*refine_and_return_invariant)\ (PartitionStack *PS, void *S, int *cells_to_refine_by, int ctrb_len), int (*compare_structures)(int *gamma_1, int *gamma_2, void *S1, void *S2, int degree), int (*generate_children)(void *, aut_gp_and_can_lab *, iterator *), void *(*apply_augmentation)(void *, void *, void *, int *, bint *), void (*free_object)(void *), void (*free_iter_data)(void *), void (*free_aug)(void *), void *(*canonical_parent)(void *child, void *parent, int *permutation, int *degree, bint *mem_err), int max_depth, bint reduce_children, iterator *cangen_prealloc) except NULL: """ Canonical generation of isomorphism classes of objects.
INPUT:
- ``S`` - pointer to the seed object
- ``degree`` - the degree of S
- ``all_children_are_equivalent`` - pointer to a function INPUT: PS -- pointer to a partition stack S -- pointer to the structure OUTPUT: bint -- returns True if it can be determined that all refinements below the current one will result in an equivalent discrete partition
- ``refine_and_return_invariant`` - pointer to a function INPUT: PS -- pointer to a partition stack S -- pointer to the structure alpha -- an array consisting of numbers, which indicate the starting positions of the cells to refine against (will likely be modified) OUTPUT: int -- returns an invariant under application of arbitrary permutations
- ``compare_structures`` - pointer to a function INPUT: gamma_1, gamma_2 -- (list) permutations of the points of S1 and S2 S1, S2 -- pointers to the structures degree -- degree of gamma_1 and 2 OUTPUT: int -- 0 if gamma_1(S1) = gamma_2(S2), otherwise -1 or 1 (see docs for cmp), such that the set of all structures is well-ordered
- ``generate_children`` - pointer to a function INPUT: S -- pointer to the structure group -- pointer to an automorphism group (canonical relabeling is not guaranteed) it -- preallocated iterator struct OUTPUT: iterator * -- pointer to an iterator over inequivalent augmentations of S
- ``apply_augmentation`` - pointer to a function INPUT: parent -- object to augment aug -- the augmentation child -- space to put the augmented object degree -- pointer to an int, function should store the degree of the augmented object here mem_err -- pointer where memory error can be reported OUTPUT: pointer to child
- ``free_object`` - pointer to a function INPUT: child -- object to be freed
- ``free_iter_data`` - pointer to a function INPUT: data -- data part of an iterator struct
- ``free_aug`` - pointer to a function INPUT: aug -- augmentation to be freed
- ``canonical_parent`` - pointer to a function INPUT: child -- pointer to the structure parent -- space to store the canonical parent permutation -- array representing a relabeling of the child degree -- pointer to store the degree of the parent mem_err -- pointer for indicating memory errors OUTPUT: pointer to the parent
- ``max_depth`` - maximum depth of augmentations to be made from the seed object S
OUTPUT:
pointer to an iterator of objects
""" raise ValueError("Maximum depth (%d) must be at least two."%max_depth) raise NotImplementedError
# Allocate memory for the arrays and check for failures: cdef iterator *canonical_generator cdef canonical_generator_data *cgd canonical_generator = <iterator *> sig_malloc(sizeof(iterator)) cgd = allocate_cgd(max_depth, degree) if canonical_generator is NULL or cgd is NULL: sig_free(canonical_generator) deallocate_cgd(cgd) raise MemoryError cgd.dealloc = 1 else: deallocate_cgd(cgd) cgd = allocate_cgd(max_depth, degree) if cgd is NULL: raise MemoryError
cdef iterator *start_canonical_generator(StabilizerChain *group, void *obj, int degree, iterator *canonical_generator) except NULL: r""" Given the containing group ``group`` and the seed object ``obj`` of degree ``degree``, initiate the canonical generator stored (and already allocated) at ``canonical_generator``. """ else: cgd.all_children_are_equivalent, cgd.refine_and_return_invariant, cgd.compare_structures, 0, group, cgd.agcl_work_spaces[0], cgd.aut_gp_stack[0]) except MemoryError: cgd.mem_err = 1 else: raise MemoryError
|