Package org.jgrapht.alg.clique
Class CliqueMinimalSeparatorDecomposition<V,E>
- java.lang.Object
-
- org.jgrapht.alg.clique.CliqueMinimalSeparatorDecomposition<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- 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/197The 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 Description CliqueMinimalSeparatorDecomposition(Graph<V,E> g)
Setup a clique minimal separator decomposition on undirected graphg
.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description 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.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.
-
-
-
Constructor Detail
-
CliqueMinimalSeparatorDecomposition
public CliqueMinimalSeparatorDecomposition(Graph<V,E> g)
Setup a clique minimal separator decomposition on undirected graphg
. 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 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.
-
-