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

API for the dejavu Schreier structure. More...

#include <groups.h>

Public Member Functions

dej_nodiscard int get_number_of_generators () const
 
void get_generator (int i, automorphism_workspace &automorphism)
 
 random_schreier (int domain_size, int error=10, bool true_random=false, int seed=0)
 
void set_base (std::vector< int > &new_base, bool resift_generators=false)
 
void sift_random ()
 
dej_nodiscard int base_size () const
 
dej_nodiscard int get_fixed_point (int pos) const
 
bool is_in_fixed_orbit (const int base_pos, const int v)
 
dej_nodiscard int get_fixed_orbit_size (const int base_pos)
 
const std::vector< int > & get_fixed_orbit (const int base_pos)
 
void get_stabilizer_orbit (int base_pos, orbit &orbit_partition)
 
std::vector< int > get_stabilizer_generators (int base_pos)
 
bool sift (automorphism_workspace &automorphism, bool known_in_group=false)
 
bool sift (int, const int *p, int nsupp, const int *supp, bool known_in_group=false)
 
big_number group_size ()
 

Detailed Description

API for the dejavu Schreier structure.

Enables sifting of automorphisms into a Schreier structure with given base. The Schreier structure does not compute proper random elements of the group, hence no guarantees regarding the error bound are given. The group described by the Schreier structure is always guaranteed to be a subgroup of the actual group generated by the contained elements.

Definition at line 1643 of file groups.h.

Constructor & Destructor Documentation

◆ random_schreier()

dejavu::groups::random_schreier::random_schreier ( int  domain_size,
int  error = 10,
bool  true_random = false,
int  seed = 0 
)
inlineexplicit

Initializes a random Schreier structure with the given parameters.

Parameters
domain_sizethe size of the domain (e.g., number of vertices of the graph)
errorhigher values reduce the likelihood of missing generators (default is 10)
true_randomwhether to use true random number generation
seedthe seed if pseudo random numbers are being used

Definition at line 1684 of file groups.h.

Member Function Documentation

◆ base_size()

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

Definition at line 1717 of file groups.h.

◆ get_fixed_orbit()

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

Returns the orbit of the fixed point at base_pos.

Parameters
base_posposition of base to look at
Returns
the fixed orbit

Definition at line 1755 of file groups.h.

◆ get_fixed_orbit_size()

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

Returns the orbit size of the fixed point at base_pos.

Parameters
base_posposition of base to look at
Returns
the orbit size

Definition at line 1745 of file groups.h.

◆ get_fixed_point()

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

Definition at line 1725 of file groups.h.

◆ get_generator()

void dejavu::groups::random_schreier::get_generator ( int  i,
automorphism_workspace automorphism 
)
inline

Loads the i-th generator into the given automorphism_workspace. Valid values for i are between 0 and get_number_of_generators()-1.

Parameters
iwill load the i-th generator
automorphismworkspace to load the generator into

Definition at line 1672 of file groups.h.

◆ get_number_of_generators()

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

Definition at line 1661 of file groups.h.

◆ get_stabilizer_generators()

std::vector< int > dejavu::groups::random_schreier::get_stabilizer_generators ( int  base_pos)
inline

Computes a list of generators for the pointwise stabilizer fixing the first base_pos points of the current base. The returned vector contains a list of generator ID's as stored in the Schreier structure. The generators can then be loaded using get_generator.

Parameters
base_posposition of base to consider
Returns
a list of generator numbers

Definition at line 1797 of file groups.h.

◆ get_stabilizer_orbit()

void dejavu::groups::random_schreier::get_stabilizer_orbit ( int  base_pos,
orbit orbit_partition 
)
inline

Computes the entire orbit partition at base_pos.

Parameters
base_posposition of base to look at
orbit_partitionorbits will be read into this orbit structure

Definition at line 1765 of file groups.h.

◆ group_size()

big_number dejavu::groups::random_schreier::group_size ( )
inline
Returns
Order of group described by this Schreier structure. Note that if the base is incomplete, the group order will not match the actual order the group.

Definition at line 1864 of file groups.h.

◆ is_in_fixed_orbit()

bool dejavu::groups::random_schreier::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 1736 of file groups.h.

◆ set_base()

void dejavu::groups::random_schreier::set_base ( std::vector< int > &  new_base,
bool  resift_generators = false 
)
inline

Sets the base of the Schreier structure.

Parameters
new_basethe base

Definition at line 1696 of file groups.h.

◆ sift() [1/2]

bool dejavu::groups::random_schreier::sift ( automorphism_workspace automorphism,
bool  known_in_group = false 
)
inline

Sift automorphism into the Schreier structure. If the automorphism is not yet represented in the Schreier structure, the structure is extended using the automorphism. I.e., the routine will add the given automorphism to the structure, if necessary.

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 1832 of file groups.h.

◆ sift() [2/2]

bool dejavu::groups::random_schreier::sift ( int  ,
const int *  p,
int  nsupp,
const int *  supp,
bool  known_in_group = false 
)
inline

Sift automorphism into the Schreier structure.

Parameters
pcomplete bijection of the automorphism
nsuppnumber of points in the support of automorphism
suppsupport of automorphism
known_in_groupwhether we know that the given automorphism is already in the group or not
Returns
whether a transversal changed

Definition at line 1845 of file groups.h.

◆ sift_random()

void dejavu::groups::random_schreier::sift_random ( )
inline

Generate random elements to complete the Schreier structure.

Definition at line 1710 of file groups.h.


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