Package org.graph4j.realization

Interface BipartiteRealizationAlgorithm

All Known Implementing Classes:
HavelHakimiBipartiteRealization
public interface BipartiteRealizationAlgorithm
The bipartite graph realization problem is to determine whether there exists a bipartite graph having a specified sequence of degrees for vertices in each partition set.
Author:
Cristian Frăsinaru
See Also:

  • Method Summary

    Modifier and Type
    Method
    Description
    static boolean
    checkGaleRyserCondition(int[] leftDegrees, int[] rightDegrees)
    Checks if the degree sequence is valid, using the Gale–Ryser theorem.
    Graph
    getGraph()
    Creates a bipartite graph with the specified degree sequence.
    static BipartiteRealizationAlgorithm
    getInstance(int[] leftDegrees, int[] rightDegrees)
    Returns the default implementation of the algorithm.
    boolean
    isBigraphic()
    Checks if the degree sequence is valid (bigraphic).

  • Method Details

    • getGraph

      Graph getGraph()
      Creates a bipartite graph with the specified degree sequence.
      Returns:
      a bipartite graph with the specified degree sequence.
      Throws:
      IllegalArgumentException - if the sequence is not valid (bigraphic).

    • isBigraphic

      boolean isBigraphic()
      Checks if the degree sequence is valid (bigraphic).
      Returns:
      true if the sequence is bigraphic, false otherwise.

    • checkGaleRyserCondition

      static boolean checkGaleRyserCondition(int[] leftDegrees, int[] rightDegrees)
      Checks if the degree sequence is valid, using the Gale–Ryser theorem.
      Parameters:
      leftDegrees - the degrees of the vertices on the left side.
      rightDegrees - the degrees of the vertices on the left side.
      Returns:
      true if the sequence is digraphic, false otherwise.

    • getInstance

      static BipartiteRealizationAlgorithm getInstance(int[] leftDegrees, int[] rightDegrees)
      Returns the default implementation of the algorithm.
      Parameters:
      leftDegrees - the degrees of the vertices on the left side.
      rightDegrees - the degrees of the vertices on the right side.
      Returns:
      the default implementation of the algorithm.