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

Graph generator for generating a random simple graph with exactly the given degree sequence based on the Edge-Switching Markov-Chain method. More...

#include <EdgeSwitchingMarkovChainGenerator.h>

Public Member Functions

 EdgeSwitchingMarkovChainGenerator (const std::vector< NetworKit::count > &sequence, bool ignoreIfRealizable=false)
 Initializes the configuration model generator with the given degree sequence sequence. More...
 
virtual Graph generate () override
 Generate a graph according to the configuration model. 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

Graph generator for generating a random simple graph with exactly the given degree sequence based on the Edge-Switching Markov-Chain method.

This implementation is based on the paper "Random generation of large connected simple graphs with prescribed degree distribution" by Fabien Viger and Matthieu Latapy, available at http://www-rp.lip6.fr/~latapy/FV/generation.html, however without preserving connectivity (this could later be added as optional feature).

The Havel-Hakami generator is used for the initial graph generation, then the Markov-Chain Monte-Carlo algorithm as described and implemented by Fabien Viger and Matthieu Latapy but without the steps for ensuring connectivity is executed. This should lead to a graph that is drawn uniformly at random from all graphs with the given degree sequence.

Note that at most 10 times the number of edges edge swaps are performed (same number as in the abovementioned implementation) and in order to limit the running time, at most 200 times as many attempts to perform an edge swap are made (as certain degree distributions do not allow edge swaps at all).

Constructor & Destructor Documentation

NetworKit::EdgeSwitchingMarkovChainGenerator::EdgeSwitchingMarkovChainGenerator ( const std::vector< NetworKit::count > &  sequence,
bool  ignoreIfRealizable = false 
)

Initializes the configuration model generator with the given degree sequence sequence.

If the sequence cannot be realized, optionally if ignoreIfRealizable is true, a graph with a different degree sequence is generated where certain nodes might not have their full degree.

Parameters
sequenceThe wanted degree sequence.
ignoreIfRealizableIgnore if the sequence is realizable and generate a graph anyway.

Member Function Documentation

NetworKit::Graph NetworKit::EdgeSwitchingMarkovChainGenerator::generate ( )
overridevirtual

Generate a graph according to the configuration model.

Issues a INFO log message if the wanted number of edge swaps cannot be performed because of the limit of attempts (see in the description of the class for details).

Exceptions
std::runtime_errorIf the sequence cannot be generated and ignoreIfRealizable is false.
Returns
The generated graph

Implements NetworKit::StaticDegreeSequenceGenerator.


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