Class CliqueMinimalSeparatorDecomposition<V,E>

java.lang.Object
org.jgrapht.alg.clique.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.

  • Field Details

    • graph

      private Graph<V,E> graph
      Source graph to operate on

    • chordalGraph

      private Graph<V,E> chordalGraph
      Minimal triangulation of graph

    • fillEdges

      private Set<E> fillEdges
      Fill edges

    • meo

      private LinkedList<V> meo
      Minimal elimination ordering on the vertices of graph

    • generators

      private List<V> generators
      List of all vertices that generate a minimal separator of chordGraph

    • separators

      private Set<Set<V>> separators
      Set of clique minimal separators

    • atoms

      private Set<Set<V>> atoms
      The atoms generated by the decomposition

    • fullComponentCount

      private Map<Set<V>,Integer> fullComponentCount
      Map for each separator how many components it produces.

  • Constructor Details

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

    • 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(Map<V,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(Integer k, V v, HashMap<Integer, 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(Graph<V,E> graph, 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> Graph<V,E> copyAsSimpleGraph(Graph<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 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.