coset representative search for a set image based on partition backtracking More...

#include <set_image_search.h>

Inheritance diagram for permlib::partition::SetImageSearch< BSGSIN, TRANSRET >:

Public Types
typedef RBase< BSGSIN, TRANSRET >::PERM	PERM

Public Types inherited from permlib::partition::RBase< BSGSIN, TRANSRET >
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
	SetImageSearch (const BSGSIN &bsgs, unsigned int pruningLevelDCM)
	constructor More...

template<class InputIterator >
void	construct (InputIterator begin, InputIterator end, InputIterator beginImg, InputIterator endImg)
	initializes search More...

Public Member Functions inherited from permlib::partition::RBase< BSGSIN, TRANSRET >
	RBase (const BSGSIN &bsgs, unsigned int pruningLevelDCM, bool stopAfterFirstElement=false)
	constructor More...

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 More...

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

Protected Member Functions
virtual unsigned int	processNewFixPoints (const Partition &pi, unsigned int backtrackCount)
	callback when a new fix point appears during R-base construction

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 More...

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()

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

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::SetImageSearch< BSGSIN, TRANSRET >

coset representative search for a set image based on partition backtracking

tries to find a such that $\Delta^g = \Gamma$ for two given sets $\Delta,\Gamma$

Constructor & Destructor Documentation

◆ SetImageSearch()

template<class BSGSIN , class TRANSRET >

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

constructor

Parameters

bsgs	BSGS of group
pruningLevelDCM	level up to which expensive double coset minimality pruning is performed; zero to disable

Member Function Documentation

◆ construct()

template<class BSGSIN , class TRANSRET >

template<class InputIterator >

void permlib::partition::SetImageSearch< BSGSIN, TRANSRET >::construct	(	InputIterator	begin,
		InputIterator	end,
		InputIterator	beginImg,
		InputIterator	endImg
	)

initializes search

Parameters

begin	iterator(unsigned long) begin of the set $\Delta$
end	iterator(unsigned long) end of the set $\Delta$
beginImg	iterator(unsigned long) begin of the set $\Gamma$
endImg	iterator(unsigned long) end of the set $\Gamma$

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

include/permlib/search/partition/set_image_search.h

Public Types

Public Member Functions

Protected Member Functions