Package com.jgalgo.alg.color

Class ColoringGreedy

java.lang.Object

com.jgalgo.alg.color.ColoringAlgoAbstract

com.jgalgo.alg.color.ColoringGreedy

All Implemented Interfaces:

ColoringAlgo, RandomizedAlgorithm

public class ColoringGreedy
extends ColoringAlgoAbstract
implements RandomizedAlgorithm

A greedy coloring algorithm with random vertices order.

The algorithm examine the vertices in a random order and assign for each vertex the minimum (integer) color which is not used by its neighbors.

The algorithm runs in linear time, assuming the number of colors is constant.

For deterministic behavior, set the seed using setSeed(long).

Note that the result is an approximation for the minimum number of colors, as finding an optimal coloring is an NP-hard problem.

Author:

Barak Ugav

See Also:

• Wikipedia

Constructor Summary

Constructors

Constructor	Description
ColoringGreedy()	Create a new coloring algorithm object.

Method Summary

Modifier and Type	Method	Description
void	setSeed(long seed)	Sets the seed for the random number generator.

Methods inherited from class com.jgalgo.alg.color.ColoringAlgoAbstract

computeColoring

Methods inherited from class java.lang.Object

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

Constructor Details

ColoringGreedy

public ColoringGreedy()

Create a new coloring algorithm object.

Please prefer using ColoringAlgo.newInstance() to get a default implementation for the ColoringAlgo interface.

Method Details

setSeed

public void setSeed(long seed)

Description copied from interface: RandomizedAlgorithm

Sets the seed for the random number generator.

The algorithm will use the same seed for the random number generator, in order to perform deterministically. Note that if methods of the algorithm are called multiple times, the seed should be set before each call.

Specified by:

setSeed in interface RandomizedAlgorithm

Parameters:

seed - the seed for the random number generator.