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 isomorphism-invariant 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.