org.jgrapht.alg.clique

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.

Author:

Timofey Chudakov

Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.CliqueAlgorithm

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

Constructor Summary

Constructors

Constructor and 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 and Description
CliqueAlgorithm.Clique<V>	getClique() Returns a maximum cardinality clique of the inspected graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

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 Detail

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.