Package org.graph4j.realization

Interface DigraphRealizationAlgorithm

All Known Implementing Classes:
KleitmanWangDigraphRealization
public interface DigraphRealizationAlgorithm
The digraph realization problem is to determine whether there exists a directed graph having a specified sequence of in-degrees and out-degrees for each vertex.
Author:
Cristian Frăsinaru
See Also:

  • Method Summary

    Modifier and Type
    Method
    Description
    static boolean
    checkFulkersonChenAnsteeCondition(int[] indegrees, int[] outdegrees)
    Checks if the in-degree, out-degree sequence is digraphic, using the Fulkerson–Chen–Anstee theorem.
    Digraph
    getDigraph()
    Creates a directed graph with the specified in-degrees and out-degrees.
    static DigraphRealizationAlgorithm
    getInstance(int[] indegrees, int[] outdegrees)
    Returns the default implementation of the algorithm.
    boolean
    isDigraphic()
    Checks if the degree sequence is digraphic.

  • Method Details

    • getDigraph

      Digraph getDigraph()
      Creates a directed graph with the specified in-degrees and out-degrees.
      Returns:
      a digraph with the specified degree sequence.
      Throws:
      IllegalArgumentException - if the sequence is not digraphic.

    • isDigraphic

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

    • checkFulkersonChenAnsteeCondition

      static boolean checkFulkersonChenAnsteeCondition(int[] indegrees, int[] outdegrees)
      Checks if the in-degree, out-degree sequence is digraphic, using the Fulkerson–Chen–Anstee theorem.
      Parameters:
      indegrees - the in-degrees of the vertices.
      outdegrees - the out-degrees of the vertices.
      Returns:
      true if the sequence is digraphic, false otherwise.

    • getInstance

      static DigraphRealizationAlgorithm getInstance(int[] indegrees, int[] outdegrees)
      Returns the default implementation of the algorithm.
      Parameters:
      indegrees - the in-degrees of the vertices.
      outdegrees - the out-degrees of the vertices.
      Returns:
      the default implementation of the algorithm.