networkit.coloring¶

class networkit.coloring.SpectralColoring(G)¶

Bases: object

Algorithm for computing a valid spectral coloring for a given graph.

Parameters:

G (networkit.Graph) – The graph to compute the spectral coloring for.

buildReverseDict()¶

Helper method for computing spectral coloring. This function does not need to be called, it is sufficient to call run() for the SpectralColoring-object.

getColoring()¶

Returns a valid coloring for a given graph. Each node has a color ID to be mapped onto a color palette.

Returns:

A list of nodes containing a valid color mapping.

Return type:

list(int)

prepareSpectrum()¶

Computes eigenvalues and eigenvector in order to prepare the spectral coloring. This function does not need to be called, it is sufficient to call run() for the SpectralColoring-object.

run()¶

Main method of SpectralColoring. This computes a valid coloring.

split(color, depth=0)¶

Helper method for computing spectral coloring. This function does not need to be called, it is sufficient to call run() for the SpectralColoring-object.

Parameters:

• color (int) – colorID to split corresponding nodes into colorID and new color.

• depth (int, optional) – Sets index of eigenvector to compare to depth. Default: 0

valid(color)¶

Checks whether colorID is valid

Parameters:

color (int) – colorID to check for.

Returns:

Returns True if valid, False if not.

Return type:

bool