Package org.jgrapht.alg.independentset
Class ChordalGraphIndependentSetFinder<V,E>
- 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 theChordalityInspector
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 inspectedgraph
.
-
-
-
Constructor Detail
-
ChordalGraphIndependentSetFinder
public ChordalGraphIndependentSetFinder(Graph<V,E> graph)
Creates a new ChordalGraphIndependentSetFinder instance. TheChordalityInspector
used in this implementation uses the defaultMaximumCardinalityIterator
iterator.- Parameters:
graph
- graph
-
ChordalGraphIndependentSetFinder
public ChordalGraphIndependentSetFinder(Graph<V,E> graph, ChordalityInspector.IterationOrder iterationOrder)
Creates a new ChordalGraphIndependentSetFinder 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 Detail
-
getIndependentSet
public IndependentSetAlgorithm.IndependentSet<V> getIndependentSet()
Returns a maximum cardinality independent set of the inspectedgraph
. If the graph isn't chordal, returns null.- Specified by:
getIndependentSet
in interfaceIndependentSetAlgorithm<V>
- Returns:
- a maximum independent set of the
graph
if it is chordal, null otherwise.
-
-