org.jgrapht.alg

Class ChromaticNumber

java.lang.Object

org.jgrapht.alg.ChromaticNumber

public abstract class ChromaticNumber
extends Object

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

Constructor and Description
ChromaticNumber()

Method Summary

Modifier and Type	Method and Description
static <V,E> int	findGreedyChromaticNumber(UndirectedGraph<V,E> g) Finds the number of colors required for a greedy coloring of the graph.
static <V,E> Map<Integer,Set<V>>	findGreedyColoredGroups(UndirectedGraph<V,E> g) Finds a greedy coloring of the graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

ChromaticNumber

public ChromaticNumber()

Method Detail

findGreedyChromaticNumber

public static <V,E> int findGreedyChromaticNumber(UndirectedGraph<V,E> g)

Finds the number of colors required for a greedy coloring of the graph.

Type Parameters:

V - the graph vertex type

E - the graph edge type

Parameters:

g - an undirected graph to find the chromatic number of

Returns:

integer the approximate chromatic number from the greedy algorithm

findGreedyColoredGroups

public static <V,E> Map<Integer,Set<V>> findGreedyColoredGroups(UndirectedGraph<V,E> g)

Finds a greedy coloring of the graph.

Type Parameters:

V - the graph vertex type

E - the graph edge type

Parameters:

g - an undirected graph for which to find the coloring

Returns:

a greedy coloring