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

Workspace for sparse automorphisms. More...

#include <groups.h>

Public Member Functions

 automorphism_workspace (int domain_sz=0)
 
void resize (int new_domain_size)
 
int & operator[] (int point) const
 
void set_support01 (const bool new_support01)
 
void write_color_diff (const int *vertex_to_col, const int *col_to_vertex)
 
void update_support ()
 
void apply (automorphism_workspace &other, int pwr=1)
 
void apply (worklist &scratch_apply1, worklist &scratch_apply2, markset &scratch_apply3, automorphism_workspace &other, int pwr=1)
 
void apply (worklist &scratch_apply1, worklist &scratch_apply2, markset &scratch_apply3, const int *p, int pwr=1)
 
void apply_sparse (worklist &scratch_apply1, worklist &scratch_apply2, markset &scratch_apply3, const int *p, const int *support, const int nsupport, int pwr=1)
 
void write_singleton (const std::vector< int > *singletons1, const std::vector< int > *singletons2, const int pos_start, const int pos_end)
 
void cycle_completion (markset &scratch_set)
 
void write_single_map (const int from, const int to)
 
void reset ()
 
dej_nodiscard int * p () const
 
dej_nodiscard int * supp () const
 
dej_nodiscard int nsupp () const
 

Detailed Description

Workspace for sparse automorphisms.

Enables O(1) lookup on a sparse automorphism by using an O(n) workspace.

Definition at line 68 of file groups.h.

Constructor & Destructor Documentation

◆ automorphism_workspace()

dejavu::groups::automorphism_workspace::automorphism_workspace ( int  domain_sz = 0)
inlineexplicit

Initializes the stored automorphism to the identity.

Parameters
domain_szSize of the domain on which automorphisms operate

Definition at line 102 of file groups.h.

Member Function Documentation

◆ apply() [1/3]

void dejavu::groups::automorphism_workspace::apply ( automorphism_workspace other,
int  pwr = 1 
)
inline

Apply another automorphism to the stored automorphism. To be more precise, other^pwr is applied to the automorphism stored in this object.

Closely follows the implementation in nauty / Traces.

Parameters
otherAutomorphism in sparse notation that is applied to this automorphism in.
pwrPower with which other is applied to this automorphism.

Definition at line 196 of file groups.h.

◆ apply() [2/3]

void dejavu::groups::automorphism_workspace::apply ( worklist scratch_apply1,
worklist scratch_apply2,
markset scratch_apply3,
automorphism_workspace other,
int  pwr = 1 
)
inline

Apply another automorphism to the stored automorphism. To be more precise, other^pwr is applied to the automorphism stored in this object.

Closely follows the implementation in nauty / Traces.

Parameters
scratch_apply1Auxiliary workspace used for the operation.
scratch_apply2Auxiliary workspace used for the operation.
scratch_apply3Auxiliary workspace used for the operation.
otherAutomorphism in sparse notation that is applied to this automorphism in.
pwrPower with which other is applied to this automorphism.

Definition at line 225 of file groups.h.

◆ apply() [3/3]

void dejavu::groups::automorphism_workspace::apply ( worklist scratch_apply1,
worklist scratch_apply2,
markset scratch_apply3,
const int *  p,
int  pwr = 1 
)
inline

Apply another automorphism to the stored automorphism. To be more precise, other^pwr is applied to the automorphism stored in this object.

Closely follows the implementation in nauty / Traces.

Parameters
scratch_apply1Auxiliary workspace used for the operation.
scratch_apply2Auxiliary workspace used for the operation.
scratch_apply3Auxiliary workspace used for the operation.
otherAutomorphism in dense notation that is applied to this automorphism.
pwrPower with which other is applied to this automorphism.

Definition at line 248 of file groups.h.

◆ apply_sparse()

void dejavu::groups::automorphism_workspace::apply_sparse ( worklist scratch_apply1,
worklist scratch_apply2,
markset scratch_apply3,
const int *  p,
const int *  support,
const int  nsupport,
int  pwr = 1 
)
inline

Definition at line 312 of file groups.h.

◆ cycle_completion()

void dejavu::groups::automorphism_workspace::cycle_completion ( markset scratch_set)
inline

Heuristic that turns the internal mapping into a bijection (in some way).

Parameters
scratch_setsome auxiliary workspace

Definition at line 439 of file groups.h.

◆ nsupp()

dej_nodiscard int dejavu::groups::automorphism_workspace::nsupp ( ) const
inline
Returns
Size of the support.

Definition at line 497 of file groups.h.

◆ operator[]()

int & dejavu::groups::automorphism_workspace::operator[] ( int  point) const
inline

Returns where point is mapped to under currently stored automorphism.

Parameters
point
Returns

Definition at line 135 of file groups.h.

◆ p()

dej_nodiscard int * dejavu::groups::automorphism_workspace::p ( ) const
inline
Returns
Integer array p describing the stored automorphism, where point v is mapped to p[v].

Definition at line 483 of file groups.h.

◆ reset()

void dejavu::groups::automorphism_workspace::reset ( )
inline

Reset the contained automorphism back to the identity.

Definition at line 475 of file groups.h.

◆ resize()

void dejavu::groups::automorphism_workspace::resize ( int  new_domain_size)
inline

Resizes the datastructure.

Parameters
new_domain_sizeallocate and initialize space for a domain of this size

Definition at line 118 of file groups.h.

◆ set_support01()

void dejavu::groups::automorphism_workspace::set_support01 ( const bool  new_support01)
inline

If 0/1 support is activated, this automorphism_workspace will only track whether the support of the underlying automorphism is trivial (=0) or non-trivial (>=1). Some operations are more efficient, if 0/1 support is used (e.g., apply)

Parameters
new_support01Flag of whether to use 0/1 support, or not.

Definition at line 148 of file groups.h.

◆ supp()

dej_nodiscard int * dejavu::groups::automorphism_workspace::supp ( ) const
inline
Returns
Integer array which contains all vertices in the support of the contained automorphism.

Definition at line 490 of file groups.h.

◆ update_support()

void dejavu::groups::automorphism_workspace::update_support ( )
inline

Updates the support using the internal dense notation.

Definition at line 169 of file groups.h.

◆ write_color_diff()

void dejavu::groups::automorphism_workspace::write_color_diff ( const int *  vertex_to_col,
const int *  col_to_vertex 
)
inline

Create automorphism from two discrete vertex colorings.

Parameters
vertex_to_colVertex-to-color mapping of the first coloring, i.e., vertex i is mapped to color vertex_to_col[i].
col_to_vertexColor-to-vertex mapping of the second coloring, i.e., the color i contains the vertex col_to_vertex[i] (since the colorings are assumed to be discrete, every i must be a distinct color).

Definition at line 160 of file groups.h.

◆ write_single_map()

void dejavu::groups::automorphism_workspace::write_single_map ( const int  from,
const int  to 
)
inline

Write

Parameters
from
to

Definition at line 463 of file groups.h.

◆ write_singleton()

void dejavu::groups::automorphism_workspace::write_singleton ( const std::vector< int > *  singletons1,
const std::vector< int > *  singletons2,
const int  pos_start,
const int  pos_end 
)
inline

Create mapping from two canonically-ordered vectors of singletons. The resulting automorphism maps singletons1[i] to singletons2[i] for i in pos_start, ..., pos_end.

May result in a mapping that is not a bijection.

Parameters
singletons1first vector of singletons
singletons2second vector of singletons
pos_startstart reading the vectors at this position
pos_endstop reading the vecvtors at this position.

Definition at line 420 of file groups.h.


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