Package org.graph4j.realization

Class HavelHakimiGraphRealization

java.lang.Object

org.graph4j.realization.HavelHakimiGraphRealization

All Implemented Interfaces:

GraphRealizationAlgorithm

public class HavelHakimiGraphRealization
extends Object
implements GraphRealizationAlgorithm

This class provides a method to generate a graph from a given degree sequence, using the Havel-Hakimi 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
HavelHakimiGraphRealization(int[] degreeSequence)	Creates an algorithm for the graph realization problem.

Method Summary

Modifier and Type	Method	Description
Graph	getGraph()	Creates a graph with the specified degree sequence.
boolean	isGraphic()	Checks if the degree sequence is graphic.

Methods inherited from class java.lang.Object

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

Constructor Details

HavelHakimiGraphRealization

public HavelHakimiGraphRealization(int[] degreeSequence)

Creates an algorithm for the graph realization problem.

Parameters:

degreeSequence - a degree sequence.

Method Details

isGraphic

public boolean isGraphic()

Description copied from interface: GraphRealizationAlgorithm

Checks if the degree sequence is graphic.

Specified by:

isGraphic in interface GraphRealizationAlgorithm

Returns:

true if the sequence is graphic, false otherwise.

getGraph

public Graph getGraph()

Description copied from interface: GraphRealizationAlgorithm

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.

Specified by:

getGraph in interface GraphRealizationAlgorithm

Returns:

a graph with the specified degree sequence.