dejavu::ds::coloring Class Reference

Vertex coloring for a graph. More...

#include <coloring.h>

Public Member Functions
	~coloring ()
void	copy_ptn (coloring *c) const
void	copy_from_ir_ancestor (coloring *c)
void	copy_any (coloring *c)
void	initialize (int new_domain_size)
void	check () const

Public Attributes
int *	lab = nullptr
int *	ptn = nullptr
int *	vertex_to_col = nullptr
int *	vertex_to_lab = nullptr
int	cells = 1
int	domain_size = 0

Detailed Description

Vertex coloring for a graph.

Stores a vertex coloring for a graph with domain_size many vertices. Has mappings to and from colorings. The datastructure mostly follows the design used by Traces, with some slight adjustments. The class mainly exposes raw arrays, to be used by the solver internally.

Definition at line 23 of file coloring.h.

Constructor & Destructor Documentation

~coloring()

dejavu::ds::coloring::~coloring ( )

inline

Definition at line 71 of file coloring.h.

Member Function Documentation

check()

void dejavu::ds::coloring::check ( ) const

inline

Definition at line 153 of file coloring.h.

copy_any()

void dejavu::ds::coloring::copy_any ( coloring *  c )

inline

Copies the given coloring into this coloring.

Parameters

c	The coloring to copy from.

Definition at line 125 of file coloring.h.

copy_from_ir_ancestor()

void dejavu::ds::coloring::copy_from_ir_ancestor ( coloring *  c )

inline

Copies the given coloring into this coloring, but is only guaranteed to produce a correct coloring if c stems from an ancestor in the IR tree of the currently stored coloring.

Essentially, this function only copies the vertex_to_col array.

Parameters

c	The coloring to copy from.

Definition at line 98 of file coloring.h.

copy_ptn()

void dejavu::ds::coloring::copy_ptn ( coloring *  c ) const

inline

This function only copies the ptn array from c to this coloring. Assumes c and this coloring have the same domain_size and are both allocated.

Parameters

c	The coloring to copy from.

Definition at line 83 of file coloring.h.

initialize()

void dejavu::ds::coloring::initialize ( int  new_domain_size )

inline

Initialize this coloring with a given domain size. Allocates memory for the coloring. Does not initialize any content and runs in O(1).

Parameters

new_domain_size

domain size of the coloring

Definition at line 149 of file coloring.h.

Member Data Documentation

cells

int dejavu::ds::coloring::cells = 1

number of colors (i.e., cells) in the coloring

Definition at line 31 of file coloring.h.

domain_size

int dejavu::ds::coloring::domain_size = 0

domain size of the coloring (i.e., number of vertices of the graph)

Definition at line 32 of file coloring.h.

lab

int* dejavu::ds::coloring::lab = nullptr

vertices of color i are listed in lab[i]...lab[ptn[i]]

Definition at line 25 of file coloring.h.

ptn

int* dejavu::ds::coloring::ptn = nullptr

color i has size ptn[i] + 1

Definition at line 26 of file coloring.h.

vertex_to_col

int* dejavu::ds::coloring::vertex_to_col = nullptr

vertex v has color vertex_to_col[v]

Definition at line 27 of file coloring.h.

vertex_to_lab

int* dejavu::ds::coloring::vertex_to_lab = nullptr

vertex v is stored in lab at position vertex_to_lab[v], i.e., lab[vertex_to_lab[v]] = v

Definition at line 28 of file coloring.h.

---

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

• coloring.h