 Type Parameters:
V
 the graph vertex type.E
 the graph edge type.
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.
 Author:
 Timofey Chudakov

Nested Class Summary
Modifier and TypeClassDescriptionstatic enum
Specifies internal iterator type. 
Constructor Summary
ConstructorDescriptionChordalityInspector
(Graph<V, E> graph) Creates a chordality inspector forgraph
, which usesMaximumCardinalityIterator
as a default iterator.ChordalityInspector
(Graph<V, E> graph, ChordalityInspector.IterationOrder iterationOrder) Creates a chordality inspector forgraph
, which uses an iterator defined by the second parameter as an internal iterator. 
Method Summary
Modifier and TypeMethodDescriptiongetHole()
A graph which is not chordal, must contain a hole (chordless cycle on 4 or more vertices).Returns the type of iterator used in thisChordalityInspector
Returns a perfect elimination order if one exists.boolean
Checks whether the inspected graph is chordal.boolean
isPerfectEliminationOrder
(List<V> vertexOrder) Checks whether the vertices in thevertexOrder
form a perfect elimination order with respect to the inspected graph.

Constructor Details

ChordalityInspector
Creates a chordality inspector forgraph
, which usesMaximumCardinalityIterator
as a default iterator. Parameters:
graph
 the graph for which a chordality inspector to be created.

ChordalityInspector
Creates a chordality inspector forgraph
, 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 thisChordalityInspector
.


Method Details

isChordal
public boolean isChordal()Checks whether the inspected graph is chordal. Returns:
 true if this graph is chordal, otherwise false.

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
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
Checks whether the vertices in thevertexOrder
form a perfect elimination order with respect to the inspected graph. Returns false otherwise. Parameters:
vertexOrder
 the sequence of vertices of thegraph
. Returns:
 true if the
graph
is chordal and the vertices invertexOrder
are in perfect elimination order, otherwise false.

getIterationOrder
Returns the type of iterator used in thisChordalityInspector
 Returns:
 the type of iterator used in this
ChordalityInspector
