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

g	the graph
p	the 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

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

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

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.

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

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.

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

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.

---

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

• refinement.h