Module org.jgrapht.core
Package org.jgrapht.alg.clique

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.

Author:
Florian Buenzli (fbuenzli@student.ethz.ch), Thomas Tschager (thomas.tschager@inf.ethz.ch), Tomas Hruz (tomas.hruz@inf.ethz.ch), Philipp Hoppen

  • 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

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