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""" Automorphism groups and canonical labels
This module implements a general algorithm for computing automorphism groups and canonical labels of objects. The class of objects in question must be some kind of structure for which an automorphism is a permutation in $S_n$ for some $n$, which we call here the order of the object. It should be noted that the word "canonical" in the term canonical label is used loosely. Given an object $X$, the canonical label $C(X)$ is just an object for which $C(X) = C(Y)$ for any $Y$ such that $X \cong Y$.
To understand the algorithm better, a few definitions will help. First one should note that throughout this module, $S_n$ is defined as the set of permutations of the set $[n] := \{0, 1, ..., n-1\}$. One speaks of ordered partitions $\Pi = (C_1, ..., C_k)$ of $[n]$. The $C_i$ are disjoint subsets of $[n]$ whose union is equal to $[n]$, and we call them cells. A partition $\Pi_1$ is said to be finer than another partition $\Pi_2$ if every cell of $\Pi_1$ is a subset of some cell of $\Pi_2$ (in this situation we also say that $\Pi_2$ is coarser than $\Pi_1$). A partition stack $\nu = (\Pi_0, ..., \Pi_k)$ is a sequence of partitions such that $\Pi_i$ is finer than $\Pi_{i-1}$ for each $i$ such that $1 \leq i \leq k$. Sometimes these are called nested partitions. The depth of $\nu$ is defined to be $k$ and the degree of $\nu$ is defined to be $n$. Partition stacks are implemented as \code{PartitionStack} (see automorphism_group_canonical_label.pxd for more information). Finally, we say that a permutation respects the partition $\Pi$ if its orbits form a partition which is finer than $\Pi$.
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{get_aut_gp_and_can_lab}. 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, of length ctrb_len. 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)}.
The value ``degree`` indicates the degree of the permutations ``gamma1`` and ``gamma_2``.
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.automorphism_group_canonical_label
REFERENCE:
- [1] McKay, Brendan D. Practical Graph Isomorphism. Congressus Numerantium, Vol. 30 (1981), pp. 45-87.
"""
#***************************************************************************** # 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 __future__ import print_function
from libc.string cimport memcmp, memcpy from cysignals.memory cimport sig_malloc, sig_realloc, sig_free
from .data_structures cimport * include "sage/data_structures/bitset.pxi"
cdef inline int agcl_cmp(int a, int b):
# 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_structures_trivial(int *gamma_1, int *gamma_2, void *S1, void *S2, int degree):
""" sage: tttt = sage.groups.perm_gps.partn_ref.automorphism_group_canonical_label.test_get_aut_gp_and_can_lab_trivially sage: tttt() 12 sage: tttt(canonical_label=False, base=False) 12 sage: tttt(canonical_label=False, base=True) 12 sage: tttt(canonical_label=True, base=True) 12 sage: tttt(n=0, partition=[]) 1 sage: tttt(n=0, partition=[], canonical_label=False, base=False) 1 sage: tttt(n=0, partition=[], canonical_label=False, base=True) 1 sage: tttt(n=0, partition=[], canonical_label=True, base=True) 1
""" cdef aut_gp_and_can_lab *output cdef PartitionStack *part raise MemoryError
""" A test for nontrivial input group in computing automorphism groups.
TESTS::
sage: from sage.groups.perm_gps.partn_ref.automorphism_group_canonical_label import test_intersect_parabolic_with_alternating as tipwa sage: tipwa() 144 sage: tipwa(5, [[0],[1],[2],[3,4]]) 1 sage: tipwa(5, [[0],[1],[2,3,4]]) 3 sage: tipwa(5, [[0,1],[2,3,4]]) 6 sage: tipwa(7, [[0,1,2,3,4,5,6]]) 2520 sage: factorial(7)/2 2520 sage: tipwa(9, [[0,1,2,3],[4,5,6,7,8]]) 1440
""" cdef aut_gp_and_can_lab *output cdef PartitionStack *part raise MemoryError PS_dealloc(part) raise MemoryError
cdef int compare_perms(int *gamma_1, int *gamma_2, void *S1, void *S2, int degree): cdef int i, j return 0
""" Given a group G generated by the given generators, defines a map from the Symmetric group to G so that any two elements from the same right coset go to the same element. Tests nontrivial input group when computing canonical labels.
TESTS::
sage: from sage.groups.perm_gps.partn_ref.automorphism_group_canonical_label import coset_rep sage: coset_rep() [5, 0, 1, 2, 3, 4] sage: gens = [[1,2,3,0]] sage: reps = [] sage: for p in SymmetricGroup(4): ....: p = [p(i)-1 for i in range(1,5)] ....: r = coset_rep(p, gens) ....: if r not in reps: ....: reps.append(r) sage: len(reps) 6 sage: gens = [[1,0,2,3],[0,1,3,2]] sage: reps = [] sage: for p in SymmetricGroup(4): ....: p = [p(i)-1 for i in range(1,5)] ....: r = coset_rep(p, gens) ....: if r not in reps: ....: reps.append(r) sage: len(reps) 6 sage: gens = [[1,2,0,3]] sage: reps = [] sage: for p in SymmetricGroup(4): ....: p = [p(i)-1 for i in range(1,5)] ....: r = coset_rep(p, gens) ....: if r not in reps: ....: reps.append(r) sage: len(reps) 8
""" cdef aut_gp_and_can_lab *output cdef PartitionStack *part sig_free(c_perm) PS_dealloc(part) SC_dealloc(group) raise MemoryError
cdef aut_gp_and_can_lab *allocate_agcl_output(int n): r""" Allocate an instance of the aut_gp_and_can_lab struct of degree n. This can be input to the get_aut_gp_and_can_lab function, and the output will be stored to it. """ return NULL deallocate_agcl_output(output) return NULL
cdef void deallocate_agcl_output(aut_gp_and_can_lab *output): r""" Deallocates an aut_gp_and_can_lab struct. """
cdef agcl_work_space *allocate_agcl_work_space(int n): r""" Allocates work space for the get_aut_gp_and_can_lab 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 agcl_work_space *work_space return NULL
n + # for label_indicators 7*n # for int_array )*sizeof(int))
deallocate_agcl_work_space(work_space) return NULL
cdef int i except MemoryError: deallocate_agcl_work_space(work_space) return NULL
cdef void deallocate_agcl_work_space(agcl_work_space *work_space): r""" Deallocate work space for the get_aut_gp_and_can_lab function. """ return
cdef aut_gp_and_can_lab *get_aut_gp_and_can_lab(void *S, PartitionStack *partition, 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), bint canonical_label, StabilizerChain *input_group, agcl_work_space *work_space_prealloc, aut_gp_and_can_lab *output_prealloc) except NULL: """ Traverse the search space for subgroup/canonical label calculation.
INPUT: S -- pointer to the structure partition -- PartitionStack representing a partition of the points len_partition -- length of the partition n -- the number of points (points are assumed to be 0,1,...,n-1) canonical_label -- whether to search for canonical label - if True, return the permutation taking S to its canonical label 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
NOTE: The partition ``partition1`` *must* satisfy the property that in each cell, the smallest element occurs first!
OUTPUT: pointer to a aut_gp_and_can_lab struct
""" cdef PartitionStack *current_ps cdef PartitionStack *first_ps cdef PartitionStack *label_ps cdef int label_meets_current cdef int first_kids_are_same
cdef int *current_indicators cdef int *first_indicators cdef int *label_indicators cdef int first_and_current_indicator_same cdef int compared_current_and_label_indicators
cdef OrbitPartition *orbits_of_subgroup cdef OrbitPartition *orbits_of_permutation 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 *label_perm cdef int *id_perm cdef int *cells_to_refine_by cdef int *vertices_determining_current_stack cdef int *perm_stack cdef StabilizerChain *old_group cdef StabilizerChain *tmp_gp
cdef int i, j, k, ell, b cdef bint discrete, automorphism, update_label
cdef aut_gp_and_can_lab *output cdef agcl_work_space *work_space
else: raise MemoryError
else: if output_prealloc is NULL: deallocate_agcl_output(output) raise MemoryError
# Allocate:
# default values of "infinity"
# set up the identity permutation
# 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. # Ignore the invariant this time, since we are # creating the root of the search tree. else:
# Refine down to a discrete partition mem_err = 1 break vertices_determining_current_stack[i], S, refine_and_return_invariant, cells_to_refine_by, group, perm_stack) else:
mem_err = 1
# Main loop:
if output_prealloc is NULL: deallocate_agcl_output(output) if work_space_prealloc is NULL: deallocate_agcl_work_space(work_space_prealloc) raise MemoryError
# If necessary, update label_meets_current
# 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. # 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. # 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 has been added to the primary orbit, update size info. # 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.
# 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], S, refine_and_return_invariant, cells_to_refine_by, group, perm_stack) else: vertices_determining_current_stack[i], S, else: # if we get here then canonical_label must be true # and we have to make a change of base mem_err = 1 break
# III. Check for automorphisms and labels # TODO: might be slight optimization for containment using perm_stack else: # if we get here, discrete must be true mem_err = 1 break else: else: mem_err = 1 break else: else: else: # add permutation as a generator of the automorphism group # must double its size output.size_of_generator_array *= 2 output.generators = <int *> sig_realloc( output.generators, output.size_of_generator_array * sizeof(int) ) if output.generators is NULL: mem_err = True continue # main loop mem_err = 1 continue # main loop current_ps.depth = first_meets_current continue # main loop else: 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.
else:
|