Coverage for local/lib/python2.7/site-packages/sage/groups/perm_gps/partn_ref2/refinement_generic.pyx : 73%
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.
For details see section 3 of [Feu2013]_.
Definitions ###########
Let `G` be a group which acts on a finite set `X` and let `\mathcal{L}(G)` denote the set of subgroups of `G`. We say that a mapping `Can_G: X \rightarrow X \times G \times \mathcal{L}(G), x \mapsto \left( CF_G(x), T_G(x), G_x \right)` with
- `CF_G(gx) = CF_G(x)` for all `x \in X` and all `g\in G` (canonical form) - `CF_G(x) = T_G(x) x` for all `x \in X` (transporter element) - `G_x = \{g \in G \mid gx=x\}` (stabilizer)
is a canonization algorithm.
Let `H` be another group acting on a set `Y`. A pair `(\theta, \omega)` with a homomorphism `\theta: G \rightarrow H` and `\omega: X \rightarrow Y` is called a homomorphism of group actions if `\omega(gx) = \theta(g)\omega(x)` for all `g \in G`, for all `x \in X`. In the case that `G=H` and `\theta = id_G`, we call `\omega` a `G`-homomorphism.
A standard partition is a sequence `C = (C_1, ..., C_k)` of subsets of `[n] = \{0, \ldots, n-1\}` where the `C_i` are disjoint, consecutive intervals and their union is equal to `[n]`. Each element is called a cell and the elements lying in a cell of cardinality 1 are called fixed points. Let `I_C` be a sequence of all fixed points of `C` (the exact ordering is important, but will be determined by the algorithm). The stabilizer of `(S_n)_C` is a standard Young subgroup of `S_n`.
Requirements ############
In the following we want to present an efficient algorithm for the canonization problem in the case that the group action is of type `G \rtimes S_n` on `X^n`. For this goal, we suppose that the group action of `G = G \rtimes \{id\}` on `X^n` has the following properties:
-- The action of `G \rtimes \{id\}` on `X^n` is given by a direct product of (maybe different) group actions of `G` on `X`.
-- For every `i \in \{0, \ldots, n-1\}` let `\Pi^{(i)}: X^n \rightarrow X` be the projection to the `i`-th coordinate. The function `\Pi^{(i)}` is an invariant under the action of the subgroup `(S_n)_i = \{\pi \in S_n \mid \pi(i) = i\}`.
Let `(i_0, \ldots, i_{k-1}) = I \subseteq \{0, \ldots, n-1\}` be an injective sequence. We define `\Pi^{(I)}(x) := (\Pi^{(i_0)}(x), \ldots, \Pi^{(i_{k-1})}(x))`. We call an element `x \in X` `I`-semicanonical if and only if `\Pi^{(I)}(x) \leq \Pi^{(I)}(gx)` for all `g \in G`.
For each `x \in X^n` there is obviously an `I`-semicanonical element in the orbit `Gx`. Suppose that `x` is already `I`-semicanonical and `J` is an injective sequence which extends `I` by one further coordinate `i`, then we call the process of computing a `J`-semicanonical representative the inner minimization at position `i`.
This could be described by a group action of the stabilizer `G_{\Pi^{(I)}(x)}`. on `x_i`.
Partitions and refinements ##########################
Now the idea for the canonization algorithm for the action of `G \rtimes S_n` on `X^n` can be formulated as follows. Let us suppose that we want to canonize `x\in X^n`. We build a backtrack tree in the following manner:
- each node gets represented by a quadruple `(C, I_C, y, G_{\Pi^{(I_C)}(y))})` where `C` is an ordered partition, `I_C` a subsequence of its fixed points, `y \in X^n` is `I_C`-semicanonical and `G_{\Pi^{(I_C)}(y))}` is the remaining group of the inner action - the root node is on level `0` and gets represented by `(([n]), (), x, G)` - nodes with `| I_C | = n`, i.e. all coordinates are fixed, will be leafs and we have `G_{\Pi^{(I_C)}(y))} = G_y` - the children of some other node `(C, I_C, y, G_{\Pi^{(I_C)}(y))})` are constructed by * picking one cell `C_j` with `| C_j |` (the choice has to be invariant in some sense) * separating the point `\min(C_j)` from its cell `C_j` which leads to the partition `D` and the sequence `I_D` * building the `| C_j |` successors `(D, I_D, z_k, G_{\Pi^{(I_D)}(z_k))})` by applying the permutation `\sigma_k := (\min(C_j), k)` for all `k \in C_j` to `y` and computing an `I_D`-semicanonical representative `z_k` of `\sigma_k y` - if the projection `\Pi^{(I_D)}(z_k)` is not optimal then we stop the backtracking in this node (i.e. prune the subtree below this node) - the tree is traversed in a depth-first manner - the smallest reached leaf node is defined to be the canonical form (the defined ordering takes all comparisons in predecessors also into account) - equal leaf nodes correspond to automorphism of `x`, they could be used to define further pruning methods.
We are able to speed up the computation by making use of refinements (i.e. `(S_n)_C`-homomorphisms). Suppose we constructed a node `(C, I_C, y, G_{\Pi^{(I_C)}(y))})`. We define `Y := \{z \in X^n \mid \Pi^{(I_C)}(z) = \Pi^{(I_C)}(y)\}` and we search for functions `\omega: Y \rightarrow \mathbb{Z}^n` which are constant on the orbits of `G_{\Pi^{(I_C)}(y)}` and compatible with the action of `(S_n)_C` on both sides. Then we compute a permutation `\pi \in (S_n)_C` which cell-wisely sorts the entries of `\omega(y)`. Afterwards we are allowed to reduce ourselves to the stabilizer `(S_n)_D` of `\omega(\pi y)`. If this stabilizer contains further fixed points, they are appended (in some fixed order) to the sequence `I_C` in order to define `I_D`. Furthermore the element `y` gets updated by an `I_D`-semicanonical representative of this orbit. These refinements could also be applied iteratively.
As said before, the backtrack search tree is traversed in a depth-first search manner, hence we maintain a candidate for the result. Each newly constructed node is compared to this candidate. If it - compares larger, then we can prune the subtree rooted in this node - compares smaller, then we replace the candidate by the actual node (more precisely by the next leaf node we will construct, for this we use the boolean flag ``_is_candidate_initialized``) - compares equal we just continue.
Implementation Details ######################
The class :class:`~sage.groups.perm_gps.partn_ref2.PartitionRefinement_generic` provides a framework for such a backtracking. It maintains the partition `C` and the sequence `I_C`. Instead of permuting the elements `x \in X` during the construction of nodes and in the refinements, we use a ``PartitionStack``, see :mod:`sage.groups.perm_gps.partn_ref.automorphism_group_canonical_label`. Hence, `C = (C_1, ..., C_k)` and `I_C` will be maintained implicitly. If `\pi \in S_n` is the permutation applied to this node, then we will store `\pi(I_C)` and in the partition stack we will store `(\pi(C_1), ..., \pi(C_k))`.
The class further decides when we have to call the inner minimization and which subtrees could be pruned by the use of automorphisms, see :class:`sage.groups.perm_gps.partn_ref2.LabelledBranching` for more details.
Derived classes ###############
Derived classes have to implement the following methods, see the method descriptions for more information: - Cython Functions: - bint _inner_min_(self, int pos, bint * inner_group_changed) - bint _refine(self, bint * part_changed) - tuple _store_state_(self) - void _restore_state_(self, tuple act_state) - void _store_best_(self) - void _latex_act_node(self, str comment=None) (to use the implemented debugging method via printing the backtrack tree using latex) - bint _minimization_allowed_on_col(self, int pos)
- Python functions: - get_canonical_form(self) - get_transporter(self) - get_autom_gens(self)
AUTHORS:
- Thomas Feulner (2012-11-15): initial version
REFERENCES:
- [Feu2013]_ """
#***************************************************************************** # Copyright (C) 2012 Thomas Feulner <thomas.feulner@uni-bayreuth.de> # # Distributed under the terms of the GNU General Public License (GPL) # 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 copy import copy
from cysignals.memory cimport sig_malloc, sig_realloc, sig_free
from sage.groups.perm_gps.partn_ref.data_structures cimport * include "sage/data_structures/bitset.pxi"
cdef tuple PS_refinement(PartitionStack * part, long *refine_vals, long *best, int begin, int end, bint * cand_initialized, bint *changed_partition): """ Refine the partition stack by the values given by ``refine_vals``. We also compare our actual refinement result with the vector ``best`` in the case that ``cand_initialized`` is set to ``True``.
If the current (canonical) vector is smaller than ``best``, then we will replace the values stored in ``best`` and set ``cand_initialized`` to ``False``.
The function will set ``changed_partition`` to ``True`` if and only if some cell was refined.
The function will return the boolean value ``False`` if and only if the (canonical) vector is larger than ``best``. The second entry of the tuple will contain all new singleton cells, which appeared in the refinement of ``refine_vals``. """ global global_refine_vals_array
# [loc_begin, ..., i] is a block of the old partition # a block of size 1
# compare with the candidate else:
# this is a singleton
cdef class _BestValStore: r""" This class implements a dynamic array of integer vectors of length `n`. """ def __cinit__(self, int n): r""" Initialization.
EXAMPLES::
sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import _BestValStore sage: B = _BestValStore(5) """
def __dealloc__(self): """ Dealloc. """
cdef long * get_row(self, int i): r""" Return the i-th row.
If this row is not yet initialized (i >= self.storage_length), then we extend the array and fill the new positions with the all zero vector. """ raise MemoryError('resizing _BestValStore')
cdef class LabelledBranching: r""" This class implements complete labelled branchings.
To each subgroup of `S_n` we can uniquely assign a directed forest on `n` vertices, where the edges `(i,j)` fulfill `i<j` and some further conditions on the edge labels (which we do not want to state). This graph is called a complete labelled branching.
The edges `(i,j)` will be stored in a vector ``father`` with ``father_j = -1`` if `j` is a root of a tree, and ``father_j = i`` if `i` is the predecessor of `j`, i.e. is an `(i,j)` is an edge.
EXAMPLES::
sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import LabelledBranching sage: L = LabelledBranching(3) sage: L.add_gen(libgap.eval('(1,2,3)')) sage: L.get_order() 3 sage: L.small_generating_set() [(1,2,3)] """
def __cinit__(self, n): r""" Initialization by the identity subgroup.
EXAMPLES::
sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import LabelledBranching sage: L = LabelledBranching(3) """
raise MemoryError('allocating LabelledBranching') sig_free(self.father) raise MemoryError('allocating LabelledBranching') cdef int i
def __dealloc__(self): """ Dealloc. """
cpdef add_gen(self, GapElement_Permutation gen): r""" Add a further generator to the group and update the complete labeled branching.
EXAMPLES::
sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import LabelledBranching sage: L = LabelledBranching(3) sage: L.add_gen(libgap.eval('(1,2,3)')) """
cdef int i, i_1, j, f
return
cdef bint has_empty_intersection(self, PartitionStack * part): r""" Pruning by automorphisms.
The partition stack ``part`` encodes a right coset `G\pi` where `G <= S_n` is a standard Young subgroup. On the other hand this complete labeled branching of the group `A` naturally defines a transversal of left coset representatives `T` of `S_n/A`.
This function returns true if and only if `T \cap G\pi` is empty, see [Feu13]_. """ cdef int i, j, k
def small_generating_set(self): r""" Return a small set of generators of the group stored by ``self``.
EXAMPLES::
sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import LabelledBranching sage: L = LabelledBranching(3) sage: L.small_generating_set() [] sage: L.add_gen(libgap.eval('(1,2,3)')) sage: L.small_generating_set() [(1,2,3)] """
def get_order(self): r""" Return the order of the group stored by ``self``.
EXAMPLES::
sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import LabelledBranching sage: L = LabelledBranching(3) sage: L.get_order() 1 sage: L.add_gen(libgap.eval('(1,2,3)')) sage: L.get_order() 3 """
cdef class PartitionRefinement_generic: r""" Implements the partition and refinement framework for group actions `G \rtimes S_n` on `X^n` as described in :mod:`sage.groups.perm_gps.partn_ref2.refinement_generic`. """
def __cinit__(self, n, *args, **kwds): """ Init.
EXAMPLES::
sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import PartitionRefinement_generic sage: P = PartitionRefinement_generic(5) """
raise MemoryError('allocating PartitionRefinement_generic')
def __dealloc__(self): """ Dealloc. """
##################################################################### # The following functions have to be implemented by derived classes ##################################################################### cdef bint _inner_min_(self, int pos, bint * inner_group_changed): """ Minimize the node by the action of the inner group on the i-th position.
INPUT:
- `pos` - A position in `range(self.n)` - `inner_group_changed` - will be set to true if `G_y` got smaller
OUTPUT:
- `True` if and only if the actual node compares less or equal to the candidate for the canonical form. """ raise NotImplementedError
cdef bint _refine(self, bint *part_changed, bint inner_group_changed, bint first_step): r""" Refine the partition ``self._part``.
Set ``part_changed`` to ``True`` if and only if the refinement let to a smaller subgroup of `S_n`. This function also has to take care on ``self._is_candidate_initialized``.
OUTPUT:
- `False` only if the actual node compares larger than the candidate for the canonical form. """ raise NotImplementedError
cdef tuple _store_state_(self): r""" Store the current state of the node to a tuple, such that it can be restored by :meth:`_restore_state_`. """ raise NotImplementedError
cdef void _restore_state_(self, tuple act_state): r""" The inverse of :meth:`_store_state_`. """ raise NotImplementedError
cdef void _store_best_(self): r""" Store this leaf node as the actual best candidate for the canonical form. """ raise NotImplementedError
cdef bint _minimization_allowed_on_col(self, int pos): r""" Decide if we are allowed to perform the inner minimization on position ``pos`` which is supposed to be a singleton. """ raise NotImplementedError
def get_canonical_form(self): r""" Return the canonical form we have computed.
EXAMPLES::
sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import PartitionRefinement_generic sage: P = PartitionRefinement_generic(5) sage: P.get_canonical_form() Traceback (most recent call last): ... NotImplementedError """
def get_transporter(self): r""" Return the transporter element we have computed.
EXAMPLES::
sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import PartitionRefinement_generic sage: P = PartitionRefinement_generic(5) sage: P.get_transporter() Traceback (most recent call last): ... NotImplementedError """
def get_autom_gens(self): r""" Return a list of generators we have computed.
EXAMPLES::
sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import PartitionRefinement_generic sage: P = PartitionRefinement_generic(5) sage: P.get_autom_gens() Traceback (most recent call last): ... NotImplementedError """
def get_autom_order_permutation(self): r""" Return the order of the automorphism group we have computes
EXAMPLES::
sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import PartitionRefinement_generic sage: P = PartitionRefinement_generic(5) sage: P.get_autom_order_permutation() 1 """
############################################### # THE BACKTRACK ALGORITHM: ############################################### cdef void _init_partition_stack(self, list partition): r""" Initialize the partition stack.
If the list ``partition`` is not ``None``, it must represent a coloring of the coordinates `\{0, \ldots, n-1\}`, i.e. a list of disjoint lists. """ else: # minimize singletons which already exist in this partition sig_free(self._refine_vals_scratch) raise MemoryError('initializing the partition stack')
cdef void _start_Sn_backtrack(self): r""" Start the partition refinement algorithm. """
cdef void _backtrack(self, bint first_step = False): r""" Backtracking with pruning.
- We first check if the subtree below this node contains any valuable information otherwise we return. This test is based on the subgroup of already known automorphisms. - Perform a refinement. If this node is a leaf, we do all necessary updates. - Else, we split the points of a fixed cell and backtrack recursively. This leads to a depth-first-search construction of the search tree. """
self._latex_act_node("inner-min") self._latex_finish_lvl() return
# store some important states of the current node
# determine a cell C of the partition stack, which we will individualize cdef bitset_t b cdef int second_pos self)
# recursively individualize the elements of the cell
#restore the old state and continue backtracking
# special case when block has size 2 # update for second run on while, i.e. pos == second_pos
# all candidates have been individualized!
cdef bint _inner_min_unminimized(self, bint *inner_group_changed): r""" Compute a subsequence `J = (j_0, \ldots, j_{l-1})` of fixed coordinates, which were not yet used in the inner minimization process (we call this sequence of used coordinates `I`) and compute the `(I+J)`-semicanonical representative. """ cdef int i, j, best_end, best_ind
else:
self._is_candidate_initialized = False reset_allowance_best = True else: return False self._is_candidate_initialized = False allowance_best = allowance_best[:best_ind] reset_allowance_best = True
return False
allowance_best = allowance_best[:best_ind] reset_allowance_best = True
return False else:
cdef bint _one_refinement(self, long * best, int begin, int end, bint *inner_group_changed, bint *changed_partition, str refine_name): r""" Let ``self._refine_vals_scratch`` contain the result of the `(S_n)_C`-homomorphism `\omega` and ``best`` be the result of `\omega` applied to the candidate.
This method computes performs the refinements, i.e. updates the partition stack and furthermore compares the result with ``best`` and decides - if we could prune the subtree -> return value is set to False - if the inner group has changed -> sets ``inner_group_changed`` to True - if the partition has changed -> sets ``changed_partition`` to True
The string ``refine_name`` is only necessary for printing within the latex output (if activated). """ &self._is_candidate_initialized, changed_partition)
else: self._latex_act_node("inner-min in " + refine_name) return False
cdef int len(self): r""" Return the degree of the acting symmetric group. """
cdef void _leaf_computations(self): r""" All necessary computations which have to be performed in a leaf.
There are to possibilities depending on the flag ``self._is_candidate_initialized``: - ``True``: There is another leaf equal to this node. This defines an automorphism which we add to the group of known automorphisms stored in ``self._known_automorphisms``. - ``False``: We have shown, that the current leaf is smaller than all other leaf nodes already visited. We set it to be the candidate for the canonical form. """ cdef int i
# transp is the inverse of the actual transporter element (seen as action from left!) else:
# call the method from the derived class
cdef bint _cut_by_known_automs(self): r""" Return ``True`` if the subtree below this node does not contain any *interesting* information. """
########################################################################### # These functions are used to produce some latex output: # it writes the actual node # to a 'tikz node' in latex. You just have to provide '_latex_act_node' # in derived classes and to set # BACKTRACK_WITHLATEX_DEBUG = 1 in the setup.py script when # building this module! ########################################################################### cdef void _latex_act_node(self, str comment="", int printlvl=0): r""" Append the actual node as a string of latex-commands to ``self._latex_debug_string`` """ raise NotImplementedError # must be implemented by derived classes
def _latex_view(self, title=None): r""" Evaluate the latex commands written to ``self._latex_debug_string`` and view the result.
EXAMPLES::
sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import PartitionRefinement_generic sage: P = PartitionRefinement_generic(5) sage: P._latex_view() sorry, no debug output was written. Set BACKTRACK_WITHLATEX_DEBUG to True if interested in this information """ from sage.misc.latex import latex, view latex.extra_preamble('') latex.add_to_preamble("\\usepackage{tikz}") latex.add_to_preamble("\\usepackage{tikz-qtree}") view(self._latex_debug_string, engine="pdflatex", title=title) else: "Set BACKTRACK_WITHLATEX_DEBUG to True if interested in this information")
cdef void _init_latex(self): r""" Add some initial commands to the string ``self._latex_debug_string``. """ from sage.misc.latex import LatexExpr self._latex_debug_string = LatexExpr( "\\resizebox{\\textwidth}{!}{\n" + "\\begin{tikzpicture}\n" + "\\tikzset{level distance=3cm, edge from parent/.style=" + "{draw, edge from parent path={(\\tikzparentnode.south) -- (\\tikzchildnode.north)}}}\n" + "\Tree") self._latex_debug_string += "[." self._latex_act_node()
cdef void _finish_latex(self): r""" Add some final commands to the string ``self._latex_debug_string``. """ self._latex_debug_string += "]\n" self._latex_debug_string += "\\end{tikzpicture} }\n"
cdef void _latex_new_lvl(self): r""" Add some commands to the string ``self._latex_debug_string``, in the case that the depth was increased during the backtracking. """ self._latex_debug_string += "[."
cdef void _latex_finish_lvl(self): r""" Add some commands to the string ``self._latex_debug_string``, in the case that we return to a node in the backtracking. """ self._latex_debug_string += "]\n" |