permlib  0.2.9
Library for permutation computations
Public Types | Public Member Functions | Public Attributes | Protected Member Functions | Protected Attributes | List of all members
permlib::BaseSearch< BSGSIN, TRANSRET > Class Template Referenceabstract

base class for searching in a group More...

#include <base_search.h>

Inheritance diagram for permlib::BaseSearch< BSGSIN, TRANSRET >:
permlib::classic::BacktrackSearch< BSGSIN, TRANSRET > permlib::partition::RBase< BSGSIN, TRANSRET > permlib::classic::IntersectionSearch< BSGSIN, TRANSRET > permlib::classic::LexSmallerImageSearch< BSGSIN, TRANSRET > permlib::classic::SetImageSearch< BSGSIN, TRANSRET > permlib::classic::SetStabilizerSearch< 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 BSGSIN::PERMtype PERM
 
typedef BSGSIN::TRANStype TRANS
 
typedef std::list< typename PERM::ptr > PERMlistType
 

Public Member Functions

 BaseSearch (const BSGSIN &bsgs, unsigned int pruningLevelDCM, bool stopAfterFirstElement)
 constructor More...
 
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 More...
 
virtual PERM::ptr searchCosetRepresentative ()
 searches for a coset representative if one exists
 
virtual PERM::ptr searchCosetRepresentative (BSGS< PERM, TRANSRET > &groupK, BSGS< PERM, TRANSRET > &groupL)=0
 searches for a coset representative if one exists More...
 

Public Attributes

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
 

Protected Member Functions

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
 
virtual const std::vector< dom_int > & subgroupBase () const =0
 base of the sought subgroup
 
void setupEmptySubgroup (BSGS< PERM, TRANSRET > &group) const
 sets up a BSGS structure for an empty group with base subgroupBase()
 

Protected Attributes

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< BaseSorterByReference > m_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
 

Detailed Description

template<class BSGSIN, class TRANSRET>
class permlib::BaseSearch< BSGSIN, TRANSRET >

base class for searching in a group

Constructor & Destructor Documentation

◆ BaseSearch()

template<class BSGSIN , class TRANSRET >
permlib::BaseSearch< BSGSIN, TRANSRET >::BaseSearch ( const BSGSIN &  bsgs,
unsigned int  pruningLevelDCM,
bool  stopAfterFirstElement 
)

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

◆ minOrbit()

template<class BSGSIN , class TRANSRET >
bool permlib::BaseSearch< BSGSIN, TRANSRET >::minOrbit ( unsigned long  alpha,
BSGS< PERM, TRANSRET > &  groupK,
unsigned int  i,
unsigned long  beta_i 
) const

finds minimal elements in an orbit

returns true iff beta_i is the minimal element of the orbit of alpha under action of the i-th stabilizer of groupK

◆ searchCosetRepresentative()

template<class BSGSIN , class TRANSRET >
virtual PERM::ptr permlib::BaseSearch< BSGSIN, TRANSRET >::searchCosetRepresentative ( BSGS< PERM, TRANSRET > &  groupK,
BSGS< PERM, TRANSRET > &  groupL 
)
pure 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

Implemented in permlib::partition::RBase< BSGSIN, TRANSRET >, and permlib::classic::BacktrackSearch< BSGSIN, TRANSRET >.

The documentation for this class was generated from the following file:
Generated on Fri Jul 23 2021 00:00:00 for permlib by doxygen 1.9.1