dejavu
Fast probabilistic symmetry detection.
Loading...
Searching...
No Matches
dejavu::ir::refinement Class Reference

Color refinement and related algorithms. More...

#include <refinement.h>

Public Member Functions

void refine_coloring (sgraph *g, coloring *c, int init_color=-1, int color_limit=-1, const std::function< type_split_color_hook > *split_hook=nullptr, const std::function< type_worklist_color_hook > *worklist_hook=nullptr)
 
void refine_coloring_first (sgraph *g, coloring *c, int init_color_class=-1)
 
bool certify_automorphism (sgraph *g, const int *p)
 
bool certify_automorphism_sparse (const sgraph *g, const int *p, int supp, const int *supp_arr)
 

Static Public Member Functions

static int individualize_vertex (coloring *c, int v, const std::function< type_split_color_hook > &split_hook=nullptr)
 

Detailed Description

Color refinement and related algorithms.

Class that is used to preserve a workspace for color refinement, automorphism certification, and other miscellaneous tasks. Once initialized to a certain size, the workspace can not be enlargened and methods can only be used for graphs of the initial size, or smaller.

Definition at line 143 of file refinement.h.

Member Function Documentation

◆ certify_automorphism()

bool dejavu::ir::refinement::certify_automorphism ( sgraph g,
const int *  p 
)
inline

Certifies automorphism of a graph. Uses the certification methods, but provides the auxiliary data structure.

See also
certification
Parameters
gthe graph
pthe mapping to be certified
Returns
whether p is an automorphism of g

Definition at line 362 of file refinement.h.

◆ certify_automorphism_sparse()

bool dejavu::ir::refinement::certify_automorphism_sparse ( const sgraph g,
const int *  p,
int  supp,
const int *  supp_arr 
)
inline

Certifies (sparse) automorphism of a graph. Uses the certification methods, but provides the auxiliary data structure. Does not certify points outside the given support.

See also
certification
Parameters
gthe graph
pthe mapping to be certified
suppthe number of points in the support of p
supp_arrthe points in the support of p
Returns
whether p is an automorphism of g (assuming the support is provided correctly)

Definition at line 379 of file refinement.h.

◆ individualize_vertex()

static int dejavu::ir::refinement::individualize_vertex ( coloring c,
int  v,
const std::function< type_split_color_hook > &  split_hook = nullptr 
)
inlinestatic

Individualizes a vertex in a coloring.

Parameters
cColoring in which the vertex is individualized.
vVertex to be individualized.
split_hookFunction to be called whenever a color class is split. Return value is not used.
Returns

Definition at line 245 of file refinement.h.

◆ refine_coloring()

void dejavu::ir::refinement::refine_coloring ( sgraph g,
coloring c,
int  init_color = -1,
int  color_limit = -1,
const std::function< type_split_color_hook > *  split_hook = nullptr,
const std::function< type_worklist_color_hook > *  worklist_hook = nullptr 
)
inline

The color refinement algorithm. Refines a given coloring with respect to a given graph.

Parameters
gThe graph.
cThe coloring to be refined.
init_colorInitialize the worklist with a single color class (e.g., after individualization). The default value -1 denotes that the worklist is initialized with all color classes of the coloring.
color_limitInteger which is used to stop refinement whenever the refined coloring reaches this number of color classes. The default value -1 denotes that refinement is performed exhaustively.
split_hookFunction pointer that is called whenever a color class is split. Return value can be used to stop refinement early.
worklist_hookFunction pointer that is called whenever a color class is considered for refinement. Return value can be used to skip refinement of that color class.

Definition at line 161 of file refinement.h.

◆ refine_coloring_first()

void dejavu::ir::refinement::refine_coloring_first ( sgraph g,
coloring c,
int  init_color_class = -1 
)
inline

The color refinement algorithm. Refines a given coloring with respect to a given graph. This color refinement does not produce an isomorphism-invariant ordered partitioning, but uses more optimization techniques – meant to be used as the first refinement in automorphism computation

Parameters
gThe graph.
cThe coloring to be refined.
init_colorInitialize the worklist with a single color class (e.g., after individualization). The default value -1 denotes that the worklist is initialized with all color classes of the coloring.

Definition at line 284 of file refinement.h.


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