org.jgrapht.alg.clique

## Class CliqueMinimalSeparatorDecomposition<V,E>

• java.lang.Object
• org.jgrapht.alg.clique.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(Graph<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.
Graph<V,E> getGraph()
Get the original graph.
LinkedList<V> getMeo()
Get the minimal elimination ordering produced by the triangulation.
Graph<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(Graph<V,E> g)
Setup a clique minimal separator decomposition on undirected graph  g. Loops and multiple (parallel) 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 Graph<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 Graph<V,E> getGraph()
Get the original graph.
Returns:
Original graph.