permlib
0.2.8
Library for permutation computations
|
subgroup search for a stabilizer of an integer vector based on partition backtracking More...
#include <vector_stabilizer_search.h>
Public Types | |
typedef RBase< BSGSIN, TRANSRET >::PERM | PERM |
![]() | |
typedef BaseSearch< BSGSIN, TRANSRET >::PERM | PERM |
typedef BaseSearch< BSGSIN, TRANSRET >::TRANS | TRANS |
typedef Refinement< PERM > ::RefinementPtr | RefinementPtr |
typedef RefinementFamily< PERM > ::PartitionPtr | PartitionPtr |
typedef std::list< std::pair < PartitionPtr, RefinementPtr > >::const_iterator | PartitionIt |
![]() | |
typedef BSGSIN::PERMtype | PERM |
typedef BSGSIN::TRANStype | TRANS |
typedef std::list< typename PERM::ptr > | PERMlistType |
Public Member Functions | |
VectorStabilizerSearch (const BSGSIN &bsgs, unsigned int pruningLevelDCM) | |
constructor | |
template<class InputIterator > | |
void | construct (InputIterator begin, InputIterator end, unsigned int maxEntries) |
initializes search | |
![]() | |
RBase (const BSGSIN &bsgs, unsigned int pruningLevelDCM, bool stopAfterFirstElement=false) | |
constructor | |
void | search (BSGS< PERM, TRANSRET > &groupK) |
perform search and store result in groupK | |
virtual BaseSearch< BSGSIN, TRANSRET >::PERM::ptr | searchCosetRepresentative (BSGS< PERM, TRANSRET > &groupK, BSGS< PERM, TRANSRET > &groupL) |
searches for a coset representative if one exists | |
![]() | |
BaseSearch (const BSGSIN &bsgs, unsigned int pruningLevelDCM, bool stopAfterFirstElement) | |
constructor | |
virtual | ~BaseSearch () |
destructor | |
bool | minOrbit (unsigned long alpha, BSGS< PERM, TRANSRET > &groupK, unsigned int i, unsigned long beta_i) const |
finds minimal elements in an orbit | |
virtual PERM::ptr | searchCosetRepresentative () |
searches for a coset representative if one exists | |
Protected Member Functions | |
virtual unsigned int | processNewFixPoints (const Partition &pi, unsigned int backtrackCount) |
callback when a new fix point appears during R-base construction | |
![]() | |
void | construct (SubgroupPredicate< PERM > *pred, RefinementFamily< PERM > *predRefinement) |
constructs an R-base for given predicate and refinement family | |
virtual const std::vector < dom_int > & | subgroupBase () const |
base of the sought subgroup | |
![]() | |
bool | pruneDCM (const PERM &t, unsigned int backtrackLevel, BSGS< PERM, TRANSRET > &groupK, BSGS< PERM, TRANSRET > &groupL) |
try to prune with advanced double coset minimality | |
bool | checkLeaf (unsigned int level) |
true iff level is a leaf level | |
unsigned int | processLeaf (const PERM &t, unsigned int level, unsigned int backtrackLevel, unsigned int completed, BSGS< PERM, TRANSRET > &groupK, BSGS< PERM, TRANSRET > &groupL) |
processes a leaf and adds corresponding element to the generator set of K | |
void | setupEmptySubgroup (BSGS< PERM, TRANSRET > &group) const |
sets up a BSGS structure for an empty group with base subgroupBase() | |
Additional Inherited Members | |
![]() | |
unsigned long | m_statNodesVisited |
nodes visited during backtrack search | |
unsigned long | m_statNodesPrunedCosetMinimality |
number of nodes where (simple) double coset minimality pruning was in effect | |
unsigned long | m_statNodesPrunedCosetMinimality2 |
number of nodes where advanced double coset minimality pruning with base change was in effect | |
unsigned long | m_statNodesPrunedChildRestriction |
number of nodes where a child constraint pruning was in effect | |
![]() | |
Partition | m_partition |
partition to base the backtrack tree on | |
Partition | m_partition2 |
subgroup search for a stabilizer of an integer vector based on partition backtracking
permlib::partition::VectorStabilizerSearch< BSGSIN, TRANSRET >::VectorStabilizerSearch | ( | const BSGSIN & | bsgs, |
unsigned int | pruningLevelDCM | ||
) |
constructor
bsgs | BSGS of group |
pruningLevelDCM | level up to which expensive double coset minimality pruning is performed; zero to disable |
void permlib::partition::VectorStabilizerSearch< BSGSIN, TRANSRET >::construct | ( | InputIterator | begin, |
InputIterator | end, | ||
unsigned int | maxEntries | ||
) |
initializes search
assume that integer vector has entries 0, 1, ..., maxEntries-1
begin | iterator(unsigned long) begin of the integer vector to be stabilized |
end | iterator(unsigned long) end of the integer vector to be stabilized |
maxEntries | value of maximal entry of integer vector plus 1 |