Graph generator for generating a random simple graph with exactly the given degree sequence based on the EdgeSwitching MarkovChain 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 () 
ErdoesGallai 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< count >  seq 
short  realizable 
Graph generator for generating a random simple graph with exactly the given degree sequence based on the EdgeSwitching MarkovChain 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://wwwrp.lip6.fr/~latapy/FV/generation.html, however without preserving connectivity (this could later be added as optional feature).
The HavelHakami generator is used for the initial graph generation, then the MarkovChain MonteCarlo 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).
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.
sequence  The wanted degree sequence. 
ignoreIfRealizable  Ignore if the sequence is realizable and generate a graph anyway. 

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).
std::runtime_error  If the sequence cannot be generated and ignoreIfRealizable is false. 
Implements NetworKit::StaticDegreeSequenceGenerator.