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

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.