V
 the graph vertex type.E
 the graph edge type.public class ChordalityInspector<V,E> extends Object
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.
Modifier and Type  Class and Description 

static class 
ChordalityInspector.IterationOrder
Specifies internal iterator type.

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. 
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. 
public ChordalityInspector(Graph<V,E> graph)
graph
, which uses
MaximumCardinalityIterator
as a default iterator.graph
 the graph for which a chordality inspector to be created.public ChordalityInspector(Graph<V,E> graph, ChordalityInspector.IterationOrder iterationOrder)
graph
, which uses an iterator defined by the
second parameter as an internal iterator.graph
 the graph for which a chordality inspector is to be created.iterationOrder
 the constant, which defines iterator to be used by this
ChordalityInspector
.public boolean isChordal()
public List<V> getPerfectEliminationOrder()
public GraphPath<V,E> getHole()
graph
is not chordal, or null if the graph is chordal.public boolean isPerfectEliminationOrder(List<V> vertexOrder)
vertexOrder
form a
perfect elimination order with respect to the inspected graph. Returns false otherwise.vertexOrder
 the sequence of vertices of the graph
.graph
is chordal and the vertices in vertexOrder
are in
perfect elimination order, otherwise false.public ChordalityInspector.IterationOrder getIterationOrder()
ChordalityInspector
ChordalityInspector
Copyright © 2019. All rights reserved.