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 typeE
- 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 algorithmGreedyColoring(Graph<V,E> g, int method)
Create a new greedy coloring algorithm
-
Method Summary
All Methods Instance Methods Concrete Methods 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()
-
-
-
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
-
-
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 interfaceApproximationAlgorithm<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 interfaceApproximationAlgorithm<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 interfaceApproximationAlgorithm<V,E>
- Returns:
- true if the algorithm is exact, false otherwise
-
-