java.lang.Object
org.jgrapht.alg.color.BrownBacktrackColoring<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
VertexColoringAlgorithm<V>
Brown graph coloring algorithm.
-
Nested Class Summary
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.VertexColoringAlgorithm
VertexColoringAlgorithm.Coloring<V>, VertexColoringAlgorithm.ColoringImpl<V>
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate BitSet[]
private int
private int[]
private int[]
private final int[][]
private int[]
private VertexColoringAlgorithm.Coloring
<V> -
Constructor Summary
ConstructorsConstructorDescriptionBrownBacktrackColoring
(Graph<V, E> graph) Construct a new Brown backtracking algorithm. -
Method Summary
Modifier and TypeMethodDescriptionint
Returns the chromatic number of the input graphComputes a vertex coloring.private void
private void
recursiveColor
(int pos)
-
Field Details
-
vertexList
-
neighbors
private final int[][] neighbors -
indexMap
-
partialColorAssignment
private int[] partialColorAssignment -
colorCount
private int[] colorCount -
allowedColors
-
chi
private int chi -
completeColorAssignment
private int[] completeColorAssignment -
vertexColoring
-
-
Constructor Details
-
BrownBacktrackColoring
Construct a new Brown backtracking algorithm.- Parameters:
graph
- the input graph
-
-
Method Details
-
recursiveColor
private void recursiveColor(int pos) -
lazyComputeColoring
private void lazyComputeColoring() -
getChromaticNumber
public int getChromaticNumber()Returns the chromatic number of the input graph- Returns:
- chromatic number of the graph
-
getColoring
Description copied from interface:VertexColoringAlgorithm
Computes a vertex coloring.- Specified by:
getColoring
in interfaceVertexColoringAlgorithm<V>
- Returns:
- a vertex coloring
-