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""" Data structures
This module implements basic data structures essential to the rest of the partn_ref module.
REFERENCES:
[1] McKay, Brendan D. Practical Graph Isomorphism. Congressus Numerantium, Vol. 30 (1981), pp. 45-87. [2] Fredman, M. and Saks, M. The cell probe complexity of dynamic data structures. Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pp. 345–354. May 1989. [3] Seress, Akos. Permutation Group Algorithms. Cambridge University Press, 2003.
"""
#***************************************************************************** # 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 libc.math cimport log, ceil from libc.string cimport memcpy, memset from libc.stdlib cimport rand from cysignals.memory cimport sig_malloc, sig_calloc, sig_realloc, sig_free
include "sage/data_structures/bitset.pxi" from sage.rings.integer cimport Integer from sage.libs.flint.ulong_extras cimport n_is_prime
# OrbitPartition (OP)
cdef inline OrbitPartition *OP_new(int n): """ Allocate and return a pointer to a new OrbitPartition of degree n. Returns a null pointer in the case of an allocation failure. """ cdef int i sig_malloc(sizeof(OrbitPartition)) sig_free(OP) sig_free(int_array) return NULL
cdef inline void OP_dealloc(OrbitPartition *OP):
cdef OP_string(OrbitPartition *OP): """ Return a string representation of the OrbitPartition. """ cdef i,j
def OP_represent(int n, merges, perm): """ Demonstration and testing.
TESTS::
sage: from sage.groups.perm_gps.partn_ref.data_structures import OP_represent sage: OP_represent(9, [(0,1),(2,3),(3,4)], [1,2,0,4,3,6,7,5,8]) Allocating OrbitPartition... Allocation passed. Checking that each element reports itself as its root. Each element reports itself as its root. Merging: Merged 0 and 1. Merged 2 and 3. Merged 3 and 4. Done merging. Finding: 0 -> 0, root: size=2, mcr=0, rank=1 1 -> 0 2 -> 2, root: size=3, mcr=2, rank=1 3 -> 2 4 -> 2 5 -> 5, root: size=1, mcr=5, rank=0 6 -> 6, root: size=1, mcr=6, rank=0 7 -> 7, root: size=1, mcr=7, rank=0 8 -> 8, root: size=1, mcr=8, rank=0 Allocating array to test merge_perm. Allocation passed. Merging permutation: [1, 2, 0, 4, 3, 6, 7, 5, 8] Done merging. Finding: 0 -> 0, root: size=5, mcr=0, rank=2 1 -> 0 2 -> 0 3 -> 0 4 -> 0 5 -> 5, root: size=3, mcr=5, rank=1 6 -> 5 7 -> 5 8 -> 8, root: size=1, mcr=8, rank=0 Deallocating OrbitPartition. Done.
""" cdef int i print("Allocation failed!") return print("Failed at i = %d!" % i) good = False print("Allocation failed!") OP_dealloc(OP) return
# PartitionStack (PS)
cdef inline PartitionStack *PS_new(int n, bint unit_partition): """ Allocate and return a pointer to a new PartitionStack of degree n. Returns a null pointer in the case of an allocation failure. """ cdef int i sig_malloc(sizeof(PartitionStack)) sig_free(PS) sig_free(int_array) return NULL
cdef void PS_unit_partition(PartitionStack *PS): """ Set partition stack to a single partition with a single cell. """
cdef inline PartitionStack *PS_copy(PartitionStack *PS): """ Allocate and return a pointer to a copy of PartitionStack PS. Returns a null pointer in the case of an allocation failure. """
sig_malloc(sizeof(PartitionStack)) sig_free(PS2) sig_free(int_array) return NULL
cdef inline void PS_dealloc(PartitionStack *PS):
cdef PartitionStack *PS_from_list(list L): """ Allocate and return a pointer to a PartitionStack representing L. Returns a null pointer in the case of an allocation failure. """ return NULL
cdef PS_print(PartitionStack *PS): """ Print a visual representation of PS. """ cdef int i
cdef PS_print_partition(PartitionStack *PS, int k): """ Print the partition at depth k. """ else:
cdef int PS_first_smallest(PartitionStack *PS, bitset_t b, int *second_pos=NULL, PartitionRefinement_generic partn_ref_alg=None): """ Find the first occurrence of the smallest cell of size greater than one, which is admissible (checked by the function ``test_allowance``). Its entries are stored to b and its minimum element is returned. """ # location now points to the beginning of the first, smallest, # nontrivial cell
else:
cdef int PS_all_new_cells(PartitionStack *PS, bitset_t** nonsingletons_ptr): """ Suppose a cell ``C`` was split into ``a`` components at ``PS.level``. Set the rows of the matrix ``nonsingletons_ptr`` to the first ``a-1`` components of ``C`` for all those ``C``. Return the number of rows of ``nonsingletons_ptr``. """ cdef bitset_t scratch
raise MemoryError("Memory error in PS_all_new_cells") else: if beg==0: nonsingletons = <bitset_t*> sig_realloc(nonsingletons, sizeof(bitset_t)) if nonsingletons is NULL: raise MemoryError("Memory error in PS_all_new_cells") bitset_init(nonsingletons[0], n) bitset_zero(scratch) bitset_complement(nonsingletons[0], scratch) count = 1
cdef int PS_find_element(PartitionStack *PS, bitset_t b, int x) except -1: """ Find the cell containing x, store its entries to b and return the location of the beginning of the cell. """ else: raise ValueError("element not found") location -= 1 i += 1
cdef list PS_singletons(PartitionStack * part): """ Return the list of all singletons in the PartitionStack. """ cdef int i
def PS_represent(partition, splits): """ Demonstration and testing.
TESTS::
sage: from sage.groups.perm_gps.partn_ref.data_structures import PS_represent sage: PS_represent([[6],[3,4,8,7],[1,9,5],[0,2]], [6,1,8,2]) Allocating PartitionStack... Allocation passed: (0 1 2 3 4 5 6 7 8 9) Checking that entries are in order and correct level. Everything seems in order, deallocating. Deallocated. Creating PartitionStack from partition [[6], [3, 4, 8, 7], [1, 9, 5], [0, 2]]. PartitionStack's data: entries -> [6, 3, 4, 8, 7, 1, 9, 5, 0, 2] levels -> [0, 10, 10, 10, 0, 10, 10, 0, 10, -1] depth = 0, degree = 10 (6|3 4 8 7|1 9 5|0 2) Checking PS_is_discrete: False Checking PS_num_cells: 4 Checking PS_is_mcr, min cell reps are: [6, 3, 1, 0] Checking PS_is_fixed, fixed elements are: [6] Copying PartitionStack: (6|3 4 8 7|1 9 5|0 2) Checking for consistency. Everything is consistent. Clearing copy: (0 3 4 8 7 1 9 5 6 2) Splitting point 6 from original: 0 (6|3 4 8 7|1 9 5|0 2) Splitting point 1 from original: 5 (6|3 4 8 7|1|5 9|0 2) Splitting point 8 from original: 1 (6|8|3 4 7|1|5 9|0 2) Splitting point 2 from original: 8 (6|8|3 4 7|1|5 9|2|0) Getting permutation from PS2->PS: [6, 1, 0, 8, 3, 9, 2, 7, 4, 5] Finding first smallest: Minimal element is 5, bitset is: 0000010001 Finding element 1: Location is: 5 Bitset is: 0100000000 Deallocating PartitionStacks. Done.
""" cdef int *gamma cdef bitset_t b cdef PartitionStack *PS2 print("Allocation failed!") return print("Failed at i = %d!" % i) print(PS.entries[i], PS.levels[i], i, n) good = False print("Failed at i = %d!"%(n-1)) good = False print("Incorrect degree or depth!") good = False print("Failed at i = %d!"%i) good = False print("Failure with degree or depth!") good = False
# StabilizerChain (SC)
cdef enum: default_num_gens = 8 default_num_bits = 64
cdef StabilizerChain *SC_new(int n, bint init_gens=True): """ Allocate and return a pointer to a new StabilizerChain of degree n. Returns a null pointer in the case of an allocation failure. """ cdef int i sig_calloc(1, sizeof(StabilizerChain)) cdef int *array1 cdef int *array2 cdef int *array3 return NULL # All internal pointers have been initialized to NULL by sig_calloc
# first level allocations # bitset_init without the MemoryError:
# check for allocation failures sig_free(int_array) sig_free(int_ptrs) SC_dealloc(SC) return NULL
# second level allocations SC_dealloc(SC) return NULL
cdef inline int SC_realloc_gens(StabilizerChain *SC, int level, int size): """ Reallocate generator array at level `level` to size `size`.
Returns 1 in case of an allocation failure. """ cdef int *temp
cdef inline void SC_dealloc(StabilizerChain *SC): cdef int i, n
cdef StabilizerChain *SC_symmetric_group(int n): """ Returns a stabilizer chain for the symmetric group on {0, 1, ..., n-1}.
Returns NULL in the case of an allocation failure. """ cdef int i, j, b return NULL SC_dealloc(SC) return NULL #j-th generator sends i+j+1 to b
cdef StabilizerChain *SC_alternating_group(int n): """ Returns a stabilizer chain for the alternating group on {0, 1, ..., n-1}.
Returns NULL in the case of an allocation failure. """ cdef int i, j, b return NULL SC_dealloc(SC) return NULL #j-th generator sends i+j+1 to b, i+j+2 to i+j+1, and b to i+j+2
cdef int SC_realloc_bitsets(StabilizerChain *SC, long size): """ If size is larger than current allocation, double the size of the bitsets until it is not.
Returns 1 in case of an allocation failure. """ cdef unsigned long new_size = size_old while new_size < size: new_size *= 2 cdef unsigned long limbs_old = SC.gen_used.limbs cdef long limbs = (new_size - 1)/(8*sizeof(unsigned long)) + 1 cdef mp_limb_t *tmp = <mp_limb_t*> sig_realloc(SC.gen_used.bits, limbs * sizeof(mp_limb_t)) if tmp is not NULL: SC.gen_used.bits = tmp else: return 1 tmp = <mp_limb_t*> sig_realloc(SC.gen_is_id.bits, limbs * sizeof(mp_limb_t)) if tmp is not NULL: SC.gen_is_id.bits = tmp else: return 1 SC.gen_used.limbs = limbs SC.gen_is_id.limbs = limbs SC.gen_used.size = new_size SC.gen_is_id.size = new_size SC.gen_used.bits[size_old >> index_shift] &= limb_lower_bits_down(size_old) memset(SC.gen_used.bits + (size_old >> index_shift) + 1, 0, (limbs - (size_old >> index_shift) - 1) * sizeof(unsigned long)) SC.gen_is_id.bits[size_old >> index_shift] &= limb_lower_bits_down(size_old) memset(SC.gen_is_id.bits + (size_old >> index_shift) + 1, 0, (limbs - (size_old >> index_shift) - 1) * sizeof(unsigned long)) return 0
cdef StabilizerChain *SC_copy(StabilizerChain *SC, int level): """ Creates a copy of the first `level` levels of SC. Must have 0 < level.
Returns a null pointer in case of allocation failure. """ return NULL SC_dealloc(SCC) return NULL SC_dealloc(SCC) return NULL
cdef int SC_copy_nomalloc(StabilizerChain *SC_dest, StabilizerChain *SC, int level): if SC_realloc_gens(SC_dest, i, max(SC.num_gens[i], 2*SC_dest.array_size[i])): return 1
cdef SC_print_level(StabilizerChain *SC, int level): cdef int i, j, n = SC.degree if level < SC.base_size: print('/ level {}'.format(level)) print('| orbit {}'.format([SC.base_orbits[level][i] for i from 0 <= i < SC.orbit_sizes[level]])) print('| parents {}'.format([SC.parents [level][i] for i from 0 <= i < n])) print('| labels {}'.format([SC.labels [level][i] for i from 0 <= i < n])) print('|') print('| generators {}'.format([[SC.generators [level][n*i + j] for j from 0 <= j < n] for i from 0 <= i < SC.num_gens[level]])) print('\ inverses {}'.format([[SC.gen_inverses[level][n*i + j] for j from 0 <= j < n] for i from 0 <= i < SC.num_gens[level]])) else: print('/ level {}'.format(level)) print('|') print('\ base_size {}'.format(SC.base_size))
cdef StabilizerChain *SC_new_base(StabilizerChain *SC, int *base, int base_len): """ Create a new stabilizer chain whose base starts with the given base, and which represents the same permutation group. Original StabilizerChain is unmodified.
Use SC_cleanup to remove redundant base points.
Returns a null pointer in case of an allocation failure. """ return NULL SC_dealloc(NEW) return NULL
cdef int SC_new_base_nomalloc(StabilizerChain *SC_dest, StabilizerChain *SC, int *base, int base_len): SC_dealloc(SC_dest) return 1
cdef int SC_update(StabilizerChain *dest, StabilizerChain *source, int level): cdef mpz_t src_order, dst_order cdef int i, first_moved, b else: break else: SC_add_base_point(dest, b) mpz_clear(dst_order) mpz_clear(src_order) return 1
cdef StabilizerChain *SC_insert_base_point(StabilizerChain *SC, int level, int p): """ Insert the point ``p`` as a base point on level ``level``. Return a new StabilizerChain with this new base. Original StabilizerChain is unmodified.
Use SC_cleanup to remove redundant base points.
Returns a null pointer in case of an allocation failure. """ cdef StabilizerChain *NEW NEW = SC_copy(SC, level) else: return NULL SC_dealloc(NEW) return NULL
cdef int SC_insert_base_point_nomalloc(StabilizerChain *SC_dest, StabilizerChain *SC, int level, int p): return 1
cdef int SC_re_tree(StabilizerChain *SC, int level, int *perm, int x): """ Return values: 0 - No errors. 1 - Allocation failure. """ cdef int *gen cdef int *gen_inv
# make sure we have room for the new generator: if SC_realloc_gens(SC, level, 2*SC.array_size[level]): return 1
# new generator is perm^(-1) * (path from x to base) (left to right composition)
# now that we have our generators, regenerate the tree, breadth-first
cdef int SC_sift(StabilizerChain *SC, int level, int x, int *gens, int num_gens, int *new_gens): """ Apply Schreier's subgroup lemma[1] as follows. Given a level, a point x, and a generator s, find the coset traversal element r coming from x. Try inserting rsR(rs)^(-1) (composing left to right) on level+1, where R(g) is the coset representative of g.
level - which level we are currently working on x - the object representing r gens - points to the generators to sift by num_gens - how many of these there are new_gens - space of size at least num_gens*n for the sifted perms to go
Returns 1 in case of an allocation failure. """ return 0
# copy a representative taking base to the point x to each of these cdef int i # (available since num_gens > 0)
# post-compose each one with a generator
# for each one, look up the representative it now gives, and post-compose with that inverse cdef int *perm cdef int j
cdef int SC_insert_and_sift(StabilizerChain *SC, int level, int *pi, int num_perms, bint sift): cdef int perm_gen_index cdef int max_orbit_size, max_orbit_place return 1 else: else: # Now b is the base element at level `level`
# Record the old orbit elements and the old generators (see sifting phase)
# Add new points to the tree: cdef int x cdef int *perm cdef int error # now we have an x which maps to a new point under perm, return 1 # now we have an x which maps to a new point under perm, if SC_re_tree(SC, level, perm, x): return 1 start_over = 1 # we must look anew break # now we have an x which maps to a new point under perm, return 1
# store the rest of the unused generators in the generator array, after the added ones cdef int new_size return 1
# Sift: cdef int section, gens_in_section return 1
cdef bint SC_is_giant(int n, int num_perms, int *perms, float p, bitset_t support): """ Test whether the group generated by the input permutations is a giant, i.e., the alternating or symmetric group.
If the group is not a giant, this routine will return False. This could also indicate an allocation failure.
If the group is a giant, this routine will return True with approximate probability p. It will set `support' to the support of the group in this case. Use bitset_len to get the size of support.
The bitset `support' must be initialized. Must have 0 <= p < 1.
Running time is roughly O(-ln(1-p)*n*ln(m)) where m <= n is the size of the support of the group. """ cdef unsigned long q cdef int *gen OP_dealloc(OP) sig_free(perm) return False
# giants are transitive else:
# get a bit lost in the group, so our random elements are more random:
# look for elements with cycles of prime length q, m/2 < q < m-2
def SC_test_list_perms(list L, int n, int limit, bint gap, bint limit_complain, bint test_contains): """ Test that the permutation group generated by list perms in L of degree n is of the correct order, by comparing with GAP. Don't test if the group is of size greater than limit.
TESTS::
sage: from sage.groups.perm_gps.partn_ref.data_structures import SC_test_list_perms sage: limit = 10^7 sage: def test_Sn_on_m_points(n, m, gap, contains): ....: perm1 = [1,0] + list(range(2, m)) ....: perm2 = [(i+1)%n for i in range( n )] + list(range(n,m)) ....: SC_test_list_perms([perm1, perm2], m, limit, gap, 0, contains) sage: for i in range(2,9): ....: test_Sn_on_m_points(i,i,1,0) sage: for i in range(2,9): ....: test_Sn_on_m_points(i,i,0,1) sage: for i in range(2,9): # long time ....: test_Sn_on_m_points(i,i,1,1) # long time sage: test_Sn_on_m_points(8,8,1,1) sage: def test_stab_chain_fns_1(n, gap, contains): ....: perm1 = sum([[2*i+1,2*i] for i in range(n)], []) ....: perm2 = [(i+1)%(2*n) for i in range( 2*n)] ....: SC_test_list_perms([perm1, perm2], 2*n, limit, gap, 0, contains) sage: for n in range(1,11): ....: test_stab_chain_fns_1(n, 1, 0) sage: for n in range(1,11): ....: test_stab_chain_fns_1(n, 0, 1) sage: for n in range(1,9): # long time ....: test_stab_chain_fns_1(n, 1, 1) # long time sage: test_stab_chain_fns_1(11, 1, 1) sage: def test_stab_chain_fns_2(n, gap, contains): ....: perms = [] ....: for p,e in factor(n): ....: perm1 = [(p*(i//p)) + ((i+1)%p) for i in range(n)] ....: perms.append(perm1) ....: SC_test_list_perms(perms, n, limit, gap, 0, contains) sage: for n in range(2,11): ....: test_stab_chain_fns_2(n, 1, 0) sage: for n in range(2,11): ....: test_stab_chain_fns_2(n, 0, 1) sage: for n in range(2,11): # long time ....: test_stab_chain_fns_2(n, 1, 1) # long time sage: test_stab_chain_fns_2(11, 1, 1) sage: def test_stab_chain_fns_3(n, gap, contains): ....: perm1 = [(-i)%n for i in range( n )] ....: perm2 = [(i+1)%n for i in range( n )] ....: SC_test_list_perms([perm1, perm2], n, limit, gap, 0, contains) sage: for n in range(2,20): ....: test_stab_chain_fns_3(n, 1, 0) sage: for n in range(2,20): ....: test_stab_chain_fns_3(n, 0, 1) sage: for n in range(2,14): # long time ....: test_stab_chain_fns_3(n, 1, 1) # long time sage: test_stab_chain_fns_3(20, 1, 1) sage: def test_stab_chain_fns_4(n, g, gap, contains): ....: perms = [] ....: for _ in range(g): ....: perm = list(range(n)) ....: shuffle(perm) ....: perms.append(perm) ....: SC_test_list_perms(perms, n, limit, gap, 0, contains) sage: for n in range(4,9): # long time ....: test_stab_chain_fns_4(n, 1, 1, 0) # long time ....: test_stab_chain_fns_4(n, 2, 1, 0) # long time ....: test_stab_chain_fns_4(n, 2, 1, 0) # long time ....: test_stab_chain_fns_4(n, 2, 1, 0) # long time ....: test_stab_chain_fns_4(n, 2, 1, 0) # long time ....: test_stab_chain_fns_4(n, 3, 1, 0) # long time sage: for n in range(4,9): ....: test_stab_chain_fns_4(n, 1, 0, 1) ....: for j in range(6): ....: test_stab_chain_fns_4(n, 2, 0, 1) ....: test_stab_chain_fns_4(n, 3, 0, 1) sage: for n in range(4,8): # long time ....: test_stab_chain_fns_4(n, 1, 1, 1) # long time ....: test_stab_chain_fns_4(n, 2, 1, 1) # long time ....: test_stab_chain_fns_4(n, 2, 1, 1) # long time ....: test_stab_chain_fns_4(n, 3, 1, 1) # long time sage: test_stab_chain_fns_4(8, 2, 1, 1) sage: def test_stab_chain_fns_5(n, gap, contains): ....: perms = [] ....: m = n//3 ....: perm1 = list(range(2*m)) ....: shuffle(perm1) ....: perm1 += list(range(2*m,n)) ....: perm2 = list(range(m,n)) ....: shuffle(perm2) ....: perm2 = list(range(m)) + perm2 ....: SC_test_list_perms([perm1, perm2], n, limit, gap, 0, contains) sage: for n in [4..9]: # long time ....: for _ in range(2): # long time ....: test_stab_chain_fns_5(n, 1, 0) # long time sage: for n in [4..8]: # long time ....: test_stab_chain_fns_5(n, 0, 1) # long time sage: for n in [4..9]: # long time ....: test_stab_chain_fns_5(n, 1, 1) # long time sage: def random_perm(x): ....: shuffle(x) ....: return x sage: def test_stab_chain_fns_6(m,n,k, gap, contains): ....: perms = [] ....: for i in range(k): ....: perm = sum([random_perm(list(range(i*(n//m),min(n,(i+1)*(n//m))))) for i in range(m)], []) ....: perms.append(perm) ....: SC_test_list_perms(perms, m*(n//m), limit, gap, 0, contains) sage: for m in range(2,9): # long time ....: for n in range(m,3*m): # long time ....: for k in range(1,3): # long time ....: test_stab_chain_fns_6(m,n,k, 1, 0) # long time sage: for m in range(2,10): ....: for n in range(m,4*m): ....: for k in range(1,3): ....: test_stab_chain_fns_6(m,n,k, 0, 1) sage: test_stab_chain_fns_6(10,20,2, 1, 1) sage: test_stab_chain_fns_6(8,16,2, 1, 1) sage: test_stab_chain_fns_6(6,36,2, 1, 1) sage: test_stab_chain_fns_6(4,40,3, 1, 1) sage: test_stab_chain_fns_6(4,40,2, 1, 1) sage: def test_stab_chain_fns_7(n, cop, gap, contains): ....: perms = [] ....: for i in range(0,n//2,2): ....: p = list(range(n)) ....: p[i] = i+1 ....: p[i+1] = i ....: if cop: ....: perms.append([c for c in p]) ....: else: ....: perms.append(p) ....: SC_test_list_perms(perms, n, limit, gap, 0, contains) sage: for n in [6..14]: ....: test_stab_chain_fns_7(n, 1, 1, 0) ....: test_stab_chain_fns_7(n, 0, 1, 0) sage: for n in [6..30]: ....: test_stab_chain_fns_7(n, 1, 0, 1) ....: test_stab_chain_fns_7(n, 0, 0, 1) sage: for n in [6..14]: # long time ....: test_stab_chain_fns_7(n, 1, 1, 1) # long time ....: test_stab_chain_fns_7(n, 0, 1, 1) # long time sage: test_stab_chain_fns_7(20, 1, 1, 1) sage: test_stab_chain_fns_7(20, 0, 1, 1)
"""
cdef StabilizerChain *SC cdef StabilizerChain *SCC cdef StabilizerChain *SCCC cdef StabilizerChain *SC_nb cdef Integer order, order2 cdef int i, j, m, SC_says cdef bitset_t giant_support except MemoryError: sig_free(perm) SC_dealloc(SC) raise MemoryError bitset_free(giant_support) sig_free(perm) SC_dealloc(SC) raise MemoryError bitset_free(giant_support) sig_free(perm) SC_dealloc(SC) raise MemoryError bitset_free(giant_support) sig_free(perm) SC_dealloc(SC) SC_dealloc(SCC) SC_dealloc(SCCC) SC_dealloc(SC_nb) raise MemoryError print("SC_is_giant failed: %s %s"%(str(L), order)) raise AssertionError print("SC_symmetric_group failed: %s %s"%(str(L), order)) raise AssertionError print("SC_alternating_group failed: %s %s"%(str(L), order)) raise AssertionError print("FAIL {}".format(L)) print('SC_copy(n) does not agree with order of original {} {}'.format(order, order2)) raise AssertionError print("FAIL {}".format(L)) print('does not agree with order of inserted base point {} {}'.format(order, order2)) raise AssertionError print("FAIL {}".format(L)) print('does not agree with order of new base {} {}'.format(order, order2)) raise AssertionError print("FAIL {}".format(L)) print('element {}'.format([perm[ii] for ii in range(n)])) print('SC_random_element says it is an element, SC_contains(modify=0) does not') raise AssertionError print("FAIL {}".format(L)) print('element {}'.format([perm[ii] for ii in range(n)])) print('SC_random_element says it is an element, SC_contains(modify=1) does not') raise AssertionError print("FAIL {}".format(L)) print('element {}'.format([perm[ii] for ii in range(n)])) print('SC_random_element says it is an element, SC_contains(modify=0) does not on copy') raise AssertionError print("FAIL {}".format(L)) print('element {}'.format([perm[ii] for ii in range(n)])) print('SC_random_element says it is an element, SC_contains(modify=1) does not on copy') raise AssertionError print("FAIL {}".format(L)) print('element {}'.format([perm[ii] for ii in range(n)])) print('SC_random_element says it is an element, SC_contains(modify=0) does not on inserted base point') raise AssertionError print("FAIL {}".format(L)) print('element {}'.format([perm[ii] for ii in range(n)])) print('SC_random_element says it is an element, SC_contains(modify=1) does not on inserted base point') raise AssertionError print("FAIL {}".format(L)) print('element {}'.format([perm[ii] for ii in range(n)])) print('SC_random_element says it is an element, SC_contains(modify=0) does not on new base') raise AssertionError print("FAIL {}".format(L)) print('element {}'.format([perm[ii] for ii in range(n)])) print('SC_random_element says it is an element, SC_contains(modify=1) does not on new base') raise AssertionError print("FAIL {}".format(L)) print('element {}'.format([perm[ii] for ii in range(n)])) print('SC_random_element says it is an element of copy, SC_contains(modify=0) does not') raise AssertionError print("FAIL {}".format(L)) print('element {}'.format([perm[ii] for ii in range(n)])) print('SC_random_element says it is an element of copy, SC_contains(modify=1) does not') raise AssertionError print("FAIL {}".format(L)) print('element {}'.format([perm[ii] for ii in range(n)])) print('SC_random_element says it is an element of inserted base point, SC_contains(modify=0) does not') raise AssertionError print("FAIL {}".format(L)) print('element {}'.format([perm[ii] for ii in range(n)])) print('SC_random_element says it is an element of inserted base point, SC_contains(modify=1) does not') raise AssertionError print("FAIL {}".format(L)) print('element {}'.format([perm[ii] for ii in range(n)])) print('SC_random_element says it is an element of new base, SC_contains(modify=0) does not') raise AssertionError print("FAIL {}".format(L)) print('element {}'.format([perm[ii] for ii in range(n)])) print('SC_random_element says it is an element of new base, SC_contains(modify=1) does not') raise AssertionError print("SC_is_giant failed: %s %s"%(str(L), order)) raise AssertionError print("FAIL {}".format(L)) print('order was computed to be {}'.format(order)) print('GAP says it is {}'.format(G.order())) raise AssertionError print("FAIL {}".format(L)) print('element {}'.format(permy)) print('GAP says it is an element, SC_contains(modify=0) does not') raise AssertionError print("FAIL {}".format(L)) print('element {}'.format(permy)) print('GAP says it is an element, SC_contains(modify=1) does not') raise AssertionError print("FAIL {}".format(L)) print('element {}'.format(permy)) print('GAP says %d, SC_contains(modify=0) says %d'%(gap_says, SC_says)) raise AssertionError print("FAIL {}".format(L)) print('element {}'.format(permy)) print('GAP says %d, SC_contains(modify=0) says %d'%(gap_says, SC_says)) raise AssertionError print("FAIL {}".format(L)) print('element {}'.format(permy)) print('random element not contained in group, modify=false') raise AssertionError print("FAIL {}".format(L)) print('element {}'.format(permy)) print('random element not contained in group, modify=true') raise AssertionError print("FAIL {}".format(L)) print('element {}'.format(permy)) print('random element not contained in group, according to GAP') raise AssertionError except Exception: if giant: print("detected giant!") raise finally:
# Functions
cdef int sort_by_function(PartitionStack *PS, int start, int *degrees): """ A simple counting sort, given the degrees of vertices to a certain cell.
INPUT: PS -- the partition stack to be checked start -- beginning index of the cell to be sorted degrees -- the values to be sorted by, must have extra scratch space for a total of 3*n+1
""" cdef int i, j, max, max_location # i+start is the right endpoint of the cell now
cdef int refine_by_orbits(PartitionStack *PS, StabilizerChain *SC, int *perm_stack, int *cells_to_refine_by, int *ctrb_len): """ Given a stabilizer chain SC, refine the partition stack PS so that each cell contains elements from at most one orbit, and sort the refined cells by their minimal cell representatives in the orbit of the group. """ cdef int *gen # update cells_to_refine_by
cdef int compute_relabeling(StabilizerChain *group, StabilizerChain *scratch_group, int *permutation, int *relabeling): """ Technically, compute the INVERSE of the relabeling """ return 1 |