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<Integer,V>

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

Compute greedy graph colorings.

Field Summary

Fields

Modifier and Type	Field and Description
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 and 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 and Description
Integer	getLowerBound(Map<V,Object> optionalData) Get the result.
Integer	getUpperBound(Map<V,Object> optionalData) Get the result.
boolean	isExact() Checks if the algorithm is an exact algorithm.

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

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

getLowerBound

public Integer getLowerBound(Map<V,Object> optionalData)

Description copied from interface: ApproximationAlgorithm

Get the result.

Specified by:

getLowerBound in interface ApproximationAlgorithm<Integer,V>

Parameters:

optionalData - optional data

Returns:

the result

getUpperBound

public Integer getUpperBound(Map<V,Object> optionalData)

Description copied from interface: ApproximationAlgorithm

Get the result.

Specified by:

getUpperBound in interface ApproximationAlgorithm<Integer,V>

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<Integer,V>

Returns:

true if the algorithm is exact, false otherwise