Package org.graph4j.realization

Class HavelHakimiBipartiteRealization

java.lang.Object

org.graph4j.realization.HavelHakimiBipartiteRealization

All Implemented Interfaces:

BipartiteRealizationAlgorithm

public class HavelHakimiBipartiteRealization
extends Object
implements BipartiteRealizationAlgorithm

This class provides a method to generate a bipartite graph from a given sequence of degrees, using an adaptation of the Havel-Hakimi algorithm. The time complexity is O(n^2 log n), where n is the number of vertices.

Author:

Cristian Frăsinaru

See Also:

• HavelHakimiGraphRealization

Constructor Summary

Constructors

Constructor	Description
HavelHakimiBipartiteRealization(int[] leftDegrees, int[] rightDegrees)	Creates an algorithm for the bipartite realization problem.

Method Summary

Modifier and Type	Method	Description
Graph	getGraph()	Creates a bipartite graph with the specified degree sequence.
boolean	isBigraphic()	Checks if the degree sequence is valid (bigraphic).

Methods inherited from class java.lang.Object

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

Constructor Details

HavelHakimiBipartiteRealization

public HavelHakimiBipartiteRealization(int[] leftDegrees,
 int[] rightDegrees)

Creates an algorithm for the bipartite realization problem.

Parameters:

leftDegrees - the degrees of the vertices on the left side.

rightDegrees - the degrees of the vertices on the right side.

Method Details

isBigraphic

public boolean isBigraphic()

Description copied from interface: BipartiteRealizationAlgorithm

Checks if the degree sequence is valid (bigraphic).

Specified by:

isBigraphic in interface BipartiteRealizationAlgorithm

Returns:

true if the sequence is bigraphic, false otherwise.

getGraph

public Graph getGraph()

Description copied from interface: BipartiteRealizationAlgorithm

Creates a bipartite graph with the specified degree sequence.

Specified by:

getGraph in interface BipartiteRealizationAlgorithm

Returns:

a bipartite graph with the specified degree sequence.