All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | List of all members
NetworKit::HavelHakimiGenerator Class Reference

Havel-Hakimi algorithm for generating a graph according to a given degree sequence. More...

#include <HavelHakimiGenerator.h>

Public Member Functions

 HavelHakimiGenerator (const std::vector< count > &sequence, bool ignoreIfRealizable=false)
Graph generate () override
 Generates degree sequence seq (if it is realizable). More...
- Public Member Functions inherited from NetworKit::StaticDegreeSequenceGenerator
 StaticDegreeSequenceGenerator (const std::vector< count > &sequence)
virtual bool isRealizable ()
 Erdoes-Gallai test if degree sequence seq is realizable. More...
virtual bool getRealizable () const
- Public Member Functions inherited from NetworKit::StaticGraphGenerator
virtual ~StaticGraphGenerator ()=default
 Default destructor. More...

Additional Inherited Members

- Protected Attributes inherited from NetworKit::StaticDegreeSequenceGenerator
std::vector< countseq
short realizable

Detailed Description

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.

Constructor & Destructor Documentation

NetworKit::HavelHakimiGenerator::HavelHakimiGenerator ( const std::vector< count > &  sequence,
bool  ignoreIfRealizable = false 
[in]sequenceDegree sequence to realize. Must be non-increasing.
[in]ignoreIfRealizableIf true, generate the graph even if the degree sequence is not realizable. Some nodes may get lower degrees than requested in the sequence.

Member Function Documentation

Graph NetworKit::HavelHakimiGenerator::generate ( )

Generates degree sequence seq (if it is realizable).

std::runtime_errorIf 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.

Implements NetworKit::StaticDegreeSequenceGenerator.

The documentation for this class was generated from the following files: