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 
)
Parameters
[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 ( )
overridevirtual

Generates degree sequence seq (if it is realizable).

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

Implements NetworKit::StaticDegreeSequenceGenerator.


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