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.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private java.util.Set<java.util.Set<V>> atoms
      The atoms generated by the decomposition
      private UndirectedGraph<V,​E> chordalGraph
      Minimal triangulation of graph
      private java.util.Set<E> fillEdges
      Fill edges
      private java.util.Map<java.util.Set<V>,​java.lang.Integer> fullComponentCount
      Map for each separator how many components it produces.
      private java.util.List<V> generators
      List of all vertices that generate a minimal separator of chordGraph
      private UndirectedGraph<V,​E> graph
      Source graph to operate on
      private java.util.LinkedList<V> meo
      Minimal elimination ordering on the vertices of graph
      private java.util.Set<java.util.Set<V>> separators
      Set of clique minimal separators
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void addToReach​(java.lang.Integer k, V v, java.util.HashMap<java.lang.Integer,​java.util.HashSet<V>> r)
      Add a vertex to reach.
      private void computeAtoms()
      Compute the unique decomposition of the input graph G (atoms of G).
      private void computeMinimalTriangulation()
      Compute the minimal triangulation of the graph.
      private static <V,​E>
      UndirectedGraph<V,​E>
      copyAsSimpleGraph​(UndirectedGraph<V,​E> graph)
      Create a copy of a graph for internal use.
      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.
      UndirectedGraph<V,​E> getGraph()
      Get the original graph.
      private V getMaxLabelVertex​(java.util.Map<V,​java.lang.Integer> vertexLabels)
      Get the vertex with the maximal label.
      java.util.LinkedList<V> getMeo()
      Get the minimal elimination ordering produced by the triangulation.
      UndirectedGraph<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.
      private static <V,​E>
      boolean
      isClique​(UndirectedGraph<V,​E> graph, java.util.Set<V> vertices)
      Check whether the subgraph of graph induced by the given vertices is complete, i.e.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • chordalGraph

        private UndirectedGraph<V,​E> chordalGraph
        Minimal triangulation of graph
      • fillEdges

        private java.util.Set<E> fillEdges
        Fill edges
      • meo

        private java.util.LinkedList<V> meo
        Minimal elimination ordering on the vertices of graph
      • generators

        private java.util.List<V> generators
        List of all vertices that generate a minimal separator of chordGraph
      • separators

        private java.util.Set<java.util.Set<V>> separators
        Set of clique minimal separators
      • atoms

        private java.util.Set<java.util.Set<V>> atoms
        The atoms generated by the decomposition
      • fullComponentCount

        private java.util.Map<java.util.Set<V>,​java.lang.Integer> fullComponentCount
        Map for each separator how many components it produces.
    • Constructor Detail

      • CliqueMinimalSeparatorDecomposition

        public CliqueMinimalSeparatorDecomposition​(UndirectedGraph<V,​E> g)
        Setup a clique minimal separator decomposition on undirected graph g. Loops and multiple edges are removed, i.e. the graph is transformed to a simple graph.
        Parameters:
        g - The graph to decompose.
    • Method Detail

      • computeMinimalTriangulation

        private void computeMinimalTriangulation()
        Compute the minimal triangulation of the graph. Implementation of Algorithm MCS-M+ as described in Berry et al. (2010), DOI:10.3390/a3020197 http://www.mdpi.com/1999-4893/3/2/197
      • getMaxLabelVertex

        private V getMaxLabelVertex​(java.util.Map<V,​java.lang.Integer> vertexLabels)
        Get the vertex with the maximal label.
        Parameters:
        vertexLabels - Map that gives a label for each vertex.
        Returns:
        Vertex with the maximal label.
      • addToReach

        private void addToReach​(java.lang.Integer k,
                                V v,
                                java.util.HashMap<java.lang.Integer,​java.util.HashSet<V>> r)
        Add a vertex to reach.
        Parameters:
        k - vertex' label
        v - the vertex
        r - the reach structure.
      • computeAtoms

        private void computeAtoms()
        Compute the unique decomposition of the input graph G (atoms of G). Implementation of algorithm Atoms as described in Berry et al. (2010), DOI:10.3390/a3020197, http://www.mdpi.com/1999-4893/3/2/197
      • isClique

        private static <V,​E> boolean isClique​(UndirectedGraph<V,​E> graph,
                                                    java.util.Set<V> vertices)
        Check whether the subgraph of graph induced by the given vertices is complete, i.e. a clique.
        Parameters:
        graph - the graph.
        vertices - the vertices to induce the subgraph from.
        Returns:
        true if the induced subgraph is a clique.
      • copyAsSimpleGraph

        private static <V,​E> UndirectedGraph<V,​E> copyAsSimpleGraph​(UndirectedGraph<V,​E> graph)
        Create a copy of a graph for internal use.
        Parameters:
        graph - the graph to copy.
        Returns:
        A copy of the graph projected to a SimpleGraph.
      • 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 UndirectedGraph<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 UndirectedGraph<V,​E> getGraph()
        Get the original graph.
        Returns:
        Original graph.