Module org.jgrapht.core
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
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
FieldsModifier and TypeFieldDescriptionThe atoms generated by the decompositionMinimal triangulation of graphFill edgesMap for each separator how many components it produces.List of all vertices that generate a minimal separator ofchordGraph
Source graph to operate onprivate LinkedList
<V> Minimal elimination ordering on the vertices of graphSet of clique minimal separators -
Constructor Summary
ConstructorsConstructorDescriptionSetup a clique minimal separator decomposition on undirected graphg
. -
Method Summary
Modifier and TypeMethodDescriptionprivate void
Add a vertex to reach.private void
Compute the unique decomposition of the input graph $G$ (atoms of $G$).private void
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.getAtoms()
Get the atoms generated by the decomposition.Get the fill edges generated by the triangulation.Get a map to know for each separator how many components it produces.Get the generators of the separators of the triangulated graph, i.e.getGraph()
Get the original graph.private V
getMaxLabelVertex
(Map<V, Integer> vertexLabels) Get the vertex with the maximal label.getMeo()
Get the minimal elimination ordering produced by the triangulation.Get the minimal triangulation of the graph.Get the clique minimal separators.boolean
Check if the graph is chordal.private static <V,
E> boolean Check whether the subgraph ofgraph
induced by the givenvertices
is complete, i.e.
-
Field Details
-
graph
Source graph to operate on -
chordalGraph
Minimal triangulation of graph -
fillEdges
Fill edges -
meo
Minimal elimination ordering on the vertices of graph -
generators
List of all vertices that generate a minimal separator ofchordGraph
-
separators
Set of clique minimal separators -
atoms
The atoms generated by the decomposition -
fullComponentCount
Map for each separator how many components it produces.
-
-
Constructor Details
-
CliqueMinimalSeparatorDecomposition
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 Details
-
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
Get the vertex with the maximal label.- Parameters:
vertexLabels
- Map that gives a label for each vertex.- Returns:
- Vertex with the maximal label.
-
addToReach
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
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
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
Get the fill edges generated by the triangulation.- Returns:
- Set of fill edges.
-
getMinimalTriangulation
Get the minimal triangulation of the graph.- Returns:
- Triangulated graph.
-
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
Get a map to know for each separator how many components it produces.- Returns:
- A map from separators to integers (component count).
-
getAtoms
Get the atoms generated by the decomposition.- Returns:
- Set of atoms, where each atom is described as the set of its vertices.
-
getSeparators
Get the clique minimal separators.- Returns:
- Set of separators, where each separator is described as the set of its vertices.
-
getGraph
Get the original graph.- Returns:
- Original graph.
-