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

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.