Package org.jgrapht.alg
Class ChromaticNumber
java.lang.Object
org.jgrapht.alg.ChromaticNumber
Allows the
chromatic number of a graph to be calculated. This is the minimal number
of colors needed to color each vertex such that no two adjacent vertices
share the same color. This algorithm will not find the true chromatic number,
since this is an NP-complete problem. So, a greedy algorithm will find an
approximate chromatic number.
- Since:
- Dec 21, 2008
- Author:
- Andrew Newell
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionstatic <V,
E> int Finds the number of colors required for a greedy coloring of the graph.
-
Constructor Details
-
ChromaticNumber
public ChromaticNumber()
-
-
Method Details
-
findGreedyChromaticNumber
Finds the number of colors required for a greedy coloring of the graph.- Parameters:
g
- an undirected graph to find the chromatic number of- Returns:
- integer the approximate chromatic number from the greedy algorithm
-