Class HavelHakimiGenerator¶

Inheritance Relationships¶

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)¶

Parameters:

• 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).

Throws:

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

Returns:

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