facett-graphview/src/generate.rs
//! **Seeded graph generators** — deterministic, pure Rust, no `rand`: the standard
//! synthetic graphs a graph pane is demoed and measured on, each with an **O(n)
//! structural placement** so a caller-laid-out canvas (`DecoratedGraphView`,
//! `facett-graphpan`, the instanced GPU cloud) can draw it at 100 000 or 1 000 000 nodes
//! without a force pass.
//!
//! | [`GenKind`] | shape |
//! |------------------|----------------------------------------------------------------------|
//! | `Community` | rings of √n nodes + a local chord + one long-range edge per 16 nodes — the graph `examples/layout_matrix.rs`, the GridLane parity test and the browser bench lay out |
//! | `Sbm` | stochastic block model: k blocks, 3 intra-block edges per node, 10 % inter-block |
//! | `Random` | Erdős–Rényi G(n, m) with m = 2n (mean degree 4) |
//! | `ScaleFree` | Barabási–Albert preferential attachment, m = 2 |
//! | `Grid` | a √n × √n 4-neighbour lattice |
//! | `Tree` | a complete ternary tree |
//! | `Crates` | the repo → crate → function world (≥ 136 nodes: whole crates) ([`crate::world::WorldGraph::synthetic`]) on its galaxy placement ([`crate::world::hier_placement`]) |
//!
//! Every generator is a pure function of `(kind, n, seed)`: the same three give the same
//! bytes on native and wasm (a SplitMix64 stream, integer arithmetic for every choice).
//! Positions land in `[-1, 1]²`; `group[i]` is a small categorical id (community, block,
//! depth, repo, degree class) a host colours by ([`group_rgb`]).
use crate::world::{hier_placement, Lod, WorldGraph};
/// Which generator. `ALL` is the display order a picker lists.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum GenKind {
Community,
Sbm,
Random,
ScaleFree,
Grid,
Tree,
Crates,
}
impl GenKind {
pub const ALL: [GenKind; 7] =
[GenKind::Community, GenKind::Sbm, GenKind::Random, GenKind::ScaleFree, GenKind::Grid, GenKind::Tree, GenKind::Crates];
/// Stable key (state_json, a robot's control).
#[must_use]
pub fn key(self) -> &'static str {
match self {
GenKind::Community => "community",
GenKind::Sbm => "sbm",
GenKind::Random => "random",
GenKind::ScaleFree => "scale-free",
GenKind::Grid => "grid",
GenKind::Tree => "tree",
GenKind::Crates => "crates",
}
}
/// Human label for a picker.
#[must_use]
pub fn label(self) -> &'static str {
match self {
GenKind::Community => "community rings",
GenKind::Sbm => "communities (SBM)",
GenKind::Random => "random (Erdos-Renyi)",
GenKind::ScaleFree => "scale-free (Barabasi-Albert)",
GenKind::Grid => "grid lattice",
GenKind::Tree => "tree (ternary)",
GenKind::Crates => "crates (repo / crate / fn)",
}
}
#[must_use]
pub fn from_key(k: &str) -> Option<GenKind> {
GenKind::ALL.into_iter().find(|g| g.key() == k)
}
}
/// A generated graph: index-space edges, a categorical group per node and an O(n)
/// placement in `[-1, 1]²`.
#[derive(Clone, Debug, PartialEq)]
pub struct Generated {
pub kind: GenKind,
pub seed: u64,
pub n: usize,
pub edges: Vec<(u32, u32)>,
pub group: Vec<u32>,
/// Number of distinct groups (`group[i] < groups`).
pub groups: u32,
pub pos: Vec<[f32; 2]>,
}
impl Generated {
/// A stable 64-bit fingerprint of the whole graph (edges, groups, positions) — the
/// determinism proof a test compares across two runs.
#[must_use]
pub fn fingerprint(&self) -> u64 {
let mut h: u64 = 0xcbf2_9ce4_8422_2325;
let mut eat = |v: u64| {
h ^= v;
h = h.wrapping_mul(0x0000_0100_0000_01b3);
};
eat(self.n as u64);
for &(a, b) in &self.edges {
eat(u64::from(a) << 32 | u64::from(b));
}
for &g in &self.group {
eat(u64::from(g));
}
for p in &self.pos {
eat(u64::from(p[0].to_bits()) << 32 | u64::from(p[1].to_bits()));
}
h
}
}
/// SplitMix64 — one u64 of state, identical on every target.
#[derive(Clone, Copy, Debug)]
pub struct SplitMix(u64);
impl SplitMix {
#[must_use]
pub fn new(seed: u64) -> Self {
Self(seed ^ 0x9e37_79b9_7f4a_7c15)
}
pub fn next_u64(&mut self) -> u64 {
self.0 = self.0.wrapping_add(0x9e37_79b9_7f4a_7c15);
let mut z = self.0;
z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
z ^ (z >> 31)
}
/// Uniform in `0..n` (n > 0), by 128-bit multiply (no modulo bias worth naming).
pub fn below(&mut self, n: usize) -> usize {
((u128::from(self.next_u64()) * n as u128) >> 64) as usize
}
/// Uniform in `[0, 1)`.
pub fn unit(&mut self) -> f32 {
(self.next_u64() >> 40) as f32 / (1u64 << 24) as f32
}
}
/// Generate `kind` with (about) `n` nodes from `seed`. `Crates` lands within a few
/// nodes of `n` (the hierarchy fills whole crates); every other kind is exact.
#[must_use]
pub fn generate(kind: GenKind, n: usize, seed: u64) -> Generated {
let n = n.max(1);
let mut rng = SplitMix::new(seed ^ (kind as u64).wrapping_mul(0x51_7cc1_b727_220a));
match kind {
GenKind::Community => community(n, &mut rng, seed),
GenKind::Sbm => sbm(n, &mut rng, seed),
GenKind::Random => random(n, &mut rng, seed),
GenKind::ScaleFree => scale_free(n, &mut rng, seed),
GenKind::Grid => grid(n, seed),
GenKind::Tree => tree(n, seed),
GenKind::Crates => crates(n, seed),
}
}
/// A categorical colour for group `g`: golden-angle hue steps at fixed saturation and
/// value, so neighbouring ids are far apart on the wheel.
#[must_use]
pub fn group_rgb(g: u32) -> [u8; 3] {
let h = (g as f32 * 137.507_77).rem_euclid(360.0);
hsv(h, 0.58, 0.92)
}
fn hsv(h: f32, s: f32, v: f32) -> [u8; 3] {
let c = v * s;
let hp = h / 60.0;
let x = c * (1.0 - (hp % 2.0 - 1.0).abs());
let (r, g, b) = match hp as u32 {
0 => (c, x, 0.0),
1 => (x, c, 0.0),
2 => (0.0, c, x),
3 => (0.0, x, c),
4 => (x, 0.0, c),
_ => (c, 0.0, x),
};
let m = v - c;
[((r + m) * 255.0) as u8, ((g + m) * 255.0) as u8, ((b + m) * 255.0) as u8]
}
/// Point `i` of `n` on a Vogel sunflower filling the unit disc (even density, O(1)).
fn sunflower(i: usize, n: usize) -> [f32; 2] {
let r = ((i as f32 + 0.5) / n.max(1) as f32).sqrt();
let a = i as f32 * 2.399_963_2;
[r * a.cos(), r * a.sin()]
}
/// Members of `count` groups of sizes `sizes`, packed as discs whose centres sit on a
/// sunflower: the shared placement of every clustered generator.
fn cluster_place(group: &[u32], groups: u32, rng: &mut SplitMix) -> Vec<[f32; 2]> {
let k = groups.max(1) as usize;
let mut size = vec![0usize; k];
for &g in group {
size[g as usize] += 1;
}
// Cell radius from the even spacing of k discs in the unit disc.
let cell = 0.9 / (k as f32).sqrt();
let mut seen = vec![0usize; k];
group
.iter()
.map(|&g| {
let g = g as usize;
// Centres pulled in by one disc radius so every member stays inside the box.
let c = if k == 1 { [0.0, 0.0] } else { sunflower(g, k) };
let c = [c[0] * (1.0 - cell * 0.8), c[1] * (1.0 - cell * 0.8)];
let j = seen[g];
seen[g] += 1;
let p = sunflower(j, size[g]);
// A small jitter keeps ring/lattice artefacts of the sunflower out of the disc.
let jx = (rng.unit() - 0.5) * 0.04;
let jy = (rng.unit() - 0.5) * 0.04;
[c[0] + (p[0] + jx) * cell * 0.8, c[1] + (p[1] + jy) * cell * 0.8]
})
.collect()
}
fn community(n: usize, rng: &mut SplitMix, seed: u64) -> Generated {
let c = (n as f64).sqrt().ceil() as usize;
let per = n.div_ceil(c).max(1);
let mut edges = Vec::with_capacity(n * 2 + n / 16);
let mut group = vec![0u32; n];
for k in 0..c {
let (lo, hi) = (k * per, ((k + 1) * per).min(n));
if hi <= lo {
break;
}
let len = hi - lo;
for (i, g) in group.iter_mut().enumerate().take(hi).skip(lo) {
*g = k as u32;
if len > 1 {
edges.push((i as u32, (lo + (i - lo + 1) % len) as u32));
}
if len > 3 {
edges.push((i as u32, (lo + (i - lo + 2 + rng.below(len - 2)) % len) as u32));
}
}
}
for i in (0..n).step_by(16) {
let j = rng.below(n);
if j != i {
edges.push((i as u32, j as u32));
}
}
let groups = group.iter().copied().max().unwrap_or(0) + 1;
// Each ring on its own circle (the ring order IS the edge order, so the picture
// shows the structure the edges have).
let k = groups as usize;
let cell = 0.9 / (k as f32).sqrt();
let pos = (0..n)
.map(|i| {
let g = group[i] as usize;
let (lo, hi) = (g * per, ((g + 1) * per).min(n));
let t = (i - lo) as f32 / (hi - lo).max(1) as f32 * std::f32::consts::TAU;
let c = if k == 1 { [0.0, 0.0] } else { sunflower(g, k) };
[c[0] + t.cos() * cell * 0.7, c[1] + t.sin() * cell * 0.7]
})
.collect();
Generated { kind: GenKind::Community, seed, n, edges, group, groups, pos }
}
fn sbm(n: usize, rng: &mut SplitMix, seed: u64) -> Generated {
let k = ((n as f64).sqrt() as usize / 4).clamp(2, 64).min(n);
let group: Vec<u32> = (0..n).map(|i| (i * k / n) as u32).collect();
let block = |b: usize| (b * n).div_ceil(k)..((b + 1) * n).div_ceil(k);
let mut edges = Vec::with_capacity(n * 3 + n / 10);
for (i, &g) in group.iter().enumerate() {
let r = block(g as usize);
let len = r.end - r.start;
if len > 1 {
for _ in 0..3 {
let j = r.start + rng.below(len);
if j != i {
edges.push((i as u32, j as u32));
}
}
}
if rng.below(10) == 0 {
let j = rng.below(n);
if j != i {
edges.push((i as u32, j as u32));
}
}
}
let groups = k as u32;
let pos = cluster_place(&group, groups, rng);
Generated { kind: GenKind::Sbm, seed, n, edges, group, groups, pos }
}
/// Degree class: `floor(log2(deg + 1))`, capped — the colour of an unclustered graph.
fn degree_classes(n: usize, edges: &[(u32, u32)]) -> (Vec<u32>, Vec<u32>, u32) {
let mut deg = vec![0u32; n];
for &(a, b) in edges {
deg[a as usize] += 1;
deg[b as usize] += 1;
}
let group: Vec<u32> = deg.iter().map(|&d| (32 - (d + 1).leading_zeros() - 1).min(11)).collect();
let groups = group.iter().copied().max().unwrap_or(0) + 1;
(deg, group, groups)
}
fn random(n: usize, rng: &mut SplitMix, seed: u64) -> Generated {
let m = if n > 1 { n * 2 } else { 0 };
let mut edges = Vec::with_capacity(m);
while edges.len() < m {
let (a, b) = (rng.below(n), rng.below(n));
if a != b {
edges.push((a as u32, b as u32));
}
}
let (_, group, groups) = degree_classes(n, &edges);
let pos = (0..n).map(|i| sunflower(i, n)).collect();
Generated { kind: GenKind::Random, seed, n, edges, group, groups, pos }
}
fn scale_free(n: usize, rng: &mut SplitMix, seed: u64) -> Generated {
const M: usize = 2;
let mut edges: Vec<(u32, u32)> = Vec::with_capacity(n * M);
// Every edge endpoint once: sampling it uniformly IS degree-proportional sampling.
let mut ends: Vec<u32> = Vec::with_capacity(n * M * 2);
let seedn = (M + 1).min(n);
for i in 0..seedn {
for j in 0..i {
edges.push((i as u32, j as u32));
ends.push(i as u32);
ends.push(j as u32);
}
}
for i in seedn..n {
let mut picked = [u32::MAX; M];
for slot in 0..M {
let mut t = ends[rng.below(ends.len())];
// Retry a duplicate target a few times (multi-edges are rare and harmless).
for _ in 0..4 {
if !picked.contains(&t) {
break;
}
t = ends[rng.below(ends.len())];
}
picked[slot] = t;
edges.push((i as u32, t));
}
for t in picked {
ends.push(i as u32);
ends.push(t);
}
}
let (deg, group, groups) = degree_classes(n, &edges);
// Hubs at the centre: rank by degree (stable on index), place by rank.
let mut order: Vec<u32> = (0..n as u32).collect();
order.sort_by(|&a, &b| deg[b as usize].cmp(°[a as usize]).then(a.cmp(&b)));
let mut pos = vec![[0.0f32; 2]; n];
for (rank, &i) in order.iter().enumerate() {
pos[i as usize] = sunflower(rank, n);
}
Generated { kind: GenKind::ScaleFree, seed, n, edges, group, groups, pos }
}
fn grid(n: usize, seed: u64) -> Generated {
let side = (n as f64).sqrt().ceil() as usize;
let mut edges = Vec::with_capacity(n * 2);
for i in 0..n {
let (r, c) = (i / side, i % side);
if c + 1 < side && i + 1 < n {
edges.push((i as u32, (i + 1) as u32));
}
if i + side < n {
edges.push((i as u32, (i + side) as u32));
}
let _ = r;
}
let bands = 8u32.min(side as u32).max(1);
let group = (0..n).map(|i| ((i / side) as u32 * bands / side.max(1) as u32).min(bands - 1)).collect();
let s = (side.max(2) - 1) as f32;
let pos = (0..n).map(|i| [((i % side) as f32 / s) * 2.0 - 1.0, ((i / side) as f32 / s) * 2.0 - 1.0]).collect();
Generated { kind: GenKind::Grid, seed, n, edges, group, groups: bands, pos }
}
fn tree(n: usize, seed: u64) -> Generated {
const B: usize = 3;
let edges: Vec<(u32, u32)> = (1..n).map(|i| (((i - 1) / B) as u32, i as u32)).collect();
// Depth d holds B^d nodes starting at (B^d − 1)/(B − 1).
let mut depth = vec![0u32; n];
for i in 1..n {
depth[i] = depth[(i - 1) / B] + 1;
}
let max_d = depth.last().copied().unwrap_or(0).max(1);
let pos = (0..n)
.map(|i| {
let d = depth[i] as usize;
let start = (B.pow(d as u32) - 1) / (B - 1);
let width = B.pow(d as u32);
let t = ((i - start) as f32 + 0.5) / width as f32 * std::f32::consts::TAU;
let r = d as f32 / max_d as f32;
[r * t.cos(), r * t.sin()]
})
.collect();
Generated { kind: GenKind::Tree, seed, n, edges, groups: max_d + 1, group: depth, pos }
}
fn crates(n: usize, seed: u64) -> Generated {
let w = WorldGraph::synthetic(n, Lod::Functions, true);
let pos = hier_placement(&w);
let groups = w.repo_count() as u32;
Generated { kind: GenKind::Crates, seed, n: w.n, edges: w.edges, group: w.repo_of, groups, pos }
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn every_kind_is_deterministic_per_seed_and_moves_with_it() {
for kind in GenKind::ALL {
let a = generate(kind, 2_000, 7);
let b = generate(kind, 2_000, 7);
assert_eq!(a.fingerprint(), b.fingerprint(), "{kind:?}: same seed, same graph");
assert_eq!(a.pos.len(), a.n);
assert_eq!(a.group.len(), a.n);
assert!(a.group.iter().all(|&g| g < a.groups), "{kind:?}: group ids in range");
assert!(a.edges.iter().all(|&(x, y)| (x as usize) < a.n && (y as usize) < a.n), "{kind:?}: edges in range");
assert!(a.pos.iter().all(|p| p[0].abs() <= 1.05 && p[1].abs() <= 1.05), "{kind:?}: placement in the box");
assert!(!a.edges.is_empty(), "{kind:?}: has edges");
// Structured, seed-free generators (grid, tree, crates) are the same for every
// seed; the sampled ones must change.
if matches!(kind, GenKind::Community | GenKind::Sbm | GenKind::Random | GenKind::ScaleFree) {
assert_ne!(a.fingerprint(), generate(kind, 2_000, 8).fingerprint(), "{kind:?}: seed moves it");
}
}
}
#[test]
fn sizes_are_honoured() {
for kind in GenKind::ALL {
for n in [100, 10_000] {
let g = generate(kind, n, 1);
if kind == GenKind::Crates {
// Whole crates: within 10 % at scale; at 100 the hierarchy's floor
// (8 repos × 8 crates, one fn each) is 136 nodes.
let tol = if n >= 10_000 { n / 10 } else { 40 };
assert!(g.n.abs_diff(n) <= tol, "{kind:?} n={n}: got {}", g.n);
} else {
assert_eq!(g.n, n, "{kind:?}");
}
}
}
}
#[test]
fn scale_free_has_hubs_and_random_does_not() {
let deg_max = |g: &Generated| {
let mut d = vec![0u32; g.n];
for &(a, b) in &g.edges {
d[a as usize] += 1;
d[b as usize] += 1;
}
d.into_iter().max().unwrap()
};
let ba = generate(GenKind::ScaleFree, 20_000, 3);
let er = generate(GenKind::Random, 20_000, 3);
assert!(deg_max(&ba) > 4 * deg_max(&er), "BA hub {} vs ER max {}", deg_max(&ba), deg_max(&er));
}
}