úÎ×YÓ÷;      !"#$%&'()*+,-./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     Safe FGenerates the trivial graph, containing only one node and no edges Generates 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  !  !   !  !Safe "3Generate a completely connected graph with n nodes.1The generated graph contains node labels [0..n-1]In contrast to #0 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 >= 0# Variant of " generating self-loops."All generated edges (i,j) satisfy i <= j.See "+ for a more detailed behaviour description."Precondition (not checked): n >= 0$tGenerate 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 >= 0%6Generates the empty graph with n nodes and zero edges.The nodes are labelled [0..n-1]"Precondition (not checked): n >= 0&`Generate the barbell graph, consisting of two complete subgraphs connected by a single path.In contrast to 'f, this function always generates identically-sized bells. Therefore this is a special case of '"Precondition (not checked): n >= 0'`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(#Generate the cycle graph of size n.9Edges are created from lower node IDs to higher node IDs."Precondition (not checked): n >= 0)fGenerate 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 " The number of nodes in the graphThe resulting complete graph# The number of nodes in the graphThe resulting complete graph$*The number of nodes in the first partition+The number of nodes in the second partitionThe resulting graph%&)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 graph'%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 graph( n: Number of nodes in the circle The circular graph with n nodes.)n: 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 "#$%&'()*+, "#$%&'()*+, "#$%&'()*+,None-Convert a graph-generators  to a FGL ; (unlabelled)-The graph to convertThe resulting FGL graph---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().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: erdosRenyiGraph' 10 0.11UFilter 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)0The number of nodes5The probability for any pair of nodes to be connected0The resulting graph (IO required for randomness)1The random generator state+The probability to select each list elementThe list to filterThe filtered list ./01/0.1./01None2?Generate a small-world context using the Wattz Strogatz method.See 3& for a detailed algorithm description..Example usage, using a truly random generator: Dimport System.Random.MWC gen <- withSystemRandom . asGenIO $ return 3bGenerate 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...4Like 37, 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.62"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)3"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)=>?4n, 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)5The random generator state+The probability to select each list elementThe list to filterThe filtered list 2345342523=>?45None@fInternal fold state for the Barabasi generator. TODO: Remove this declaration from global namespace6¶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 element7¸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 se8ð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 reasonsAÿ/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.92Generate 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 97, 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@678A9"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)6789:9:678@678A9:B      !"#$%&'()*+,-./0123456789:;<9=>?@ABCDEFGHIJKLMgraph_3bnfH79Tn8YA2sPcBgb8qDData.Graph.GeneratorsData.Graph.Generators.ClassicData.Graph.Generators.RegularData.Graph.Generators.FGL'Data.Graph.Generators.Random.ErdosRenyi*Data.Graph.Generators.Random.WattsStrogatz+Data.Graph.Generators.Random.BarabasiAlbertData.Graph.Inductive.Basicundir GraphContextinEdges nodeLabeloutEdges GraphInfonumNodesedgescheckGraphInfonumEdges trivialGraph bullGraph fruchtGraph houseGraph houseXGraph pappusGraphsedgewickMazeGraph petersenGraph heawoodGraph diamondGraphdodecahedralGraphicosahedralGraphkrackhardtKiteGraphmoebiusKantorGraphoctahedralGraph chvatalGraph cubicalGraphdesarguesGraphtetrahedralGraphtruncatedCubeGraphtruncatedTetrahedronGraph tutteGraph nullGraph completeGraphcompleteGraphWithSelfloopscompleteBipartiteGraph emptyGraph barbellGraphgeneralizedBarbellGraph cycleGraph pathGraph starGraph wheelGraph grid2DGraphgraphInfoToUGrerdosRenyiContexterdosRenyiGrapherdosRenyiGraph'selectWithProbabilitywattsStrogatzContextwattsStrogatzGraphwattsStrogatzGraph' selectNthselectRandomElementselectNDistinctRandomElementsbarabasiAlbertGraphbarabasiAlbertGraph'fgl_1PvuJSbzF40BnsvFgNAS4e!Data.Graph.Inductive.PatriciaTreeUGrmwcra_0SEz8XRK7wOF4DF0uaF48ySystem.Random.MWCwithSystemRandom delineatememberswap BarabasiState#selectNDistinctRandomElementsWorker