Class 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
    • 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.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • 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

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