- java.lang.Object
-
- org.jgrapht.alg.color.ChordalGraphColoring<V,E>
-
- Type Parameters:
V
- the graph vertex type.E
- the graph edge type.
- All Implemented Interfaces:
VertexColoringAlgorithm<V>
public class ChordalGraphColoring<V,E> extends java.lang.Object implements VertexColoringAlgorithm<V>
Calculates a minimum vertex coloring for a chordal graph. A chordal graph is a simple graph in which all cycles of four or more vertices have a chord. A chord is an edge that is not part of the cycle but connects two vertices of the cycle. To compute the vertex coloring, this implementation relies on theChordalityInspector
to compute a perfect elimination order. The vertex coloring for a chordal graph is computed in $\mathcal{O}(|V| + |E|)$ time. All the methods in this class are invoked in a lazy fashion, meaning that computations are only started once the method gets invoked.
-
-
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 ChordalityInspector<V,E>
chordalityInspector
private VertexColoringAlgorithm.Coloring<V>
coloring
private Graph<V,E>
graph
-
Constructor Summary
Constructors Constructor Description ChordalGraphColoring(Graph<V,E> graph)
Creates a new ChordalGraphColoring instance.ChordalGraphColoring(Graph<V,E> graph, ChordalityInspector.IterationOrder iterationOrder)
Creates a new ChordalGraphColoring instance.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description VertexColoringAlgorithm.Coloring<V>
getColoring()
Returns a minimum vertex coloring of the inspectedgraph
.java.util.List<V>
getPerfectEliminationOrder()
Returns the perfect elimination order used to create the coloring (if one exists).private java.util.Set<V>
getPredecessors(java.util.Map<V,java.lang.Integer> vertexInOrder, V vertex)
Returns the predecessors ofvertex
in the order defined bymap
.private java.util.Map<V,java.lang.Integer>
getVertexInOrder(java.util.List<V> vertexOrder)
Returns a map containing vertices from thevertexOrder
mapped to their indices invertexOrder
.private void
lazyComputeColoring()
Lazily computes the coloring of the graph.
-
-
-
Field Detail
-
chordalityInspector
private final ChordalityInspector<V,E> chordalityInspector
-
coloring
private VertexColoringAlgorithm.Coloring<V> coloring
-
-
Constructor Detail
-
ChordalGraphColoring
public ChordalGraphColoring(Graph<V,E> graph)
Creates a new ChordalGraphColoring instance. TheChordalityInspector
used in this implementation uses the defaultMaximumCardinalityIterator
iterator.- Parameters:
graph
- graph
-
ChordalGraphColoring
public ChordalGraphColoring(Graph<V,E> graph, ChordalityInspector.IterationOrder iterationOrder)
Creates a new ChordalGraphColoring instance. TheChordalityInspector
used in this implementation uses either theMaximumCardinalityIterator
iterator or theLexBreadthFirstIterator
iterator, depending on the parameteriterationOrder
.- Parameters:
graph
- graphiterationOrder
- constant which defines iterator to be used by theChordalityInspector
in this implementation.
-
-
Method Detail
-
lazyComputeColoring
private void lazyComputeColoring()
Lazily computes the coloring of the graph.
-
getVertexInOrder
private java.util.Map<V,java.lang.Integer> getVertexInOrder(java.util.List<V> vertexOrder)
Returns a map containing vertices from thevertexOrder
mapped to their indices invertexOrder
.- Parameters:
vertexOrder
- a list with vertices.- Returns:
- a mapping of vertices from
vertexOrder
to their indices invertexOrder
.
-
getPredecessors
private java.util.Set<V> getPredecessors(java.util.Map<V,java.lang.Integer> vertexInOrder, V vertex)
Returns the predecessors ofvertex
in the order defined bymap
. More precisely, returns those ofvertex
, whose mapped index inmap
is less then the index ofvertex
.- Parameters:
vertexInOrder
- defines the mapping of vertices ingraph
to their indices in order.vertex
- the vertex whose predecessors in order are to be returned.- Returns:
- the predecessors of
vertex
in order defines bymap
.
-
getColoring
public VertexColoringAlgorithm.Coloring<V> getColoring()
Returns a minimum vertex coloring of the inspectedgraph
. If the graph isn't chordal, returns null. The number of colors used in the coloring equals the chromatic number of the input graph.- Specified by:
getColoring
in interfaceVertexColoringAlgorithm<V>
- Returns:
- a coloring of the
graph
if it is chordal, null otherwise.
-
getPerfectEliminationOrder
public java.util.List<V> getPerfectEliminationOrder()
Returns the perfect elimination order used to create the coloring (if one exists). This method returns null if the graph is not chordal.- Returns:
- the perfect elimination order used to create the coloring, or null if graph is not chordal.
-
-