graph-generators-0.1.4.0: Functions for generating structured or random FGL graphs

Data.Graph.Generators.Random.ErdosRenyi

Description

Implementations of binomially random graphs, as described by Erdős and Rényi.

Graphs generated using this method have a constant edge probability between two nodes.

See Erdős and A. Rényi, On Random Graphs, Publ. Math. 6, 290 (1959).

Synopsis

## Graph generators

Arguments

 :: GenIO The random number generator to use -> Int The number of nodes -> Double The probability for any pair of nodes to be connected -> IO GraphInfo The resulting graph (IO required for randomness)

Generate a unlabelled directed random graph using the Algorithm introduced by Erdős and Rényi, also called a binomial random graph generator.

Note that self-loops with also be generated with probability p.

This algorithm runs in O(n²) and is best suited for non-sparse networks.

The generated nodes are identified by [0..n-1].

Example usage, using a truly random generator:

import System.Random.MWC


## Utility functions

Arguments

 :: GenIO The random generator state -> Double The probability to select each list element -> [a] The list to filter -> IO [a] The filtered list

Filter a list by selecting each list element uniformly with a given probability p

Although this is mainly used internally, it can be used as general utility function