Class ChordalGraphMaxCliqueFinder<V,E>

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 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 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 CliqueAlgorithm

CliqueAlgorithm.Clique<V>, CliqueAlgorithm.CliqueImpl<V>

Field Summary

Fields

Modifier and Type	Field	Description
private final Graph<V,E>	graph
private boolean	isChordal
private final 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

Modifier and Type	Method	Description
CliqueAlgorithm.Clique<V>	getClique()	Returns a maximum cardinality clique of the inspected graph.
private Set<V>	getPredecessors(Map<V,Integer> vertexInOrder, V vertex)	Returns the predecessors of vertex in the order defined by map.
private Map<V,Integer>	getVertexInOrder(List<V> vertexOrder)	Returns a map containing vertices from the vertexOrder mapped to their indices in vertexOrder.
private void	lazyComputeMaximumClique()	Lazily computes some maximum clique of the graph.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

graph

private final Graph<V,E> graph

iterationOrder

private final ChordalityInspector.IterationOrder iterationOrder

maximumClique

private CliqueAlgorithm.Clique<V> maximumClique

isChordal

private boolean isChordal

Constructor Details

ChordalGraphMaxCliqueFinder

public ChordalGraphMaxCliqueFinder(Graph<V,E> graph)

Creates a new ChordalGraphMaxCliqueFinder instance. The ChordalityInspector used in this implementation uses the default MaximumCardinalityIterator iterator.

Parameters:

graph - graph

ChordalGraphMaxCliqueFinder

public ChordalGraphMaxCliqueFinder(Graph<V,E> graph,
 ChordalityInspector.IterationOrder iterationOrder)

Creates a new ChordalGraphMaxCliqueFinder instance. The ChordalityInspector used in this implementation uses either the MaximumCardinalityIterator iterator or the LexBreadthFirstIterator iterator, depending on the parameter iterationOrder.

Parameters:

graph - graph

iterationOrder - constant which defines iterator to be used by the ChordalityInspector in this implementation.

Method Details

lazyComputeMaximumClique

private void lazyComputeMaximumClique()

Lazily computes some maximum clique of the graph.

getVertexInOrder

private Map<V,Integer> getVertexInOrder(List<V> vertexOrder)

Returns a map containing vertices from the vertexOrder mapped to their indices in vertexOrder.

Parameters:

vertexOrder - a list with vertices.

Returns:

a mapping of vertices from vertexOrder to their indices in vertexOrder.

getPredecessors

private Set<V> getPredecessors(Map<V,Integer> vertexInOrder,
 V vertex)

Returns the predecessors of vertex in the order defined by map. More precisely, returns those of vertex, whose mapped index in map is less then the index of vertex.

Parameters:

vertexInOrder - defines the mapping of vertices in graph to their indices in order.

vertex - the vertex whose predecessors in order are to be returned.

Returns:

the predecessors of vertex in order defines by map.

getClique

public CliqueAlgorithm.Clique<V> getClique()

Returns a maximum cardinality clique of the inspected graph. If the graph isn't chordal, returns null.

Specified by:

getClique in interface CliqueAlgorithm<V>

Returns:

a maximum clique of the graph if it is chordal, null otherwise.