R-base for partition backtracking. More...

#include <r_base.h>

Inheritance diagram for permlib::partition::RBase< 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< 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

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

bsgs	BSGS to search in
pruningLevelDCM	prune levels smaller than pruningLevelDCM by double coset minimality with base change
stopAfterFirstElement	true 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
predRefinement	refinement 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

callback when a new fix point appears during R-base construction

Reimplemented in permlib::partition::SetImageSearch< BSGSIN, TRANSRET >, permlib::partition::SetStabilizerSearch< BSGSIN, TRANSRET >, and permlib::partition::VectorStabilizerSearch< BSGSIN, TRANSRET >.

◆ 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

groupK	subgroup of G
groupL	subgroup 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:

include/permlib/search/partition/r_base.h

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ RBase()

Member Function Documentation

◆ construct()

◆ processNewFixPoints()

◆ searchCosetRepresentative()

◆ subgroupBase()