Coverage for local/lib/python2.7/site-packages/sage/groups/perm_gps/partn_ref/data_structures.pxd : 76%
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
|
#***************************************************************************** # Copyright (C) 2006 - 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 sage.data_structures.bitset cimport bitset_s, bitset_t
from libc.string cimport memcpy from libc.stdlib cimport rand from sage.libs.gmp.mpz cimport * from sage.groups.perm_gps.partn_ref2.refinement_generic cimport PartitionRefinement_generic
cdef enum: # The following is for the automorphism group computation, says what the # length of fixed point and minimal cell representative arrays should be, # which are used to prune the search tree under known symmetries. # Increasing this may make certain automorphism_group_and_canonical_label # computations faster for incredibly large groups. len_of_fp_and_mcr = 100
cdef struct OrbitPartition: # Disjoint set data structure for representing the orbits of the generators # so far found. Also keeps track of the minimum elements of the cells and # their sizes. int degree int num_cells int *parent int *rank int *mcr # minimum cell representatives - only valid at the root of a cell int *size # also only valid at the root of a cell
cdef struct PartitionStack: # Representation of a node of the search tree. A sequence of partitions of # length depth + 1, each of which is finer than the last. Partition k is # represented as PS.entries in order, broken up immediately after each # entry of levels which is at most k. int *entries int *levels int depth int degree
cdef struct StabilizerChain: # A representation of a permutation group acting on 0, 1, ..., degree-1. int degree int base_size
int *orbit_sizes int *num_gens # dimension of generator cube on each level int *array_size # size of space to hold generators on each level (number of permutations)
int **base_orbits # int **parents # three n*n squares, orbits and tree structures int **labels #
int **generators # generators for each level, int **gen_inverses # and their inverses
bitset_s gen_used bitset_s gen_is_id int *perm_scratch OrbitPartition *OP_scratch
# OrbitPartition (OP)
cdef OrbitPartition *OP_new(int n)
cdef void OP_dealloc(OrbitPartition *OP)
cdef inline int OP_copy_from_to(OrbitPartition *OP, OrbitPartition *OP2): """ Copy all data from OP to OP2, we suppose that
- OP2.degree == OP.degree - OP2.num_cells == OP.num_cells """
cdef inline OrbitPartition *OP_copy(OrbitPartition *OP): """ Allocate and return a pointer to a copy of a OrbitPartition of degree n.
Returns a null pointer in the case of an allocation failure. """ raise MemoryError("MemoryError allocating OrbitPartition in copy method")
cdef OP_string(OrbitPartition *OP)
cdef inline void OP_clear(OrbitPartition *OP):
cdef inline int OP_find(OrbitPartition *OP, int n): """ Report the representative ("root") of the cell which contains n. """ else:
cdef inline int OP_join(OrbitPartition *OP, int m, int n): """ Join the cells containing m and n, if they are different. """
cdef inline int OP_merge_list_perm(OrbitPartition *OP, int *gamma): """ Joins the cells of OP which intersect the same orbit of gamma.
INPUT: gamma - an integer array representing i -> gamma[i].
OUTPUT: 1 - something changed 0 - orbits of gamma all contained in cells of OP """
# PartitionStack (PS)
cdef inline int PS_copy_from_to(PartitionStack *PS, PartitionStack *PS2): """ Copy all data from PS to PS2. """
cdef inline bint PS_is_discrete(PartitionStack *PS): """ Returns whether the deepest partition consists only of singleton cells. """ cdef int i
cdef inline int PS_num_cells(PartitionStack *PS): """ Returns the number of cells. """
cdef inline void PS_move_min_to_front(PartitionStack *PS, int start, int end): """ Makes sure that the first element of the segment of entries i with start <= i <= end is minimal. """
cdef inline bint PS_is_mcr(PartitionStack *PS, int m): """ Returns whether PS.elements[m] (not m!) is the smallest element of its cell. """
cdef inline bint PS_is_fixed(PartitionStack *PS, int m): """ Returns whether PS.elements[m] (not m!) is in a singleton cell, assuming PS_is_mcr(PS, m) is already true. """
cdef inline int PS_clear(PartitionStack *PS): """ Sets the current partition to the first shallower one, i.e. forgets about boundaries between cells that are new to the current level. """
cdef inline int PS_move_all_mins_to_front(PartitionStack *PS): """ Move minimal cell elements to the front of each cell. """
cdef inline int PS_get_perm_from(PartitionStack *PS1, PartitionStack *PS2, int *gamma): """ Store the permutation determined by PS2[i] -> PS1[i] for each i, where PS[i] denotes the entry of the ith cell of the discrete partition PS. """ cdef int i
cdef PartitionStack *PS_new(int n, bint unit_partition)
cdef PartitionStack *PS_copy(PartitionStack *PS)
cdef void PS_dealloc(PartitionStack *PS)
cdef PS_print(PartitionStack *PS)
cdef void PS_unit_partition(PartitionStack *PS)
cdef int PS_first_smallest(PartitionStack *PS, bitset_t b, int *second_pos=?, PartitionRefinement_generic partn_ref_alg=?)
cdef PartitionStack *PS_from_list(list L)
cdef list PS_singletons(PartitionStack * part)
cdef int PS_all_new_cells(PartitionStack *PS, bitset_t** nonsingletons_ptr)
cdef inline bint stacks_are_equivalent(PartitionStack *PS1, PartitionStack *PS2):
cdef int sort_by_function(PartitionStack *PS, int start, int *degrees)
cdef inline int PS_split_point(PartitionStack *PS, int v): """ Detaches the point v from the cell it is in, putting the singleton cell of just v in front. Returns the position where v is now located. """ # if v is first (make sure v is not already alone) else: # If v is not at front, i.e. v is not minimal in its cell, # then move_min_to_front is not necessary since v will swap # with the first before making its own cell, leaving it at # the front of the other.
cdef inline int split_point_and_refine(PartitionStack *PS, int v, void *S, int (*refine_and_return_invariant) (PartitionStack *PS, void *S, int *cells_to_refine_by, int ctrb_len), int *cells_to_refine_by): """ Make the partition stack one longer by copying the last partition in the stack, split off a given point, and refine. Return the invariant given by the refinement function.
INPUT: PS -- the partition stack to refine v -- the point to split S -- the structure refine_and_return_invariant -- the refinement function provided cells_to_refine_by -- an array, contents ignored group -- the containing group, NULL for full S_n perm_stack -- represents a partial traversal decomposition for group
"""
# StabilizerChain (SC)
cdef StabilizerChain *SC_new(int n, bint init_gens=?)
cdef int SC_realloc_gens(StabilizerChain *SC, int level, int size)
cdef void SC_dealloc(StabilizerChain *SC)
cdef int SC_copy_nomalloc(StabilizerChain *SC_dest, StabilizerChain *SC, int level)
cdef StabilizerChain *SC_alternating_group(int n)
cdef int SC_insert_and_sift(StabilizerChain *SC, int level, int *pi, int num_perms, bint sift)
cdef int SC_insert_base_point_nomalloc(StabilizerChain *SC_dest, StabilizerChain *SC, int level, int p)
cdef inline int SC_perm_is_identity(int *perm, int degree): else:
cdef inline void SC_mult_perms(int *out, int *first, int *second, int degree): """ DON'T DO THIS WITH out == second! """ cdef int i
cdef inline void SC_invert_perm(int *out, int *input, int degree): """ DON'T DO THIS WITH out == in! """ cdef int i
cdef inline void SC_identify(int *perm, int degree): cdef int i
cdef inline void SC_add_base_point(StabilizerChain *SC, int b): """ Adds base point b to the end of SC. Assumes b is not already in the base. """
cdef inline int SC_cleanup(StabilizerChain *SC): """ Remove redundant base elements from SC.
Returns 1 if nothing changed, and 2 in case of an allocation failure. """ cdef int old, new = 0, i, n = SC.degree for old from 0 <= old < SC.base_size: if SC.orbit_sizes[old] != 1: if old != new: # copy row old to row new SC.orbit_sizes[new] = SC.orbit_sizes[old] SC.num_gens[new] = SC.num_gens[old] if SC.array_size[new] < SC.array_size[old]: if SC_realloc_gens(SC, new, max(SC.array_size[old], 2*SC.array_size[new])): return 2 memcpy(SC.base_orbits[new], SC.base_orbits[old], n * sizeof(int)) memcpy(SC.parents[new], SC.parents[old], n * sizeof(int)) memcpy(SC.labels[new], SC.labels[old], n * sizeof(int)) memcpy(SC.generators[new], SC.generators[old], n*SC.num_gens[old] * sizeof(int)) memcpy(SC.gen_inverses[new], SC.gen_inverses[old], n*SC.num_gens[old] * sizeof(int)) new += 1 old = SC.base_size SC.base_size = new return (old == new)
cdef inline void SC_compose_up_to_base(StabilizerChain *SC, int level, int x, int *perm): """ Repeatedly compose the given perm by labels on the Schreier tree, starting with x, until the base is reached. The composition is stored to perm. """ cdef int *label cdef int label_no else:
cdef inline void SC_scan(StabilizerChain *SC, int level, int x, int gen_index, int *gen, int sign): """ See whether the point x is moved to a point outside the tree by gen, and if so add it to the tree (arc label is gen_inv).
gen_index - where in the generator array the generator is located gen - points to the generator gen_inv - points to the inverse sign - whether to take SC.generators or SC.gen_inverses to go *up* the tree """
cdef inline int SC_insert(StabilizerChain *SC, int level, int *pi, int num_perms): """ Add permutations in pi to the stabilizer chain. The array pi is a sequence of num_perms permutations, each in list representation, hence pi should be at least length SC.degree*num_perms. There must be at most SC.degree perms. (Simply call the function again if you want to add more.)
The variable ``level`` is used for recursion. From the outside, should be set to zero. On the inside, used to bring the data structure up to date of level ``level``, given that it is up to date on ``level + 1``.
Return values: 0 - No errors. 1 - Allocation failure. """
cdef inline int SC_update_tree(StabilizerChain *SC, int level, int *pi, int num_perms):
cdef inline void SC_order(StabilizerChain *SC, int i, mpz_t order): """ Gives the order of the stabilizer of base points up to but not including the i-th, storing it to ``order``, which must be already initialized.
To get the order of the full group, let ``i = 0``. """ cdef int k
cdef inline bint SC_contains(StabilizerChain *SC, int level, int *pi, bint modify): """ Test whether pi is in the level-th stabilizer.
Assumes that pi stabilizes the first level base points. """ cdef int *perm else:
cdef inline void SC_random_element(StabilizerChain *SC, int level, int *perm): """ Gives a random element of the level-th stabilizer. For a random element of the whole group, set level to 0. Must have level < SC.base_size. """
cdef int compute_relabeling(StabilizerChain *group, StabilizerChain *scratch_group, int *permutation, int *relabeling)
cdef inline void update_perm_stack(StabilizerChain *group, int level, int point, int *perm_stack): """ Ensure that perm_stack[level] is gamma_0^{-1}...gamma_{level-1}^{-1}, where each gamma_i represents the coset representative at the ith level determined by our current position in the search tree.
For internal use within the automorphism group, canonical label and double coset functions, to be called after refinement (level = depth after refinement). """
cdef inline int split_point_and_refine_by_orbits(PartitionStack *PS, int v, void *S, int (*refine_and_return_invariant) (PartitionStack *PS, void *S, int *cells_to_refine_by, int ctrb_len), int *cells_to_refine_by, StabilizerChain *SC, int *perm_stack): """ """
cdef int refine_by_orbits(PartitionStack *PS, StabilizerChain *SC, int *perm_stack, int *cells_to_refine_by, int *ctrb_len)
cdef inline int refine_also_by_orbits(PartitionStack *PS, void *S, int (*refine_and_return_invariant) (PartitionStack *PS, void *S, int *cells_to_refine_by, int ctrb_len), int *cells_to_refine_by, int ctrb_len, StabilizerChain *SC, int *perm_stack): """ """ cdef int inv |