Package org.graph4j.realization

Interface GraphRealizationAlgorithm

All Known Implementing Classes:
HavelHakimiGraphRealization
public interface GraphRealizationAlgorithm
The graph realization problem is to determine whether a given degree sequence can be represented by a simple, undirected graph. A degree sequence is a list of non-negative integers representing the degrees of the vertices in a graph. Such a sequence is called "graphic".
Author:
Cristian Frăsinaru

  • Method Summary

    Modifier and Type
    Method
    Description
    static boolean
    checkErdosGallaiCondition(int[] degreeSequence)
    An alternative method to check if a degree sequence is graphic, using the Erdos-Gallai theorem.
    Graph
    getGraph()
    Creates a graph with the specified degree sequence.
    static GraphRealizationAlgorithm
    getInstance(int[] degreeSequence)
    Returns the default implementation of the algorithm.
    boolean
    isGraphic()
    Checks if the degree sequence is graphic.

  • Method Details

    • getGraph

      Graph getGraph()
      Creates a graph with the specified degree sequence. The vertices of the graph are numbered from 0 to n - 1, where n is the length of the sequence.
      Returns:
      a graph with the specified degree sequence.
      Throws:
      IllegalArgumentException - if the sequence is not graphic.

    • isGraphic

      boolean isGraphic()
      Checks if the degree sequence is graphic.
      Returns:
      true if the sequence is graphic, false otherwise.

    • checkErdosGallaiCondition

      static boolean checkErdosGallaiCondition(int[] degreeSequence)
      An alternative method to check if a degree sequence is graphic, using the Erdos-Gallai theorem.
      Parameters:
      degreeSequence - a degree sequence.
      Returns:
      true if the sequence is graphic, false otherwise.

    • getInstance

      static GraphRealizationAlgorithm getInstance(int[] degreeSequence)
      Returns the default implementation of the algorithm.
      Parameters:
      degreeSequence - a degree sequence.
      Returns:
      the default implementation of the algorithm.