org.jgrapht.alg

## Class CliqueMinimalSeparatorDecomposition<V,E>

• Type Parameters:
`V` - the graph vertex type
`E` - the graph edge type

```public class CliqueMinimalSeparatorDecomposition<V,E>
extends Object```
Clique Minimal Separator Decomposition using MCS-M+ and Atoms algorithm as described in Berry et al. An Introduction to Clique Minimal Separator Decomposition (2010), DOI:10.3390/a3020197, http://www.mdpi.com/1999-4893/3/2/197

The Clique Minimal Separator (CMS) Decomposition is a procedure that splits a graph into a set of subgraphs separated by minimal clique separators, adding the separating clique to each component produced by the separation. At the end we have a set of atoms. The CMS decomposition is unique and yields the set of the atoms independent of the order of the decomposition.

Author:
Florian Buenzli (fbuenzli@student.ethz.ch), Thomas Tschager (thomas.tschager@inf.ethz.ch), Tomas Hruz (tomas.hruz@inf.ethz.ch), Philipp Hoppen
• ### Constructor Summary

Constructors
Constructor and Description
`CliqueMinimalSeparatorDecomposition(UndirectedGraph<V,E> g)`
Setup a clique minimal separator decomposition on undirected graph ``` g```.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`Set<Set<V>>` `getAtoms()`
Get the atoms generated by the decomposition.
`Set<E>` `getFillEdges()`
Get the fill edges generated by the triangulation.
`Map<Set<V>,Integer>` `getFullComponentCount()`
Get a map to know for each separator how many components it produces.
`List<V>` `getGenerators()`
Get the generators of the separators of the triangulated graph, i.e.
`UndirectedGraph<V,E>` `getGraph()`
Get the original graph.
`LinkedList<V>` `getMeo()`
Get the minimal elimination ordering produced by the triangulation.
`UndirectedGraph<V,E>` `getMinimalTriangulation()`
Get the minimal triangulation of the graph.
`Set<Set<V>>` `getSeparators()`
Get the clique minimal separators.
`boolean` `isChordal()`
Check if the graph is chordal.
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### CliqueMinimalSeparatorDecomposition

`public CliqueMinimalSeparatorDecomposition(UndirectedGraph<V,E> g)`
Setup a clique minimal separator decomposition on undirected graph ``` g```. Loops and multiple edges are removed, i.e. the graph is transformed to a simple graph.
Parameters:
`g` - The graph to decompose.
• ### Method Detail

• #### isChordal

`public boolean isChordal()`
Check if the graph is chordal.
Returns:
true if the graph is chordal, false otherwise.
• #### getFillEdges

`public Set<E> getFillEdges()`
Get the fill edges generated by the triangulation.
Returns:
Set of fill edges.
• #### getMinimalTriangulation

`public UndirectedGraph<V,E> getMinimalTriangulation()`
Get the minimal triangulation of the graph.
Returns:
Triangulated graph.
• #### getGenerators

`public List<V> getGenerators()`
Get the generators of the separators of the triangulated graph, i.e. all vertices that generate a minimal separator of triangulated graph.
Returns:
List of generators.
• #### getMeo

`public LinkedList<V> getMeo()`
Get the minimal elimination ordering produced by the triangulation.
Returns:
The minimal elimination ordering.
• #### getFullComponentCount

`public Map<Set<V>,Integer> getFullComponentCount()`
Get a map to know for each separator how many components it produces.
Returns:
A map from separators to integers (component count).
• #### getAtoms

`public Set<Set<V>> getAtoms()`
Get the atoms generated by the decomposition.
Returns:
Set of atoms, where each atom is described as the set of its vertices.
• #### getSeparators

`public Set<Set<V>> getSeparators()`
Get the clique minimal separators.
Returns:
Set of separators, where each separator is described as the set of its vertices.
• #### getGraph

`public UndirectedGraph<V,E> getGraph()`
Get the original graph.
Returns:
Original graph.