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

Schreier structure. More...

#include <groups.h>

+ Collaboration diagram for dejavu::groups::random_schreier_internal:

Public Member Functions

dej_nodiscard int s_sparsegen () const
 
dej_nodiscard int s_densegen () const
 
void initialize (const int new_domain_size, std::vector< int > &base, std::vector< int > &base_sizes, int stop=INT32_MAX)
 
void set_base (schreier_workspace &w, automorphism_workspace &automorphism, random_source &rng, std::vector< int > &new_base, int err=10, bool resift_generators=false)
 
void sift_random (schreier_workspace &w, automorphism_workspace &automorphism, random_source &rng, int err)
 
bool reset (int new_domain_size, schreier_workspace &w, std::vector< int > &new_base, std::vector< int > &new_base_sizes, const int stop, bool keep_old, bool remove_generators, 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_fixed_orbit (const int base_pos, const int v)
 
const std::vector< int > & get_fixed_orbit (const int base_pos)
 
const std::vector< int > & get_stabilizer_generators (const int base_pos)
 
const std::vector< int > & get_stabilized_generators ()
 
dej_nodiscard int get_fixed_orbit_size (const int base_pos)
 
void reduce_to_unfinished (schreier_workspace &w, std::vector< int > &selection, int base_pos)
 
dej_nodiscard bool is_finished (const int base_pos) const
 
bool sift (schreier_workspace &w, automorphism_workspace &automorphism, bool uniform=false, bool keep_at_end=false)
 
void generate_random (schreier_workspace &w, automorphism_workspace &automorphism, random_source &rng)
 
void load_generator (automorphism_workspace &automorphism, int generator)
 
bool sift_random (schreier_workspace &w, automorphism_workspace &automorphism, random_source &rng, bool keep_at_end=false)
 
bool sift_generator (schreier_workspace &w, automorphism_workspace &automorphism, int generator, bool keep_at_end=false)
 
void record_sift_result (const bool changed)
 
void reset_probabilistic_criterion ()
 
dej_nodiscard bool probabilistic_abort_criterion () const
 
dej_nodiscard bool deterministic_abort_criterion () const
 
dej_nodiscard int finished_up_to_level () const
 
void compute_group_size ()
 

Public Attributes

int s_consecutive_success = 0
 
int h_error_bound = 10
 
big_number s_grp_sz
 

Detailed Description

Schreier structure.

Enables sifting of automorphisms into a Schreier structure with given base. Intended for internal use in dejavu.

Definition at line 1224 of file groups.h.

Member Function Documentation

◆ base_point()

dej_nodiscard int dejavu::groups::random_schreier_internal::base_point ( int  pos) const
inline
Parameters
posPosition in base.
Returns
Vertex fixed at position pos in base.

Definition at line 1402 of file groups.h.

◆ base_size()

dej_nodiscard int dejavu::groups::random_schreier_internal::base_size ( ) const
inline
Returns
Size of base of this Schreier structure.

Definition at line 1409 of file groups.h.

◆ compute_group_size()

void dejavu::groups::random_schreier_internal::compute_group_size ( )
inline
Returns
Size of group described by this Schreier structure.

Definition at line 1626 of file groups.h.

◆ determine_potential_individualization()

void dejavu::groups::random_schreier_internal::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 1387 of file groups.h.

◆ deterministic_abort_criterion()

dej_nodiscard bool dejavu::groups::random_schreier_internal::deterministic_abort_criterion ( ) const
inline
Returns
Whether the deterministic abort criterion allows termination or not.

Definition at line 1611 of file groups.h.

◆ finished_up_to_level()

dej_nodiscard int dejavu::groups::random_schreier_internal::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 1619 of file groups.h.

◆ generate_random()

void dejavu::groups::random_schreier_internal::generate_random ( schreier_workspace w,
automorphism_workspace automorphism,
random_source rng 
)
inline

Generate a (semi-)random element from the generators.

Parameters
wAuxiliary workspace used for procedures.
automorphismRandom element is saved in this automorphism_workspace.
rn_generatorRandom number generator used for the generation.

Definition at line 1525 of file groups.h.

◆ get_fixed_orbit()

const std::vector< int > & dejavu::groups::random_schreier_internal::get_fixed_orbit ( const int  base_pos)
inline

Definition at line 1429 of file groups.h.

◆ get_fixed_orbit_size()

dej_nodiscard int dejavu::groups::random_schreier_internal::get_fixed_orbit_size ( const int  base_pos)
inline

Definition at line 1445 of file groups.h.

◆ get_stabilized_generators()

const std::vector< int > & dejavu::groups::random_schreier_internal::get_stabilized_generators ( )
inline

Definition at line 1441 of file groups.h.

◆ get_stabilizer_generators()

const std::vector< int > & dejavu::groups::random_schreier_internal::get_stabilizer_generators ( const int  base_pos)
inline

Definition at line 1435 of file groups.h.

◆ initialize()

void dejavu::groups::random_schreier_internal::initialize ( const int  new_domain_size,
std::vector< int > &  base,
std::vector< int > &  base_sizes,
int  stop = INT32_MAX 
)
inline

Set up this Schreier structure using the given base. The base is then fixed and can not be adjusted later on.

Parameters
basethe base
base_sizesupper bounds for the size of transversals
stopinteger which indicates to stop reading the base at this position

Definition at line 1262 of file groups.h.

◆ is_finished()

dej_nodiscard bool dejavu::groups::random_schreier_internal::is_finished ( const int  base_pos) const
inline

Checks whether the transversal at position s_base_pos matches its size upper bound.

Parameters
base_posPosition in base.
Returns
Bool that indicates whether the transversal at position s_base_pos matches its size upper bound.

Definition at line 1468 of file groups.h.

◆ is_in_fixed_orbit()

bool dejavu::groups::random_schreier_internal::is_in_fixed_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 1420 of file groups.h.

◆ load_generator()

void dejavu::groups::random_schreier_internal::load_generator ( automorphism_workspace automorphism,
int  generator 
)
inline

Definition at line 1546 of file groups.h.

◆ probabilistic_abort_criterion()

dej_nodiscard bool dejavu::groups::random_schreier_internal::probabilistic_abort_criterion ( ) const
inline
Returns
Whether the probabilistic abort criterion allows termination or not.

Definition at line 1604 of file groups.h.

◆ record_sift_result()

void dejavu::groups::random_schreier_internal::record_sift_result ( const bool  changed)
inline

Records a sift result for the probabilistic abort criterion.

Parameters
changedWhether the sift was successful or not.

Definition at line 1583 of file groups.h.

◆ reduce_to_unfinished()

void dejavu::groups::random_schreier_internal::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 1458 of file groups.h.

◆ reset()

bool dejavu::groups::random_schreier_internal::reset ( int  new_domain_size,
schreier_workspace w,
std::vector< int > &  new_base,
std::vector< int > &  new_base_sizes,
const int  stop,
bool  keep_old,
bool  remove_generators,
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 1335 of file groups.h.

◆ reset_probabilistic_criterion()

void dejavu::groups::random_schreier_internal::reset_probabilistic_criterion ( )
inline

Reset the probabilistic abort criterion.

Definition at line 1597 of file groups.h.

◆ s_densegen()

dej_nodiscard int dejavu::groups::random_schreier_internal::s_densegen ( ) const
inline
Returns
Number of stored generators using a dense data structure.

Definition at line 1250 of file groups.h.

◆ s_sparsegen()

dej_nodiscard int dejavu::groups::random_schreier_internal::s_sparsegen ( ) const
inline
Returns
Number of stored generators using a sparse data structure.

Definition at line 1243 of file groups.h.

◆ set_base()

void dejavu::groups::random_schreier_internal::set_base ( schreier_workspace w,
automorphism_workspace automorphism,
random_source rng,
std::vector< int > &  new_base,
int  err = 10,
bool  resift_generators = false 
)
inline

Definition at line 1281 of file groups.h.

◆ sift()

bool dejavu::groups::random_schreier_internal::sift ( schreier_workspace w,
automorphism_workspace automorphism,
bool  uniform = false,
bool  keep_at_end = 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 1479 of file groups.h.

◆ sift_generator()

bool dejavu::groups::random_schreier_internal::sift_generator ( schreier_workspace w,
automorphism_workspace automorphism,
int  generator,
bool  keep_at_end = false 
)
inline

Definition at line 1568 of file groups.h.

◆ sift_random() [1/2]

bool dejavu::groups::random_schreier_internal::sift_random ( schreier_workspace w,
automorphism_workspace automorphism,
random_source rng,
bool  keep_at_end = false 
)
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 1558 of file groups.h.

◆ sift_random() [2/2]

void dejavu::groups::random_schreier_internal::sift_random ( schreier_workspace w,
automorphism_workspace automorphism,
random_source rng,
int  err 
)
inline

Definition at line 1316 of file groups.h.

Member Data Documentation

◆ h_error_bound

int dejavu::groups::random_schreier_internal::h_error_bound = 10

determines error probability

Definition at line 1237 of file groups.h.

◆ s_consecutive_success

int dejavu::groups::random_schreier_internal::s_consecutive_success = 0

track repeated sifts for probabilistic abort criterion

Definition at line 1236 of file groups.h.

◆ s_grp_sz

big_number dejavu::groups::random_schreier_internal::s_grp_sz

size of the automorphism group computed

Definition at line 1238 of file groups.h.


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