@graphty/cytoscape-extensions / samples / GENERATORS
Variable: GENERATORS
constGENERATORS:object
Defined in: cytoscape-extensions/src/samples.ts:20
Every generator by its name: the graph-samples function name in kebab case without "Graph". Each takes that function's options; the random ones take seed (default 0) and give the same graph for the same options on every platform.
Type Declaration
ak
readonlyak: (options) =>FlowNetwork=g.akGraph
The AK network of B. V. Cherkassky and A. V. Goldberg ("On implementing the push-relabel method for the maximum flow problem", Algorithmica 19, 390-410, 1997, doi:10.1007/PL00009180), built to be hard for push-relabel. Deterministic; n = 4k + 6 nodes, m = 6k + 7 arcs.
Nodes: s = 0, t = 1; part A a_i = 2 + i (i = 0 .. k); a hub chain h = k + 3 .. e = 2k + 3; part B b_i = 2k + 4 + i (i = 0 .. 2k + 1). Arcs, in this order: for i = 0 .. k - 1, a_i -> a_{i+1} (capacity k + 1 - i) then a_i -> h (1); a_k -> e (1), a_k -> h (1); the chain j -> j + 1 for j = h .. e - 1 (k + 1); b_i -> b_{i+1} for i = 0 .. 2k (k); the folds b_i -> b_{2k+1-i} (1) for i = 0 .. k - 1; finally s -> a_0, s -> b_0, e -> t and b_{2k+1} -> t, each 1000000. The maximum flow is 2k + 3 and the largest inner capacity k + 1, so k is capped at 499998 to keep the terminal capacity 1000000 from ever binding (every value is then exact in Float32). Node column role (u8). O(k).
Parameters
options
AkOptions
k
Returns
FlowNetwork
the flow network
balanced-tree
readonlybalanced-tree: (options) =>SampleGraph=g.balancedTreeGraph
The balanced r-ary tree of height h, numbered breadth first: node i's children are r i + 1 .. r i + r; edges (parent(c), c) for c = 1 .. n - 1.
Parameters
options
object & WeightOptions
the options
Returns
SampleGraph
the graph
barabasi-albert
readonlybarabasi-albert: (options) =>SampleGraph=g.barabasiAlbertGraph
Barabasi-Albert preferential attachment (A.-L. Barabasi and R. Albert, "Emergence of scaling in random networks", Science 286, 509-512, 1999), optionally with triad formation (P. Holme and B. J. Kim, "Growing scale-free networks with tunable clustering", Phys. Rev. E 65, 026107, 2002), in O(n m) with the repeated-endpoint list of Batagelj and Brandes (2005).
The algorithm is networkx's powerlaw_cluster_graph, which is barabasi_albert_graph when the triad probability is 0: start from m isolated nodes 0 .. m - 1 whose repeated list holds each once; each new node s = m .. n - 1 draws m distinct targets uniformly from the repeated list (in draw order), then adds m edges (s, t): the first to the first target; each further one, with probability triadProbability, to a uniformly chosen neighbour of the previous target that s is not yet joined to, otherwise to the next unused target. Every endpoint is appended to the repeated list, s itself m times. All draws come from the single stream (seed, "barabasi-albert", 0): the process is sequential. Edges are listed by new node, in the order added. (n - m) m edges, no self-loops, no repeats.
Parameters
options
BarabasiAlbertOptions
n, m, triadProbability and seed
Returns
SampleGraph
the undirected graph
barbell
readonlybarbell: (options) =>SampleGraph=g.barbellGraph
The barbell: a clique on 0 .. m1 - 1, the path m1 - 1, m1, .., m1 + m2 (m2 path nodes plus the two joining edges' ends), and a clique on m1 + m2 .. 2 m1 + m2 - 1. Edge order: left clique, path, right clique.
Parameters
options
object & WeightOptions
the options
Returns
SampleGraph
the graph
bianconi-barabasi
readonlybianconi-barabasi: (options) =>SampleGraph=g.bianconiBarabasiGraph
The Bianconi-Barabasi fitness model (G. Bianconi and A.-L. Barabasi, "Competition and multiscaling in evolving networks", Europhys. Lett. 54, 436-442, 2001, doi:10.1209/epl/i2001-00260-6): preferential attachment weighted by fitness, so a fit latecomer can overtake older hubs ("fit get richer").
Start from the clique on nodes 0 .. m, edges (a, b) for a < b in lexicographic order. Each new node s = m + 1 .. n - 1 picks m distinct existing nodes, one at a time, with probability proportional to fitness_i * degree_i among those not yet picked: x = nextFloat() * total, then a descent of a Fenwick tree over the Float64 weights. Edges (s, t) follow in pick order. Draws come from the stream (seed, "bianconi-barabasi", 0). O(n m log n). Emits the Float64 node column fitness.
Parameters
options
BianconiBarabasiOptions
n, m, fitness and seed
Returns
SampleGraph
the undirected graph
bipartite-configuration-model
readonlybipartite-configuration-model: (options) =>SampleGraph=g.bipartiteConfigurationModelGraph
The bipartite configuration model (Newman, Strogatz and Watts 2001, section on bipartite graphs): left nodes are 0 .. L - 1, right nodes L .. L + R - 1. The right stub list (ascending) is Fisher-Yates shuffled with stream (seed, "bipartite-configuration", 0) and paired in order with the ascending left stub list; edge k is (k-th left stub, k-th shuffled right stub). Node column side (u8): 0 left, 1 right. O(n + m).
Parameters
options
BipartiteConfigurationModelOptions
leftDegrees, rightDegrees, multiEdges and seed
Returns
SampleGraph
the undirected bipartite graph
caveman
readonlycaveman: (options) =>SampleGraph=g.cavemanGraph
The caveman graph (Watts 1999): cliques disjoint cliques of size nodes, clique g on g * size .. (g + 1) * size - 1. Node column community (u32): the clique.
Parameters
options
object & WeightOptions
the options
Returns
SampleGraph
the graph
chung-lu
readonlychung-lu: (options) =>SampleGraph=g.chungLuGraph
The Chung-Lu expected-degree graph (F. Chung and L. Lu, "The average distances in random graphs with given expected degrees", PNAS 99, 15879-15882, 2002, doi:10.1073/pnas.252631999): every pair u != v is joined independently with probability min(1, w_u w_v / S), S the weight sum, so node u's expected degree is about w_u when every w_u w_v is below S. Linear time by the skipping of J. C. Miller and A. Hagberg, "Efficient generation of networks with given expected degrees", WAW 2011, LNCS 6732, 115-126, doi:10.1007/978-3-642-21286-4_10. Rows are the nodes sorted by weight descending (ties by index ascending); row i draws from stream (seed, "chung-lu", i) (see chungLuRows). Edges are listed by row, each (row node, later node) in original indices. Simple, undirected. O(n log n + m).
Parameters
options
ChungLuOptions
expectedDegrees and seed
Returns
SampleGraph
the undirected graph
circular-ladder
readonlycircular-ladder: (options) =>SampleGraph=g.circularLadderGraph
The circular ladder CL_n (the n-prism): the ladder's rails 0 .. n - 1 and n .. 2n - 1 and rungs (i, n + i), as ladderGraph lists them, then the closing edges (n - 1, 0) and (2n - 1, n). 3-regular and planar.
Parameters
options
object & WeightOptions
the options
Returns
SampleGraph
the graph
complete
readonlycomplete: (options) =>SampleGraph=g.completeGraph
The complete graph K_n: every pair (i, j), i < j, row-major.
Parameters
options
object & WeightOptions
the options
Returns
SampleGraph
the graph
complete-bipartite
readonlycomplete-bipartite: (options) =>SampleGraph=g.completeBipartiteGraph
The complete bipartite graph K_{a,b}: left nodes 0 .. a - 1, right nodes a .. a + b - 1, every pair (i, a + j), row-major. Node column side (u8): 0 left, 1 right.
Parameters
options
object & WeightOptions
the options
Returns
SampleGraph
the graph
complete-multipartite
readonlycomplete-multipartite: (options) =>SampleGraph=g.completeMultipartiteGraph
The complete multipartite graph K_{s0, s1, ...}: part p holds the next sizes[p] node indices, and every pair of nodes in different parts is joined; for each node in index order, the edges to every later node of a later part, ascending. Node column part (u32).
Parameters
options
object & WeightOptions
the options
Returns
SampleGraph
the graph
configuration-model
readonlyconfiguration-model: (options) =>SampleGraph=g.configurationModelGraph
The configuration model (E. A. Bender and E. R. Canfield, "The asymptotic number of labeled graphs with given degree sequences", J. Combin. Theory A 24, 296-307, 1978, doi:10.1016/0097-3165(78)90059-6; M. Molloy and B. Reed, "A critical point for random graphs with a given degree sequence", Random Struct. Algorithms 6, 161-179, 1995, doi:10.1002/rsa.3240060204; M. E. J. Newman, S. H. Strogatz and D. J. Watts, "Random graphs with arbitrary degree distributions and their applications", Phys. Rev. E 64, 026118, 2001, doi:10.1103/PhysRevE.64.026118). The stub list (node i repeated degrees[i] times, ascending) is Fisher-Yates shuffled with stream (seed, "configuration", 0) and consecutive stubs are paired: edge k is (stubs[2k], stubs[2k + 1]), in that order. With keep / keep the degrees are exact (a multigraph); erasing drops self-loops and every repeat of a pair after its first occurrence, so degrees can only go down. An odd degree sum is a RangeError. O(n + m).
Parameters
options
ConfigurationModelOptions
degrees, selfLoops, multiEdges and seed
Returns
SampleGraph
the undirected graph
connected-caveman
readonlyconnected-caveman: (options) =>SampleGraph=g.connectedCavemanGraph
The connected caveman graph (Watts 1999, as networkx builds it): the caveman graph with, in each clique starting at s, the edge (s, s + 1) replaced in place by (s, s - 1 mod n), which joins the cliques into a ring. Node column community (u32): the clique.
Parameters
options
object & WeightOptions
the options
Returns
SampleGraph
the graph
cycle
readonlycycle: (options) =>SampleGraph=g.cycleGraph
The cycle C_n: the path P_n plus the edge (n - 1, 0).
Parameters
options
object & WeightOptions
the options
Returns
SampleGraph
the graph
degree-corrected-sbm
readonlydegree-corrected-sbm: (options) =>SampleGraph=g.degreeCorrectedSbmGraph
The degree-corrected stochastic block model (B. Karrer and M. E. J. Newman, "Stochastic blockmodels and community structure in networks", Phys. Rev. E 83, 016107, 2011, doi:10.1103/PhysRevE.83.016107), sampled as a simple graph with Bernoulli edges: P(uv) = min(1, theta_u theta_v omega_rs) with theta_u = d_u / kappa_r (kappa_r the degree total of u's block r, K the grand total), omega_rr = (1 - mu) kappa_r and omega_rs = mu kappa_r kappa_s / K for r != s. So node u's expected degree is about d_u (1 - mu kappa_r / K): the inside share is 1 - mu, but the outside share misses the mu kappa_r / K that would land in u's own block. Rows: block by block, inside a block the nodes sorted by d descending (ties by index); row i draws from stream (seed, "dcsbm", i) and walks its own block's later rows, then every later block (see chungLuRows). Edges are listed by row in original node indices. Node column community (u32). With one block and mu = 0 it is Chung-Lu. O(n log n + n B + m).
Parameters
options
DegreeCorrectedSbmOptions
sizes, expectedDegrees, mixing and seed
Returns
SampleGraph
the undirected graph
directed-configuration-model
readonlydirected-configuration-model: (options) =>SampleGraph=g.directedConfigurationModelGraph
The directed configuration model (Newman, Strogatz and Watts 2001, section on directed graphs): the in-stub list (node i repeated inDegrees[i] times, ascending) is Fisher-Yates shuffled with stream (seed, "configuration-directed", 0) and paired in order with the ascending out-stub list, so edge k runs from the k-th out-stub to the k-th shuffled in-stub (edges come grouped by source, ascending). Erasing works as in configurationModelGraph on ordered pairs. O(n + m).
Parameters
options
DirectedConfigurationModelOptions
outDegrees, inDegrees, selfLoops, multiEdges and seed
Returns
SampleGraph
the directed graph
duplication-divergence
readonlyduplication-divergence: (options) =>SampleGraph=g.duplicationDivergenceGraph
The duplication-divergence model (I. Ispolatov, P. L. Krapivsky and A. Yuryev, "Duplication-divergence model of protein interaction network", Phys. Rev. E 71, 061911, 2005, doi:10.1103/PhysRevE.71.061911), as networkx's duplication_divergence_graph: protein-network like, with many nodes sharing neighbours.
Start with the edge (0, 1). While there are fewer than n nodes, draw a node x = nextBelow(i) for the next index i, then one float per neighbour of x (in the order they were joined to x): below retention, the edge (i, neighbour). If i got at least one edge it is kept, otherwise the attempt is discarded. All draws come from the stream (seed, "duplication-divergence", 0). Edges are listed by new node. Simple and connected.
Cost: O(sum of the copied nodes' degrees). Each attempt succeeds with probability at least retention; after 1000 n attempts in total it throws a RangeError rather than loop on.
Parameters
options
DuplicationDivergenceOptions
n, retention and seed
Returns
SampleGraph
the undirected graph
empty
readonlyempty: (options) =>SampleGraph=g.emptyGraph
The empty graph: n isolated nodes, no edges.
Parameters
options
object & WeightOptions
the options
Returns
SampleGraph
the graph
erdos-renyi
readonlyerdos-renyi: (options) =>SampleGraph=g.erdosRenyiGraph
Gilbert's G(n, p) in O(n + m) by geometric skipping (Batagelj and Brandes 2005). Edges are the pairs (u, v), u < v, in row-major order; row u draws from its own stream, so the graph does not depend on how the rows are split between workers. With directed: true, the arcs (u, v) of every ordered pair u != v, by u then v ascending, each row from stream (seed, "gnp-directed", u).
Parameters
options
ErdosRenyiOptions
n, p and seed
Returns
SampleGraph
the undirected graph
erdos-renyi-gnm
readonlyerdos-renyi-gnm: (options) =>SampleGraph=g.erdosRenyiGnmGraph
Erdos-Renyi's G(n, m): m distinct pairs chosen uniformly, by Floyd's sampling over the pair indices 0 .. n (n - 1) / 2 - 1 (exactly m draws from stream (seed, "gnm", 0), no rejection loop), in O(m log m). Edges are the pairs (u, v), u < v, in row-major order.
Parameters
options
ErdosRenyiGnmOptions
n, m and seed
Returns
SampleGraph
the undirected graph
forest-fire
readonlyforest-fire: (options) =>SampleGraph=g.forestFireGraph
The forest fire model (J. Leskovec, J. Kleinberg and C. Faloutsos, "Graphs over time: densification laws, shrinking diameters and possible explanations", KDD 2005, doi:10.1145/1081870.1081893). Directed; heavy-tailed degrees, densification, community locality.
Node 0 starts alone. Each new node v = 1 .. n - 1 draws an ambassador w = nextBelow(v) and burns breadth-first from it: for each burning node x in burn order, draw x_out = floor(ln(1 - u) / ln p) (geometric, P(x_out >= k) = p^k, mean p / (1 - p)) and then x_in the same way with r p; then pick x_out of x's out-neighbours and then x_in of its in-neighbours uniformly among those not yet burned (adjacency order, partial Fisher-Yates; all of them when there are fewer), and burn them. Burning stops at maxBurn nodes. v then links to every burned node: arcs (v, t) in burn order. Edges are listed by v. All draws come from the stream (seed, "forest-fire", 0).
Cost: O(sum over burning nodes of their degree), since each burning node's lists are scanned; the edge count explodes for p above about 0.37, which maxBurn bounds at n maxBurn arcs.
Parameters
options
ForestFireOptions
n, forward, backward, maxBurn and seed
Returns
SampleGraph
the directed graph
genrmf
readonlygenrmf: (options) =>FlowNetwork=g.genrmfGraph
GENRMF, the max-flow family of D. Goldfarb and M. D. Grigoriadis ("A computational comparison of the Dinic and network simplex methods for maximum flow", Annals of Operations Research 13, 81-123, 1988, doi:10.1007/BF02288321) as generated by Tamas Badics's genrmf (1991, First DIMACS Implementation Challenge): b frames, each an a x a grid. Node f a^2 + r a + c is (r, c) of frame f. Arcs, frame by frame: the frame's grid arcs to each 4-neighbour in both directions (by node; right, down, left, up) with capacity c2 a^2; then, for f < b - 1, node j of frame f -> node perm_f(j) of frame f + 1 for j ascending, with capacity uniform in [c1, c2]. Stream (seed, "genrmf", f) first draws perm_f, a Fisher-Yates shuffle of 0 .. a^2 - 1 (for i = a^2 - 1 down to 1, swap i with nextBelow(i + 1)), then the a^2 capacities in j order. The source is node 0 (the first node of the first frame), the sink the last node of the last frame. Node columns frame (u32) and role (u8). Badics's own random numbers are not reproduced; the structure is. O(a^2 b).
Parameters
options
GenrmfOptions
a, b, c1, c2 and seed
Returns
FlowNetwork
the flow network
grid
readonlygrid: (options) =>SampleGraph=g.gridGraph
The rows x cols grid: grid3dGraph with one layer. Node (r, c) is index r * cols + c; for each node in index order, the edge to its right neighbour, then the one below, then (with diagonals) below-left and below-right.
Parameters
options
GridOptions
sizes and the lattice options
Returns
SampleGraph
the graph
grid-3d
readonlygrid-3d: (options) =>SampleGraph=g.grid3dGraph
The rows x cols x layers grid. Node (l, r, c) is index (l * rows + r) * cols + c. For each node in index order, the edge to each forward neighbour in the order of the offsets: +column, +row, +layer, then the diagonals. Without options this is the 6-neighbour lattice of phase 1, edge for edge. Obstacles draw one float per node from stream (seed, "grid-obstacles", node) -- node < p blocks it -- so the obstacle map does not depend on the other options.
Parameters
options
Grid3dOptions
sizes and the lattice options
Returns
SampleGraph
the graph
grid-flow-network
readonlygrid-flow-network: (options) =>FlowNetwork=g.gridFlowNetwork
A grid flow network, the shape of graph-cut image segmentation: node r * cols + c for pixel (r, c), arcs to each 4-neighbour in both directions, listed by node, in the order right, down, left, up; node u draws its arcs' capacities, uniform integers in [minCapacity, maxCapacity], from stream (seed, "grid-flow", u) in that order. Then the source rows * cols with an arc to every left-column node (by row), and every right-column node with an arc to the sink rows * cols + 1 (by row), each of capacity 4 * maxCapacity. Those terminal arcs are never a minimum cut: the arcs from the first column to the second already cut the network with at most rows * maxCapacity. Node columns x = c and y = r (Float64), the source at x = -1 and the sink at x = cols, both at the middle row; role (u8: 0 inner, 1 source, 2 sink). O(rows cols).
Parameters
options
GridFlowOptions
rows, cols, minCapacity, maxCapacity and seed
Returns
FlowNetwork
the flow network
hexagonal-lattice
readonlyhexagonal-lattice: (options) =>SampleGraph=g.hexagonalLatticeGraph
The hexagonal (honeycomb) lattice in its brick-wall form: node (r, c) is index r * cols + c and links to (r, c + 1) always and to (r + 1, c) when r + c is even, in that order, for each node in index order. Interior nodes have degree 3; every face is a hexagon. Positions give unit edges: x = c sqrt(3) / 2, y = 1.5 r + (r + c even ? 0.5 : 0).
Parameters
options
PlanarLatticeOptions
rows, cols, positions
Returns
SampleGraph
the undirected graph
hyperbolic
readonlyhyperbolic: (options) =>SampleGraph=g.hyperbolicGraph
A random hyperbolic graph (Krioukov et al. 2010): n points in a hyperbolic disk of radius R, angles uniform and radii with density proportional to sinh(alpha r), alpha = (gamma - 1) / 2, so the degrees follow a power law with exponent gamma. At temperature 0 two nodes are joined iff their hyperbolic distance is below R; at T > 0 with probability 1 / (1 + exp((d - R) / (2 T))).
R comes from the paper's approximation of the mean degree, R = 2 ln(2 xi^2 n / (pi k)) with xi = alpha / (alpha - 1/2), times (pi T / sin(pi T)) inside the logarithm for T > 0. It is an approximation, so the measured mean degree only lands near averageDegree: measured at n = 3000 and 10000, within about 10% for exponent >= 2.5 and T <= 0.7, but about 0.6x at exponent 2.2 and about 0.5x at T = 0.9 (the approximation degrades as gamma approaches 2 and T approaches 1).
Node i draws its angle theta = 2 pi u and then its radius r = acosh(1 + (cosh(alpha R) - 1) u') / alpha (inverse CDF) from stream (seed, "hyperbolic-points", i); the pairs are decided by hyperbolicRows. Edges are the pairs (u, v), u < v, ascending u then v. Node columns (all Float64Array): x, y (the native polar embedding r cos theta, r sin theta) and radius (r).
Cost: O(n^2) pairs (and one draw per pair at T > 0), so n is capped at 20000. ponytail: naive pair loop, n <= 20000; the band algorithm of M. von Looz, H. Meyerhenke and R. Prutkin, "Generating random hyperbolic graphs in subquadratic time", ISAAC 2015, doi:10.1007/978-3-662-48971-0_40, is the upgrade path.
Parameters
options
HyperbolicOptions
n, averageDegree, exponent, temperature and seed
Returns
SampleGraph
the undirected graph
hypercube
readonlyhypercube: (options) =>SampleGraph=g.hypercubeGraph
The hypercube Q_d: nodes are the d-bit integers, edges join integers one bit apart; for each node i in order and each bit b ascending that is 0 in i, the edge (i, i | 2^b).
Parameters
options
object & WeightOptions
the options
Returns
SampleGraph
the graph
knn
readonlyknn: (options) =>SampleGraph=g.knnGraph
The k-nearest-neighbour graph of random points, the standard input of spectral clustering (U. von Luxburg, "A tutorial on spectral clustering", Statistics and Computing 17, 395-416, 2007, doi:10.1007/s11222-007-9033-z).
Points: uniform in the unit square or cube (point i = nextFloat() per axis from stream (seed, "knn-points", i)), or with clusters a Gaussian mixture: cluster centres uniform in the unit cube from stream (seed, "knn-centres", c), point i picks its cluster uniformly and adds normal offsets of standard deviation spread (Marsaglia polar method) from stream (seed, "knn-points", i); mixture points may leave [0, 1). Each node's k nearest are exact, ties broken by the smaller index, found by an expanding ring search over a cell grid of about n / k cells: expected O(n k^2) for uniform points.
Directed (default): the arcs u -> each of its k nearest, ascending u then ascending target. Undirected: the union of those pairs without duplicates as (u, v), u < v, ascending u then v. Node columns x, y (, z): Float64Array; with clusters, community (u32): the cluster.
Parameters
options
KnnOptions
n, k, dimension, directed, clusters, spread and seed
Returns
SampleGraph
the graph
kronecker
readonlykronecker: (options) =>SampleGraph=g.kroneckerGraph
A stochastic Kronecker graph (J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos and Z. Ghahramani, "Kronecker graphs: an approach to modeling networks", JMLR 11, 985-1042, 2010) by their fast O(E power) sampling: n = k^power nodes and E = round(S^power) edges, S the sum of the initiator (S^power by repeated multiplication), unless edges is given. Edge e draws from stream (seed, "kronecker", e): power descents, most significant first, each drawing u = nextFloat() and picking the first initiator cell (row-major) whose cumulative entry over S exceeds u; cell (r, c) appends digit r to the source and c to the target in base k. Edges are listed in sampling order. A multigraph unless erased: see selfLoops, multiEdges, permute (stream (seed, "kronecker-permute", 0)) and directed.
Parameters
options
KroneckerOptions
initiator, power, edges, the shared recursive options and seed
Returns
SampleGraph
the graph
ladder
readonlyladder: (options) =>SampleGraph=g.ladderGraph
The ladder L_n: two paths 0 .. n - 1 and n .. 2n - 1, then the rungs (i, n + i).
Parameters
options
object & WeightOptions
the options
Returns
SampleGraph
the graph
layered-flow-network
readonlylayered-flow-network: (options) =>FlowNetwork=g.layeredFlowNetwork
A random layered flow network: inner layers as in randomDagGraph (arcs only from layer i to layer i + 1, each with probability p, capacities uniform integers in [minCapacity, maxCapacity]), a source feeding every node of the first layer and every node of the last layer feeding a sink. Inner nodes come first, layer by layer; the source is node N and the sink N + 1 (N inner nodes). Arcs: the inner arcs by source node (see layeredFlowRows), then source -> first-layer nodes ascending, then last-layer nodes -> sink ascending; each terminal arc has capacity maxCapacity * (the widest layer), at least what any one node can pass on. Node column layer (u32): inner layer i is i + 1, the source is layer 0 and the sink layer L + 1, so the column is a topological layering of the whole network; role (u8). O(N + m).
Parameters
options
LayeredFlowOptions
layers, p, minCapacity, maxCapacity and seed
Returns
FlowNetwork
the flow network
lfr
readonlylfr: (options) =>SampleGraph=g.lfrGraph
The LFR benchmark (A. Lancichinetti, S. Fortunato and F. Radicchi, "Benchmark graphs for testing community detection algorithms", Phys. Rev. E 78, 046110, 2008, doi:10.1103/PhysRevE.78.046110), built with configuration models:
- Degrees: node i's degree is the i-th power-law draw on [minDegree, maxDegree] from stream (seed, "lfr-degrees", 0); an odd sum is fixed on the last node as in powerLawDegreeSequence.
- Community sizes: power law on [minCommunity, maxCommunity] summing to exactly n (stream "lfr-sizes"); community ids are the draw order.
- Internal degree round((1 - mu) d); assignment of nodes to communities larger than their internal degree (stream "lfr-assign"); a RangeError when none exists.
- Inside each community c, ascending: when its internal degrees sum to an odd number the member with the largest (lowest index on ties) moves one stub to the outside; then a configuration model on the members' ascending stub list shuffled with stream (seed, "lfr-internal", c).
- Outside: a configuration model on the remaining degrees d - internal, stream (seed, "lfr-external", 0).
Self-loops and repeated pairs are erased, and so are external pairs that land inside one community, so degrees and the mixing come out approximate: the mean degree drops by up to about 10% (repeated pairs inside small communities), and the measured mixing lands within about 0.02 of mu for thousands of nodes. No edge switching repairs this. Edges: every community's internal edges (communities ascending, pair order), then the external edges. Node column community (u32). O(n log n + m); n at most 1,000,000.
Parameters
options
LfrOptions
n, degree and community power laws, mixing and seed
Returns
SampleGraph
the undirected graph
lollipop
readonlylollipop: (options) =>SampleGraph=g.lollipopGraph
The lollipop: a clique on 0 .. m - 1 and a tail path m - 1, m, .., m + n - 1.
Parameters
options
object & WeightOptions
the options
Returns
SampleGraph
the graph
mobius-ladder
readonlymobius-ladder: (options) =>SampleGraph=g.mobiusLadderGraph
The Moebius ladder M_{2n}: the cycle 0 .. 2n - 1 (edges (i, i + 1), then (2n - 1, 0)) and the n chords (i, i + n). 3-regular and, unlike the circular ladder, not planar for n >= 3.
Parameters
options
object & WeightOptions
the options
Returns
SampleGraph
the graph
named
readonlynamed: (o) =>SampleGraph
Parameters
o
object & WeightOptions
Returns
SampleGraph
newman-watts
readonlynewman-watts: (options) =>SampleGraph=g.newmanWattsGraph
The Newman-Watts small world (M. E. J. Newman and D. J. Watts, "Renormalization group analysis of the small-world network model", Phys. Lett. A 263, 341-346, 1999, doi:10.1016/S0375-9601(99)00757-4): Watts-Strogatz with shortcuts added instead of rewired, so the graph stays connected.
The ring lattice of wattsStrogatzGraph comes first: edge slot u k/2 + (j - 1) is (u, (u + j) mod n). Then for each slot in order, with source u: draw a float; if it is below p and u is not joined to every other node, redraw w = nextBelow(n) until w is neither u nor a neighbour of u, and append the shortcut (u, w). All draws come from the stream (seed, "newman-watts", 0). O(n k) expected.
Parameters
options
NewmanWattsOptions
n, k, p and seed
Returns
SampleGraph
the undirected graph
path
readonlypath: (options) =>SampleGraph=g.pathGraph
The path P_n: edges (i, i + 1) for i = 0 .. n - 2.
Parameters
options
object & WeightOptions
the options
Returns
SampleGraph
the graph
petersen
readonlypetersen: (options?) =>SampleGraph=g.petersenGraph
The Petersen graph: outer cycle 0 .. 4, spokes (i, i + 5), inner pentagram (5 + i, 5 + (i + 2) mod 5). 3-regular, girth 5, non-planar.
Parameters
options?
WeightOptions
the common weight options
Returns
SampleGraph
the graph
planted-partition
readonlyplanted-partition: (options) =>SampleGraph=g.plantedPartitionGraph
The planted partition model: groups equal blocks, pIn inside, pOut between. Exactly the stochastic block model with that matrix (same seed, same graph). Node column community (u32).
Parameters
options
PlantedPartitionOptions
groups, groupSize, pIn, pOut and seed
Returns
SampleGraph
the undirected graph
price
readonlyprice: (options) =>SampleGraph=g.priceGraph
Price's citation network (D. J. de S. Price, "Networks of scientific papers", Science 149, 510-515, 1965, doi:10.1126/science.149.3683.510; "A general theory of bibliometric and other cumulative advantage processes", J. Am. Soc. Inf. Sci. 27, 292-306, 1976): a directed acyclic graph with arcs from the citing (newer) node to the cited (older) one, in-degrees following a power law with exponent 2 + a / m.
Node t = 1 .. n - 1 cites min(m, t) distinct earlier nodes, each chosen with probability proportional to in-degree + a, the in-degrees as they were when t arrived. When t <= m it cites every earlier node, ascending, without drawing. Otherwise, with E arcs made before t, every draw takes x = nextFloat() * (E + a t) and then, if x < E, the target of a uniformly chosen earlier arc (nextBelow(E) into the list of cited targets), else a uniform node nextBelow(t); a node t already cites is redrawn. All draws come from the single stream (seed, "price", 0): the process is sequential. Arcs are listed by citing node, in draw order. O(n m) expected.
Parameters
options
PriceOptions
n, citations, attractiveness and seed
Returns
SampleGraph
the directed graph
random-apollonian
readonlyrandom-apollonian: (options) =>SampleGraph=g.randomApollonianGraph
The random Apollonian network (T. Zhou, G. Yan and B.-H. Wang, "Maximal planar networks with large clustering coefficient and power-law degree distribution", Phys. Rev. E 71, 046141, 2005, doi:10.1103/PhysRevE.71.046141; the deterministic one is J. S. Andrade et al., Phys. Rev. Lett. 94, 018702, 2005): maximal planar, power-law degrees, high clustering.
Start from the triangle 0, 1, 2 (edges (0, 1), (0, 2), (1, 2)) whose inner face is face 0; the outer face is never split. Each new node v = 3 .. n - 1 picks face f = nextBelow(faceCount) = (a, b, c), adds the edges (v, a), (v, b), (v, c), and splits f: face f becomes (a, b, v), and (b, c, v) and (a, c, v) are appended. Draws come from the stream (seed, "apollonian", 0). 3n - 6 edges. O(n).
Parameters
options
RandomApollonianOptions
n and seed
Returns
SampleGraph
the undirected graph
random-bipartite
readonlyrandom-bipartite: (options) =>SampleGraph=g.randomBipartiteGraph
The random bipartite graph G(n1, n2, p) in O(n + m): left nodes 0 .. n1 - 1, right nodes n1 .. n1 + n2 - 1, each left-right pair independently with probability p; edges row by row from the left side, right ends ascending. Node column side (u8): 0 left, 1 right.
Parameters
options
RandomBipartiteOptions
n1, n2, p, perfectMatching and seed
Returns
SampleGraph
the undirected graph
random-dag
readonlyrandom-dag: (options) =>SampleGraph=g.randomDagGraph
A random layered DAG: arcs only from layer i to layer i + 1, each independently with probability p, O(n + m). The standard input for layered (Sugiyama) drawing, topological sort and longest path. Arcs are listed by source node, targets ascending. Node column layer (u32).
Parameters
options
RandomDagOptions
layers, p and seed
Returns
SampleGraph
the directed graph
random-geometric
readonlyrandom-geometric: (options) =>SampleGraph=g.randomGeometricGraph
The random geometric graph (E. N. Gilbert, "Random plane networks", J. SIAM 9(4), 533-543, 1961, doi:10.1137/0109045; M. Penrose, Random Geometric Graphs, Oxford University Press, 2003): n uniform points in the unit square or cube, u and v joined iff their Euclidean distance (torus distance when periodic) is at most radius.
Node i's point is x, y (, z) = one nextFloat() per axis from stream (seed, "rgg-points", i). The points are bucketed into a uniform grid of cells of side >= radius (at most about n cells) and each node checks the 3^dimension cells around its own. Edges are the pairs (u, v), u < v, ascending u then ascending v. Expected cost O(n + m). Node columns x, y (, z): Float64Array in [0, 1). The mean degree is about n pi r^2 in 2D and n 4/3 pi r^3 in 3D (less near the border unless periodic); connectivity needs r above about sqrt(ln n / (pi n)) in 2D.
Parameters
options
RandomGeometricOptions
n, radius, dimension, periodic and seed
Returns
SampleGraph
the undirected graph
random-order-dag
readonlyrandom-order-dag: (options) =>SampleGraph=g.randomOrderDagGraph
The random-order DAG: a directed G(n, p) restricted to the arcs i -> j with i < j, so node index order is a topological order (B. Karrer and M. E. J. Newman, "Random acyclic networks", Phys. Rev. Lett. 102, 128701, 2009, doi:10.1103/PhysRevLett.102.128701). O(n + m) by geometric skipping; arcs in row-major order, see orderDagRows.
Parameters
options
RandomOrderDagOptions
n, p and seed
Returns
SampleGraph
the directed acyclic graph
random-recursive-tree
readonlyrandom-recursive-tree: (options) =>SampleGraph=g.randomRecursiveTreeGraph
The random recursive tree (R. T. Smythe and H. M. Mahmoud, "A survey of recursive trees", Theory Probab. Math. Statist. 51, 1-27, 1995): node t = 1 .. n - 1 attaches to a uniform earlier node, drawn as nextBelow(t) from the stream (seed, "recursive-tree", 0). Edge t - 1 is (parent, t), in t order. O(n). Depth about ln n, root degree about ln n.
Parameters
options
RandomRecursiveTreeOptions
n and seed
Returns
SampleGraph
the undirected tree
random-regular
readonlyrandom-regular: (options) =>SampleGraph=g.randomRegularGraph
A uniformly-ish random d-regular simple graph by the pairing algorithm of A. Steger and N. C. Wormald, "Generating random regular graphs quickly", Combin. Probab. Comput. 8, 377-396, 1999, doi:10.1017/S0963548399003867, structured like networkx's random_regular_graph: attempt a (a = 0, 1, ...) draws from stream (seed, "random-regular", a); it Fisher-Yates shuffles the stub list (node i repeated d times, ascending), keeps each consecutive pair that is not a loop and not yet an edge, and re-pairs the leftover stubs (ascending node order) while some leftover pair could still be joined; otherwise it restarts. At most 100 attempts of at most 1000 rounds, then a RangeError. Edges (u, v), u < v, in lexicographic order. Expected O(n d^2) for small d.
Parameters
options
RandomRegularOptions
n, d and seed
Returns
SampleGraph
the undirected graph
random-tree
readonlyrandom-tree: (options) =>SampleGraph=g.randomTreeGraph
A uniformly random labelled tree: a uniformly random Pruefer sequence (H. Pruefer, Archiv der Mathematik und Physik 27, 142-144, 1918) of n - 2 draws nextBelow(n) from stream (seed, "prufer", 0), decoded in O(n). Edge k joins the k-th removed leaf to its neighbour; the last edge is (leaf, n - 1).
Parameters
options
RandomTreeOptions
n and seed
Returns
SampleGraph
the undirected tree
ring-of-cliques
readonlyring-of-cliques: (options) =>SampleGraph=g.ringOfCliquesGraph
The ring of cliques, as networkx's ring_of_cliques: for each clique i in order, its edges (row-major), then the ring edge (i size + 1, (i + 1) size mod n). The standard example of modularity's resolution limit (Fortunato and Barthelemy, PNAS 104:36-41, 2007, doi:10.1073/pnas.0605965104). Node column community (u32): the clique.
Parameters
options
object & WeightOptions
the options
Returns
SampleGraph
the graph
rmat
readonlyrmat: (options) =>SampleGraph=g.rmatGraph
R-MAT (D. Chakrabarti, Y. Zhan and C. Faloutsos, "R-MAT: a recursive model for graph mining", SIAM SDM 2004, 442-446, doi:10.1137/1.9781611972740.43) with Graph500's defaults: n = 2^scale nodes and m = edgeFactor n edges in O(m scale). Edge e draws from stream (seed, "rmat", e): scale levels, most significant bit first, each comparing one nextFloat() with a, a + b and a + b + c to pick the top-left, top-right, bottom-left or else bottom-right quadrant (bit 0/1 of the source for top/bottom, of the target for left/right). Edges are listed in sampling order. A multigraph with self-loops unless erased: see selfLoops, multiEdges, permute (stream (seed, "rmat-permute", 0)) and directed.
webgpu-graph-algorithms carries three private R-MAT copies on xorshift / LCG streams (benchmarks/datasets.ts, test/helpers/graphs.ts, demo/main.ts) that should move to this. Two of them move a self-loop to (u, (v + 1) mod n), keeping exactly m edges; selfLoops: "erase" drops the loop instead (about m / n^0.4 fewer edges at the defaults), and weights: { kind: "integer", min: 1, max: 10 } reproduces their 1..10 weights. The third keeps self-loops, which is this function's default.
Parameters
options
RmatOptions
scale, edgeFactor, a, b, c, d, the shared recursive options and seed
Returns
SampleGraph
the graph
star
readonlystar: (options) =>SampleGraph=g.starGraph
The star: hub 0 joined to every other node, edges (0, i) for i = 1 .. n - 1.
Parameters
options
object & WeightOptions
the options
Returns
SampleGraph
the graph
stochastic-block-model
readonlystochastic-block-model: (options) =>SampleGraph=g.stochasticBlockModelGraph
The stochastic block model in O(n B + m): node pairs are joined independently with the probability of their blocks, by geometric skipping inside each row's block segments. Edges are the pairs (u, v), u < v, row-major. Node column community (u32): the block.
Parameters
options
StochasticBlockModelOptions
sizes, probabilities and seed
Returns
SampleGraph
the undirected graph
triangular-lattice
readonlytriangular-lattice: (options) =>SampleGraph=g.triangularLatticeGraph
The triangular lattice as a triangulated rows x cols grid: node (r, c) is index r * cols + c and links to (r, c + 1), (r + 1, c) and (r + 1, c - 1), in that order, for each node in index order. Interior nodes have degree 6. Positions shear the grid into a parallelogram of equilateral triangles: x = c + r / 2, y = r sqrt(3) / 2.
Parameters
options
PlanarLatticeOptions
rows, cols, positions
Returns
SampleGraph
the undirected graph
watts-strogatz
readonlywatts-strogatz: (options) =>SampleGraph=g.wattsStrogatzGraph
The Watts-Strogatz small world (D. J. Watts and S. H. Strogatz, "Collective dynamics of 'small-world' networks", Nature 393, 440-442, 1998), as networkx's watts_strogatz_graph builds it, in O(n k).
Start from the ring lattice: edge slot u k/2 + (j - 1) holds (u, (u + j) mod n) for j = 1 .. k/2. Then for j = 1 .. k/2 and u = 0 .. n - 1 in that order: draw a float; if it is below beta and u is not already joined to every other node, redraw w = nextBelow(n) until w is neither u nor a neighbour of u, and rewire the slot to (u, w). All draws come from the single stream (seed, "watts-strogatz", 0). Edges are listed in slot order.
Parameters
options
WattsStrogatzOptions
n, k, beta and seed
Returns
SampleGraph
the undirected graph
waxman
readonlywaxman: (options) =>SampleGraph=g.waxmanGraph
The Waxman graph (B. M. Waxman, "Routing of multipoint connections", IEEE J. Selected Areas in Communications 6(9), 1617-1622, 1988): n uniform points in the unit square, each pair joined independently with probability beta exp(-d / (alpha L)).
L is fixed at sqrt(2), the diagonal of the unit square (networkx uses the largest distance between the drawn points instead, so the two differ slightly). Node i's point is x, y = two nextFloat() draws from stream (seed, "waxman-points", i); the pairs are drawn by waxmanRows. Edges are the pairs (u, v), u < v, ascending u then v. Every pair has a non-zero probability, so the cost is O(n + beta n^2 / 2) draws; above 5e8 expected draws it throws a RangeError (n about 31,600 at beta 1). Node columns x, y: Float64Array in [0, 1).
Parameters
options
WaxmanOptions
n, alpha, beta and seed
Returns
SampleGraph
the undirected graph
wheel
readonlywheel: (options) =>SampleGraph=g.wheelGraph
The wheel W_n: the star's spokes (0, i), then the rim (i, i + 1) for i = 1 .. n - 2, then (n - 1, 1).
Parameters
options
object & WeightOptions
the options
Returns
SampleGraph
the graph
wilson-maze
readonlywilson-maze: (options) =>SampleGraph=g.wilsonMazeGraph
A uniform spanning tree of the rows x cols grid, a perfect maze, by Wilson's algorithm (D. B. Wilson, "Generating random spanning trees more quickly than the cover time", STOC 1996, doi:10.1145/237814.237880): loop-erased random walks.
Node (r, c) is index r cols + c. The root is node 0. For each start node in index order that is not yet in the tree, walk until the tree is hit, each step to a uniform grid neighbour (candidates in the order left, right, up, down; nextBelow(count)), remembering only the last exit from each node (which erases the loops); then add the path: edges (u, next(u)) from the start to the tree, in that order. Draws come from the stream (seed, "wilson", 0). rows cols - 1 edges. Float64 node columns x = column and y = row. Expected cost is the mean hitting time of the root, about O(n log n) on a grid.
Parameters
options
WilsonMazeOptions
rows, cols and seed
Returns
SampleGraph
the undirected tree