dejavu
Fast probabilistic symmetry detection.

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) 
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.

inline 
Certifies automorphism of a graph. Uses the certification
methods, but provides the auxiliary data structure.
g  the graph 
p  the mapping to be certified 
Definition at line 362 of file refinement.h.

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.
g  the graph 
p  the mapping to be certified 
supp  the number of points in the support of p 
supp_arr  the points in the support of p 
Definition at line 379 of file refinement.h.

inlinestatic 
Individualizes a vertex in a coloring.
c  Coloring in which the vertex is individualized. 
v  Vertex to be individualized. 
split_hook  Function to be called whenever a color class is split. Return value is not used. 
Definition at line 245 of file refinement.h.

inline 
The color refinement algorithm. Refines a given coloring with respect to a given graph.
g  The graph. 
c  The coloring to be refined. 
init_color  Initialize 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_limit  Integer 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_hook  Function pointer that is called whenever a color class is split. Return value can be used to stop refinement early. 
worklist_hook  Function 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.

inline 
The color refinement algorithm. Refines a given coloring with respect to a given graph. This color refinement does not produce an isomorphisminvariant ordered partitioning, but uses more optimization techniques – meant to be used as the first refinement in automorphism computation
g  The graph. 
c  The coloring to be refined. 
init_color  Initialize 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.