Package org.jgrapht.alg.clique

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.