coset representative search for a lex-smaller set images More...

#include <lex_smaller_image_search.h>

Inheritance diagram for permlib::classic::LexSmallerImageSearch< BSGSIN, TRANSRET >:

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

Public Types inherited from permlib::classic::BacktrackSearch< BSGSIN, TRANSRET >
typedef BaseSearch< BSGSIN, TRANSRET >::PERM	PERM

typedef BaseSearch< BSGSIN, TRANSRET >::TRANS	TRANS

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
	LexSmallerImageSearch (const BSGSIN &bsgs, unsigned int pruningLevelDCM)
	constructor More...

template<class InputIteratorZ , class InputIteratorO >
void	construct (InputIteratorZ zerosBegin, InputIteratorZ zerosEnd, InputIteratorO onesBegin, InputIteratorO onesEnd)
	initializes search More...

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

void	search (BSGS< PERM, TRANSRET > &groupK)
	searches for a subgroup and stores it into 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

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 Member Functions inherited from permlib::classic::BacktrackSearch< BSGSIN, TRANSRET >
virtual const std::vector< dom_int > &	subgroupBase () const
	base of the sought subgroup

void	construct (SubgroupPredicate< PERM > *pred, bool addPredRefinement)
	initializes the search

unsigned int	search (const PERM &t, unsigned int level, unsigned int &completed, BSGS< PERM, TRANSRET > &groupK, BSGS< PERM, TRANSRET > &groupL)
	recursive backtrack search

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

coset representative search for a lex-smaller set images

tries to find a such that $val(\Delta^g) <_{lex} val(\Delta)$

Constructor & Destructor Documentation

◆ LexSmallerImageSearch()

template<class BSGSIN , class TRANSRET >

permlib::classic::LexSmallerImageSearch< BSGSIN, TRANSRET >::LexSmallerImageSearch	(	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 InputIteratorZ , class InputIteratorO >

void permlib::classic::LexSmallerImageSearch< BSGSIN, TRANSRET >::construct	(	InputIteratorZ	zerosBegin,
		InputIteratorZ	zerosEnd,
		InputIteratorO	onesBegin,
		InputIteratorO	onesEnd
	)

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/classic/lex_smaller_image_search.h

Public Types

Public Member Functions