ChordalGraphIndependentSetFinder (JGraphT : a free Java graph library)

java.lang.Object
- org.jgrapht.alg.independentset.ChordalGraphIndependentSetFinder<V,E>

Type Parameters:

V - the graph vertex type.

E - the graph edge type.

All Implemented Interfaces:

IndependentSetAlgorithm<V>
```
public class ChordalGraphIndependentSetFinder<V,E>
extends java.lang.Object
implements IndependentSetAlgorithm<V>
```
Calculates a maximum cardinality independent set 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 independent set, this implementation relies on the ChordalityInspector to compute a perfect elimination order. The maximum cardinality independent set 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.IndependentSetAlgorithm
  IndependentSetAlgorithm.IndependentSet<V>, IndependentSetAlgorithm.IndependentSetImpl<V>

Constructor Summary

Constructors
Constructor	Description
`ChordalGraphIndependentSetFinder(Graph<V,E> graph)`	Creates a new ChordalGraphIndependentSetFinder instance.
`ChordalGraphIndependentSetFinder(Graph<V,E> graph, ChordalityInspector.IterationOrder iterationOrder)`	Creates a new ChordalGraphIndependentSetFinder instance.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`IndependentSetAlgorithm.IndependentSet<V>`	`getIndependentSet()`	Returns a maximum cardinality independent set of the inspected `graph`.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - ChordalGraphIndependentSetFinder
```
public ChordalGraphIndependentSetFinder(Graph<V,E> graph)
```
    Creates a new ChordalGraphIndependentSetFinder instance. The ChordalityInspector used in this implementation uses the default MaximumCardinalityIterator iterator.
    
    Parameters:
    
    graph - graph
  - ChordalGraphIndependentSetFinder
```
public ChordalGraphIndependentSetFinder(Graph<V,E> graph,
                                        ChordalityInspector.IterationOrder iterationOrder)
```
    Creates a new ChordalGraphIndependentSetFinder 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
  - getIndependentSet
```
public IndependentSetAlgorithm.IndependentSet<V> getIndependentSet()
```
    Returns a maximum cardinality independent set of the inspected graph. If the graph isn't chordal, returns null.
    
    Specified by:
    
    getIndependentSet in interface IndependentSetAlgorithm<V>
    
    Returns:
    
    a maximum independent set of the graph if it is chordal, null otherwise.