Package org.jgrapht.alg
Class CliqueMinimalSeparatorDecomposition<V,E>
- java.lang.Object
-
- org.jgrapht.alg.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.
-
-
Field Summary
Fields Modifier and Type Field Description private java.util.Set<java.util.Set<V>>
atoms
The atoms generated by the decompositionprivate UndirectedGraph<V,E>
chordalGraph
Minimal triangulation of graphprivate java.util.Set<E>
fillEdges
Fill edgesprivate 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 ofchordGraph
private UndirectedGraph<V,E>
graph
Source graph to operate onprivate java.util.LinkedList<V>
meo
Minimal elimination ordering on the vertices of graphprivate java.util.Set<java.util.Set<V>>
separators
Set of clique minimal separators
-
Constructor Summary
Constructors Constructor Description CliqueMinimalSeparatorDecomposition(UndirectedGraph<V,E> g)
Setup a clique minimal separator decomposition on undirected graphg
.
-
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>
UndirectedGraph<V,E>copyAsSimpleGraph(UndirectedGraph<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.UndirectedGraph<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.UndirectedGraph<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>
booleanisClique(UndirectedGraph<V,E> graph, java.util.Set<V> vertices)
Check whether the subgraph ofgraph
induced by the givenvertices
is complete, i.e.
-
-
-
Field Detail
-
graph
private UndirectedGraph<V,E> graph
Source graph to operate on
-
chordalGraph
private UndirectedGraph<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 ofchordGraph
-
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(UndirectedGraph<V,E> g)
Setup a clique minimal separator decomposition on undirected graphg
. Loops and multiple 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' labelv
- the vertexr
- 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(UndirectedGraph<V,E> graph, java.util.Set<V> vertices)
Check whether the subgraph ofgraph
induced by the givenvertices
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> UndirectedGraph<V,E> copyAsSimpleGraph(UndirectedGraph<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 UndirectedGraph<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 UndirectedGraph<V,E> getGraph()
Get the original graph.- Returns:
- Original graph.
-
-