ChordalGraphMaxCliqueFinder (JGraphT : a free Java graph library)

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