Coverage for local/lib/python2.7/site-packages/sage/coding/binary_code.pyx : 75%
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""" Optimized low-level binary code representation
Some computations with linear binary codes. Fix a basis for $GF(2)^n$. A linear binary code is a linear subspace of $GF(2)^n$, together with this choice of basis. A permutation $g \in S_n$ of the fixed basis gives rise to a permutation of the vectors, or words, in $GF(2)^n$, sending $(w_i)$ to $(w_{g(i)})$. The permutation automorphism group of the code $C$ is the set of permutations of the basis that bijectively map $C$ to itself. Note that if $g$ is such a permutation, then
.. MATH::
g(a_i) + g(b_i) = (a_{g(i)} + b_{g(i)}) = g((a_i) + (b_i)).
Over other fields, it is also required that the map be linear, which as per above boils down to scalar multiplication. However, over $GF(2),$ the only scalars are 0 and 1, so the linearity condition has trivial effect.
AUTHOR:
- Robert L Miller (Oct-Nov 2007)
* compiled code data structure * union-find based orbit partition * optimized partition stack class * NICE-based partition refinement algorithm * canonical generation function
"""
#***************************************************************************** # Copyright (C) 2007 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 __future__ import absolute_import, print_function
from libc.string cimport memcpy from cpython.mem cimport * from cpython.object cimport PyObject_RichCompare from cysignals.memory cimport sig_malloc, sig_realloc, sig_free
from sage.rings.integer cimport Integer
cdef enum: chunk_size = 8
cdef inline int min(int a, int b): else:
## NOTE - Since most of the functions are used from within the module, cdef'd ## functions come without an underscore, and the def'd equivalents, which are ## essentially only for doctesting and debugging, have underscores.
cdef int *hamming_weights(): cdef int *ham_wts cdef int i sig_free(ham_wts) raise MemoryError("Memory.")
include 'sage/data_structures/bitset.pxi' """ Computes the weight distribution of the row space of M.
EXAMPLES::
sage: from sage.coding.binary_code import weight_dist sage: M = Matrix(GF(2),[ ....: [1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0], ....: [0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0], ....: [0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1], ....: [0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1], ....: [0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]]) sage: weight_dist(M) [1, 0, 0, 0, 0, 0, 0, 0, 30, 0, 0, 0, 0, 0, 0, 0, 1] sage: M = Matrix(GF(2),[ ....: [1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0], ....: [0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0], ....: [0,0,0,0,0,1,0,1,0,0,0,1,1,1,1,1,1], ....: [0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,1]]) sage: weight_dist(M) [1, 0, 0, 0, 0, 0, 0, 0, 11, 0, 0, 0, 4, 0, 0, 0, 0, 0] sage: M=Matrix(GF(2),[ ....: [1,0,0,1,1,1,1,0,0,1,0,0,0,0,0,0,0], ....: [0,1,0,0,1,1,1,1,0,0,1,0,0,0,0,0,0], ....: [0,0,1,0,0,1,1,1,1,0,0,1,0,0,0,0,0], ....: [0,0,0,1,0,0,1,1,1,1,0,0,1,0,0,0,0], ....: [0,0,0,0,1,0,0,1,1,1,1,0,0,1,0,0,0], ....: [0,0,0,0,0,1,0,0,1,1,1,1,0,0,1,0,0], ....: [0,0,0,0,0,0,1,0,0,1,1,1,1,0,0,1,0], ....: [0,0,0,0,0,0,0,1,0,0,1,1,1,1,0,0,1]]) sage: weight_dist(M) [1, 0, 0, 0, 0, 0, 68, 0, 85, 0, 68, 0, 34, 0, 0, 0, 0, 0]
""" cdef bitset_t word cdef list L else:
""" Tests the WordPermutation structs for at least t_limit seconds.
These are structures written in pure C for speed, and are tested from this function, which performs the following tests:
1. Tests create_word_perm, which creates a WordPermutation from a Python list L representing a permutation i --> L[i]. Takes a random word and permutes it by a random list permutation, and tests that the result agrees with doing it the slow way.
1b. Tests create_array_word_perm, which creates a WordPermutation from a C array. Does the same as above.
2. Tests create_comp_word_perm, which creates a WordPermutation as a composition of two WordPermutations. Takes a random word and two random permutations, and tests that the result of permuting by the composition is correct.
3. Tests create_inv_word_perm and create_id_word_perm, which create a WordPermutation as the inverse and identity permutations, resp. Takes a random word and a random permutation, and tests that the result permuting by the permutation and its inverse in either order, and permuting by the identity both return the original word.
.. NOTE::
The functions permute_word_by_wp and dealloc_word_perm are implicitly involved in each of the above tests.
TESTS::
sage: from sage.coding.binary_code import test_word_perms sage: test_word_perms() # long time (5s on sage.math, 2011)
""" cdef WordPermutation *g cdef WordPermutation *h cdef WordPermutation *i cdef codeword cw1, cw2, cw3 cdef int n = sizeof(codeword) << 3 cdef int j cdef int *arr = <int*> sig_malloc(n * sizeof(int)) if arr is NULL: raise MemoryError("Error allocating memory.") from sage.misc.prandom import randint from sage.combinat.permutation import Permutations S = Permutations(list(xrange(n))) t = cputime() while cputime(t) < t_limit: word = [randint(0, 1) for _ in xrange(n)] cw1 = 0 for j from 0 <= j < n: cw1 += (<codeword>word[j]) << (<codeword>j) # 1. test create_word_perm gg = S.random_element() g = create_word_perm(gg) word2 = [0]*n for j from 0 <= j < n: word2[gg[j]] = word[j] cw2 = permute_word_by_wp(g, cw1) cw3 = 0 for j from 0 <= j < n: cw3 += (<codeword>word2[j]) << (<codeword>j) if cw3 != cw2: print("ERROR1") dealloc_word_perm(g) # 1b. test create_array_word_perm gg = S.random_element() for j from 0 <= j < n: arr[j] = gg[j] g = create_array_word_perm(arr, 0, n) word2 = [0]*n for j from 0 <= j < n: word2[gg[j]] = word[j] cw2 = permute_word_by_wp(g, cw1) cw3 = 0 for j from 0 <= j < n: cw3 += (<codeword>word2[j]) << (<codeword>j) if cw3 != cw2: print("ERROR1b") dealloc_word_perm(g) # 2. test create_comp_word_perm gg = S.random_element() hh = S.random_element() g = create_word_perm(gg) h = create_word_perm(hh) i = create_comp_word_perm(g, h) word2 = [0]*n for j from 0 <= j < n: word2[gg[hh[j]]] = word[j] cw2 = permute_word_by_wp(i, cw1) cw3 = 0 for j from 0 <= j < n: cw3 += (<codeword>word2[j]) << (<codeword>j) if cw3 != cw2: print("ERROR2") dealloc_word_perm(g) dealloc_word_perm(h) dealloc_word_perm(i) # 3. test create_inv_word_perm and create_id_word_perm gg = S.random_element() g = create_word_perm(gg) h = create_inv_word_perm(g) i = create_id_word_perm(n) cw2 = permute_word_by_wp(g, cw1) cw2 = permute_word_by_wp(h, cw2) if cw1 != cw2: print("ERROR3a") cw2 = permute_word_by_wp(h, cw1) cw2 = permute_word_by_wp(g, cw2) if cw1 != cw2: print("ERROR3b") cw2 = permute_word_by_wp(i, cw1) if cw1 != cw2: print("ERROR3c") dealloc_word_perm(g) dealloc_word_perm(h) dealloc_word_perm(i) sig_free(arr)
cdef WordPermutation *create_word_perm(object list_perm): r""" Create a word permutation from a Python list permutation L, i.e. such that $i \mapsto L[i]$. """ cdef codeword *images_i cdef codeword image raise RuntimeError("Error allocating memory.") sig_free(word_perm) raise RuntimeError("Error allocating memory.") for j from 0 <= j < i: sig_free(word_perm.images[j]) sig_free(word_perm.images) sig_free(word_perm) raise RuntimeError("Error allocating memory.") else:
cdef WordPermutation *create_array_word_perm(int *array, int start, int degree): """ Create a word permutation of a given degree from a C array, starting at start. """ cdef codeword *images_i cdef codeword image raise RuntimeError("Error allocating memory.") sig_free(word_perm) raise RuntimeError("Error allocating memory.") for j from 0 <= j < i: sig_free(word_perm.images[j]) sig_free(word_perm.images) sig_free(word_perm) raise RuntimeError("Error allocating memory.") else:
cdef WordPermutation *create_id_word_perm(int degree): """ Create the identity word permutation of degree degree. """ cdef int i, j, parity, comb, words_per_chunk, num_chunks = 1 cdef codeword *images_i cdef codeword image cdef WordPermutation *word_perm = <WordPermutation *> sig_malloc( sizeof(WordPermutation) ) if word_perm is NULL: raise RuntimeError("Error allocating memory.") word_perm.degree = degree while num_chunks*chunk_size < degree: num_chunks += 1 word_perm.images = <codeword **> sig_malloc(num_chunks * sizeof(codeword *)) if word_perm.images is NULL: sig_free(word_perm) raise RuntimeError("Error allocating memory.") word_perm.chunk_num = num_chunks words_per_chunk = 1 << chunk_size word_perm.gate = ( (<codeword>1) << chunk_size ) - 1 word_perm.chunk_words = words_per_chunk for i from 0 <= i < num_chunks: images_i = <codeword *> sig_malloc(words_per_chunk * sizeof(codeword)) if images_i is NULL: for j from 0 <= j < i: sig_free(word_perm.images[j]) sig_free(word_perm.images) sig_free(word_perm) raise RuntimeError("Error allocating memory.") word_perm.images[i] = images_i for j from 0 <= j < chunk_size: images_i[1 << j] = (<codeword>1) << (chunk_size*i + j) image = <codeword> 0 parity = 0 comb = 0 while True: images_i[comb] = image parity ^= 1 j = 0 if not parity: while not comb & (1 << j): j += 1 j += 1 if j == chunk_size: break else: comb ^= (1 << j) image ^= images_i[1 << j] return word_perm
cdef WordPermutation *create_comp_word_perm(WordPermutation *g, WordPermutation *h): r""" Create the composition of word permutations $g \circ h$. """ cdef int i, j, parity, comb, words_per_chunk, num_chunks = 1 cdef codeword *images_i cdef codeword image cdef WordPermutation *word_perm = <WordPermutation *> sig_malloc( sizeof(WordPermutation) ) if word_perm is NULL: raise RuntimeError("Error allocating memory.") word_perm.degree = g.degree while num_chunks*chunk_size < word_perm.degree: num_chunks += 1 word_perm.images = <codeword **> sig_malloc(num_chunks * sizeof(codeword *)) if word_perm.images is NULL: sig_free(word_perm) raise RuntimeError("Error allocating memory.") word_perm.chunk_num = num_chunks words_per_chunk = 1 << chunk_size word_perm.gate = ( (<codeword>1) << chunk_size ) - 1 word_perm.chunk_words = words_per_chunk for i from 0 <= i < num_chunks: images_i = <codeword *> sig_malloc(words_per_chunk * sizeof(codeword)) if images_i is NULL: for j from 0 <= j < i: sig_free(word_perm.images[j]) sig_free(word_perm.images) sig_free(word_perm) raise RuntimeError("Error allocating memory.") word_perm.images[i] = images_i for j from 0 <= j < chunk_size: image = (<codeword>1) << (chunk_size*i + j) image = permute_word_by_wp(h, image) image = permute_word_by_wp(g, image) images_i[1 << j] = image image = <codeword> 0 parity = 0 comb = 0 while True: images_i[comb] = image parity ^= 1 j = 0 if not parity: while not comb & (1 << j): j += 1 j += 1 if j == chunk_size: break else: comb ^= (1 << j) image ^= images_i[1 << j] return word_perm
cdef WordPermutation *create_inv_word_perm(WordPermutation *g): r""" Create the inverse $g^{-1}$ of the word permutation of $g$. """ cdef int i, j cdef codeword temp cdef WordPermutation *w
cdef int dealloc_word_perm(WordPermutation *wp): """ Free the memory used by a word permutation. """ cdef int i
cdef codeword permute_word_by_wp(WordPermutation *wp, codeword word): """ Return the codeword obtained by applying the permutation wp to word. """ cdef int i
""" This function is written in pure C for speed, and is tested from this function.
INPUT:
- B -- a BinaryCode in standard form
OUTPUT:
An array of codewords which represent the expansion of a basis for $B$ to a basis for $(B^\prime)^\perp$, where $B^\prime = B$ if the all-ones vector 1 is in $B$, otherwise $B^\prime = \text{span}(B,1)$ (note that this guarantees that all the vectors in the span of the output have even weight).
TESTS::
sage: from sage.coding.binary_code import test_expand_to_ortho_basis, BinaryCode sage: M = Matrix(GF(2), [[1,1,1,1,1,1,0,0,0,0],[0,0,1,1,1,1,1,1,1,1]]) sage: B = BinaryCode(M) sage: B.put_in_std_form() 0 sage: test_expand_to_ortho_basis(B=B) INPUT CODE: Binary [10,2] linear code, generator matrix [1010001111] [0101111111] Expanding to the basis of an orthogonal complement... Basis: 0010000010 0001000010 0000100001 0000010001 0000001001
""" cdef codeword *output cdef BinaryCode C raise TypeError()
cdef codeword *expand_to_ortho_basis(BinaryCode B, int n): r""" INPUT:
- B -- a BinaryCode in standard form - n -- the degree
OUTPUT:
An array of codewords which represent the expansion of a basis for $B$ to a basis for $(B^\prime)^\perp$, where $B^\prime = B$ if the all-ones vector 1 is in $B$, otherwise $B^\prime = \text{span}(B,1)$ (note that this guarantees that all the vectors in the span of the output have even weight). """ # assumes B is already in standard form cdef codeword *basis cdef WordPermutation *wp raise MemoryError() # If 11...1 is already a word of the code, # then being orthogonal to the code guarantees # being even weight. Otherwise, add this in. else: # NOTE THIS WILL NEVER HAPPEN AS CURRENTLY SET UP! temp = (<codeword>1 << k) - 1 i = k word = <codeword>1 << k # Now: # k is the length of the basis so far # we are now looking at the ith free variable, # word has a 1 in the ith place, and # j is the current row we are putting in basis # now basis is length i else: else:
cdef class BinaryCode: """ Minimal, but optimized, binary code object.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: M = Matrix(GF(2), [[1,1,1,1]]) sage: B = BinaryCode(M) # create from matrix sage: C = BinaryCode(B, 60) # create using glue sage: D = BinaryCode(C, 240) sage: E = BinaryCode(D, 85) sage: B Binary [4,1] linear code, generator matrix [1111] sage: C Binary [6,2] linear code, generator matrix [111100] [001111] sage: D Binary [8,3] linear code, generator matrix [11110000] [00111100] [00001111] sage: E Binary [8,4] linear code, generator matrix [11110000] [00111100] [00001111] [10101010]
sage: M = Matrix(GF(2), [[1]*32]) sage: B = BinaryCode(M) sage: B Binary [32,1] linear code, generator matrix [11111111111111111111111111111111]
""" def __cinit__(self, arg1, arg2=None): cdef int nrows, i, j, size cdef int nwords, other_nwords, parity, combination cdef codeword word, glue_word cdef BinaryCode other cdef codeword *self_words cdef codeword *self_basis cdef codeword *other_basis
else: else: raise NotImplementedError("!")
raise NotImplementedError("Columns and rows are stored as ints. This code is too big.")
if self.words is not NULL: sig_free(self.words) if self.basis is not NULL: sig_free(self.basis) raise MemoryError("Memory.")
else:
else: # isinstance(arg1, BinaryCode)
def __dealloc__(self):
def __reduce__(self): """ Method for pickling and unpickling BinaryCodes.
TESTS::
sage: from sage.coding.binary_code import * sage: M = Matrix(GF(2), [[1,1,1,1]]) sage: B = BinaryCode(M) sage: loads(dumps(B)) == B True
"""
def __richcmp__(self, other, int op): """ Comparison of BinaryCodes.
TESTS::
sage: from sage.coding.binary_code import * sage: M = Matrix(GF(2), [[1,1,1,1]]) sage: B = BinaryCode(M) sage: C = BinaryCode(B.matrix()) sage: B == C True """ return NotImplemented
def matrix(self): """ Returns the generator matrix of the BinaryCode, i.e. the code is the rowspace of B.matrix().
EXAMPLES::
sage: M = Matrix(GF(2), [[1,1,1,1,0,0],[0,0,1,1,1,1]]) sage: from sage.coding.binary_code import * sage: B = BinaryCode(M) sage: B.matrix() [1 1 1 1 0 0] [0 0 1 1 1 1]
""" cdef int i, j
def print_data(self): """ Print all data for ``self``.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: M = Matrix(GF(2), [[1,1,1,1]]) sage: B = BinaryCode(M) sage: C = BinaryCode(B, 60) sage: D = BinaryCode(C, 240) sage: E = BinaryCode(D, 85) sage: B.print_data() # random - actually "print(P.print_data())" ncols: 4 nrows: 1 nwords: 2 radix: 32 basis: 1111 words: 0000 1111 sage: C.print_data() # random - actually "print(P.print_data())" ncols: 6 nrows: 2 nwords: 4 radix: 32 basis: 111100 001111 words: 000000 111100 001111 110011 sage: D.print_data() # random - actually "print(P.print_data())" ncols: 8 nrows: 3 nwords: 8 radix: 32 basis: 11110000 00111100 00001111 words: 00000000 11110000 00111100 11001100 00001111 11111111 00110011 11000011 sage: E.print_data() # random - actually "print(P.print_data())" ncols: 8 nrows: 4 nwords: 16 radix: 32 basis: 11110000 00111100 00001111 10101010 words: 00000000 11110000 00111100 11001100 00001111 11111111 00110011 11000011 10101010 01011010 10010110 01100110 10100101 01010101 10011001 01101001 """ cdef int ui cdef int i
def __repr__(self): """ String representation of ``self``.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: M = Matrix(GF(2), [[1,1,1,1,0,0,0,0],[0,0,1,1,1,1,0,0],[0,0,0,0,1,1,1,1],[1,0,1,0,1,0,1,0]]) sage: B = BinaryCode(M) sage: B Binary [8,4] linear code, generator matrix [11110000] [00111100] [00001111] [10101010]
""" cdef int i, j
def _word(self, coords): """ Considering coords as an integer in binary, think of the 0's and 1's as coefficients of the basis given by self.matrix(). This function returns a string representation of that word.
EXAMPLES::
sage: from sage.coding.binary_code import * sage: M = Matrix(GF(2), [[1,1,1,1]]) sage: B = BinaryCode(M) sage: B._word(0) '0000' sage: B._word(1) '1111'
Note that behavior under input which does not represent a word in the code is unspecified (gives nonsense).
"""
def _is_one(self, word, col): """ Returns the col-th letter of word, i.e. 0 or 1. Words are expressed as integers, which represent linear combinations of the rows of the generator matrix of the code.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: M = Matrix(GF(2), [[1,1,1,1,0,0,0,0],[0,0,1,1,1,1,0,0],[0,0,0,0,1,1,1,1],[1,0,1,0,1,0,1,0]]) sage: B = BinaryCode(M) sage: B Binary [8,4] linear code, generator matrix [11110000] [00111100] [00001111] [10101010] sage: B._is_one(7, 4) 0 sage: B._is_one(8, 4) 1 sage: B._is_automorphism([1,0,3,2,4,5,6,7], [0, 1, 2, 3, 4, 5, 6, 7, 9, 8, 11, 10, 13, 12, 15, 14]) 1
"""
cdef int is_one(self, int word, int column):
def _is_automorphism(self, col_gamma, word_gamma): """ Check whether a given permutation is an automorphism of the code.
INPUT:
- col_gamma -- permutation sending i |--> col_gamma[i] acting on the columns. - word_gamma -- permutation sending i |--> word_gamma[i] acting on the words.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: M = Matrix(GF(2), [[1,1,1,1,0,0,0,0],[0,0,1,1,1,1,0,0],[0,0,0,0,1,1,1,1],[1,0,1,0,1,0,1,0]]) sage: B = BinaryCode(M) sage: B Binary [8,4] linear code, generator matrix [11110000] [00111100] [00001111] [10101010] sage: B._is_automorphism([1,0,3,2,4,5,6,7], [0, 1, 2, 3, 4, 5, 6, 7, 9, 8, 11, 10, 13, 12, 15, 14]) 1
""" cdef int i cdef int *_col_gamma cdef int *_word_gamma if _word_gamma is not NULL: sig_free(_word_gamma) if _col_gamma is not NULL: sig_free(_col_gamma) raise MemoryError("Memory.")
cdef int is_automorphism(self, int *col_gamma, int *word_gamma):
def apply_permutation(self, labeling): """ Apply a column permutation to the code.
INPUT:
- labeling -- a list permutation of the columns
EXAMPLES::
sage: from sage.coding.binary_code import * sage: B = BinaryCode(codes.GolayCode(GF(2)).generator_matrix()) sage: B Binary [24,12] linear code, generator matrix [100000000000101011100011] [010000000000111110010010] [001000000000110100101011] [000100000000110001110110] [000010000000110011011001] [000001000000011001101101] [000000100000001100110111] [000000010000101101111000] [000000001000010110111100] [000000000100001011011110] [000000000010101110001101] [000000000001010111000111] sage: B.apply_permutation(list(range(11,-1,-1)) + list(range(12, 24))) sage: B Binary [24,12] linear code, generator matrix [000000000001101011100011] [000000000010111110010010] [000000000100110100101011] [000000001000110001110110] [000000010000110011011001] [000000100000011001101101] [000001000000001100110111] [000010000000101101111000] [000100000000010110111100] [001000000000001011011110] [010000000000101110001101] [100000000000010111000111]
""" # Tests for this function implicitly test _apply_permutation_to_basis # and _update_words_from_basis. These functions should not be used # individually by the user, so they remain cdef'd.
cdef void _apply_permutation_to_basis(self, object labeling): cdef WordPermutation *wp cdef int i
cdef void _update_words_from_basis(self): cdef codeword word cdef int j, parity, combination else:
cpdef int put_in_std_form(self): """ Put the code in binary form, which is defined by an identity matrix on the left, augmented by a matrix of data.
EXAMPLES::
sage: from sage.coding.binary_code import * sage: M = Matrix(GF(2), [[1,1,1,1,0,0],[0,0,1,1,1,1]]) sage: B = BinaryCode(M); B Binary [6,2] linear code, generator matrix [111100] [001111] sage: B.put_in_std_form(); B 0 Binary [6,2] linear code, generator matrix [101011] [010111]
""" cdef object perm else:
cdef class OrbitPartition: """ Structure which keeps track of which vertices are equivalent under the part of the automorphism group that has already been seen, during search. Essentially a disjoint-set data structure*, which also keeps track of the minimum element and size of each cell of the partition, and the size of the partition.
See :wikipedia:`Disjoint-set_data_structure`
""" def __cinit__(self, int nrows, int ncols): cdef int col cdef int nwords, word if self.wd_parent is not NULL: sig_free(self.wd_parent) if self.wd_rank is not NULL: sig_free(self.wd_rank) if self.wd_min_cell_rep is not NULL: sig_free(self.wd_min_cell_rep) if self.wd_size is not NULL: sig_free(self.wd_size) if self.col_parent is not NULL: sig_free(self.col_parent) if self.col_rank is not NULL: sig_free(self.col_rank) if self.col_min_cell_rep is not NULL: sig_free(self.col_min_cell_rep) if self.col_size is not NULL: sig_free(self.col_size) raise MemoryError("Memory.")
def __dealloc__(self):
def __repr__(self): """ Return a string representation of the orbit partition.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: O = OrbitPartition(4, 8) sage: O OrbitPartition on 16 words and 8 columns. Data: Words: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 Columns: 0,1,2,3,4,5,6,7
""" cdef int i cdef int j # s += 'Parents::\n' # s = s[:-1] + '\n' # s += 'Min Cell Reps::\n' # s += 'Words:\n' # for i from 0 <= i < self.nwords: # s += '%d,'%self.wd_min_cell_rep[i] # s = s[:-1] + '\nColumns:\n' # for j from 0 <= j < self.ncols: # s += '%d,'%self.col_min_cell_rep[j]
def _wd_find(self, word): """ Returns the root of word.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: O = OrbitPartition(4, 8) sage: O OrbitPartition on 16 words and 8 columns. Data: Words: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 Columns: 0,1,2,3,4,5,6,7 sage: O._wd_find(12) 12
"""
cdef int wd_find(self, int word): else:
def _wd_union(self, x, y): """ Join the cells containing x and y.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: O = OrbitPartition(4, 8) sage: O OrbitPartition on 16 words and 8 columns. Data: Words: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 Columns: 0,1,2,3,4,5,6,7 sage: O._wd_union(1,10) sage: O OrbitPartition on 16 words and 8 columns. Data: Words: 0,1,2,3,4,5,6,7,8,9,1,11,12,13,14,15 Columns: 0,1,2,3,4,5,6,7 sage: O._wd_find(10) 1
"""
cdef void wd_union(self, int x, int y): cdef int x_root, y_root
def _col_find(self, col): """ Returns the root of col.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: O = OrbitPartition(4, 8) sage: O OrbitPartition on 16 words and 8 columns. Data: Words: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 Columns: 0,1,2,3,4,5,6,7 sage: O._col_find(6) 6
"""
cdef int col_find(self, int col): else:
def _col_union(self, x, y): """ Join the cells containing x and y.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: O = OrbitPartition(4, 8) sage: O OrbitPartition on 16 words and 8 columns. Data: Words: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 Columns: 0,1,2,3,4,5,6,7 sage: O._col_union(1,4) sage: O OrbitPartition on 16 words and 8 columns. Data: Words: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 Columns: 0,1,2,3,1,5,6,7 sage: O._col_find(4) 1
"""
cdef void col_union(self, int x, int y): cdef int x_root, y_root
def _merge_perm(self, col_gamma, wd_gamma): """ Merges the cells of self under the given permutation. If gamma[a] = b, then after merge_perm, a and b will be in the same cell. Returns 0 if nothing was done, otherwise returns 1.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: O = OrbitPartition(4, 8) sage: O OrbitPartition on 16 words and 8 columns. Data: Words: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 Columns: 0,1,2,3,4,5,6,7 sage: O._merge_perm([1,0,3,2,4,5,6,7], [0,1,2,3,4,5,6,7,9,8,11,10,13,12,15,14]) 1 sage: O OrbitPartition on 16 words and 8 columns. Data: Words: 0,1,2,3,4,5,6,7,8,8,10,10,12,12,14,14 Columns: 0,0,2,2,4,5,6,7
""" cdef int i cdef int *_col_gamma cdef int *_wd_gamma if _wd_gamma is not NULL: sig_free(_wd_gamma) if _col_gamma is not NULL: sig_free(_col_gamma) raise MemoryError("Memory.")
cdef int merge_perm(self, int *col_gamma, int *wd_gamma): cdef int i, gamma_i_root
cdef class PartitionStack: """ Partition stack structure for traversing the search tree during automorphism group computation. """ def __cinit__(self, arg1, arg2=None): cdef int k, nwords, ncols, sizeof_int cdef int *wd_ents cdef int *wd_lvls cdef int *col_ents cdef int *col_lvls cdef int *col_degs cdef int *col_counts cdef int *col_output cdef int *wd_degs cdef int *wd_counts cdef int *wd_output
# data
# scratch space
if self.wd_ents is not NULL: sig_free(self.wd_ents) if self.wd_lvls is not NULL: sig_free(self.wd_lvls) if self.col_ents is not NULL: sig_free(self.col_ents) if self.col_lvls is not NULL: sig_free(self.col_lvls) if self.col_degs is not NULL: sig_free(self.col_degs) if self.col_counts is not NULL: sig_free(self.col_counts) if self.col_output is not NULL: sig_free(self.col_output) if self.wd_degs is not NULL: sig_free(self.wd_degs) if self.wd_counts is not NULL: sig_free(self.wd_counts) if self.wd_output is not NULL: sig_free(self.wd_output) raise MemoryError("Memory.")
else:
def __dealloc__(self):
def print_data(self): """ Prints all data for self.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: P = PartitionStack(2, 6) sage: print(P.print_data()) nwords:4 nrows:2 ncols:6 radix:32 wd_ents: 0 1 2 3 wd_lvls: 12 12 12 -1 col_ents: 0 1 2 3 4 5 col_lvls: 12 12 12 12 12 -1 col_degs: 0 0 0 0 0 0 col_counts: 0 0 0 0 col_output: 0 0 0 0 0 0 wd_degs: 0 0 0 0 wd_counts: 0 0 0 0 0 0 0 wd_output: 0 0 0 0
""" cdef int i, j s += "basis_locations:" + '\n' j = 1 while (1 << j) < self.nwords: j += 1 for i from 0 <= i < j: s += str(self.basis_locations[i]) + '\n'
def __repr__(self): """ Return a string representation of self.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: P = PartitionStack(2, 6) sage: P ({0,1,2,3}) ({0,1,2,3,4,5})
""" cdef int i, j, k
def _repr_at_k(self, k): """ Gives a string representing the partition at level k:
EXAMPLES::
sage: from sage.coding.binary_code import * sage: P = PartitionStack(2, 6); P ({0,1,2,3}) ({0,1,2,3,4,5}) sage: P._repr_at_k(0) '({0,1,2,3}) ({0,1,2,3,4,5})\n'
""" else: else:
def _is_discrete(self, k): """ Returns whether the partition at level k is discrete.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: P = PartitionStack(2, 6) sage: [P._split_vertex(i,i+1) for i in range(5)] [0, 1, 2, 3, 4] sage: P._sort_wds(0, [0,2,3,1], 5) 0 sage: P ({0,3,1,2}) ({0,1,2,3,4,5}) ({0,3,1,2}) ({0},{1,2,3,4,5}) ({0,3,1,2}) ({0},{1},{2,3,4,5}) ({0,3,1,2}) ({0},{1},{2},{3,4,5}) ({0,3,1,2}) ({0},{1},{2},{3},{4,5}) ({0},{3},{1},{2}) ({0},{1},{2},{3},{4},{5}) sage: P._is_discrete(4) 0 sage: P._is_discrete(5) 1
"""
cdef int is_discrete(self, int k):
def _num_cells(self, k): """ Returns the number of cells in the partition at level k.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: P = PartitionStack(2, 6) sage: [P._split_vertex(i,i+1) for i in range(5)] [0, 1, 2, 3, 4] sage: P ({0,1,2,3}) ({0,1,2,3,4,5}) ({0,1,2,3}) ({0},{1,2,3,4,5}) ({0,1,2,3}) ({0},{1},{2,3,4,5}) ({0,1,2,3}) ({0},{1},{2},{3,4,5}) ({0,1,2,3}) ({0},{1},{2},{3},{4,5}) ({0,1,2,3}) ({0},{1},{2},{3},{4},{5}) sage: P._num_cells(3) 5
"""
cdef int num_cells(self, int k):
def _sat_225(self, k): """ Returns whether the partition at level k satisfies the hypotheses of Lemma 2.25 in Brendan McKay's Practical Graph Isomorphism paper (see sage/graphs/graph_isom.pyx.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: P = PartitionStack(2, 6) sage: [P._split_vertex(i,i+1) for i in range(5)] [0, 1, 2, 3, 4] sage: P._sat_225(3) 0 sage: P._sat_225(4) 1 sage: P ({0,1,2,3}) ({0,1,2,3,4,5}) ({0,1,2,3}) ({0},{1,2,3,4,5}) ({0,1,2,3}) ({0},{1},{2,3,4,5}) ({0,1,2,3}) ({0},{1},{2},{3,4,5}) ({0,1,2,3}) ({0},{1},{2},{3},{4,5}) ({0,1,2,3}) ({0},{1},{2},{3},{4},{5})
"""
cdef int sat_225(self, int k): else: else: return 1 return 1
# def _new_min_cell_reps(self, k): #TODO # """ # Returns an integer whose bits represent which columns are minimal cell # representatives. # # EXAMPLES: # sage: import sage.coding.binary_code # sage: from sage.coding.binary_code import * # sage: P = PartitionStack(2, 6) # sage: [P._split_column(i,i+1) for i in range(5)] # [0, 1, 2, 3, 4] # sage: a = P._min_cell_reps(2) # sage: Integer(a).binary() # '111' # sage: P # ({0,1,2,3}) # ({0,1,2,3}) # ({0,1,2,3}) # ({0,1,2,3}) # ({0,1,2,3,4,5}) # ({0},{1,2,3,4,5}) # ({0},{1},{2,3,4,5}) # ({0},{1},{2},{3,4,5}) # ({0},{1},{2},{3},{4,5}) # ({0},{1},{2},{3},{4},{5}) # # """ # return self.min_cell_reps(k) # # cdef int min_cell_reps(self, int k): # cdef int i # cdef int reps = 1 # cdef int *self_col_lvls = self.col_lvls # for i from 0 < i < self.ncols: # if self_col_lvls[i-1] <= k: # reps += (1 << i) # return reps # cdef void new_min_cell_reps(self, int k, unsigned int *Omega, int start): cdef int i, j cdef int *self_col_lvls = self.col_lvls cdef int *self_wd_lvls = self.wd_lvls cdef int *self_col_ents = self.col_ents cdef int *self_wd_ents = self.wd_ents cdef int reps = (1 << self_col_ents[0]), length, word cdef int radix = self.radix, nwords = self.nwords, ncols = self.ncols length = 1 + nwords/radix if nwords%radix: length += 1 for i from 0 <= i < length: Omega[start+i] = 0 for i from 0 < i < ncols: Omega[start] += ((self_col_lvls[i-1] <= k) << self_col_ents[i]) Omega[start+1] = (1 << self_wd_ents[0]) for i from 0 < i < nwords: if self_wd_lvls[i-1] <= k: word = self_wd_lvls[i-1] Omega[start+1+word/radix] += (1 << word%radix)
# def _fixed_cols(self, mcrs, k): #TODO # """ # Returns an integer whose bits represent which columns are fixed. For # efficiency, mcrs is the output of min_cell_reps. # # EXAMPLES: # sage: import sage.coding.binary_code # sage: from sage.coding.binary_code import * # sage: P = PartitionStack(2, 6) # sage: [P._split_column(i,i+1) for i in range(5)] # [0, 1, 2, 3, 4] # sage: a = P._fixed_cols(7, 2) # sage: Integer(a).binary() # '11' # sage: P # ({0,1,2,3}) # ({0,1,2,3}) # ({0,1,2,3}) # ({0,1,2,3}) # ({0,1,2,3,4,5}) # ({0},{1,2,3,4,5}) # ({0},{1},{2,3,4,5}) # ({0},{1},{2},{3,4,5}) # ({0},{1},{2},{3},{4,5}) # ({0},{1},{2},{3},{4},{5}) # # """ # return self.fixed_cols(mcrs, k) # # cdef int fixed_cols(self, int mcrs, int k): # cdef int i # cdef int fixed = 0 # cdef int *self_col_lvls = self.col_lvls # for i from 0 <= i < self.ncols: # if self_col_lvls[i] <= k: # fixed += (1 << i) # return fixed & mcrs # cdef void fixed_vertices(self, int k, unsigned int *Phi, unsigned int *Omega, int start): cdef int i, j, length, ell, fixed = 0 cdef int radix = self.radix, nwords = self.nwords, ncols = self.ncols cdef int *self_col_lvls = self.col_lvls cdef int *self_wd_lvls = self.wd_lvls cdef int *self_col_ents = self.col_ents cdef int *self_wd_ents = self.wd_ents for i from 0 <= i < ncols: fixed += ((self_col_lvls[i] <= k) << self_col_ents[i]) Phi[start] = fixed & Omega[start] # zero out the rest of Phi length = 1 + nwords/self.radix if nwords%self.radix: length += 1 for i from 0 < i < length: Phi[start+i] = 0 for i from 0 <= i < nwords: ell = self_wd_ents[i] Phi[start+1+ell/radix] = ((self_wd_lvls[i] <= k) << ell%radix) for i from 0 < i < length: Phi[i] &= Omega[i]
# def _first_smallest_nontrivial(self, k): #TODO # """ # Returns an integer representing the first, smallest nontrivial cell of columns. # # EXAMPLES: # sage: import sage.coding.binary_code # sage: from sage.coding.binary_code import * # sage: P = PartitionStack(2, 6) # sage: [P._split_column(i,i+1) for i in range(5)] # [0, 1, 2, 3, 4] # sage: a = P._first_smallest_nontrivial(2) # sage: Integer(a).binary().zfill(32) # '00000000000000000000000000111100' # sage: P # ({0,1,2,3}) # ({0,1,2,3}) # ({0,1,2,3}) # ({0,1,2,3}) # ({0,1,2,3,4,5}) # ({0},{1,2,3,4,5}) # ({0},{1},{2,3,4,5}) # ({0},{1},{2},{3,4,5}) # ({0},{1},{2},{3},{4,5}) # ({0},{1},{2},{3},{4},{5}) # # """ # return self.first_smallest_nontrivial(k) # # cdef int first_smallest_nontrivial(self, int k): # cdef int cell # cdef int i = 0, j = 0, location = 0, ncols = self.ncols # cdef int *self_col_lvls = self.col_lvls # while True: # if self_col_lvls[i] <= k: # if i != j and ncols > i - j + 1: # ncols = i - j + 1 # location = j # j = i + 1 # if self_col_lvls[i] == -1: break # i += 1 # # location now points to the beginning of the first, smallest, # # nontrivial cell # j = location # self.v = self.col_ents[j] # while True: # if self_col_lvls[j] <= k: break # j += 1 # # j now points to the last element of the cell # i = self.radix - j - 1 # the cell is represented in binary, reading from the right: # cell = (~0 << location) ^ (~0 << j+1) # <------- self.radix -----> # return cell # [0]*(radix-j-1) + [1]*(j-location+1) + [0]*location # cdef int new_first_smallest_nontrivial(self, int k, unsigned int *W, int start): cdef int ell # i = 0; j = 0 # while True: # if self_wd_lvls[i] <= k: # if i != j and min > i - j + 1: # min = i - j + 1 # min_is_col = 0 # location = j # j = i + 1 # if self_wd_lvls[i] == -1: break # i += 1 # location now points to the beginning of the first, smallest, # nontrivial cell #zero out this level of W: # j now points to the last element of the cell else: while True: if self_wd_lvls[j] <= k: break j += 1 # j now points to the last element of the cell i = location while i <= j: ell = self_wd_ents[i] W[start+1+ell/radix] ^= (1 << ell%radix) i += 1 return self_wd_ents[location] ^ self.flag
def _dangerous_dont_use_set_ents_lvls(self, col_ents, col_lvls, wd_ents, wd_lvls): """ For debugging only.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: P = PartitionStack(2, 6) sage: P ({0,1,2,3}) ({0,1,2,3,4,5}) sage: P._dangerous_dont_use_set_ents_lvls([99]*6, [0,3,2,3,5,-1], [4,3,5,6], [3,2,1,-1]) sage: P ({4,3,5,6}) ({99},{99,99,99,99,99}) ({4,3,5},{6}) ({99},{99,99,99,99,99}) ({4,3},{5},{6}) ({99},{99,99},{99,99,99}) ({4},{3},{5},{6}) ({99},{99},{99},{99},{99,99})
""" cdef int i
def _col_percolate(self, start, end): """ Do one round of bubble sort on ents.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: P = PartitionStack(2, 6) sage: P._dangerous_dont_use_set_ents_lvls(list(range(5,-1,-1)), [1,2,2,3,3,-1], list(range(3,-1,-1)), [1,1,2,-1]) sage: P ({3,2,1,0}) ({5,4,3,2,1,0}) ({3},{2},{1,0}) ({5},{4,3,2,1,0}) ({3},{2},{1},{0}) ({5},{4},{3},{2,1,0}) ({3},{2},{1},{0}) ({5},{4},{3},{2},{1},{0}) sage: P._wd_percolate(0,3) sage: P._col_percolate(0,5) sage: P ({0,3,2,1}) ({0,5,4,3,2,1}) ({0},{3},{2,1}) ({0},{5,4,3,2,1}) ({0},{3},{2},{1}) ({0},{5},{4},{3,2,1}) ({0},{3},{2},{1}) ({0},{5},{4},{3},{2},{1})
"""
cdef void col_percolate(self, int start, int end): cdef int i, temp
def _wd_percolate(self, start, end): """ Do one round of bubble sort on ents.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: P = PartitionStack(2, 6) sage: P._dangerous_dont_use_set_ents_lvls(list(range(5,-1,-1)), [1,2,2,3,3,-1], list(range(3,-1,-1)), [1,1,2,-1]) sage: P ({3,2,1,0}) ({5,4,3,2,1,0}) ({3},{2},{1,0}) ({5},{4,3,2,1,0}) ({3},{2},{1},{0}) ({5},{4},{3},{2,1,0}) ({3},{2},{1},{0}) ({5},{4},{3},{2},{1},{0}) sage: P._wd_percolate(0,3) sage: P._col_percolate(0,5) sage: P ({0,3,2,1}) ({0,5,4,3,2,1}) ({0},{3},{2,1}) ({0},{5,4,3,2,1}) ({0},{3},{2},{1}) ({0},{5},{4},{3,2,1}) ({0},{3},{2},{1}) ({0},{5},{4},{3},{2},{1})
"""
cdef void wd_percolate(self, int start, int end): cdef int i, temp
# def _split_column(self, int v, int k): #TODO # """ # Split column v out, placing it before the rest of the cell it was in. # Returns the location of the split column. # # EXAMPLES: # sage: import sage.coding.binary_code # sage: from sage.coding.binary_code import * # sage: P = PartitionStack(2, 6) # sage: [P._split_column(i,i+1) for i in range(5)] # [0, 1, 2, 3, 4] # sage: P # ({0,1,2,3}) # ({0,1,2,3}) # ({0,1,2,3}) # ({0,1,2,3}) # ({0,1,2,3,4,5}) # ({0},{1,2,3,4,5}) # ({0},{1},{2,3,4,5}) # ({0},{1},{2},{3,4,5}) # ({0},{1},{2},{3},{4,5}) # ({0},{1},{2},{3},{4},{5}) # sage: P = PartitionStack(2, 6) # sage: P._split_column(0,1) # 0 # sage: P._split_column(2,2) # 1 # sage: P # ({0,1,2,3}) # ({0,1,2,3}) # ({0,1,2,3}) # ({0,1,2,3}) # ({0,2,1,3,4,5}) # ({0},{2,1,3,4,5}) # ({0},{2},{1,3,4,5}) # ({0},{2},{1,3,4,5}) # ({0},{2},{1,3,4,5}) # ({0},{2},{1,3,4,5}) # # """ # return self.split_column(v, k) # # cdef int split_column(self, int v, int k): # cdef int i = 0, j # cdef int *self_col_ents = self.col_ents # cdef int *self_col_lvls = self.col_lvls # while self_col_ents[i] != v: i += 1 # j = i # while self_col_lvls[i] > k: i += 1 # if j == 0 or self_col_lvls[j-1] <= k: # self.col_percolate(j+1, i) # else: # while j != 0 and self_col_lvls[j-1] > k: # self_col_ents[j] = self_col_ents[j-1] # j -= 1 # self_col_ents[j] = v # self_col_lvls[j] = k # return j #
def _split_vertex(self, v, k): """ Split vertex v out, placing it before the rest of the cell it was in. Returns the location of the split vertex.
.. NOTE::
There is a convention regarding whether a vertex is a word or a column. See the 'flag' attribute of the PartitionStack object: If vertex&flag is not zero, it is a word.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: P = PartitionStack(2, 6) sage: [P._split_vertex(i,i+1) for i in range(5)] [0, 1, 2, 3, 4] sage: P ({0,1,2,3}) ({0,1,2,3,4,5}) ({0,1,2,3}) ({0},{1,2,3,4,5}) ({0,1,2,3}) ({0},{1},{2,3,4,5}) ({0,1,2,3}) ({0},{1},{2},{3,4,5}) ({0,1,2,3}) ({0},{1},{2},{3},{4,5}) ({0,1,2,3}) ({0},{1},{2},{3},{4},{5})
"""
cdef int split_vertex(self, int v, int k): cdef int *ents cdef int *lvls ents = self.wd_ents lvls = self.wd_lvls v = v ^ flag while ents[i] != v: i += 1 v = v ^ flag else: self.wd_percolate(j+1, i) else: else: ents[j] = v ^ flag else: return j ^ flag else:
def _col_degree(self, C, col, wd_ptr, k): """ Returns the number of words in the cell specified by wd_ptr that have a 1 in the col-th column.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: P = PartitionStack(2, 6) sage: M = Matrix(GF(2), [[1,1,1,1,0,0],[0,0,1,1,1,1]]) sage: B = BinaryCode(M) sage: B Binary [6,2] linear code, generator matrix [111100] [001111] sage: [P._split_vertex(i,i+1) for i in range(5)] [0, 1, 2, 3, 4] sage: P ({0,1,2,3}) ({0,1,2,3,4,5}) ({0,1,2,3}) ({0},{1,2,3,4,5}) ({0,1,2,3}) ({0},{1},{2,3,4,5}) ({0,1,2,3}) ({0},{1},{2},{3,4,5}) ({0,1,2,3}) ({0},{1},{2},{3},{4,5}) ({0,1,2,3}) ({0},{1},{2},{3},{4},{5}) sage: P._col_degree(B, 2, 0, 2) 2
"""
cdef int col_degree(self, BinaryCode CG, int col, int wd_ptr, int k):
def _wd_degree(self, C, wd, col_ptr, k): """ Returns the number of columns in the cell specified by col_ptr that are 1 in wd.
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: P = PartitionStack(2, 6) sage: M = Matrix(GF(2), [[1,1,1,1,0,0],[0,0,1,1,1,1]]) sage: B = BinaryCode(M) sage: B Binary [6,2] linear code, generator matrix [111100] [001111] sage: [P._split_vertex(i,i+1) for i in range(5)] [0, 1, 2, 3, 4] sage: P ({0,1,2,3}) ({0,1,2,3,4,5}) ({0,1,2,3}) ({0},{1,2,3,4,5}) ({0,1,2,3}) ({0},{1},{2,3,4,5}) ({0,1,2,3}) ({0},{1},{2},{3,4,5}) ({0,1,2,3}) ({0},{1},{2},{3},{4,5}) ({0,1,2,3}) ({0},{1},{2},{3},{4},{5}) sage: P._wd_degree(B, 1, 1, 1) 3
"""
cdef int wd_degree(self, BinaryCode CG, int wd, int col_ptr, int k, int *ham_wts):
def _sort_cols(self, start, degrees, k): """ Essentially a counting sort, but on only one cell of the partition.
INPUT:
- start -- location of the beginning of the cell - k -- at what level of refinement the partition of interest lies - degrees -- the counts to sort by
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: P = PartitionStack(2, 6) sage: [P._split_vertex(i,i+1) for i in range(5)] [0, 1, 2, 3, 4] sage: P._sort_cols(1, [0,2,2,1,1], 1) 2 sage: P ({0,1,2,3}) ({0,1,4,5,2,3}) ({0,1,2,3}) ({0},{1},{4,5},{2,3})
""" cdef int i
cdef int sort_cols(self, int start, int k):
# i+start is the right endpoint of the cell now
def _sort_wds(self, start, degrees, k): """ Essentially a counting sort, but on only one cell of the partition.
INPUT:
- start -- location of the beginning of the cell - k -- at what level of refinement the partition of interest lies - degrees -- the counts to sort by
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: P = PartitionStack(3, 6) sage: P._sort_wds(0, [0,0,3,3,3,3,2,2], 1) 4 sage: P ({0,1,6,7,2,3,4,5}) ({0,1,2,3,4,5}) ({0,1},{6,7},{2,3,4,5}) ({0,1,2,3,4,5})
""" cdef int i
cdef int sort_wds(self, int start, int k):
# i+start is the right endpoint of the cell now
def _refine(self, k, alpha, CG): """ EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: M = Matrix(GF(2), [[1,1,1,1,0,0,0,0],[0,0,1,1,1,1,0,0],[0,0,0,0,1,1,1,1],[1,0,1,0,1,0,1,0]]) sage: B = BinaryCode(M) sage: P = PartitionStack(4, 8) sage: P._refine(1, [[0,0],[1,0]], B) 181 sage: P._split_vertex(0, 2) 0 sage: P._refine(2, [[0,0]], B) 290 sage: P._split_vertex(1, 3) 1 sage: P._refine(3, [[0,1]], B) 463 sage: P._split_vertex(2, 4) 2 sage: P._refine(4, [[0,2]], B) 1500 sage: P._split_vertex(3, 5) 3 sage: P._refine(5, [[0,3]], B) 641 sage: P._split_vertex(4, 6) 4 sage: P._refine(6, [[0,4]], B) 1224 sage: P._is_discrete(5) 0 sage: P._is_discrete(6) 1 sage: P ({0,4,6,2,13,9,11,15,10,14,12,8,7,3,1,5}) ({0,1,2,3,4,7,6,5}) ({0},{4,6,2,13,9,11,15,10,14,12,8,7,3,1},{5}) ({0,1,2,3,4,7,6,5}) ({0},{4,6,2,13,9,11,15},{10,14,12,8,7,3,1},{5}) ({0},{1,2,3,4,7,6,5}) ({0},{4,6,2},{13,9,11,15},{10,14,12,8},{7,3,1},{5}) ({0},{1},{2,3,4,7,6,5}) ({0},{4},{6,2},{13,9},{11,15},{10,14},{12,8},{7,3},{1},{5}) ({0},{1},{2},{3,4,7,6,5}) ({0},{4},{6,2},{13,9},{11,15},{10,14},{12,8},{7,3},{1},{5}) ({0},{1},{2},{3},{4,7,6,5}) ({0},{4},{6},{2},{13},{9},{11},{15},{10},{14},{12},{8},{7},{3},{1},{5}) ({0},{1},{2},{3},{4},{7},{6},{5})
""" raise MemoryError("Memory.") else:
cdef int refine(self, int k, int *alpha, int alpha_length, BinaryCode CG, int *ham_wts): else:
def _clear(self, k): """ EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: P = PartitionStack(2, 6) sage: [P._split_vertex(i,i+1) for i in range(5)] [0, 1, 2, 3, 4] sage: P ({0,1,2,3}) ({0,1,2,3,4,5}) ({0,1,2,3}) ({0},{1,2,3,4,5}) ({0,1,2,3}) ({0},{1},{2,3,4,5}) ({0,1,2,3}) ({0},{1},{2},{3,4,5}) ({0,1,2,3}) ({0},{1},{2},{3},{4,5}) ({0,1,2,3}) ({0},{1},{2},{3},{4},{5}) sage: P._clear(2) sage: P ({0,1,2,3}) ({0,1,2,3,4,5}) ({0,1,2,3}) ({0},{1,2,3,4,5})
"""
cdef void clear(self, int k):
cpdef int cmp(self, PartitionStack other, BinaryCode CG): """ EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: M = Matrix(GF(2), [[1,1,1,1,0,0,0,0],[0,0,1,1,1,1,0,0],[0,0,0,0,1,1,1,1],[1,0,1,0,1,0,1,0]]) sage: B = BinaryCode(M) sage: P = PartitionStack(4, 8) sage: P._refine(0, [[0,0],[1,0]], B) 181 sage: P._split_vertex(0, 1) 0 sage: P._refine(1, [[0,0]], B) 290 sage: P._split_vertex(1, 2) 1 sage: P._refine(2, [[0,1]], B) 463 sage: P._split_vertex(2, 3) 2 sage: P._refine(3, [[0,2]], B) 1500 sage: P._split_vertex(4, 4) 4 sage: P._refine(4, [[0,4]], B) 1224 sage: P._is_discrete(4) 1 sage: Q = PartitionStack(P) sage: Q._clear(4) sage: Q._split_vertex(5, 4) 4 sage: Q._refine(4, [[0,4]], B) 1224 sage: Q._is_discrete(4) 1 sage: Q.cmp(P, B) 0 """
def print_basis(self): """ EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: P = PartitionStack(4, 8) sage: P._dangerous_dont_use_set_ents_lvls(list(range(8)), list(range(7))+[-1], [4,7,12,11,1,9,3,0,2,5,6,8,10,13,14,15], [0]*16) sage: P ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1,2,3,4,5,6,7}) ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1},{2,3,4,5,6,7}) ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1},{2},{3,4,5,6,7}) ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1},{2},{3},{4,5,6,7}) ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1},{2},{3},{4},{5,6,7}) ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1},{2},{3},{4},{5},{6,7}) ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1},{2},{3},{4},{5},{6},{7}) sage: P._find_basis() sage: P.print_basis() basis_locations: 4 8 0 11
""" cdef int i, j
def _find_basis(self): """ EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: P = PartitionStack(4, 8) sage: P._dangerous_dont_use_set_ents_lvls(list(range(8)), list(range(7))+[-1], [4,7,12,11,1,9,3,0,2,5,6,8,10,13,14,15], [0]*16) sage: P ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1,2,3,4,5,6,7}) ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1},{2,3,4,5,6,7}) ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1},{2},{3,4,5,6,7}) ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1},{2},{3},{4,5,6,7}) ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1},{2},{3},{4},{5,6,7}) ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1},{2},{3},{4},{5},{6,7}) ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1},{2},{3},{4},{5},{6},{7}) sage: P._find_basis() sage: P.print_basis() basis_locations: 4 8 0 11
""" cdef int i
cdef int find_basis(self, int *ham_wts): raise MemoryError("Memory.")
def _get_permutation(self, other): """ EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: M = Matrix(GF(2), [[1,1,1,1,0,0,0,0],[0,0,1,1,1,1,0,0],[0,0,0,0,1,1,1,1],[1,0,1,0,1,0,1,0]]) sage: B = BinaryCode(M) sage: P = PartitionStack(4, 8) sage: P._refine(0, [[0,0],[1,0]], B) 181 sage: P._split_vertex(0, 1) 0 sage: P._refine(1, [[0,0]], B) 290 sage: P._split_vertex(1, 2) 1 sage: P._refine(2, [[0,1]], B) 463 sage: P._split_vertex(2, 3) 2 sage: P._refine(3, [[0,2]], B) 1500 sage: P._split_vertex(4, 4) 4 sage: P._refine(4, [[0,4]], B) 1224 sage: P._is_discrete(4) 1 sage: Q = PartitionStack(P) sage: Q._clear(4) sage: Q._split_vertex(5, 4) 4 sage: Q._refine(4, [[0,4]], B) 1224 sage: Q._is_discrete(4) 1 sage: P._get_permutation(Q) ([0, 1, 2, 3, 4, 5, 6, 7, 12, 13, 14, 15, 8, 9, 10, 11], [0, 1, 2, 3, 5, 4, 7, 6])
""" cdef int i if word_g is not NULL: sig_free(word_g) if col_g is not NULL: sig_free(col_g) raise MemoryError("Memory.")
cdef void get_permutation(self, PartitionStack other, int *word_gamma, int *col_gamma): cdef int i # word_gamma[i] := image of the ith row as linear comb of rows
cdef class BinaryCodeClassifier:
def __cinit__(self):
if self.Phi is not NULL: sig_free(self.Phi) if self.Omega is not NULL: sig_free(self.Omega) if self.W is not NULL: sig_free(self.W) if self.Lambda1 is not NULL: sig_free(self.Lambda1) if self.Lambda2 is not NULL: sig_free(self.Lambda2) if self.Lambda3 is not NULL: sig_free(self.Lambda3) if self.w_gamma is not NULL: sig_free(self.w_gamma) if self.c_gamma is not NULL: sig_free(self.c_gamma) if self.alpha is not NULL: sig_free(self.alpha) if self.v is not NULL: sig_free(self.v) if self.e is not NULL: sig_free(self.e) if self.aut_gp_gens is not NULL: sig_free(self.aut_gp_gens) if self.labeling is not NULL: sig_free(self.labeling) if self.base is not NULL: sig_free(self.base) raise MemoryError("Memory.")
def __dealloc__(self):
cdef void record_automorphism(self, int *gamma, int ncols): cdef int i, j self.aut_gens_size *= 2 self.aut_gp_gens = <int *> sig_realloc( self.aut_gp_gens, self.aut_gens_size * sizeof(int) ) if self.aut_gp_gens is NULL: raise MemoryError("Memory.")
def _aut_gp_and_can_label(self, CC, verbosity=0): """ Compute the automorphism group and canonical label of the code CC.
INPUT:
- CC - a BinaryCode object - verbosity -- a nonnegative integer
OUTPUT: a tuple, (gens, labeling, size, base) gens -- a list of permutations (in list form) representing generators of the permutation automorphism group of the code CC. labeling -- a permutation representing the canonical labeling of the code. mostly for internal use; entries describe the relabeling on the columns. size -- the order of the automorphism group. base -- a set of cols whose action determines the action on all cols
EXAMPLES::
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: BC = BinaryCodeClassifier()
sage: M = Matrix(GF(2),[ ....: [1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0], ....: [0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0], ....: [0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1], ....: [0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1], ....: [0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]]) sage: B = BinaryCode(M) sage: gens, labeling, size, base = BC._aut_gp_and_can_label(B) sage: S = SymmetricGroup(M.ncols()) sage: L = [S([x+1 for x in g]) for g in gens] sage: PermutationGroup(L).order() 322560 sage: size 322560
sage: M = Matrix(GF(2),[ ....: [1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0], ....: [0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0], ....: [0,0,0,0,0,1,0,1,0,0,0,1,1,1,1,1,1], ....: [0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,1]]) sage: B = BinaryCode(M) sage: gens, labeling, size, base = BC._aut_gp_and_can_label(B) sage: S = SymmetricGroup(M.ncols()) sage: L = [S([x+1 for x in g]) for g in gens] sage: PermutationGroup(L).order() 2304 sage: size 2304
sage: M=Matrix(GF(2),[ ....: [1,0,0,1,1,1,1,0,0,1,0,0,0,0,0,0,0], ....: [0,1,0,0,1,1,1,1,0,0,1,0,0,0,0,0,0], ....: [0,0,1,0,0,1,1,1,1,0,0,1,0,0,0,0,0], ....: [0,0,0,1,0,0,1,1,1,1,0,0,1,0,0,0,0], ....: [0,0,0,0,1,0,0,1,1,1,1,0,0,1,0,0,0], ....: [0,0,0,0,0,1,0,0,1,1,1,1,0,0,1,0,0], ....: [0,0,0,0,0,0,1,0,0,1,1,1,1,0,0,1,0], ....: [0,0,0,0,0,0,0,1,0,0,1,1,1,1,0,0,1]]) sage: B = BinaryCode(M) sage: gens, labeling, size, base = BC._aut_gp_and_can_label(B) sage: S = SymmetricGroup(M.ncols()) sage: L = [S([x+1 for x in g]) for g in gens] sage: PermutationGroup(L).order() 136 sage: size 136
sage: M=Matrix(GF(2),[ ....: [0,1,0,1,1,1,0,0,0,1,0,0,0,1,0,0,0,1,1,1,0,1], ....: [1,0,1,1,1,0,0,0,1,0,0,0,1,0,0,0,1,1,1,0,1,0], ....: [0,1,1,1,0,0,0,1,0,0,1,1,0,0,0,1,1,1,0,1,0,0], ....: [1,1,1,0,0,0,1,0,0,1,0,0,0,0,1,1,1,0,1,0,0,1], ....: [1,1,0,0,0,1,0,0,1,0,1,0,0,1,1,1,0,1,0,0,1,0], ....: [1,0,0,0,1,0,0,1,0,1,1,0,1,1,1,0,1,0,0,1,0,0], ....: [0,0,0,1,0,0,1,0,1,1,1,1,1,1,0,1,0,0,1,0,0,0], ....: [0,0,1,0,0,1,0,1,1,1,0,1,1,0,1,0,0,1,0,0,0,1], ....: [0,1,0,0,1,0,1,1,1,0,0,1,0,1,0,0,1,0,0,0,1,1], ....: [1,0,0,1,0,1,1,1,0,0,0,0,1,0,0,1,0,0,0,1,1,1], ....: [0,0,1,0,1,1,1,0,0,0,1,1,0,0,1,0,0,0,1,1,1,0]]) sage: B = BinaryCode(M) sage: gens, labeling, size, base = BC._aut_gp_and_can_label(B) sage: S = SymmetricGroup(M.ncols()) sage: L = [S([x+1 for x in g]) for g in gens] sage: PermutationGroup(L).order() 887040 sage: size 887040
sage: B = BinaryCode(Matrix(GF(2),[[1,0,1],[0,1,1]])) sage: BC._aut_gp_and_can_label(B) ([[0, 2, 1], [1, 0, 2]], [0, 1, 2], 6, [0, 1])
sage: B = BinaryCode(Matrix(GF(2),[[1,1,1,1]])) sage: BC._aut_gp_and_can_label(B) ([[0, 1, 3, 2], [0, 2, 1, 3], [1, 0, 2, 3]], [0, 1, 2, 3], 24, [0, 1, 2])
sage: B = BinaryCode(Matrix(GF(2),[[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]])) sage: gens, labeling, size, base = BC._aut_gp_and_can_label(B) sage: size 87178291200
sage: M = Matrix(GF(2),[ ....: [1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0], ....: [0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0], ....: [0,0,0,0,1,1,0,0,0,0,0,0,1,1,1,1,1,1], ....: [0,0,1,1,0,0,0,0,0,0,1,1,1,1,0,0,1,1], ....: [0,0,0,1,0,0,0,1,0,1,0,1,0,1,1,1,0,1], ....: [0,1,0,0,0,1,0,0,0,1,1,1,0,1,0,1,1,0]]) sage: B = BinaryCode(M) sage: BC._aut_gp_and_can_label(B)[2] 2160
sage: M = Matrix(GF(2),[ ....: [1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], ....: [0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0], ....: [0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0], ....: [0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0], ....: [0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0], ....: [0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0], ....: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1], ....: [1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,1,1,0,0], ....: [1,1,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1,0,0], ....: [1,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,1,0]]) sage: B = BinaryCode(M) sage: BC._aut_gp_and_can_label(B)[2] 294912
sage: M = Matrix(GF(2), [ ....: [1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], ....: [0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], ....: [0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0], ....: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0], ....: [0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0], ....: [0,0,0,0,0,0,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0], ....: [0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1], ....: [0,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1,0,0,1,1,1,0,1], ....: [0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,1,1,1,0,0,0,1]]) sage: B = BinaryCode(M) sage: BC = BinaryCodeClassifier() sage: BC._aut_gp_and_can_label(B)[2] 442368
""" cdef int i, j
cdef void aut_gp_and_can_label(self, BinaryCode C, int verbosity):
# declare variables: cdef int i, j, ii, jj, iii, jjj, iiii # local variables
cdef PartitionStack nu, zeta, rho # nu is the current position in the tree, # zeta the first terminal position, # and rho the best-so-far guess at canonical labeling position cdef int k_rho # the number of partitions in rho # -1 indicates that zeta is not yet defined cdef int hb # longest common ancestor of rho and nu: # rho[hb] == nu[hb], rho[hb+1] != nu[hb+1] # if nu does not satisfy it at k, then hh = k cdef int ht # smallest such that all descendants of zeta[ht] are equivalent under # the portion of the automorphism group so far discovered cdef int *alpha # for storing pointers to cells of nu[k] cdef int tvc # tvc keeps track of which vertex is the first where nu and zeta differ- # zeta was defined by splitting one vertex, and nu was defined by splitting tvc
cdef OrbitPartition Theta # keeps track of which vertices have been discovered to be equivalent cdef unsigned int *Phi # Phi stores the fixed point sets of each automorphism cdef unsigned int *Omega # Omega stores the minimal elements of each cell of the orbit partition # we increment first, the first place we write to is 0. cdef unsigned int *W # for each k, W[k] is a list (as int mask) of the vertices to be searched down from # the current partition, at k. Phi and Omega are ultimately used to make the size of # W as small as possible cdef int *e # 0 or 1, whether or not we have used Omega and Phi to narrow down W[k] yet: see states 12 and 17
# $\Gamma^{(i)} := \Gamma^{(-1)}_{v_0,...,v_i}$. # Then index = $|\Gamma^{(k-1)}|/|\Gamma^{(k)}|$ at (POINT A) # and size = $|\Gamma^{(k-1)}|$ at (POINT A) and (POINT B).
cdef int qzb # keeps track of Lambda[k] {>,<,=} zb[k] cdef int hzf__h_zeta # the max height for which Lambda and zf agree
cdef int *word_gamma cdef int state # keeps track of position in algorithm - see sage/graphs/graph_isom.pyx, search for "STATE DIAGRAM"
while self.w_gamma_size < nwords: self.w_gamma_size *= 2 self.alpha_size = self.w_gamma_size + self.radix self.Phi_size = self.w_gamma_size/self.radix + 1 self.w_gamma = <int *> sig_realloc(self.w_gamma, self.w_gamma_size * sizeof(int) ) self.alpha = <int *> sig_realloc(self.alpha, self.alpha_size * sizeof(int) ) self.Phi = <unsigned int *> sig_realloc(self.Phi, self.Phi_size * self.L * sizeof(int) ) self.Omega = <unsigned int *> sig_realloc(self.Omega, self.Phi_size * self.L * sizeof(int) ) self.W = <unsigned int *> sig_realloc(self.W, self.Phi_size * self.radix * 2 * sizeof(int) ) if self.w_gamma is NULL or self.alpha is NULL or self.Phi is NULL or self.Omega is NULL or self.W is NULL: if self.w_gamma is not NULL: sig_free(self.w_gamma) if self.alpha is not NULL: sig_free(self.alpha) if self.Phi is not NULL: sig_free(self.Phi) if self.Omega is not NULL: sig_free(self.Omega) if self.W is not NULL: sig_free(self.W) raise MemoryError("Memory.")
# trivial case raise NotImplementedError("Must supply a nontrivial code.")
# store the first smallest nontrivial cell in W[k], and set v[k] # equal to its minimum element
elif state == 2: # Move down the search tree one level by refining nu: # split out a vertex, and refine nu against it
# only if this is the first time moving down the search tree:
# update hzf__h_zeta # update qzb else: # update hzb # if Lambda[k] > zb[k], then zb[k] := Lambda[k] # (zb keeps track of the indicator invariants corresponding to # rho, the closest canonical leaf so far seen- if Lambda is # bigger, then rho must be about to change
elif state == 3: # attempt to rule out automorphisms while moving down the tree # if k > hzf, then we know that nu currently does not look like zeta, the first # terminal node encountered, thus there is no automorphism to discover. If qzb < 0, # i.e. Lambda[k] < zb[k], then the indicator is not maximal, and we can't reach a # canonical leaf. If neither of these is the case, then proceed to state 4. else: state = 6
elif state == 4: # at this point we have -not- ruled out the presence of automorphisms
# otherwise, prepare to split out another column: # store the first smallest nontrivial cell in W[k], and set v[k] # equal to its minimum element
elif state == 5: # same as state 3, but in the case where we haven't yet defined zeta # i.e. this is our first time down the tree. Once we get to the bottom, # we will have zeta = nu = rho, so we do:
elif state == 6: # at this stage, there is no reason to continue downward, so backtrack
# return to the longest ancestor nu[i] of nu that could have a # descendant equivalent to zeta or could improve on rho. # All terminal nodes descending from nu[hh] are known to be # equivalent, so i < hh. Also, if i > hzb, none of the # descendants of nu[i] can improve rho, since the indicator is # off (Lambda(nu) < Lambda(rho)). If i >= ht, then no descendant # of nu[i] is equivalent to zeta (see [1, p67]). if ht-1 < hh-1: k = ht-1 else: k = hh-1 else: k = hzb__h_rho else: # TODO: is the following line necessary?
# if j == hh, then all nodes lower than our current position are equivalent, so bail out
# recall hh: the height of the oldest ancestor of zeta for which Lemma 2.25 is # satisfied, which implies that all terminal nodes descended from there are equivalent. # If we are looking at such a node, then the partition at nu[hh] can be used for later # pruning, so we store its fixed set and a set of representatives of its cells. if l < self.L-1: l += 1 nu.new_min_cell_reps(hh, Omega, self.Phi_size*l) nu.fixed_vertices(hh, Phi, Omega, self.Phi_size*l)
state = 12
elif state == 7: # we have just arrived at a terminal node of the search tree T(G, Pi) # if this is the first terminal node, go directly to 18, to # process zeta
# hzf is the extremal height of ancestors of both nu and zeta, so if k < hzf, nu is not # equivalent to zeta, i.e. there is no automorphism to discover.
# if C^gamma == C, the permutation is an automorphism, goto 10 else:
elif state == 8: # we have just ruled out the presence of automorphism and have not yet # considered whether nu improves on rho # if qzb < 0, then rho already has larger indicator tuple
# if Lambda[k] > zb[k] or nu is shorter than rho, then we have an improvement for rho
# now Lambda[k] == zb[k] and k == k_rho, so we appeal to an enumeration: # if C(nu) > C(rho), we have a new label, goto 9
# if C(nu) < C(rho), no new label, goto 6
# if C(nu) == C(rho), get the automorphism and goto 10
elif state == 9: # nu is a better guess at the canonical label than rho # set zb[k+1] = Infinity
elif state == 10: # we have an automorphism to process # increment l # store information about the automorphism to Omega and Phi # Omega[ii] = ~(~0 << ncols) # Omega[ii+jj-1] = ~((1 << nwords%self.radix) - 1) # Omega stores the minimum cell representatives # Phi stores the columns fixed by the automorphism
# Now incorporate the automorphism into Theta
# j stores whether anything happened or not- if not, then the automorphism we have # discovered is already in the subgroup spanned by the generators we have output
# otherwise, we have a new generator, so record it: # The variable tvc was set to be the minimum element of W[k] the last time the # algorithm came up to meet zeta. At this point, we were considering the new # possibilities for descending away from zeta at this level. # if this is still a minimum cell representative of Theta, even in light # of this new automorphism, then the current branch off of zeta hasn't been # found equivalent to one already searched yet, so there may still be a # better canonical label downward. i = tvc^nu.flag if Theta.wd_min_cell_rep[Theta.wd_find(i)] == i: state = 11; continue else:
# Otherwise, proceed to where zeta meets nu: k = h state = 13
elif state == 11: # We have just found a new automorphism, and deduced that there may # be a better canonical label below the current branch off of zeta. So go to where # nu meets rho
elif state == 12: # Coming here from either state 6 or 11, the algorithm has discovered # some new information. 11 came from 10, where a new line in Omega and # Phi was just recorded, and 6 stored information about implicit auto- # morphisms in Omega and Phi # this means that the algorithm has come upward to this position (in state 17) # before, so we have already intersected W[k] with the bulk of Omega and Phi, but # we should still catch up with the latest ones ii = self.Phi_size*l jj = self.Phi_size*k j = 1 + nwords/self.radix if nwords%self.radix: j += 1 W[jj] &= Omega[ii] for i from 0 < i < j: W[jj+i] &= Omega[ii+i]
elif state == 13: # hub state
# since we have returned to a partition of zeta # otherwise k < h, hence we have just backtracked up zeta, and are one level closer to done else: ii = 0 while not W[jj+1+ii]: ii += 1 while not W[jj+1+ii] & (1 << tvc): tvc += 1 tvc = (ii*self.radix + tvc) ^ nu.flag # now tvc points to the minimal cell representative of W[k]
elif state == 14: # see if there are any more splits to make from this level of zeta (see state 17) if Theta.wd_find(v[k]^nu.flag) == Theta.wd_find(tvc^nu.flag): index += 1 else:
# keep tabs on how many elements are in the same cell of Theta as tvc # find the next split ii = self.radix i = (v[k]^nu.flag) + 1 while i < nwords and not (1 << i%ii) & W[jj+1+i/ii]: i += 1 if i < nwords: v[k] = i^nu.flag else: # there is no new split at this level state = 16; continue # new split column better be a minimal representative in Theta, or wasted effort if Theta.wd_min_cell_rep[Theta.wd_find(i)] == i: state = 15 else: state = 14 else: else: # there is no new split at this level # new split column better be a minimal representative in Theta, or wasted effort else:
elif state == 15: # split out the column v[k] # hh is smallest such that nu[hh] satisfies Lemma 2.25. If it is larger than k+1, # it must be modified, since we are changing that part # hzf is maximal such that indicators line up for nu and zeta # hzb is longest such that nu and rho have the same indicators
elif state == 16: # backtrack up zeta, updating information about stabilizer vector else: i = 0; j = 0 ii = self.radix while i*ii < nwords: iii = W[jj+1+i] j += ham_wts[iii & 65535] + ham_wts[(iii >> 16) & 65535] i += 1 # (POINT A)
elif state == 17: # see if there are any more splits to make from this level of nu (and not zeta)
# intersect W[k] with each Omega[i] such that v[0]...v[k-1] is in Phi[i] iii += 1 i = v[ii]^nu.flag Phi[jj+1+i/self.radix] ^= (1 << i%self.radix) else:
# see if there is a vertex to split out i = (v[k]^nu.flag) while i < nwords: i += 1 if (1 << i%self.radix) & W[jjj+1+i/self.radix]: break if i < nwords: v[k] = i^nu.flag state = 15; continue else:
elif state == 18: # the first time nu becomes a discrete partition: set up zeta, our "identity" leaf # initialize counters for zeta: # (POINT B) # initialize counters for rho:
# end big while loop
def put_in_canonical_form(self, BinaryCode B): """ Puts the code into canonical form.
Canonical form is obtained by performing row reduction, permuting the pivots to the front so that the generator matrix is of the form: the identity matrix augmented to the right by arbitrary data.
EXAMPLES::
sage: from sage.coding.binary_code import * sage: BC = BinaryCodeClassifier() sage: B = BinaryCode(codes.GolayCode(GF(2)).generator_matrix()) sage: B.apply_permutation(list(range(24,-1,-1))) sage: B Binary [24,12] linear code, generator matrix [011000111010100000000000] [001001001111100000000001] [011010100101100000000010] [001101110001100000000100] [010011011001100000001000] [010110110011000000010000] [011101100110000000100000] [000011110110100001000000] [000111101101000010000000] [001111011010000100000000] [010110001110101000000000] [011100011101010000000000] sage: BC.put_in_canonical_form(B) sage: B Binary [24,12] linear code, generator matrix [100000000000001100111001] [010000000000001010001111] [001000000000001111010010] [000100000000010110101010] [000010000000010110010101] [000001000000010001101101] [000000100000011000110110] [000000010000011111001001] [000000001000010101110011] [000000000100010011011110] [000000000010001011110101] [000000000001001101101110]
"""
def generate_children(self, BinaryCode B, int n, int d=2): """ Use canonical augmentation to generate children of the code B.
INPUT:
- B -- a BinaryCode
- n -- limit on the degree of the code
- d -- test whether new vector has weight divisible by d. If d==4, this ensures that all doubly-even canonically augmented children are generated.
EXAMPLES::
sage: from sage.coding.binary_code import * sage: BC = BinaryCodeClassifier() sage: B = BinaryCode(Matrix(GF(2), [[1,1,1,1]])) sage: BC.generate_children(B, 6, 4) [ [1 1 1 1 0 0] [0 1 0 1 1 1] ]
.. NOTE::
The function ``codes.databases.self_orthogonal_binary_codes`` makes heavy use of this function.
MORE EXAMPLES::
sage: soc_iter = codes.databases.self_orthogonal_binary_codes(12, 6, 4) sage: L = list(soc_iter) sage: for n in range(0, 13): ....: s = 'n=%2d : '%n ....: for k in range(1,7): ....: s += '%3d '%len([C for C in L if C.length() == n and C.dimension() == k]) ....: print(s) n= 0 : 0 0 0 0 0 0 n= 1 : 0 0 0 0 0 0 n= 2 : 0 0 0 0 0 0 n= 3 : 0 0 0 0 0 0 n= 4 : 1 0 0 0 0 0 n= 5 : 0 0 0 0 0 0 n= 6 : 0 1 0 0 0 0 n= 7 : 0 0 1 0 0 0 n= 8 : 1 1 1 1 0 0 n= 9 : 0 0 0 0 0 0 n=10 : 0 1 1 1 0 0 n=11 : 0 0 1 1 0 0 n=12 : 1 2 3 4 2 0
""" cdef BinaryCode m cdef codeword *ortho_basis cdef codeword *B_can_lab cdef codeword current, swap cdef codeword word, temp, gate, nonzero_gate, orbit, bwd, k_gate cdef codeword *temp_basis cdef codeword *orbit_checks cdef codeword orb_chx_size, orb_chx_shift, radix_gate cdef WordPermutation *gwp cdef WordPermutation *hwp cdef WordPermutation *can_lab cdef WordPermutation *can_lab_inv cdef WordPermutation **parent_generators cdef BinaryCode B_aug cdef int base_size, row cdef int *multimod2_index cdef int *num_inner_gens cdef int *num_outer_gens cdef int *v cdef int log_2_radix cdef bint bingo, bingo2, bingo3
sig_free(ortho_basis) if B_can_lab is not NULL: sig_free(B_can_lab) if can_lab is not NULL: sig_free(can_lab) raise MemoryError() B_can_lab[j] ^= B_can_lab[row]
# now we assume (<codeword>1 << log_2_radix) == self.radix else: raise MemoryError()
# check if (B, B_aug) ~ (m(B_aug), B_aug)
# row reduce to get canonical label # done row reduction
if True:#size*factorial(n-B.ncols) == m_size:
aut_m = PermutationGroup([()]) else:
aut_B_aug = PermutationGroup([()]) else: #dealloc_word_perm(gwp) #...
else:
|