- 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 java.lang.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 eitherMaximumCardinalityIterator
orLexBreadthFirstIterator
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
orLexBreadthFirstIterator
) 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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
ChordalityInspector.IterationOrder
Specifies internal iterator type.
-
Field Summary
Fields Modifier and Type Field Description private boolean
chordal
Contains true if the graph is chordal, otherwise false.private Graph<V,E>
graph
The inspected graph.private GraphPath<V,E>
hole
A hole contained in the inspectedgraph
.private ChordalityInspector.IterationOrder
iterationOrder
Stores the type of iterator used by thisChordalityInspector
.private java.util.List<V>
order
Order produced byorderIterator
.private GraphIterator<V,E>
orderIterator
Iterator used for producing perfect elimination order.
-
Constructor Summary
Constructors Constructor Description ChordalityInspector(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
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
dfsVisit(java.util.List<V> cycle, java.util.Map<V,java.lang.Boolean> visited, V finish, V middle, V current)
Computes some cycle in the graph on the vertices from the domain of the mapvisited
.private void
findHole(V a, V b, V c)
Computes a hole from the vertices ofsubgraph
of the inspectedgraph
with verticesa
,b
andc
on this cycle (there must be no edge betweena
andc
.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 thisChordalityInspector
java.util.List<V>
getPerfectEliminationOrder()
Returns a perfect elimination order if one exists.private java.util.Set<V>
getPredecessors(java.util.Map<V,java.lang.Integer> vertexInOrder, V vertex)
Returns the predecessors ofvertex
in the order defined bymap
.private java.util.Map<V,java.lang.Integer>
getVertexInOrder(java.util.List<V> vertexOrder)
Returns a map containing vertices from thevertexOrder
mapped to their indices invertexOrder
.boolean
isChordal()
Checks whether the inspected graph is chordal.boolean
isPerfectEliminationOrder(java.util.List<V> vertexOrder)
Checks whether the vertices in thevertexOrder
form a perfect elimination order with respect to the inspected graph.private boolean
isPerfectEliminationOrder(java.util.List<V> vertexOrder, boolean computeHole)
Checks whether the vertices in thevertexOrder
form a perfect elimination order with respect to the inspected graph.private java.util.List<V>
lazyComputeOrder()
Computes vertex order viaorderIterator
.private java.util.List<V>
minimizeCycle(java.util.List<V> cycle)
Minimizes the cycle represented by the listcycle
.
-
-
-
Field Detail
-
iterationOrder
private final ChordalityInspector.IterationOrder iterationOrder
Stores the type of iterator used by thisChordalityInspector
.
-
orderIterator
private final GraphIterator<V,E> orderIterator
Iterator used for producing perfect elimination order.
-
chordal
private boolean chordal
Contains true if the graph is chordal, otherwise false.
-
order
private java.util.List<V> order
Order produced byorderIterator
.
-
-
Constructor Detail
-
ChordalityInspector
public ChordalityInspector(Graph<V,E> graph)
Creates a chordality inspector forgraph
, which usesMaximumCardinalityIterator
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 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 Detail
-
isChordal
public boolean isChordal()
Checks whether the inspected graph is chordal.- Returns:
- true if this graph is chordal, otherwise false.
-
getPerfectEliminationOrder
public java.util.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(java.util.List<V> vertexOrder)
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.
-
lazyComputeOrder
private java.util.List<V> lazyComputeOrder()
Computes vertex order viaorderIterator
.- Returns:
- computed order.
-
isPerfectEliminationOrder
private boolean isPerfectEliminationOrder(java.util.List<V> vertexOrder, boolean computeHole)
Checks whether the vertices in thevertexOrder
form a perfect elimination order with respect to the inspected graph. Returns false otherwise. Computes a hole if thecomputeHole
is true.- Parameters:
vertexOrder
- the sequence of vertices ofgraph
.computeHole
- tells whether to compute the hole if the graph isn't chordal.- Returns:
- true if the
graph
is chordal and the vertices invertexOrder
are in perfect elimination order.
-
getVertexInOrder
private java.util.Map<V,java.lang.Integer> getVertexInOrder(java.util.List<V> vertexOrder)
Returns a map containing vertices from thevertexOrder
mapped to their indices invertexOrder
.- Parameters:
vertexOrder
- a list with vertices.- Returns:
- a mapping of vertices from
vertexOrder
to their indices invertexOrder
.
-
findHole
private void findHole(V a, V b, V c)
Computes a hole from the vertices ofsubgraph
of the inspectedgraph
with verticesa
,b
andc
on this cycle (there must be no edge betweena
andc
.- Parameters:
a
- vertex that belongs to the cycleb
- vertex that belongs to the cyclec
- vertex that belongs to the cycle
-
dfsVisit
private void dfsVisit(java.util.List<V> cycle, java.util.Map<V,java.lang.Boolean> visited, V finish, V middle, V current)
Computes some cycle in the graph on the vertices from the domain of the mapvisited
. More precisely, finds some path frommiddle
tofinish
. The vertexmiddle
isn't the endpoint of any chord in this cycle.- Parameters:
cycle
- already computed part of the cyclevisited
- the map that defines which vertex has been visited by this methodfinish
- the last vertex in the cycle.middle
- the vertex, which must be adjacent onlcurrent
- currently examined vertex.
-
minimizeCycle
private java.util.List<V> minimizeCycle(java.util.List<V> cycle)
Minimizes the cycle represented by the listcycle
. More precisely it retains first 2 vertices and finds a chordless cycle starting from the third vertex.- Parameters:
cycle
- vertices of the graph that represent the cycle.- Returns:
- a chordless cycle
-
getPredecessors
private java.util.Set<V> getPredecessors(java.util.Map<V,java.lang.Integer> vertexInOrder, V vertex)
Returns the predecessors ofvertex
in the order defined bymap
. More precisely, returns those ofvertex
, whose mapped index inmap
is less then the index ofvertex
.- Parameters:
vertexInOrder
- defines the mapping of vertices ingraph
to their indices in order.vertex
- the vertex whose predecessors in order are to be returned.- Returns:
- the predecessors of
vertex
in order defines bymap
.
-
getIterationOrder
public ChordalityInspector.IterationOrder getIterationOrder()
Returns the type of iterator used in thisChordalityInspector
- Returns:
- the type of iterator used in this
ChordalityInspector
-
-