Package org.jgrapht.experimental.alg.color

Class GreedyColoring<V,E>

java.lang.Object

org.jgrapht.experimental.alg.IntArrayGraphAlgorithm<V,E>

org.jgrapht.experimental.alg.color.GreedyColoring<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

ApproximationAlgorithm<java.lang.Integer,V>

public class GreedyColoring<V,E>
extends IntArrayGraphAlgorithm<V,E>
implements ApproximationAlgorithm<java.lang.Integer,V>

Compute greedy graph colorings.

Field Summary

Fields

Modifier and Type	Field	Description
private int	_order
static int	BEST_ORDER
static int	LARGEST_SATURATION_FIRST_ORDER
static int	NATURAL_ORDER
static int	SMALLEST_DEGREE_LAST_ORDER

Fields inherited from class org.jgrapht.experimental.alg.IntArrayGraphAlgorithm

_neighbors, _vertexToPos, _vertices

Constructor Summary

Constructors

Constructor	Description
GreedyColoring(Graph<V,E> g)	Create a new greedy coloring algorithm
GreedyColoring(Graph<V,E> g, int method)	Create a new greedy coloring algorithm

Method Summary

Modifier and Type	Method	Description
(package private) int	color(int[] order)
java.lang.Integer	getLowerBound(java.util.Map<V,java.lang.Object> optionalData)	Get the result.
java.lang.Integer	getUpperBound(java.util.Map<V,java.lang.Object> optionalData)	Get the result.
boolean	isExact()	Checks if the algorithm is an exact algorithm.
(package private) int[]	largestSaturationFirstOrder()
(package private) int[]	smallestDegreeLastOrder()

Methods inherited from class java.lang.Object

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

Field Detail

BEST_ORDER

public static final int BEST_ORDER

See Also:

Constant Field Values

NATURAL_ORDER

public static final int NATURAL_ORDER

See Also:

Constant Field Values

SMALLEST_DEGREE_LAST_ORDER

public static final int SMALLEST_DEGREE_LAST_ORDER

See Also:

Constant Field Values

LARGEST_SATURATION_FIRST_ORDER

public static final int LARGEST_SATURATION_FIRST_ORDER

See Also:

Constant Field Values

_order

private int _order

Constructor Detail

GreedyColoring

public GreedyColoring(Graph<V,E> g)

Create a new greedy coloring algorithm

Parameters:

g - the graph

GreedyColoring

public GreedyColoring(Graph<V,E> g,
                      int method)

Create a new greedy coloring algorithm

Parameters:

g - the graph

method - the method to use

Method Detail

color

int color(int[] order)

smallestDegreeLastOrder

int[] smallestDegreeLastOrder()

largestSaturationFirstOrder

int[] largestSaturationFirstOrder()

getLowerBound

public java.lang.Integer getLowerBound(java.util.Map<V,java.lang.Object> optionalData)

Description copied from interface: ApproximationAlgorithm

Get the result.

Specified by:

getLowerBound in interface ApproximationAlgorithm<V,E>

Parameters:

optionalData - optional data

Returns:

the result

getUpperBound

public java.lang.Integer getUpperBound(java.util.Map<V,java.lang.Object> optionalData)

Description copied from interface: ApproximationAlgorithm

Get the result.

Specified by:

getUpperBound in interface ApproximationAlgorithm<V,E>

Parameters:

optionalData - optional data

Returns:

the result

isExact

public boolean isExact()

Description copied from interface: ApproximationAlgorithm

Checks if the algorithm is an exact algorithm.

Specified by:

isExact in interface ApproximationAlgorithm<V,E>

Returns:

true if the algorithm is exact, false otherwise