Package org.graph4j.coloring

Class GreedyColoring

java.lang.Object

org.graph4j.SimpleGraphAlgorithm

org.graph4j.coloring.GreedyColoringBase

org.graph4j.coloring.GreedyColoring

All Implemented Interfaces:

ColoringAlgorithm

Direct Known Subclasses:

GreedyBandwithColoring, LargestDegreeFirstColoring, RandomGreedyColoring, SmallestDegreeLastColoring

public class GreedyColoring
extends GreedyColoringBase

The order in which vertices are colored is either according to their indices in the graph, or can be specified in the constructor.

Author:

Cristian Frăsinaru

Field Summary

Fields

Modifier and Type	Field	Description
protected int	pos
protected int[]	vertexOrdering

Fields inherited from class org.graph4j.coloring.GreedyColoringBase

colors, numColors, used

Fields inherited from class org.graph4j.SimpleGraphAlgorithm

graph

Constructor Summary

Constructors

Constructor	Description
GreedyColoring(Graph graph)	The vertices will be colored in the order of their graph indices.
GreedyColoring(Graph graph, int[] vertexOrdering)	Creates a greedy algorithm that will color the vertices of the graph in the specified order.
GreedyColoring(Graph graph, int[] vertexOrdering, boolean validateOrdering)	Creates a greedy algorithm that will color the vertices of the graph in the specified order.Validation of the ordering is optional.

Method Summary

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

Methods inherited from class org.graph4j.coloring.GreedyColoringBase

findColoring, findColoring, markUsedColor, update

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

Field Details

pos

protected int pos

vertexOrdering

protected int[] vertexOrdering

Constructor Details

GreedyColoring

public GreedyColoring(Graph graph)

The vertices will be colored in the order of their graph indices.

Parameters:

graph - the input graph.

GreedyColoring

public GreedyColoring(Graph graph,
 int[] vertexOrdering)

Creates a greedy algorithm that will color the vertices of the graph in the specified order. Checks if the ordering is valid.

Parameters:

graph - the input graph.

vertexOrdering - an ordering of the graph vertices.

Throws:

InvalidVertexOrdering - if the ordering is invalid.

GreedyColoring

public GreedyColoring(Graph graph,
 int[] vertexOrdering,
 boolean validateOrdering)

Creates a greedy algorithm that will color the vertices of the graph in the specified order.Validation of the ordering is optional.

Parameters:

graph - the input graph.

vertexOrdering - an ordering of the graph vertices.

validateOrdering - true if the order should be validate, false otherwise.

Throws:

InvalidVertexOrdering - if the ordering is invalid.

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