úÎÖ)Ò“=      !"#$%&'()*+,-./0123456789:;<Safe& #The context of a single graph node.WThis data-structure is library-agnostic, however, it is isomophic to FGL's UContext(Nodes having an edge to the current node'The node identifier of the current node2Nodes having an ingoing edge from the current node*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.5Copyright (C) 2014 Uli Köhler Apache License v2.0Number of nodes Edge list sCheck the integrity of a GraphInfo instance: Ensures for every edge (i,j), the following condition is met: 0 <= i < n && 0 <= j < n 1Get the edge count for a given GraphInfo instance   SafeC. FGenerates the trivial graph, containing only one node and no edgesGenerates the Bull graph.<Contains only one edge between two connected nodes, use   to make it quasi-undirected : 0 1 / 2---3 / 4 Generate the Frucht Graph.<Contains only one edge between two connected nodes, use   to make it quasi-undirectedSee -http://mathworld.wolfram.com/FruchtGraph.htmlGenerate the house graph.<Contains only one edge between two connected nodes, use   to make it quasi-undirected $ 1 / 2---3 | | 4---5 Generate the house X graph.<Contains only one edge between two connected nodes, use   to make it quasi-undirected $ 1 / 2---3 | X | 4---5 Generate the Pappus Graph.<Contains only one edge between two connected nodes, use  ! to make it quasi-undirected.Nodes are labelled [0..17]"Generate the Sedgewick Maze Graph.<Contains only one edge between two connected nodes, use  ! to make it quasi-undirected.Generate the Petersen Graph.<Contains only one edge between two connected nodes, use  ! to make it quasi-undirected.Generate the Heawood Graph.<Contains only one edge between two connected nodes, use  ! to make it quasi-undirected.Generate the Diamond Graph.<Contains only one edge between two connected nodes, use  ! to make it quasi-undirected. Generate the dodecahedral Graph.<Contains only one edge between two connected nodes, use  ! to make it quasi-undirected.Generate the icosahedral Graph.<Contains only one edge between two connected nodes, use  ! to make it quasi-undirected.#Generate the Krackhardt-Kite Graph.<Contains only one edge between two connected nodes, use  ! to make it quasi-undirected.!Generate the Möbius-Kantor Graph.<Contains only one edge between two connected nodes, use  ! to make it quasi-undirected.Generate the octahedral graph.<Contains only one edge between two connected nodes, use  ! to make it quasi-undirected.Generate the Chvatal graph.<Contains only one edge between two connected nodes, use  ! to make it quasi-undirected.Generate the cubical graph.<Contains only one edge between two connected nodes, use  ! to make it quasi-undirected.Generate the Desargues graph.<Contains only one edge between two connected nodes, use  ! to make it quasi-undirected.Generate the tetrahedral graph.<Contains only one edge between two connected nodes, use  ! to make it quasi-undirected. "Generate the truncated cube graph.<Contains only one edge between two connected nodes, use  ! to make it quasi-undirected.!)Generate the truncated tetrahedron graph.<Contains only one edge between two connected nodes, use  ! to make it quasi-undirected."Generate the Tutte graph.<Contains only one edge between two connected nodes, use  ! to make it quasi-undirected.#&The null graph with no nodes and edges  !"#  !"#NoneEÉ$Convert a graph-generators  to a FGL = (unlabelled)$The graph to convertThe resulting FGL graph$$Nonee!>fInternal fold state for the Barabasi generator. TODO: Remove this declaration from global namespace%¶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?ÿ/Internal recursive worker for selectNDistinctRandomElements Precondition: n > num distinct elems in multiset (not checked). Does not terminate if the precondition doesn't apply. This implementation is quite naive and selects elements randomly until the predefined number of elements are set.(2Generate 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 <= n4Modeled after NetworkX 1.8.1 barabasi_albert_graph())Like (7, but uses a newly initialized random number generator.See @5 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("The random number generator to useThe overall number of nodes (n)BThe number of edges to create between a new and existing nodes (m)0The resulting graph (IO required for randomness))The number of nodesBThe number of edges to create between a new and existing nodes (m)0The resulting graph (IO required for randomness)%&'()()%&'Noneƒä*?Generate a unlabelled context using the ErdQs and Rényi method.See +& for a detailed algorithm description..Example usage, using a truly random generator: Dimport System.Random.MWC gen <- withSystemRandom . asGenIO $ return +‘Generate a unlabelled directed random graph using the Algorithm introduced by ErdQs and Rényi, also called a binomial random graph generator.?Note that self-loops with also be generated with probability p.HThis 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: Zimport System.Random.MWC gen <- withSystemRandom . asGenIO $ return erdosRenyiGraph 10 0.1...2Modelled after NetworkX 1.8.1 erdos_renyi_graph().,Like +7, but uses a newly initialized random number generator.See @5 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-UFilter a list by selecting each list element uniformly with a given probability pSAlthough this is mainly used internally, it can be used as general utility function*"The random number generator to use(Identifier of the context's central nodeTThe algorithm will generate random edges to those nodes from or to the given node5The probability for any pair of nodes to be connected0The resulting graph (IO required for randomness)+"The random number generator to useThe number of nodes5The probability for any pair of nodes to be connected0The resulting graph (IO required for randomness),The number of nodes5The probability for any pair of nodes to be connected0The resulting graph (IO required for randomness)-The random generator state+The probability to select each list elementThe list to filterThe filtered list *+,-+,*-None '.?Generate a small-world context using the Wattz Strogatz method.See /& for a detailed algorithm description..Example usage, using a truly random generator: Dimport System.Random.MWC gen <- withSystemRandom . asGenIO $ return /bGenerate 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: fimport System.Random.MWC gen <- withSystemRandom . asGenIO $ return wattsStrogatzGraph gen 1000 10 0.6...0Like /7, but uses a newly initialized random number generator.See @5 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."The random number generator to use(Identifier of the context's central nodeTThe algorithm will generate random edges to those nodes from or to the given node5The probability for any pair of nodes to be connected0The resulting graph (IO required for randomness)/"The random number generator to usen, The number of nodes9k, the size of the neighborhood / degree (should be even)9beta, The probability of a forward edge getting rewritten0The resulting graph (IO required for randomness)0n, The number of nodes9k, the size of the neighborhood / degree (should be even)9beta, The probability of a forward edge getting rewritten0The resulting graph (IO required for randomness)1The random generator state+The probability to select each list elementThe list to filterThe filtered list ./01/0.1SafeÒ5 23Generate a completely connected graph with n nodes.1The generated graph contains node labels [0..n-1]In contrast to 30 this function does not generate self-loops.<Contains only one edge between two connected nodes, use  E to make it quasi-undirected. The generated edge (i,j) satisfied i < j."Precondition (not checked): n >= 03 Variant of 2 generating self-loops."All generated edges (i,j) satisfy i <= j.See 2+ for a more detailed behaviour description."Precondition (not checked): n >= 04tGenerate the complete bipartite graph with n1 nodes in the first partition and n2 nodes in the second partition.WEach 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  H to also add edges from the second partition to the first partition."Precondition (not checked): n >= 056Generates the empty graph with n nodes and zero edges.The nodes are labelled [0..n-1]"Precondition (not checked): n >= 06`Generate the barbell graph, consisting of two complete subgraphs connected by a single path.In contrast to 7f, this function always generates identically-sized bells. Therefore this is a special case of 7"Precondition (not checked): n >= 07`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 >= 08#Generate the cycle graph of size n.9Edges are created from lower node IDs to higher node IDs."Precondition (not checked): n >= 09fGenerate the path graph of size n, consisting of n nodes that are interconnected in a single path."Precondition (not checked): n >= 0:‰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;{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<,Generate the 2D grid graph of dimensions m*nAlgorithm courtesy 2 The number of nodes in the graphThe resulting complete graph3 The number of nodes in the graphThe resulting complete graph4*The number of nodes in the first partition+The number of nodes in the second partitionThe resulting graph6)The number of nodes in the complete bellsMThe number of nodes in the path, i.e the number of nodes outside the bellsThe resulting barbell graph7%The number of nodes in the first bellNThe number of nodes in the path, i.e. the number of nodes outside the bells&The number of nodes in the second bellThe resulting barbell graph8 n: Number of nodes in the circle The circular graph with n nodes.9n: Number of nodes:n: Number of overall nodes;n: Number of overall nodes<m: Number of rows in the grid n: Number of columns in the grid 23456789:;< 23456789:;<A      !"#$%&'()*+,-./01234567859:;<=>?@ABCDEFGHIJKL/graph-generators-0.1.4.0-LVZFQrPvevG4p3TatusuuCData.Graph.GeneratorsData.Graph.Generators.ClassicData.Graph.Generators.FGL+Data.Graph.Generators.Random.BarabasiAlbert'Data.Graph.Generators.Random.ErdosRenyi*Data.Graph.Generators.Random.WattsStrogatzData.Graph.Generators.RegularData.Graph.Inductive.Basicundir GraphContextinEdges nodeLabeloutEdges GraphInfonumNodesedgescheckGraphInfonumEdges $fEqGraphInfo$fShowGraphInfo trivialGraph bullGraph fruchtGraph houseGraph houseXGraph pappusGraphsedgewickMazeGraph petersenGraph heawoodGraph diamondGraphdodecahedralGraphicosahedralGraphkrackhardtKiteGraphmoebiusKantorGraphoctahedralGraph chvatalGraph cubicalGraphdesarguesGraphtetrahedralGraphtruncatedCubeGraphtruncatedTetrahedronGraph tutteGraph nullGraphgraphInfoToUGr selectNthselectRandomElementselectNDistinctRandomElementsbarabasiAlbertGraphbarabasiAlbertGraph'erdosRenyiContexterdosRenyiGrapherdosRenyiGraph'selectWithProbabilitywattsStrogatzContextwattsStrogatzGraphwattsStrogatzGraph' completeGraphcompleteGraphWithSelfloopscompleteBipartiteGraph emptyGraph barbellGraphgeneralizedBarbellGraph cycleGraph pathGraph starGraph wheelGraph grid2DGraph"fgl-5.6.0.0-DDxvYDarHoD8InSsmJt0D7!Data.Graph.Inductive.PatriciaTreeUGr BarabasiState#selectNDistinctRandomElementsWorker*mwc-random-0.13.6.0-6B2n3ti2bt6KwYaDpSV81VSystem.Random.MWCwithSystemRandom