Safe Haskell | None |
---|---|

Language | Haskell2010 |

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.

- barabasiAlbertGraph :: GenIO -> Int -> Int -> IO GraphInfo
- barabasiAlbertGraph' :: Int -> Int -> IO GraphInfo
- selectNth :: Int -> [(Int, Int)] -> Int
- selectRandomElement :: GenIO -> (IntMultiSet, Int) -> IO Int
- selectNDistinctRandomElements :: GenIO -> Int -> (IntMultiSet, Int) -> IO [Int]

## Graph generators

:: 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()

:: 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

selectRandomElement :: GenIO -> (IntMultiSet, Int) -> IO Int Source #

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

selectNDistinctRandomElements :: GenIO -> Int -> (IntMultiSet, Int) -> IO [Int] Source #

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