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

Data.Graph.Generators.Random.WattsStrogatz

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 n, The number of nodes -> Int k, the size of the neighborhood / degree (should be even) -> Double beta, The probability of a forward edge getting rewritten -> IO GraphInfo The resulting graph (IO required for randomness)

Generate a unlabelled undirected random graph using the Algorithm introduced by WattsStrogatz.

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

This algorithm runs in O(kn).

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