Package org.graph4j.coloring

Class LargestDegreeFirstColoring

java.lang.Object

org.graph4j.SimpleGraphAlgorithm

org.graph4j.coloring.GreedyColoringBase

org.graph4j.coloring.GreedyColoring

org.graph4j.coloring.LargestDegreeFirstColoring

All Implemented Interfaces:

ColoringAlgorithm

public class LargestDegreeFirstColoring
extends GreedyColoring

The vertices are colored in decreasing order by their degree. The vertex ordering is computed statically before the algorithm starts.

The Largest First Vertex Ordering (LFVO) produces an ordering of the vertices such that the vertices with the largest degree are processed first.

Author:

Cristian Frăsinaru

See Also:

• VertexOrderings

Field Summary

Fields inherited from class org.graph4j.coloring.GreedyColoring

pos, 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
LargestDegreeFirstColoring(Graph graph)	The vertices will be colored in decreasing order by their degree.

Method Summary

Methods inherited from class org.graph4j.coloring.GreedyColoring

hasUncoloredVertices, init, 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

Constructor Details

LargestDegreeFirstColoring

public LargestDegreeFirstColoring(Graph graph)

The vertices will be colored in decreasing order by their degree.

Parameters:

graph - the input graph;