permlib  0.2.8
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
Public Types | Public Member Functions
permlib::partition::IntersectionSearch< BSGSIN, TRANSRET > Class Template Reference

subgroup search for a group intersection based on partition backtracking More...

#include <intersection_search.h>

Inheritance diagram for permlib::partition::IntersectionSearch< BSGSIN, TRANSRET >:
permlib::partition::RBase< BSGSIN, TRANSRET > permlib::BaseSearch< BSGSIN, TRANSRET >

List of all members.

Public Types

typedef RBase< BSGSIN,
TRANSRET >::PERM 
PERM
typedef RBase< BSGSIN,
TRANSRET >::TRANS 
TRANS
typedef RBase< BSGSIN,
TRANSRET >::PartitionIt 
PartitionIt
- Public Types inherited from permlib::partition::RBase< BSGSIN, TRANSRET >
typedef Refinement< PERM >
::RefinementPtr 
RefinementPtr
typedef RefinementFamily< PERM >
::PartitionPtr 
PartitionPtr
- Public Types inherited from permlib::BaseSearch< BSGSIN, TRANSRET >
typedef std::list< typename
PERM::ptr > 
PERMlistType

Public Member Functions

 IntersectionSearch (const BSGSIN &bsgs, unsigned int pruningLevelDCM)
 constructor
void construct (BSGSIN *bsgs2)
 initializes search
- Public Member Functions inherited from permlib::partition::RBase< BSGSIN, TRANSRET >
 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

Additional Inherited Members

- Protected Member Functions inherited from permlib::partition::RBase< BSGSIN, TRANSRET >
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 inherited from permlib::partition::RBase< BSGSIN, TRANSRET >
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
< 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::partition::IntersectionSearch< BSGSIN, TRANSRET >

subgroup search for a group intersection based on partition backtracking


Constructor & Destructor Documentation

template<class BSGSIN , class TRANSRET >
permlib::partition::IntersectionSearch< BSGSIN, TRANSRET >::IntersectionSearch ( const BSGSIN &  bsgs,
unsigned int  pruningLevelDCM 
)

constructor

Parameters:
bsgsBSGS of first group
pruningLevelDCMlevel up to which expensive double coset minimality pruning is performed; zero to disable

Member Function Documentation

template<class BSGSIN , class TRANSRET >
void permlib::partition::IntersectionSearch< BSGSIN, TRANSRET >::construct ( BSGSIN *  bsgs2)

initializes search

Parameters:
bsgs2BSGS of second group for intersection

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