Package org.graph4j.coloring

Class DSaturGreedyColoring

java.lang.Object

org.graph4j.SimpleGraphAlgorithm

org.graph4j.coloring.GreedyColoringBase

org.graph4j.coloring.DSaturGreedyColoring

All Implemented Interfaces:

ColoringAlgorithm

public class DSaturGreedyColoring
extends GreedyColoringBase

DSatur (Degree of Saturation) is an adaptive coloring algorithm in which the vertex ordering is not computed statically at the beginning. Once a new vertex has been colored, the algorithm determines which of the remaining uncolored vertices has the highest number of distinct colors in its neighborhood and colors this vertex next. This number is called the degree of saturation of a given vertex. DSatur produces exact results for bipartite, cycle, and wheel graphs. The complexity is O((n+m)lg n).

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.coloring.GreedyColoringBase

colors, numColors, used

Fields inherited from class org.graph4j.SimpleGraphAlgorithm

graph

Constructor Summary

Constructors

Constructor	Description
DSaturGreedyColoring(Graph graph)

Method Summary

Modifier and Type	Method	Description
protected boolean	hasUncoloredVertices()
protected void	init()
protected int	nextUncoloredVertex()
protected void	update(int v)

Methods inherited from class org.graph4j.coloring.GreedyColoringBase

findColoring, findColoring, markUsedColor

Methods inherited from class org.graph4j.SimpleGraphAlgorithm

getGraph

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.graph4j.coloring.ColoringAlgorithm

getGraph, getHeuristicColoring, getLowerBound, getMaximalClique, isOptimalityEnsured, isSolvingComponents, isStoppingOnFailure, isValid

Constructor Details

DSaturGreedyColoring

public DSaturGreedyColoring(Graph graph)

Method Details

init

protected void init()

Overrides:

init in class GreedyColoringBase

hasUncoloredVertices

protected boolean hasUncoloredVertices()

Specified by:

hasUncoloredVertices in class GreedyColoringBase

nextUncoloredVertex

protected int nextUncoloredVertex()

Specified by:

nextUncoloredVertex in class GreedyColoringBase

update

protected void update(int v)

Overrides:

update in class GreedyColoringBase