Class CliqueMinimalSeparatorDecomposition<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type

    public class CliqueMinimalSeparatorDecomposition<V,​E>
    extends 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 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 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 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 LinkedList<V> getMeo()
        Get the minimal elimination ordering produced by the triangulation.
        Returns:
        The minimal elimination ordering.
      • getFullComponentCount

        public Map<Set<V>,​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 Set<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 Set<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.