Defined in File ErdosRenyiEnumerator.hpp
Generates a stream of edges of a G(n,p) graph. The edges are not written to memory, but emitted only via usual forEdges semantics to a callback.
Use ErdosRenyiGenerator as a wrapper to output a graph.
The enumerator implements both floating point and fixed point arithmetic, to compute the edges which can be selected via the template parameter UseFixedPoint. It defaults to true, as this algorithm is typically 2 to 3 times faster. In theory, floating point arithmetic allows for longer runs of consecutive edges not selected. As those events virtually never occur, there are no measurable implications of using the faster variant.
Public Functions
Generates a G(n, p) graph for n > 1 and 0 < p < 1.
For an directed graph, the resulting edge stream is equivalent to throwing a coin for each node pair (u, v) and accepting it with probability prob; i.e. the stream may include self-loops. Hence the expected number of edges is n*n*prob.
For an undirected graph, all node pairs (u, v) with 1 < v < u < n are considered. Hence the expected number of edges is n*(n-1)/2*prob
n – Number of nodes to generate
prob – Probability that an edge exists
directed – Selects an directed graph
Generates an Erdos-Renyi-Graph as specified in the constructor on the fly. The stream is generated in parallel on as many core as an OpenMP parallel section is allotted to. For each edge the callback handle is invoked. Two signatures are supported for callback:
(unsigned tid, node u, node v) (node u, node v)
where tid is the current thread id as returned by omp_get_thread_num() and u and v are the edge’s nodes. In case of an undirected graph u > v.
It is guaranteed that no two threads emit edges for the same u.
It can be expected that all threads emit a similar number of edges.
Returns number of edges produced.
Similarly to forEdgesParallel but computed on one thread only. If the callback accepts three arguments tid is always 0.