Class HavelHakimiGenerator

Inheritance Relationships

Base Type

Class Documentation

class HavelHakimiGenerator : public NetworKit::StaticDegreeSequenceGenerator

Havel-Hakimi algorithm for generating a graph according to a given degree sequence. The sequence, if it is realizable, is reconstructed exactly. The resulting graph usually has a high clustering coefficient. Construction runs in linear time O(m). However, the test if a sequence is realizable is quadratic in the sequence length.

Public Functions

HavelHakimiGenerator(const std::vector<count> &sequence, bool ignoreIfRealizable = false)
  • sequence[in] Degree sequence to realize. Must be non-increasing.

  • ignoreIfRealizable[in] If true, generate the graph even if the degree sequence is not realizable. Some nodes may get lower degrees than requested in the sequence.

virtual Graph generate() override

Generates degree sequence seq (if it is realizable).


std::runtime_error – If the sequence is not realizable and ignoreIfRealizable is false.


Graph with degree sequence seq or modified sequence if ignoreIfRealizable is true and the sequence is not realizable.