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>
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 the
ChordalityInspector
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
FieldsModifier and TypeFieldDescriptionprivate final ChordalityInspector
<V, E> private VertexColoringAlgorithm.Coloring
<V> -
Constructor Summary
ConstructorsConstructorDescriptionChordalGraphColoring
(Graph<V, E> graph) Creates a new ChordalGraphColoring instance.ChordalGraphColoring
(Graph<V, E> graph, ChordalityInspector.IterationOrder iterationOrder) Creates a new ChordalGraphColoring instance. -
Method Summary
Modifier and TypeMethodDescriptionReturns a minimum vertex coloring of the inspectedgraph
.Returns the perfect elimination order used to create the coloring (if one exists).getPredecessors
(Map<V, Integer> vertexInOrder, V vertex) Returns the predecessors ofvertex
in the order defined bymap
.getVertexInOrder
(List<V> vertexOrder) Returns a map containing vertices from thevertexOrder
mapped to their indices invertexOrder
.private void
Lazily computes the coloring of the graph.
-
Field Details
-
graph
-
chordalityInspector
-
coloring
-
-
Constructor Details
-
ChordalGraphColoring
Creates a new ChordalGraphColoring instance. TheChordalityInspector
used in this implementation uses the defaultMaximumCardinalityIterator
iterator.- Parameters:
graph
- graph
-
ChordalGraphColoring
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 Details
-
lazyComputeColoring
private void lazyComputeColoring()Lazily computes the coloring of the graph. -
getVertexInOrder
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
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
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
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.
-