subgroup search for the automorphism group of a symmetric matrix based on partition backtracking More...

#include <matrix_automorphism_search.h>

Inheritance diagram for permlib::partition::MatrixAutomorphismSearch< 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
	MatrixAutomorphismSearch (const BSGSIN &bsgs, unsigned int pruningLevelDCM)
	constructor More...

template<class MATRIX , class Iterator >
void	construct (const MATRIX &matrix, Iterator initialPartitionBegin, Iterator initialPartitionEnd)
	initializes search with inital partition More...

template<class MATRIX >
void	construct (const MATRIX &matrix)
	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

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::partition::RBase< BSGSIN, TRANSRET >
void	construct (SubgroupPredicate< PERM > pred, RefinementFamily< PERM > predRefinement)
	constructs an R-base for given predicate and refinement family More...

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

subgroup search for the automorphism group of a symmetric matrix based on partition backtracking

Constructor & Destructor Documentation

◆ MatrixAutomorphismSearch()

template<class BSGSIN , class TRANSRET >

permlib::partition::MatrixAutomorphismSearch< BSGSIN, TRANSRET >::MatrixAutomorphismSearch	(	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() [1/2]

template<class BSGSIN , class TRANSRET >

template<class MATRIX >

void permlib::partition::MatrixAutomorphismSearch< BSGSIN, TRANSRET >::construct ( const MATRIX & matrix )

inline

initializes search

Parameters

matrix symmetric matrix

◆ construct() [2/2]

template<class BSGSIN , class TRANSRET >

template<class MATRIX , class Iterator >

void permlib::partition::MatrixAutomorphismSearch< BSGSIN, TRANSRET >::construct	(	const MATRIX &	matrix,
		Iterator	initialPartitionBegin,
		Iterator	initialPartitionEnd
	)

initializes search with inital partition

Parameters

matrix	symmetric matrix
initialPartitionBegin	begin-iterator to initial list of row/column indices that have to be mapped onto each other
initialPartitionEnd	end-iterator to initial list of row/column indices that have to be mapped onto each other

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

include/permlib/search/partition/matrix_automorphism_search.h

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

template<class BSGSIN, class TRANSRET> class permlib::partition::MatrixAutomorphismSearch< BSGSIN, TRANSRET >

Constructor & Destructor Documentation

◆ MatrixAutomorphismSearch()

Member Function Documentation

◆ construct() [1/2]

◆ construct() [2/2]

template<class BSGSIN, class TRANSRET>
class permlib::partition::MatrixAutomorphismSearch< BSGSIN, TRANSRET >