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 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 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.

Since:

March 2018

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 and 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

Modifier and Type	Method and Description
VertexColoringAlgorithm.Coloring<V>	getColoring() Returns a minimum vertex coloring of the inspected graph.
List<V>	getPerfectEliminationOrder() Returns the perfect elimination order used to create the coloring (if one exists).

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ChordalGraphColoring

public ChordalGraphColoring(Graph<V,E> graph)

Creates a new ChordalGraphColoring instance. The ChordalityInspector used in this implementation uses the default MaximumCardinalityIterator iterator.

Parameters:

graph - graph

ChordalGraphColoring

public ChordalGraphColoring(Graph<V,E> graph,
                            ChordalityInspector.IterationOrder iterationOrder)

Creates a new ChordalGraphColoring instance. The ChordalityInspector used in this implementation uses either the MaximumCardinalityIterator iterator or the LexBreadthFirstIterator iterator, depending on the parameter iterationOrder.

Parameters:

graph - graph

iterationOrder - constant which defines iterator to be used by the ChordalityInspector in this implementation.

Method Detail

getColoring

public VertexColoringAlgorithm.Coloring<V> getColoring()

Returns a minimum vertex coloring of the inspected graph. 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 interface VertexColoringAlgorithm<V>

Returns:

a coloring of the graph if it is chordal, null otherwise.

getPerfectEliminationOrder

public 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.