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 java.lang.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.

Field Summary

Fields
Modifier and Type	Field	Description
`private java.util.Set<java.util.Set<V>>`	`atoms`	The atoms generated by the decomposition
`private Graph<V,E>`	`chordalGraph`	Minimal triangulation of graph
`private java.util.Set<E>`	`fillEdges`	Fill edges
`private java.util.Map<java.util.Set<V>,java.lang.Integer>`	`fullComponentCount`	Map for each separator how many components it produces.
`private java.util.List<V>`	`generators`	List of all vertices that generate a minimal separator of `chordGraph`
`private Graph<V,E>`	`graph`	Source graph to operate on
`private java.util.LinkedList<V>`	`meo`	Minimal elimination ordering on the vertices of graph
`private java.util.Set<java.util.Set<V>>`	`separators`	Set of clique minimal separators

Constructor Summary

Constructors
Constructor Description

CliqueMinimalSeparatorDecomposition(Graph<V,E> g)
Setup a clique minimal separator decomposition on undirected graph g.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`private void`	`addToReach(java.lang.Integer k, V v, java.util.HashMap<java.lang.Integer,java.util.HashSet<V>> r)`	Add a vertex to reach.
`private void`	`computeAtoms()`	Compute the unique decomposition of the input graph $G$ (atoms of $G$).
`private void`	`computeMinimalTriangulation()`	Compute the minimal triangulation of the graph.
`private static <V,E> Graph<V,E>`	`copyAsSimpleGraph(Graph<V,E> graph)`	Create a copy of a graph for internal use.
`java.util.Set<java.util.Set<V>>`	`getAtoms()`	Get the atoms generated by the decomposition.
`java.util.Set<E>`	`getFillEdges()`	Get the fill edges generated by the triangulation.
`java.util.Map<java.util.Set<V>,java.lang.Integer>`	`getFullComponentCount()`	Get a map to know for each separator how many components it produces.
`java.util.List<V>`	`getGenerators()`	Get the generators of the separators of the triangulated graph, i.e.
`Graph<V,E>`	`getGraph()`	Get the original graph.
`private V`	`getMaxLabelVertex(java.util.Map<V,java.lang.Integer> vertexLabels)`	Get the vertex with the maximal label.
`java.util.LinkedList<V>`	`getMeo()`	Get the minimal elimination ordering produced by the triangulation.
`Graph<V,E>`	`getMinimalTriangulation()`	Get the minimal triangulation of the graph.
`java.util.Set<java.util.Set<V>>`	`getSeparators()`	Get the clique minimal separators.
`boolean`	`isChordal()`	Check if the graph is chordal.
`private static <V,E> boolean`	`isClique(Graph<V,E> graph, java.util.Set<V> vertices)`	Check whether the subgraph of `graph` induced by the given `vertices` is complete, i.e.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - graph
```
private Graph<V,E> graph
```
    Source graph to operate on
  - chordalGraph
```
private Graph<V,E> chordalGraph
```
    Minimal triangulation of graph
  - fillEdges
```
private java.util.Set<E> fillEdges
```
    Fill edges
  - meo
```
private java.util.LinkedList<V> meo
```
    Minimal elimination ordering on the vertices of graph
  - generators
```
private java.util.List<V> generators
```
    List of all vertices that generate a minimal separator of chordGraph
  - separators
```
private java.util.Set<java.util.Set<V>> separators
```
    Set of clique minimal separators
  - atoms
```
private java.util.Set<java.util.Set<V>> atoms
```
    The atoms generated by the decomposition
  - fullComponentCount
```
private java.util.Map<java.util.Set<V>,java.lang.Integer> fullComponentCount
```
    Map for each separator how many components it produces.
- 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
  - computeMinimalTriangulation
```
private void computeMinimalTriangulation()
```
    Compute the minimal triangulation of the graph. Implementation of Algorithm MCS-M+ as described in Berry et al. (2010), DOI:10.3390/a3020197 http://www.mdpi.com/1999-4893/3/2/197
  - getMaxLabelVertex
```
private V getMaxLabelVertex(java.util.Map<V,java.lang.Integer> vertexLabels)
```
    Get the vertex with the maximal label.
    
    Parameters:
    
    vertexLabels - Map that gives a label for each vertex.
    
    Returns:
    
    Vertex with the maximal label.
  - addToReach
```
private void addToReach(java.lang.Integer k,
                        V v,
                        java.util.HashMap<java.lang.Integer,java.util.HashSet<V>> r)
```
    Add a vertex to reach.
    
    Parameters:
    
    k - vertex' label
    
    v - the vertex
    
    r - the reach structure.
  - computeAtoms
```
private void computeAtoms()
```
    Compute the unique decomposition of the input graph $G$ (atoms of $G$). Implementation of algorithm Atoms as described in Berry et al. (2010), DOI:10.3390/a3020197, http://www.mdpi.com/1999-4893/3/2/197
  - isClique
```
private static <V,E> boolean isClique(Graph<V,E> graph,
                                            java.util.Set<V> vertices)
```
    Check whether the subgraph of graph induced by the given vertices is complete, i.e. a clique.
    
    Parameters:
    
    graph - the graph.
    
    vertices - the vertices to induce the subgraph from.
    
    Returns:
    
    true if the induced subgraph is a clique.
  - copyAsSimpleGraph
```
private static <V,E> Graph<V,E> copyAsSimpleGraph(Graph<V,E> graph)
```
    Create a copy of a graph for internal use.
    
    Parameters:
    
    graph - the graph to copy.
    
    Returns:
    
    A copy of the graph projected to a SimpleGraph.
  - isChordal
```
public boolean isChordal()
```
    Check if the graph is chordal.
    
    Returns:
    
    true if the graph is chordal, false otherwise.
  - getFillEdges
```
public java.util.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 java.util.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 java.util.LinkedList<V> getMeo()
```
    Get the minimal elimination ordering produced by the triangulation.
    
    Returns:
    
    The minimal elimination ordering.
  - getFullComponentCount
```
public java.util.Map<java.util.Set<V>,java.lang.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 java.util.Set<java.util.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 java.util.Set<java.util.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.

Class CliqueMinimalSeparatorDecomposition<V,​E>

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

graph

chordalGraph

fillEdges

meo

generators

separators

atoms

fullComponentCount

Constructor Detail

CliqueMinimalSeparatorDecomposition

Method Detail

computeMinimalTriangulation

getMaxLabelVertex

addToReach

computeAtoms

isClique

copyAsSimpleGraph

isChordal

getFillEdges

getMinimalTriangulation

getGenerators

getMeo

getFullComponentCount

getAtoms

getSeparators

getGraph

Class CliqueMinimalSeparatorDecomposition<V,E>