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

Data.Graph.Generators.Random.BarabasiAlbert

Description

Random graph generators using the generator algorithm introduced by A. L. Barabási and R. Albert.

See. A. L. Barabási and R. Albert "Emergence of scaling in random networks", Science 286, pp 509-512, 1999.

Synopsis

Graph generators

Arguments

 :: GenIO The random number generator to use -> Int The overall number of nodes (n) -> Int The number of edges to create between a new and existing nodes (m) -> IO GraphInfo The resulting graph (IO required for randomness)

Generate a random quasi-undirected Barabasi graph.

Only one edge (with nondeterministic direction) is created between a node pair, because adding the other edge direction is easier than removing duplicates.

Precondition (not checked): m <= n

Modeled after NetworkX 1.8.1 barabasi_albert_graph()

Arguments

 :: Int The number of nodes -> Int The number of edges to create between a new and existing nodes (m) -> IO GraphInfo The resulting graph (IO required for randomness)

Like barabasiAlbertGraph, but uses a newly initialized random number generator.

See withSystemRandom for details on how the generator is initialized.

By using this function, you don't have to initialize the generator by yourself, however generator initialization is slow, so reusing the generator is recommended.

Usage example:

barabasiAlbertGraph' 10 5

Utility functions

selectNth :: Int -> [(Int, Int)] -> Int Source #

Select the nth element from a multiset occur list, treating it as virtual large list This is significantly faster than building up the entire list and selecting the nth element

Select a single random element from the multiset, with precalculated size Note that the given size must be the total multiset size, not the number of distinct elements in said se

Select n distinct random elements from a multiset, with This function will fail to terminate if there are less than n distinct elements in the multiset. This function accepts a multiset with precomputed size for performance reasons