Package org.graph4j.support

Class ChordalGraphSupport

java.lang.Object
org.graph4j.UndirectedGraphAlgorithm
org.graph4j.support.ChordalGraphSupport
public class ChordalGraphSupport extends UndirectedGraphAlgorithm
Support class for chordal graphs. A chordal graph is a graph where every cycle of four or more vertices has a chord. A chord is an edge that connects two non-consecutive vertices within the cycle, but it's not part of the cycle itself. In a chordal graph, all induced cycles must be triangles. A graph which is not chordal must contain a hole, that is an induced cycle on four or more vertices. A graph is chordal if and only if it has a perfect elimination ordering.
Author:
Cristian Frăsinaru
See Also:

  • Constructor Details

    • ChordalGraphSupport

      public ChordalGraphSupport(Graph graph)
      Creates an instance of the support class.
      Parameters:
      graph - the input graph.

  • Method Details

    • isChordal

      public boolean isChordal()
      Determines if the graph is chordal using the property that a graph is chordal if and only if it has a perfect elimination ordering.
      Returns:
      true if the graph is chordal, false otherwise.
      See Also:

    • findPerfectEliminationOrdering

      public int[] findPerfectEliminationOrdering()
      Finds a perfect elimination ordering in a chordal graph.
      Returns:
      a perfect elimination ordering if the graph is chordal, null otherwise;

    • findHole

      public Cycle findHole()
      Finds a hole, that is an induced cycle on four or more vertices, if the graph is not chordal.
      Returns:
      a hole, if the graph is not chordal, null otherwise.

    • getMaximumCliqueSize

      public int getMaximumCliqueSize()
      Determines the maximum clique size of a chordal graph, without computing the maximal cliques.
      Returns:
      the maximum clique size of a chordal graph.
      Throws:
      NotChordalException - if the graph is not chordal.

    • getMaximumClique

      public Clique getMaximumClique()
      Determines a clique of maximum size in a chordal graph.
      Returns:
      a clique of maximum size in a chordal graph.
      Throws:
      NotChordalException - if the graph is not chordal.

    • getMaximalCliques

      public List<Clique> getMaximalCliques()
      Determines all maximal cliques of a chordal graph. A chordal graph can have at most |V| maximal cliques.
      Returns:
      the maximal cliques of a chordal graph.
      Throws:
      NotChordalException - if the graph is not chordal.

    • getMaximumStableSet

      public StableSet getMaximumStableSet()
      Determines a maximum stable set of a chordal graph.
      Returns:
      a maximum stable set of a chordal graph.
      Throws:
      NotChordalException - if the graph is not chordal.

    • getMinimumCliqueCover

      public List<Clique> getMinimumCliqueCover()
      Determines a minimum clique cover of a chordal graph.
      Returns:
      a minimum clique cover of a chordal graph.
      Throws:
      NotChordalException - if the graph is not chordal.

    • getChromaticNumber

      public int getChromaticNumber()
      Determines the chromatic number of a chordal graph, without computing the optimal coloring. Since chordal graphs are perfect, this is equal to the maximum clique number.
      Returns:
      the chromatic number of a chordal graph.
      Throws:
      NotChordalException - if the graph is not chordal.

    • getOptimalColoring

      public Coloring getOptimalColoring()
      Creates an optimal coloring of a chordal graph, using the greedy algorithm with the reversed perfect elimination ordering.
      Returns:
      an optimal coloring of a chordal graph.
      Throws:
      NotChordalException - if the graph is not chordal.

    • getMinimumVertexSeparators

      public Map<Clique,Integer> getMinimumVertexSeparators()
      Determines a map of all minimal vertex separators, together with their multiplicities. The multiplicity of of a minimal vertex separator is the number of different pairs of vertices separated by it. To determine only the set of minimal separators, use Map.keySet(). Note that an undirected graph is chordal if and only every minimal vertex separator of it induces a clique (Dirac). See: Kumar, P. Sreenivasa & Madhavan, C. E. Veni. (1998). Minimal vertex separators of chordal graphs. Discrete Applied Mathematics. 89. 155-168. 10.1016/S0166-218X(98)00123-1.
      Returns:
      the map of all minimal vertex separators, with multiplicities.