org.jgrapht.alg.cycle

Class ChordalityInspector<V,E>

java.lang.Object

org.jgrapht.alg.cycle.ChordalityInspector<V,E>

Type Parameters:

V - the graph vertex type.

E - the graph edge type.

public class ChordalityInspector<V,E>
extends Object

Tests whether a graph is chordal. 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. A graph is chordal if and only if it has a perfect elimination order. A perfect elimination order in a graph is an ordering of the vertices of the graph such that, for each vertex $v$, $v$ and the neighbors of $v$ that occur after $v$ in the order form a clique. This implementation uses either MaximumCardinalityIterator or LexBreadthFirstIterator to compute a perfect elimination order. The desired method is specified during construction time.

Chordal graphs are a subset of the perfect graphs. They may be recognized in polynomial time, and several problems that are hard on other classes of graphs such as minimum vertex coloring or determining maximum cardinality cliques and independent set can be performed in polynomial time when the input is chordal.

All methods in this class run in $\mathcal{O}(|V| + |E|)$ time. Determining whether a graph is chordal, as well as computing a perfect elimination order takes $\mathcal{O}(|V| + |E|)$ time, independent of the algorithm (MaximumCardinalityIterator or LexBreadthFirstIterator) used to compute the perfect elimination order.

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

Modifier and Type	Class and Description
static class	ChordalityInspector.IterationOrder Specifies internal iterator type.

Constructor Summary

Constructors

Constructor and Description
ChordalityInspector(Graph<V,E> graph) Creates a chordality inspector for graph, which uses MaximumCardinalityIterator as a default iterator.
ChordalityInspector(Graph<V,E> graph, ChordalityInspector.IterationOrder iterationOrder) Creates a chordality inspector for graph, which uses an iterator defined by the second parameter as an internal iterator.

Method Summary

Modifier and Type	Method and Description
GraphPath<V,E>	getHole() A graph which is not chordal, must contain a hole (chordless cycle on 4 or more vertices).
ChordalityInspector.IterationOrder	getIterationOrder() Returns the type of iterator used in this ChordalityInspector
List<V>	getPerfectEliminationOrder() Returns a perfect elimination order if one exists.
boolean	isChordal() Checks whether the inspected graph is chordal.
boolean	isPerfectEliminationOrder(List<V> vertexOrder) Checks whether the vertices in the vertexOrder form a perfect elimination order with respect to the inspected graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

ChordalityInspector

public ChordalityInspector(Graph<V,E> graph)

Creates a chordality inspector for graph, which uses MaximumCardinalityIterator as a default iterator.

Parameters:

graph - the graph for which a chordality inspector to be created.

ChordalityInspector

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

Creates a chordality inspector for graph, which uses an iterator defined by the second parameter as an internal iterator.

Parameters:

graph - the graph for which a chordality inspector is to be created.

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

Method Detail

isChordal

public boolean isChordal()

Checks whether the inspected graph is chordal.

Returns:

true if this graph is chordal, otherwise false.

getPerfectEliminationOrder

public List<V> getPerfectEliminationOrder()

Returns a perfect elimination order if one exists. The existence of a perfect elimination order certifies that the graph is chordal. This method returns null if the graph is not chordal.

Returns:

a perfect elimination order of a graph or null if graph is not chordal.

getHole

public GraphPath<V,E> getHole()

A graph which is not chordal, must contain a hole (chordless cycle on 4 or more vertices). The existence of a hole certifies that the graph is not chordal. This method returns a chordless cycle if the graph is not chordal, or null if the graph is chordal.

Returns:

a hole if the graph is not chordal, or null if the graph is chordal.

isPerfectEliminationOrder

public boolean isPerfectEliminationOrder(List<V> vertexOrder)

Checks whether the vertices in the vertexOrder form a perfect elimination order with respect to the inspected graph. Returns false otherwise.

Parameters:

vertexOrder - the sequence of vertices of the graph.

Returns:

true if the graph is chordal and the vertices in vertexOrder are in perfect elimination order, otherwise false.

getIterationOrder

public ChordalityInspector.IterationOrder getIterationOrder()

Returns the type of iterator used in this ChordalityInspector

Returns:

the type of iterator used in this ChordalityInspector