Compressed Schreier structure. More...

#include <groups.h>

Public Member Functions
dej_nodiscard int	s_sparsegen () const

dej_nodiscard int	s_densegen () const

bool	reset (domain_compressor *new_compressor, int new_domain_size, schreier_workspace &w, std::vector< int > &new_base, std::vector< int > &new_base_sizes, const int stop, bool keep_old, std::vector< int > &global_fixed_points)

void	determine_potential_individualization (std::vector< std::pair< int, int > > save_to_individualize, coloring root_coloring)

dej_nodiscard int	base_point (int pos) const

dej_nodiscard int	base_size () const

bool	is_in_base_orbit (const int base_pos, const int v)

void	reduce_to_unfinished (schreier_workspace &w, std::vector< int > &selection, int base_pos)

void	compress_automorphism (automorphism_workspace &automorphism, automorphism_workspace &automorphism_compress)

bool	sift (schreier_workspace &w, automorphism_workspace &automorphism, bool uniform=false)

bool	sift_random (schreier_workspace &w, automorphism_workspace &automorphism, random_source &rng)

void	reset_probabilistic_criterion ()

dej_nodiscard bool	probabilistic_abort_criterion () const

dej_nodiscard bool	deterministic_abort_criterion () const

dej_nodiscard bool	any_abort_criterion () const

void	set_error_bound (int error_bound)

dej_nodiscard int	get_consecutive_success () const

dej_nodiscard big_number	get_group_size () const

dej_nodiscard int	finished_up_to_level () const

void	compute_group_size ()

Public Attributes
double	h_min_compression_ratio = 0.4

double	s_compression_ratio = 1.0

Detailed Description

Compressed Schreier structure.

Internally, stores a random_schreier_internal structure in a compressed form using domain_compressor.

Definition at line 1976 of file groups.h.

Member Function Documentation

◆ any_abort_criterion()

dej_nodiscard bool dejavu::groups::compressed_schreier::any_abort_criterion ( ) const

inline

Returns: Whether any abort criterion allows termination or not.

Definition at line 2197 of file groups.h.

◆ base_point()

dej_nodiscard int dejavu::groups::compressed_schreier::base_point ( int pos ) const

inline

Parameters

pos	Position in base.

Returns: Vertex fixed at position pos in base.

Definition at line 2073 of file groups.h.

◆ base_size()

dej_nodiscard int dejavu::groups::compressed_schreier::base_size ( ) const

inline

Returns: Size of base of this Schreier structure.

Definition at line 2084 of file groups.h.

◆ compress_automorphism()

void dejavu::groups::compressed_schreier::compress_automorphism	(	automorphism_workspace &	automorphism,
		automorphism_workspace &	automorphism_compress
	)

inline

Definition at line 2125 of file groups.h.

◆ compute_group_size()

void dejavu::groups::compressed_schreier::compute_group_size ( )

inline

Returns: Size of group described by this Schreier structure.

Definition at line 2225 of file groups.h.

◆ determine_potential_individualization()

void dejavu::groups::compressed_schreier::determine_potential_individualization	(	std::vector< std::pair< int, int > > *	save_to_individualize,
		coloring *	root_coloring
	)

inline

Returns a vertex to individualize for each color of root_coloring that matches in size a corresponding transversal.

Parameters

save_to_individualize	Vector in which vertices deemed save to individualize are pushed.
root_coloring	The coloring with which the stored transversals are compared.

Definition at line 2054 of file groups.h.

◆ deterministic_abort_criterion()

dej_nodiscard bool dejavu::groups::compressed_schreier::deterministic_abort_criterion ( ) const

inline

Returns: Whether the deterministic abort criterion allows termination or not.

Definition at line 2190 of file groups.h.

◆ finished_up_to_level()

dej_nodiscard int dejavu::groups::compressed_schreier::finished_up_to_level ( ) const

inline

Returns: Level up to which Schreier structure is guaranteed to be complete according to given upper bounds. -1 indicates no level has been finished.

Definition at line 2218 of file groups.h.

◆ get_consecutive_success()

dej_nodiscard int dejavu::groups::compressed_schreier::get_consecutive_success ( ) const

inline

Definition at line 2206 of file groups.h.

◆ get_group_size()

dej_nodiscard big_number dejavu::groups::compressed_schreier::get_group_size ( ) const

inline

Definition at line 2210 of file groups.h.

◆ is_in_base_orbit()

bool dejavu::groups::compressed_schreier::is_in_base_orbit	(	const int	base_pos,
		const int	v
	)

inline

Checks whether a vertex v is contained in the transversal at position s_base_pos.

Parameters

base_pos	Position in base.
v	Vertex to check.

Returns: Bool indicating whether v is contained in the transversal at position s_base_pos.

Definition at line 2095 of file groups.h.

◆ probabilistic_abort_criterion()

dej_nodiscard bool dejavu::groups::compressed_schreier::probabilistic_abort_criterion ( ) const

inline

Returns: Whether the probabilistic abort criterion allows termination or not.

Definition at line 2183 of file groups.h.

◆ reduce_to_unfinished()

void dejavu::groups::compressed_schreier::reduce_to_unfinished	(	schreier_workspace &	w,
		std::vector< int > &	selection,
		int	base_pos
	)

inline

Reduces a vector of vertices selection to contain only points not contained in transversal at position s_base_pos in Schreier structure.

Parameters

w	A Schreier workspace.
selection	Vector to be reduced.
base_pos	Position in base.

Definition at line 2108 of file groups.h.

◆ reset()

bool dejavu::groups::compressed_schreier::reset	(	domain_compressor *	new_compressor,
		int	new_domain_size,
		schreier_workspace &	w,
		std::vector< int > &	new_base,
		std::vector< int > &	new_base_sizes,
		const int	stop,
		bool	keep_old,
		std::vector< int > &	global_fixed_points
	)

inline

Reset up this Schreier structure with a new base.

Parameters

new_base	the new base
new_base_sizes	upper bounds for the size of transversals
stop	integer which indicates to stop reading the base at this position
keep_old	If true, attempt to keep parts of the base that is already stored.

Definition at line 2010 of file groups.h.

◆ reset_probabilistic_criterion()

void dejavu::groups::compressed_schreier::reset_probabilistic_criterion ( )

inline

Reset the probabilistic abort criterion.

Definition at line 2176 of file groups.h.

◆ s_densegen()

dej_nodiscard int dejavu::groups::compressed_schreier::s_densegen ( ) const

inline

Returns: Number of stored generators using a dense data structure.

Definition at line 1998 of file groups.h.

◆ s_sparsegen()

dej_nodiscard int dejavu::groups::compressed_schreier::s_sparsegen ( ) const

inline

Returns: Number of stored generators using a sparse data structure.

Definition at line 1991 of file groups.h.

◆ set_error_bound()

void dejavu::groups::compressed_schreier::set_error_bound ( int error_bound )

inline

Definition at line 2202 of file groups.h.

◆ sift()

bool dejavu::groups::compressed_schreier::sift	(	schreier_workspace &	w,
		automorphism_workspace &	automorphism,
		bool	uniform = `false`
	)

inline

Sift automorphism into the Schreier structure.

Parameters

w	Auxiliary workspace used for procedures.
automorphism	Automorphism to be sifted. Will be manipulated by the method.

Returns: Whether automorphism was added to the Schreier structure or not.

Definition at line 2148 of file groups.h.

◆ sift_random()

bool dejavu::groups::compressed_schreier::sift_random	(	schreier_workspace &	w,
		automorphism_workspace &	automorphism,
		random_source &	rng
	)

inline

Sift a (semi-)randomly generated element into the Schreier structure.

Parameters

w	Auxiliary workspace used for procedures.
automorphism	An automorphism_workspace used to store the randomly generated element.

Returns: Whether the generated automorphism was added to the Schreier structure or not.

Definition at line 2164 of file groups.h.

Member Data Documentation

◆ h_min_compression_ratio

double dejavu::groups::compressed_schreier::h_min_compression_ratio = 0.4

Definition at line 1985 of file groups.h.

◆ s_compression_ratio

double dejavu::groups::compressed_schreier::s_compression_ratio = 1.0

Definition at line 1986 of file groups.h.

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

groups.h

Public Member Functions

Public Attributes

Detailed Description

Member Function Documentation

◆ any_abort_criterion()

◆ base_point()

◆ base_size()

◆ compress_automorphism()

◆ compute_group_size()

◆ determine_potential_individualization()

◆ deterministic_abort_criterion()

◆ finished_up_to_level()

◆ get_consecutive_success()

◆ get_group_size()

◆ is_in_base_orbit()

◆ probabilistic_abort_criterion()

◆ reduce_to_unfinished()

◆ reset()

◆ reset_probabilistic_criterion()

◆ s_densegen()

◆ s_sparsegen()

◆ set_error_bound()

◆ sift()

◆ sift_random()

Member Data Documentation

◆ h_min_compression_ratio

◆ s_compression_ratio