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,

    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.

    Florian Buenzli (, Thomas Tschager (, Tomas Hruz (, 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.
        g - The graph to decompose.
    • Method Detail

      • isChordal

        public boolean isChordal()
        Check if the graph is chordal.
        true if the graph is chordal, false otherwise.
      • getFillEdges

        public Set<E> getFillEdges()
        Get the fill edges generated by the triangulation.
        Set of fill edges.
      • getMinimalTriangulation

        public Graph<V,​E> getMinimalTriangulation()
        Get the minimal triangulation of the graph.
        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.
        List of generators.
      • getMeo

        public LinkedList<V> getMeo()
        Get the minimal elimination ordering produced by the triangulation.
        The minimal elimination ordering.
      • getFullComponentCount

        public Map<Set<V>,​Integer> getFullComponentCount()
        Get a map to know for each separator how many components it produces.
        A map from separators to integers (component count).
      • getAtoms

        public Set<Set<V>> getAtoms()
        Get the atoms generated by the decomposition.
        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.
        Set of separators, where each separator is described as the set of its vertices.
      • getGraph

        public Graph<V,​E> getGraph()
        Get the original graph.
        Original graph.