Coverage for local/lib/python2.7/site-packages/sage/groups/perm_gps/partn_ref/double_coset.pyx : 85%
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""" Double cosets
This module implements a general algorithm for computing double coset problems for pairs of objects. The class of objects in question must be some kind of structure for which an isomorphism is a permutation in $S_n$ for some $n$, which we call here the order of the object. Given objects $X$ and $Y$, the program returns an isomorphism in list permutation form if $X \cong Y$, and a NULL pointer otherwise.
In order to take advantage of the algorithms in this module for a specific kind of object, one must implement (in Cython) three functions which will be specific to the kind of objects in question. Pointers to these functions are passed to the main function of the module, which is \code{double_coset}. For specific examples of implementations of these functions, see any of the files in \code{sage.groups.perm_gps.partn_ref} beginning with "refinement." They are:
A. \code{refine_and_return_invariant}:
Signature:
\code{int refine_and_return_invariant(PartitionStack *PS, void *S, int *cells_to_refine_by, int ctrb_len)}
This function should split up cells in the partition at the top of the partition stack in such a way that any automorphism that respects the partition also respects the resulting partition. The array cells_to_refine_by is a list of the beginning positions of some cells which have been changed since the last refinement. It is not necessary to use this in an implementation of this function, but it will affect performance. One should consult \code{refinement_graphs} for more details and ideas for particular implementations.
Output:
An integer $I$ invariant under the orbits of $S_n$. That is, if $\gamma \in S_n$, then $$ I(G, PS, cells_to_refine_by) = I( \gamma(G), \gamma(PS), \gamma(cells_to_refine_by) ) .$$
B. \code{compare_structures}:
Signature:
\code{int compare_structures(int *gamma_1, int *gamma_2, void *S1, void *S2, int degree)}
This function must implement a total ordering on the set of objects of fixed order. Return: -1 if \code{gamma_1^{-1}(S1) < gamma_2^{-1}(S2)}, 0 if \code{gamma_1^{-1}(S1) == gamma_2^{-1}(S2)}, 1 if \code{gamma_1^{-1}(S1) > gamma_2^{-1}(S2)}.
Important note:
The permutations are thought of as being input in inverse form, and this can lead to subtle bugs. One is encouraged to consult existing implementations to make sure the right thing is being done: this is so that you can avoid *actually* needing to compute the inverse.
C. \code{all_children_are_equivalent}:
Signature:
\code{bint all_children_are_equivalent(PartitionStack *PS, void *S)}
This function must return False unless it is the case that each discrete partition finer than the top of the partition stack is equivalent to the others under some automorphism of S. The converse need not hold: if this is indeed the case, it still may return False. This function is originally used as a consequence of Lemma 2.25 in [1].
EXAMPLES::
sage: import sage.groups.perm_gps.partn_ref.double_coset
REFERENCE:
- [1] McKay, Brendan D. Practical Graph Isomorphism. Congressus Numerantium, Vol. 30 (1981), pp. 45-87.
- [2] Leon, Jeffrey. Permutation Group Algorithms Based on Partitions, I: Theory and Algorithms. J. Symbolic Computation, Vol. 12 (1991), pp. 533-583.
"""
#***************************************************************************** # 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 cysignals.memory cimport sig_calloc
from .data_structures cimport * include "sage/data_structures/bitset.pxi"
# Functions
cdef bint all_children_are_equivalent_trivial(PartitionStack *PS, void *S):
cdef int refine_and_return_invariant_trivial(PartitionStack *PS, void *S, int *cells_to_refine_by, int ctrb_len):
cdef int compare_perms(int *gamma_1, int *gamma_2, void *S1, void *S2, int degree): cdef int i, j
""" Given a group G generated by the given generators, tests whether the given permutations are in the same right coset of G. Tests nontrivial input group when using double_coset. If they are, return an element g so that g.perm1 = perm2 (composing left to right).
TESTS::
sage: from sage.groups.perm_gps.partn_ref.double_coset import coset_eq sage: coset_eq() [5, 0, 1, 2, 3, 4] sage: gens = [[1,2,3,0]] sage: reps = [[0,1,2,3]] sage: for p in SymmetricGroup(4): ....: p = [p(i)-1 for i in range(1,5)] ....: found = False ....: for r in reps: ....: if coset_eq(p, r, gens): ....: found = True ....: break ....: if not found: ....: reps.append(p) sage: len(reps) 6 sage: gens = [[1,0,2,3],[0,1,3,2]] sage: reps = [[0,1,2,3]] sage: for p in SymmetricGroup(4): ....: p = [p(i)-1 for i in range(1,5)] ....: found = False ....: for r in reps: ....: if coset_eq(p, r, gens): ....: found = True ....: break ....: if not found: ....: reps.append(p) sage: len(reps) 6 sage: gens = [[1,2,0,3]] sage: reps = [[0,1,2,3]] sage: for p in SymmetricGroup(4): ....: p = [p(i)-1 for i in range(1,5)] ....: found = False ....: for r in reps: ....: if coset_eq(p, r, gens): ....: found = True ....: break ....: if not found: ....: reps.append(p) sage: len(reps) 8
""" sig_free(c_perm) PS_dealloc(part) SC_dealloc(group) sig_free(isomorphism) raise MemoryError else:
cdef dc_work_space *allocate_dc_work_space(int n): r""" Allocates work space for the double_coset function. It can be input to the function in which case it must be deallocated after the function is called. """ cdef int *int_array
cdef dc_work_space *work_space return NULL
5*n # for int_array )*sizeof(int))
sig_free(int_array) deallocate_dc_work_space(work_space) return NULL
cdef int i except MemoryError: deallocate_dc_work_space(work_space) return NULL
cdef void deallocate_dc_work_space(dc_work_space *work_space): r""" Deallocates work space for the double_coset function. """ return
cdef int double_coset(void *S1, void *S2, PartitionStack *partition1, int *ordering2, int n, bint (*all_children_are_equivalent)(PartitionStack *PS, void *S), int (*refine_and_return_invariant)\ (PartitionStack *PS, void *S, int *cells_to_refine_by, int ctrb_len), int (*compare_structures)(int *gamma_1, int *gamma_2, void *S1, void *S2, int degree), StabilizerChain *input_group, dc_work_space *work_space_prealloc, int *isom) except -1: """ Traverse the search space for double coset calculation.
INPUT: S1, S2 -- pointers to the structures partition1 -- PartitionStack of depth 0 and degree n, whose first partition is of the points of S1 ordering2 -- an ordering of the points of S2 representing a second partition n -- the number of points (points are assumed to be 0,1,...,n-1) all_children_are_equivalent -- pointer to a function INPUT: PS -- pointer to a partition stack S -- pointer to the structure OUTPUT: bint -- returns True if it can be determined that all refinements below the current one will result in an equivalent discrete partition refine_and_return_invariant -- pointer to a function INPUT: PS -- pointer to a partition stack S -- pointer to the structure alpha -- an array consisting of numbers, which indicate the starting positions of the cells to refine against (will likely be modified) OUTPUT: int -- returns an invariant under application of arbitrary permutations compare_structures -- pointer to a function INPUT: gamma_1, gamma_2 -- (list) permutations of the points of S1 and S2 S1, S2 -- pointers to the structures degree -- degree of gamma_1 and 2 OUTPUT: int -- 0 if gamma_1(S1) = gamma_2(S2), otherwise -1 or 1 (see docs for cmp), such that the set of all structures is well-ordered input_group -- either a specified group to limit the search to, or NULL for the full symmetric group isom -- space to store the isomorphism to, or NULL if isomorphism is not needed
NOTE: The partition ``partition1`` and the resulting partition from ``ordering2`` *must* satisfy the property that in each cell, the smallest element occurs first!
OUTPUT: 1 if S1 and S2 are isomorphic, otherwise 0.
""" cdef PartitionStack *current_ps cdef PartitionStack *first_ps cdef PartitionStack *left_ps cdef int first_kids_are_same
cdef int *indicators
cdef OrbitPartition *orbits_of_subgroup cdef OrbitPartition *orbits_of_supergroup cdef int minimal_in_primary_orbit
cdef bitset_t *fixed_points_of_generators # i.e. fp cdef bitset_t *minimal_cell_reps_of_generators # i.e. mcr
cdef bitset_t *vertices_to_split cdef bitset_t *vertices_have_been_reduced cdef int *permutation cdef int *id_perm cdef int *cells_to_refine_by cdef int *vertices_determining_current_stack cdef int *perm_stack cdef StabilizerChain *group cdef StabilizerChain *old_group cdef StabilizerChain *tmp_gp
cdef int i, j, k, ell, b cdef bint discrete, automorphism, update_label
return 0
else: raise MemoryError
# Allocate:
# set up the identity permutation
# Copy reordering of left_ps coming from ordering2 to current_ps.
# default values of "infinity"
# Our first refinement needs to check every cell of the partition, # so cells_to_refine_by needs to be a list of pointers to each cell. else: else: else:
# Refine down to a discrete partition mem_err = 1 break else:
possible = 0 S2, refine_and_return_invariant, cells_to_refine_by, group, perm_stack) else: vertices_determining_current_stack[i], S2, else: else: else: # TODO: might be slight optimization for containment using perm_stack
if work_space_prealloc is NULL: deallocate_dc_work_space(work_space) raise MemoryError
# Main loop:
# I. Search for a new vertex to split, and update subgroup information # If we are not at a node of the first stack, reduce size of # vertices_to_split by using the symmetries we already know. j += 1 # If each vertex split so far is fixed by generator i, # then remove elements of vertices_to_split which are # not minimal in their orbits under generator i. for k from 0 <= k < n: if bitset_check(vertices_to_split[current_ps.depth], k) and not bitset_check(minimal_cell_reps_of_generators[i], k): bitset_flip(vertices_to_split[current_ps.depth], k) # Look for a new point to split. # There is a new point. else: # No new point: backtrack. else: # If we are at a node of the first stack, the above reduction # will not help. Also, we must update information about # primary orbits here. # If we are done searching under this part of the first # stack, then first_meets_current is one higher, and we # are looking at a new primary orbit (corresponding to a # larger subgroup in the stabilizer chain). # This was the last point to be split here. # If it is in the same orbit as minimal_in_primary_orbit, # then count it as an element of the primary orbit. # Look for a new point to split. # There is a new point. else: # No new point: backtrack. # Note that now, we are backtracking up the first stack. # If every choice of point to split gave something in the # (same!) primary orbit, then all children of the first # stack at this point are equivalent. # Backtrack.
# II. Refine down to a discrete partition, or until # we leave the part of the tree we are interested in vertices_determining_current_stack[i], S2, refine_and_return_invariant, cells_to_refine_by, group, perm_stack) else: vertices_determining_current_stack[i], S2, possible = 0 possible = 0 possible = 0 j = vertices_determining_current_stack[i] + 1 j = bitset_next(vertices_to_split[i], j) if j == -1: break else: possible = 1 vertices_determining_current_stack[i] = j current_ps.depth -= 1 # reset for next refinement break
# III. Check for automorphisms and isomorphisms # TODO: might be slight optimization for containment using perm_stack # if we get here, discrete must be true possible = 0 else: else: # TODO: might be slight optimization for containment using perm_stack else: else: else: continue # main loop bitset_and(vertices_to_split[current_ps.depth], vertices_to_split[current_ps.depth], minimal_cell_reps_of_generators[index_in_fp_and_mcr]) if index_in_fp_and_mcr < len_of_fp_and_mcr - 1: index_in_fp_and_mcr += 1 bitset_zero(fixed_points_of_generators[index_in_fp_and_mcr]) bitset_zero(minimal_cell_reps_of_generators[index_in_fp_and_mcr]) j = current_ps.depth current_ps.depth = i # just for mcr and fixed functions... for i from 0 <= i < n: if PS_is_mcr(current_ps, i): bitset_set(minimal_cell_reps_of_generators[index_in_fp_and_mcr], i) if PS_is_fixed(current_ps, i): bitset_set(fixed_points_of_generators[index_in_fp_and_mcr], i) current_ps.depth = j if bitset_check(vertices_have_been_reduced[0], current_ps.depth): bitset_and(vertices_to_split[current_ps.depth], vertices_to_split[current_ps.depth], minimal_cell_reps_of_generators[index_in_fp_and_mcr])
# End of main loop.
# Deallocate:
|