permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
permlib::partition::RBase< BSGSIN, TRANSRET > Class Template Reference

R-base for partition backtracking. More...

#include <r_base.h>

Inheritance diagram for permlib::partition::RBase< BSGSIN, TRANSRET >:
permlib::BaseSearch< BSGSIN, TRANSRET > permlib::partition::IntersectionSearch< BSGSIN, TRANSRET > permlib::partition::MatrixAutomorphismSearch< BSGSIN, TRANSRET > permlib::partition::SetImageSearch< BSGSIN, TRANSRET > permlib::partition::SetStabilizerSearch< BSGSIN, TRANSRET > permlib::partition::VectorStabilizerSearch< BSGSIN, TRANSRET >

Public Types

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
Public Types inherited from permlib::BaseSearch< BSGSIN, TRANSRET >
typedef BSGSIN::PERMtype PERM
typedef BSGSIN::TRANStype TRANS
typedef std::list< typename PERM::ptr > PERMlistType

Public Member Functions

 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
Public Member Functions inherited from permlib::BaseSearch< BSGSIN, TRANSRET >
 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

void construct (SubgroupPredicate< PERM > *pred, RefinementFamily< PERM > *predRefinement)
 constructs an R-base for given predicate and refinement family
virtual unsigned int processNewFixPoints (const Partition &pi, unsigned int level)
 callback when a new fix point appears during R-base construction
virtual const std::vector< dom_int > & subgroupBase () const
 base of the sought subgroup
Protected Member Functions inherited from permlib::BaseSearch< BSGSIN, TRANSRET >
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()

Protected Attributes

Partition m_partition
 partition to base the backtrack tree on
Partition m_partition2
Protected Attributes inherited from permlib::BaseSearch< BSGSIN, TRANSRET >
BSGSIN m_bsgs
 main BSGS to search in
BSGSIN * m_bsgs2
 second BSGS of a group the sough elements have to member of
boost::scoped_ptr< SubgroupPredicate< PERM > > m_pred
 predicate that matches sought elements
std::vector< unsigned long > m_order
 base point order
boost::scoped_ptr< BaseSorterByReferencem_sorter
 a sorter with respect to m_order
ConjugatingBaseChange< PERM, TRANS, RandomBaseTranspose< PERM, TRANS > > m_baseChange
 base change algorithm
const unsigned int m_pruningLevelDCM
 leves i with 0 <= i < m_pruningLevelDCM are prunged by advanced double coset minimality
bool m_limitInitialized
 true iff other m_limit variables have been initialized
unsigned int m_limitBase
 number of base points that correspond to maximal backtrack level m_limitLevel
unsigned int m_limitLevel
 maximal backtrack level
const bool m_stopAfterFirstElement
 true iff the search can be stopped after the first element found with the desired property
PERM::ptr m_lastElement
 last element found with desired property; only used if m_stopAfterFirstElement is true

Additional Inherited Members

Public Attributes inherited from permlib::BaseSearch< BSGSIN, TRANSRET >
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

Detailed Description

template<class BSGSIN, class TRANSRET>
class permlib::partition::RBase< BSGSIN, TRANSRET >

R-base for partition backtracking.

Constructor & Destructor Documentation

◆ RBase()

template<class BSGSIN, class TRANSRET>
permlib::partition::RBase< BSGSIN, TRANSRET >::RBase ( const BSGSIN & bsgs,
unsigned int pruningLevelDCM,
bool stopAfterFirstElement = false )

constructor

Parameters
bsgsBSGS to search in
pruningLevelDCMprune levels smaller than pruningLevelDCM by double coset minimality with base change
stopAfterFirstElementtrue iff the search can be stopped after the first element found with the desired property

Member Function Documentation

◆ construct()

template<class BSGSIN, class TRANSRET>
void permlib::partition::RBase< BSGSIN, TRANSRET >::construct ( SubgroupPredicate< PERM > * pred,
RefinementFamily< PERM > * predRefinement )
protected

constructs an R-base for given predicate and refinement family

group membership $\mathcal P$-refinement for m_bsgs is used by default

Parameters
pred
predRefinementrefinement family to use; may be zero to use only group membership $\mathcal P$-refinement

◆ processNewFixPoints()

template<class BSGSIN, class TRANSRET>
unsigned int permlib::partition::RBase< BSGSIN, TRANSRET >::processNewFixPoints ( const Partition & pi,
unsigned int level )
protectedvirtual

◆ searchCosetRepresentative()

template<class BSGSIN, class TRANSRET>
BaseSearch< BSGSIN, TRANSRET >::PERM::ptr permlib::partition::RBase< BSGSIN, TRANSRET >::searchCosetRepresentative ( BSGS< PERM, TRANSRET > & groupK,
BSGS< PERM, TRANSRET > & groupL )
virtual

searches for a coset representative if one exists

the two arguments are two groups K and L such that $KgL \subseteq G(\mathcal P)\quad \Leftrightarrow g \in G(\mathcal P)$

Parameters
groupKsubgroup of G
groupLsubgroup of G
Returns
pointer to a coset representative element or NULL

Implements permlib::BaseSearch< BSGSIN, TRANSRET >.

◆ subgroupBase()

template<class BSGSIN, class TRANSRET>
const std::vector< dom_int > & permlib::partition::RBase< BSGSIN, TRANSRET >::subgroupBase ( ) const
protectedvirtual

base of the sought subgroup

Implements permlib::BaseSearch< BSGSIN, TRANSRET >.


The documentation for this class was generated from the following file: