Package org.jgrapht.alg.color
Class ChordalGraphColoring<V,E>
- 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.- Author:
- Timofey Chudakov
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.VertexColoringAlgorithm
VertexColoringAlgorithm.Coloring<V>, VertexColoringAlgorithm.ColoringImpl<V>
-
-
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).
-
-
-
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
-
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.
-
-