- 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>
public class BrownBacktrackColoring<V,E> extends java.lang.Object implements 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
Fields Modifier and Type Field Description private java.util.BitSet[]
allowedColors
private int
chi
private int[]
colorCount
private int[]
completeColorAssignment
private java.util.Map<V,java.lang.Integer>
indexMap
private int[][]
neighbors
private int[]
partialColorAssignment
private VertexColoringAlgorithm.Coloring<V>
vertexColoring
private java.util.List<V>
vertexList
-
Constructor Summary
Constructors Constructor Description BrownBacktrackColoring(Graph<V,E> graph)
Construct a new Brown backtracking algorithm.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description int
getChromaticNumber()
Returns the chromatic number of the input graphVertexColoringAlgorithm.Coloring<V>
getColoring()
Computes a vertex coloring.private void
lazyComputeColoring()
private void
recursiveColor(int pos)
-
-
-
Field Detail
-
vertexList
private final java.util.List<V> vertexList
-
neighbors
private final int[][] neighbors
-
indexMap
private final java.util.Map<V,java.lang.Integer> indexMap
-
partialColorAssignment
private int[] partialColorAssignment
-
colorCount
private int[] colorCount
-
allowedColors
private java.util.BitSet[] allowedColors
-
chi
private int chi
-
completeColorAssignment
private int[] completeColorAssignment
-
vertexColoring
private VertexColoringAlgorithm.Coloring<V> vertexColoring
-
-
Method Detail
-
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
public VertexColoringAlgorithm.Coloring<V> getColoring()
Description copied from interface:VertexColoringAlgorithm
Computes a vertex coloring.- Specified by:
getColoring
in interfaceVertexColoringAlgorithm<V>
- Returns:
- a vertex coloring
-
-