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>
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 the
ChordalityInspector
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
FieldsModifier and TypeFieldDescriptionprivate boolean
private final ChordalityInspector.IterationOrder
private CliqueAlgorithm.Clique
<V> -
Constructor Summary
ConstructorsConstructorDescriptionChordalGraphMaxCliqueFinder
(Graph<V, E> graph) Creates a new ChordalGraphMaxCliqueFinder instance.ChordalGraphMaxCliqueFinder
(Graph<V, E> graph, ChordalityInspector.IterationOrder iterationOrder) Creates a new ChordalGraphMaxCliqueFinder instance. -
Method Summary
Modifier and TypeMethodDescriptionReturns a maximum cardinality clique of the inspectedgraph
.getPredecessors
(Map<V, Integer> vertexInOrder, V vertex) Returns the predecessors ofvertex
in the order defined bymap
.getVertexInOrder
(List<V> vertexOrder) Returns a map containing vertices from thevertexOrder
mapped to their indices invertexOrder
.private void
Lazily computes some maximum clique of thegraph
.
-
Field Details
-
graph
-
iterationOrder
-
maximumClique
-
isChordal
private boolean isChordal
-
-
Constructor Details
-
ChordalGraphMaxCliqueFinder
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 Details
-
lazyComputeMaximumClique
private void lazyComputeMaximumClique()Lazily computes some maximum clique of thegraph
. -
getVertexInOrder
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
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
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.
-