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

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 graph g.

  • Method Summary

    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.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • 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 Details

    • 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.