Package org.graph4j.realization

Class KleitmanWangDigraphRealization

java.lang.Object

org.graph4j.realization.KleitmanWangDigraphRealization

All Implemented Interfaces:

DigraphRealizationAlgorithm

public class KleitmanWangDigraphRealization
extends Object
implements DigraphRealizationAlgorithm

This class provides a method to generate a directed graph from a given sequence of in-degrees and out-degrees, using the Kleitman-Wang algorithm. The time complexity is O(n^2 log n), where n is the number of vertices.

Author:

Cristian Frăsinaru

Constructor Summary

Constructors

Constructor	Description
KleitmanWangDigraphRealization(int[] indegrees, int[] outdegrees)	Creates an algorithm for the digraph realization problem.

Method Summary

Modifier and Type	Method	Description
Digraph	getDigraph()	Creates a directed graph with the specified in-degrees and out-degrees.
boolean	isDigraphic()	Checks if the degree sequence is digraphic.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

KleitmanWangDigraphRealization

public KleitmanWangDigraphRealization(int[] indegrees,
 int[] outdegrees)

Creates an algorithm for the digraph realization problem.

Parameters:

indegrees - the in-degrees of the vertices.

outdegrees - the out-degrees of the vertices.

Method Details

isDigraphic

public boolean isDigraphic()

Description copied from interface: DigraphRealizationAlgorithm

Checks if the degree sequence is digraphic.

Specified by:

isDigraphic in interface DigraphRealizationAlgorithm

Returns:

true if the sequence is digraphic, false otherwise.

getDigraph

public Digraph getDigraph()

Description copied from interface: DigraphRealizationAlgorithm

Creates a directed graph with the specified in-degrees and out-degrees.

Specified by:

getDigraph in interface DigraphRealizationAlgorithm

Returns:

a digraph with the specified degree sequence.