- java.lang.Object
-
- org.jgrapht.alg.clique.ChordalGraphMaxCliqueFinder<V,E>
-
- Type Parameters:
V
- the graph vertex type.E
- the graph edge type.
- All Implemented Interfaces:
CliqueAlgorithm<V>
public class ChordalGraphMaxCliqueFinder<V,E> extends java.lang.Object implements CliqueAlgorithm<V>
Calculates a maximum cardinality clique in 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 clique, this implementation relies on theChordalityInspector
to compute a perfect elimination order. The maximum clique 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.
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.CliqueAlgorithm
CliqueAlgorithm.Clique<V>, CliqueAlgorithm.CliqueImpl<V>
-
-
Field Summary
Fields Modifier and Type Field Description private Graph<V,E>
graph
private boolean
isChordal
private ChordalityInspector.IterationOrder
iterationOrder
private CliqueAlgorithm.Clique<V>
maximumClique
-
Constructor Summary
Constructors Constructor Description ChordalGraphMaxCliqueFinder(Graph<V,E> graph)
Creates a new ChordalGraphMaxCliqueFinder instance.ChordalGraphMaxCliqueFinder(Graph<V,E> graph, ChordalityInspector.IterationOrder iterationOrder)
Creates a new ChordalGraphMaxCliqueFinder instance.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description CliqueAlgorithm.Clique<V>
getClique()
Returns a maximum cardinality clique of the inspectedgraph
.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
.private void
lazyComputeMaximumClique()
Lazily computes some maximum clique of thegraph
.
-
-
-
Field Detail
-
iterationOrder
private final ChordalityInspector.IterationOrder iterationOrder
-
maximumClique
private CliqueAlgorithm.Clique<V> maximumClique
-
isChordal
private boolean isChordal
-
-
Constructor Detail
-
ChordalGraphMaxCliqueFinder
public ChordalGraphMaxCliqueFinder(Graph<V,E> graph)
Creates a new ChordalGraphMaxCliqueFinder instance. TheChordalityInspector
used in this implementation uses the defaultMaximumCardinalityIterator
iterator.- Parameters:
graph
- graph
-
ChordalGraphMaxCliqueFinder
public ChordalGraphMaxCliqueFinder(Graph<V,E> graph, ChordalityInspector.IterationOrder iterationOrder)
Creates a new ChordalGraphMaxCliqueFinder instance. TheChordalityInspector
used in this implementation uses either theMaximumCardinalityIterator
iterator or theLexBreadthFirstIterator
iterator, depending on the parameteriterationOrder
.- Parameters:
graph
- graphiterationOrder
- constant which defines iterator to be used by theChordalityInspector
in this implementation.
-
-
Method Detail
-
lazyComputeMaximumClique
private void lazyComputeMaximumClique()
Lazily computes some maximum clique of thegraph
.
-
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
.
-
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
.
-
getClique
public CliqueAlgorithm.Clique<V> getClique()
Returns a maximum cardinality clique of the inspectedgraph
. If the graph isn't chordal, returns null.- Specified by:
getClique
in interfaceCliqueAlgorithm<V>
- Returns:
- a maximum clique of the
graph
if it is chordal, null otherwise.
-
-