-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Functions for generating structured or random FGL graphs -- -- Generators for graphs. Supports classic (constant-sized) graphs, -- deterministic Generators and different random graph generators, based -- on mwc-random. -- -- This library uses a library-agnostic and space-efficient graph -- representation. Combinators are provided to convert said -- representation to other graph representations (currently only FGL, see -- Data.Graph.Generators.FGL) -- -- Note that this library is in its early development stages. Don't use -- it for production code without checking the correctness of the -- algorithm implementation. @package graph-generators @version 0.1.3.0 module Data.Graph.Generators -- | The information required to build a graph. -- -- This datastructure is designed to occupy minimal space. With n being -- the number of nodes, the edge list contains tuples (from, to), -- denoting an edge from node *from* to node *to* where *from* and *to* -- are integers less than the number of nodes. -- -- Note that for a graph with n nodes, the nodes are labelled -- [0..n-1]. -- -- This data structure is library-agnostic and can be converted to -- arbitrary representations. -- -- Copyright (C) 2014 Uli Köhler Apache License v2.0 data GraphInfo GraphInfo :: Int -> [(Int, Int)] -> GraphInfo -- | Number of nodes [numNodes] :: GraphInfo -> Int -- | Edge list [edges] :: GraphInfo -> [(Int, Int)] -- | The context of a single graph node. -- -- This data-structure is library-agnostic, however, it is isomophic to -- FGL's UContext data GraphContext GraphContext :: [Int] -> Int -> [Int] -> GraphContext -- | Nodes having an edge to the current node [inEdges] :: GraphContext -> [Int] -- | The node identifier of the current node [nodeLabel] :: GraphContext -> Int -- | Nodes having an ingoing edge from the current node [outEdges] :: GraphContext -> [Int] -- | Check the integrity of a GraphInfo instance: Ensures for every edge -- (i,j), the following condition is met: 0 <= i < n && -- 0 <= j < n checkGraphInfo :: GraphInfo -> Bool -- | Get the edge count for a given GraphInfo instance numEdges :: GraphInfo -> Int instance GHC.Show.Show Data.Graph.Generators.GraphInfo instance GHC.Classes.Eq Data.Graph.Generators.GraphInfo -- | Generators for classic non-parametric graphs. -- -- Built using NetworkX 1.8.1, see NetworkX Generators -- -- graph-generators copyright: Copyright (C) 2014 Uli Köhler Apache -- License v2.0 -- -- NetworkX copyright: Copyright (C) 2004-2010 by Aric Hagberg -- hagberg@lanl.gov Dan Schult dschult@colgate.edu Pieter -- Swart swart@lanl.gov All rights reserved. BSD license. module Data.Graph.Generators.Classic -- | Generates the trivial graph, containing only one node and no edges trivialGraph :: GraphInfo -- | Generates the Bull graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected -- -- 
--   0       1
--         /
--     2---3
--       /
--       4
--
bullGraph :: GraphInfo -- | Generate the Chvatal graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected. chvatalGraph :: GraphInfo -- | Generate the cubical graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected. cubicalGraph :: GraphInfo -- | Generate the Desargues graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected. desarguesGraph :: GraphInfo -- | Generate the Diamond Graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected. diamondGraph :: GraphInfo -- | Generate the dodecahedral Graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected. dodecahedralGraph :: GraphInfo -- | Generate the Frucht Graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected -- -- See http://mathworld.wolfram.com/FruchtGraph.html fruchtGraph :: GraphInfo -- | Generate the Heawood Graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected. heawoodGraph :: GraphInfo -- | Generate the house graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected -- -- 
--     1
--    / 
--   2---3
--   |   |
--   4---5
--
houseGraph :: GraphInfo -- | Generate the house X graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected -- -- 
--     1
--    / 
--   2---3
--   | X |
--   4---5
--
houseXGraph :: GraphInfo -- | Generate the icosahedral Graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected. icosahedralGraph :: GraphInfo -- | Generate the Krackhardt-Kite Graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected. krackhardtKiteGraph :: GraphInfo -- | Generate the Möbius-Kantor Graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected. moebiusKantorGraph :: GraphInfo -- | Generate the octahedral graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected. octahedralGraph :: GraphInfo -- | Generate the Pappus Graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected. -- -- Nodes are labelled [0..17] pappusGraph :: GraphInfo -- | Generate the Petersen Graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected. petersenGraph :: GraphInfo -- | Generate the Sedgewick Maze Graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected. sedgewickMazeGraph :: GraphInfo -- | Generate the tetrahedral graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected. tetrahedralGraph :: GraphInfo -- | Generate the truncated cube graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected. truncatedCubeGraph :: GraphInfo -- | Generate the truncated tetrahedron graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected. truncatedTetrahedronGraph :: GraphInfo -- | Generate the Tutte graph. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected. tutteGraph :: GraphInfo -- | The null graph with no nodes and edges nullGraph :: GraphInfo -- | Graph generators for simple parametric, regular graphs. -- -- Built using NetworkX 1.8.1, see NetworkX Generators -- -- graph-generators copyright: Copyright (C) 2014 Uli Köhler Apache -- License v2.0 -- -- NetworkX copyright: Copyright (C) 2004-2010 by Aric Hagberg -- hagberg@lanl.gov Dan Schult dschult@colgate.edu Pieter -- Swart swart@lanl.gov All rights reserved. BSD license. module Data.Graph.Generators.Regular -- | Generate a completely connected graph with n nodes. -- -- The generated graph contains node labels [0..n-1] -- -- In contrast to completeGraphWithSelfloops this function does -- not generate self-loops. -- -- Contains only one edge between two connected nodes, use undir -- to make it quasi-undirected. The generated edge (i,j) satisfied i -- < j. -- -- Precondition (not checked): n >= 0 completeGraph :: Int -> GraphInfo -- | Variant of completeGraph generating self-loops. -- -- All generated edges (i,j) satisfy i <= j. -- -- See completeGraph for a more detailed behaviour description. -- -- Precondition (not checked): n >= 0 completeGraphWithSelfloops :: Int -> GraphInfo -- | Generate the complete bipartite graph with n1 nodes in the first -- partition and n2 nodes in the second partition. -- -- Each node in the first partition is connected to each node in the -- second partition. -- -- The first partition nodes are identified by [0..n1-1] while the nodes -- in the second partition are identified by [n1..n1+n2-1] -- -- Use undir to also add edges from the second partition to the -- first partition. -- -- Precondition (not checked): n >= 0 completeBipartiteGraph :: Int -> Int -> GraphInfo -- | Generates the empty graph with n nodes and zero edges. -- -- The nodes are labelled [0..n-1] -- -- Precondition (not checked): n >= 0 emptyGraph :: Int -> GraphInfo -- | Generate the barbell graph, consisting of two complete subgraphs -- connected by a single path. -- -- In contrast to generalizedBarbellGraph, this function always -- generates identically-sized bells. Therefore this is a special case of -- generalizedBarbellGraph -- -- Precondition (not checked): n >= 0 barbellGraph :: Int -> Int -> GraphInfo -- | Generate the barbell graph, consisting of two complete subgraphs -- connected by a single path. -- -- Self-loops are not generated. -- -- The nodes in the first bell are identified by [0..n1-1] The nodes in -- the path are identified by [n1..n1+np-1] The nodes in the second bell -- are identified by [n1+np..n1+np+n2-1] -- -- Precondition (not checked): n >= 0 generalizedBarbellGraph :: Int -> Int -> Int -> GraphInfo -- | Generate the cycle graph of size n. -- -- Edges are created from lower node IDs to higher node IDs. -- -- Precondition (not checked): n >= 0 cycleGraph :: Int -> GraphInfo -- | Generate the path graph of size n, consisting of n nodes that are -- interconnected in a single path. -- -- Precondition (not checked): n >= 0 pathGraph :: Int -> GraphInfo -- | Generate the star graph with n nodes: One central node (ID 0) -- connected to n-1 outer nodes, having no interconnections themselves -- -- Precondition (not checked): n >= 0 starGraph :: Int -> GraphInfo -- | Generate the wheel graph with n nodes: One central node (ID 0) -- connected to n-1 outer nodes building a cycle graph. -- -- Precondition (not checked): n >= 0 wheelGraph :: Int -> GraphInfo -- | Generate the 2D grid graph of dimensions m*n -- -- Algorithm courtesy grid2DGraph :: Int -> Int -> GraphInfo -- | Functions to convert graph-generators GraphInfo to FGL data -- structures. -- -- Copyright (C) 2014 Uli Köhler Apache License v2.0 module Data.Graph.Generators.FGL -- | Convert a graph-generators GraphInfo to a FGL UGr -- (unlabelled) graphInfoToUGr :: GraphInfo -> UGr -- | 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). -- -- graph-generators copyright: Copyright (C) 2014 Uli Köhler -- -- NetworkX copyright: Copyright (C) 2004-2010 by Aric Hagberg -- hagberg@lanl.gov Dan Schult dschult@colgate.edu Pieter -- Swart swart@lanl.gov All rights reserved. BSD license. module Data.Graph.Generators.Random.ErdosRenyi -- | 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
--   gen <- withSystemRandom . asGenIO $ return
--   erdosRenyiGraph 10 0.1
--
-- -- ... -- -- Modelled after NetworkX 1.8.1 erdos_renyi_graph(). erdosRenyiGraph :: GenIO -> Int -> Double -> IO GraphInfo -- | Like erdosRenyiGraph, 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: -- -- 
--   erdosRenyiGraph' 10 0.1
--
erdosRenyiGraph' :: Int -> Double -> IO GraphInfo -- | Generate a unlabelled context using the Erdős and Rényi method. -- -- See erdosRenyiGraph for a detailed algorithm description. -- -- Example usage, using a truly random generator: -- -- 
--   import System.Random.MWC
--   gen <- withSystemRandom . asGenIO $ return
--
erdosRenyiContext :: GenIO -> Int -> [Int] -> Double -> IO GraphContext -- | 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 selectWithProbability :: GenIO -> Double -> [a] -> IO [a] -- | 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). -- -- graph-generators copyright: Copyright (C) 2014 Uli Köhler -- -- NetworkX copyright: Copyright (C) 2004-2010 by Aric Hagberg -- hagberg@lanl.gov Dan Schult dschult@colgate.edu Pieter -- Swart swart@lanl.gov All rights reserved. BSD license. module Data.Graph.Generators.Random.WattsStrogatz -- | 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
--   gen <- withSystemRandom . asGenIO $ return
--   wattsStrogatzGraph gen 1000 10 0.6
--
-- -- ... wattsStrogatzGraph :: GenIO -> Int -> Int -> Double -> IO GraphInfo -- | Like wattsStrogatzGraph, 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: -- -- 
--   wattsStrogatzGraph' 1000 10 0.6
--
wattsStrogatzGraph' :: Int -> Int -> Double -> IO GraphInfo -- | Generate a small-world context using the Wattz Strogatz method. -- -- See wattsStrogatzGraph for a detailed algorithm description. -- -- Example usage, using a truly random generator: -- -- 
--   import System.Random.MWC
--   gen <- withSystemRandom . asGenIO $ return
--
wattsStrogatzContext :: GenIO -> Int -> [Int] -> Double -> IO GraphContext selectWithProbability :: GenIO -> Double -> [a] -> IO [a] -- | 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. module Data.Graph.Generators.Random.BarabasiAlbert -- | 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() barabasiAlbertGraph :: GenIO -> Int -> Int -> IO GraphInfo -- | 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
--
barabasiAlbertGraph' :: Int -> Int -> IO GraphInfo -- | 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 selectNth :: Int -> [(Int, Int)] -> Int -- | 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 selectRandomElement :: GenIO -> (IntMultiSet, Int) -> IO Int -- | 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 selectNDistinctRandomElements :: GenIO -> Int -> (IntMultiSet, Int) -> IO [Int]