dejavu
Fast probabilistic symmetry detection.
Loading...
Searching...
No Matches
dejavu::groups::compressed_schreier Class Reference

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
posPosition 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_individualizeVector in which vertices deemed save to individualize are pushed.
root_coloringThe 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_posPosition in base.
vVertex 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
wA Schreier workspace.
selectionVector to be reduced.
base_posPosition 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_basethe new base
new_base_sizesupper bounds for the size of transversals
stopinteger which indicates to stop reading the base at this position
keep_oldIf 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
wAuxiliary workspace used for procedures.
automorphismAutomorphism 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
wAuxiliary workspace used for procedures.
automorphismAn 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: