facett-graph3d/src/dataset.rs
//! **Generated graph datasets with real STRUCTURE** — the thing a 3D graph viewer
//! needs to actually look like a graph.
//!
//! ## The problem this exists to solve
//!
//! Reported on the running demo: *"Graph3d looks nicely now, please fill it with
//! more data. Longer chains of data. The sphere only has data around the sphere
//! surface."*
//!
//! Both halves of that are one fact. [`crate::Layout3D::Force`] **seeds its nodes on
//! a Fibonacci sphere shell** and then relaxes them. What pulls a node off that
//! shell and into the interior is *topology*: a long path has to fold, a cycle has
//! to enclose something, a hub has to sit in the middle of the things it holds. A
//! dataset that is a bag of depth-1 stars — which is what the demo fed it — has no
//! such structure, so relaxation barely moves anything and every node stays at
//! radius ≈ 1. The pane was a shell because the *data* was a shell.
//!
//! So this is not a cosmetic layout tweak. It is a dataset with:
//!
//! | property | how | why it matters |
//! |---|---|---|
//! | **long chains** | `chains` backbones of `chain_len` nodes each | a path of 40 cannot lie on a shell; it is what creates real graph DIAMETER |
//! | **interior volume** | rungs cross-linking neighbouring backbones into cycles | a cycle has an inside; the relaxation puts nodes there |
//! | **varied degree** | side branches every `branch_every` nodes + `hubs` high-degree collectors | degree spans 1 … dozens instead of 1 … 2 |
//!
//! ## Determinism
//!
//! Demo data must be reproducible: the generator is a pure function of
//! [`GraphSpec`] (a `seed`, no wall clock, no RNG crate — a fixed SplitMix64), so
//! the same spec yields byte-identical nodes and edges on every machine and every
//! run. Pinned by `dataset_is_deterministic_over_repeats`.
//!
//! ## Size is a knob
//!
//! [`GraphSpec::sized`] scales to any node budget while holding `chain_len` at or
//! above [`MIN_CHAIN_LEN`], so "longer chains" is a *structural invariant at every
//! size* rather than a property of one hand-tuned fixture. Benched in
//! `benches/heavy_dataset.rs` at 1k → 100k.
use egui::Color32;
/// The shortest backbone this generator will ever emit, at any size. A chain this
/// long has a diameter no shell can accommodate, which is what forces the layout
/// to use its interior.
pub const MIN_CHAIN_LEN: usize = 24;
/// A deterministic **SplitMix64** — a fixed, dependency-free bit mixer. Used
/// instead of a RNG crate so the stream is stable across toolchains and platforms.
#[derive(Clone, Copy, Debug)]
struct Mix(u64);
impl Mix {
#[inline]
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)
}
/// A uniform `usize` in `0..n` (`0` for an empty range).
#[inline]
fn below(&mut self, n: usize) -> usize {
if n == 0 { 0 } else { (self.next_u64() % n as u64) as usize }
}
/// A uniform `f32` in `0..1`.
#[inline]
fn unit(&mut self) -> f32 {
(self.next_u64() >> 40) as f32 / (1u64 << 24) as f32
}
}
/// The shape of a generated dataset. Every field is a knob; [`GraphSpec::sized`]
/// derives a balanced set for a target node count.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct GraphSpec {
/// Number of long backbone chains.
pub chains: usize,
/// Nodes per backbone chain — the DEPTH knob. Never below [`MIN_CHAIN_LEN`].
pub chain_len: usize,
/// Sprout a side branch off every Nth backbone node (`0` = no branches).
pub branch_every: usize,
/// Nodes per side branch.
pub branch_len: usize,
/// Cross-links ("rungs") between neighbouring backbones. These are what turn a
/// forest into a graph with cycles — and a cycle is what has an *inside*.
pub rungs: usize,
/// High-degree collector nodes wired to many chain heads/tails — the degree
/// variance knob.
pub hubs: usize,
/// The seed. Same seed ⇒ byte-identical output.
pub seed: u64,
}
impl Default for GraphSpec {
fn default() -> Self {
Self::sized(4_000)
}
}
impl GraphSpec {
/// A balanced spec for approximately `nodes` nodes.
///
/// Chains grow in *count* with the budget while `chain_len` grows only slowly
/// (as the cube root) — so a bigger dataset gets **more** long chains rather
/// than a few absurd ones, and the diameter keeps rising. `chain_len` is
/// floored at [`MIN_CHAIN_LEN`], so even a tiny graph has real depth.
#[must_use]
pub fn sized(nodes: usize) -> Self {
let n = nodes.max(64);
let chain_len = MIN_CHAIN_LEN.max(((n as f64).cbrt() * 3.0) as usize);
// Branches inflate the node count ~1.6x over the backbones, so budget for it.
let branch_every = 6;
let branch_len = 3;
let per_chain = chain_len + (chain_len / branch_every) * branch_len;
let chains = (n / per_chain.max(1)).max(2);
Self {
chains,
chain_len,
branch_every,
branch_len,
// Enough rungs that neighbouring backbones are genuinely braided.
rungs: chains * (chain_len / 4).max(1),
hubs: (chains / 8).max(1),
seed: 0x5EED_1234_ABCD_9876,
}
}
/// Chainable seed override (for A/B fixtures that must differ).
#[must_use]
pub fn with_seed(mut self, seed: u64) -> Self {
self.seed = seed;
self
}
/// The exact node count this spec generates (no allocation).
#[must_use]
pub fn node_count(&self) -> usize {
let branches_per_chain = self.chain_len.checked_div(self.branch_every).unwrap_or(0);
self.chains * (self.chain_len + branches_per_chain * self.branch_len) + self.hubs
}
}
/// A generated dataset in exactly the form [`crate::Graph3D::new`] takes.
#[derive(Clone, Debug, Default)]
pub struct GeneratedGraph {
/// `(label, fill)` per node, in index order.
pub nodes: Vec<(String, Color32)>,
/// `(from, to)` index pairs.
pub edges: Vec<(usize, usize)>,
}
impl GeneratedGraph {
/// Per-node degree (undirected; self-loops are never generated).
#[must_use]
pub fn degrees(&self) -> Vec<u32> {
let mut d = vec![0u32; self.nodes.len()];
for &(a, b) in &self.edges {
d[a] += 1;
d[b] += 1;
}
d
}
/// A **lower bound on the graph's diameter**, by double sweep: BFS from node 0
/// to the farthest node, then BFS from there. Exact for a tree, a tight bound
/// otherwise — and it is the number that says "longer chains of data" is true,
/// so it is computed from the edge list rather than assumed from the spec.
#[must_use]
pub fn diameter_lower_bound(&self) -> usize {
if self.nodes.is_empty() {
return 0;
}
let mut adj: Vec<Vec<u32>> = vec![Vec::new(); self.nodes.len()];
for &(a, b) in &self.edges {
adj[a].push(b as u32);
adj[b].push(a as u32);
}
let bfs = |start: usize| -> (usize, usize) {
let mut dist = vec![usize::MAX; adj.len()];
let mut q = std::collections::VecDeque::new();
dist[start] = 0;
q.push_back(start);
let (mut far, mut fd) = (start, 0usize);
while let Some(v) = q.pop_front() {
if dist[v] > fd {
fd = dist[v];
far = v;
}
for &w in &adj[v] {
let w = w as usize;
if dist[w] == usize::MAX {
dist[w] = dist[v] + 1;
q.push_back(w);
}
}
}
(far, fd)
};
let (a, _) = bfs(0);
bfs(a).1
}
}
/// A small deterministic palette — hue keyed on the node's *role* so a chain reads
/// as one strand, its branches as offshoots, and a hub as a landmark.
fn role_color(role: u8, t: f32) -> Color32 {
let (r, g, b) = match role {
// backbone: cyan → teal along the chain
0 => (40.0 + 40.0 * t, 190.0 + 40.0 * t, 220.0 - 40.0 * t),
// branch: warm amber
1 => (240.0 - 30.0 * t, 170.0 + 40.0 * t, 70.0),
// hub: magenta landmark
_ => (230.0, 80.0 + 60.0 * t, 200.0),
};
Color32::from_rgb(r as u8, g as u8, b as u8)
}
/// **Generate the dataset.** Pure: identical output for identical `spec`.
///
/// Construction order (and therefore index order) is fixed: all backbones first, in
/// chain order with each node's branches immediately after the node they hang from,
/// then the hubs. A stable index order is what lets a golden assert the output at
/// all, and what keeps `Layout3D::Force`'s Fibonacci seeding reproducible.
#[must_use]
pub fn generate(spec: &GraphSpec) -> GeneratedGraph {
let mut rng = Mix(spec.seed);
let n_hint = spec.node_count();
let mut nodes: Vec<(String, Color32)> = Vec::with_capacity(n_hint);
let mut edges: Vec<(usize, usize)> = Vec::with_capacity(n_hint * 2);
// Backbone node indices per chain, so rungs and hubs can address them.
let mut backbone: Vec<Vec<usize>> = Vec::with_capacity(spec.chains);
for c in 0..spec.chains {
let mut spine: Vec<usize> = Vec::with_capacity(spec.chain_len);
for step in 0..spec.chain_len {
let t = step as f32 / spec.chain_len.max(2) as f32;
let idx = nodes.len();
nodes.push((format!("c{c}·{step}"), role_color(0, t)));
if let Some(&prev) = spine.last() {
edges.push((prev, idx)); // the CHAIN — depth
}
spine.push(idx);
// A side branch every Nth spine node: degree variance + more depth.
if spec.branch_every > 0 && step % spec.branch_every == spec.branch_every - 1 {
let mut from = idx;
for bstep in 0..spec.branch_len {
let bt = bstep as f32 / spec.branch_len.max(1) as f32;
let b = nodes.len();
nodes.push((format!("c{c}·{step}b{bstep}"), role_color(1, bt)));
edges.push((from, b));
from = b;
}
}
}
backbone.push(spine);
}
// ── RUNGS: braid neighbouring backbones into cycles ───────────────────────
// A forest of chains still relaxes onto a shell — nothing holds its middle.
// Linking chain c to chain c+1 at scattered depths creates cycles, and a cycle
// encloses volume: THIS is what fills the sphere's interior.
if spec.chains >= 2 {
for _ in 0..spec.rungs {
let c = rng.below(spec.chains);
let d = (c + 1 + rng.below(spec.chains - 1)) % spec.chains;
let a = backbone[c][rng.below(backbone[c].len())];
let b = backbone[d][rng.below(backbone[d].len())];
if a != b {
edges.push((a, b));
}
}
}
// ── HUBS: a few very-high-degree collectors ───────────────────────────────
// Degree variance is the third thing a shell has none of. Each hub grabs a
// deterministic scatter of backbone nodes across ALL chains, so it sits in the
// middle of what it holds rather than on the rim.
for h in 0..spec.hubs {
let hub = nodes.len();
nodes.push((format!("hub{h}"), role_color(2, rng.unit())));
let reach = (spec.chains * spec.chain_len / spec.hubs.max(1) / 4).clamp(4, 512);
for _ in 0..reach {
let c = rng.below(spec.chains);
let a = backbone[c][rng.below(backbone[c].len())];
edges.push((hub, a));
}
}
GeneratedGraph { nodes, edges }
}
#[cfg(test)]
mod tests {
use super::*;
/// **Determinism** — demo data must be reproducible, so the generator is a pure
/// function of the spec: no wall clock, no thread-order, no hash iteration.
#[test]
fn dataset_is_deterministic_over_repeats() {
let spec = GraphSpec::sized(3_000);
let first = generate(&spec);
for _ in 0..16 {
let g = generate(&spec);
assert_eq!(g.nodes.len(), first.nodes.len());
assert_eq!(g.edges, first.edges, "identical spec ⇒ identical edges");
for (a, b) in g.nodes.iter().zip(&first.nodes) {
assert_eq!(a, b, "identical spec ⇒ identical node labels + colours");
}
}
// …and a different seed really does differ (the seed is not decorative).
let other = generate(&spec.with_seed(0xDEAD_BEEF));
assert_ne!(other.edges, first.edges, "a different seed gives a different graph");
}
/// **"Longer chains of data."** The generated graph must have real DEPTH at
/// every size — asserted from the edge list (a BFS double sweep), not from the
/// spec that produced it.
#[test]
fn every_size_has_long_chains() {
for n in [500usize, 4_000, 30_000] {
let spec = GraphSpec::sized(n);
assert!(spec.chain_len >= MIN_CHAIN_LEN, "n={n}: chain_len {} ", spec.chain_len);
let g = generate(&spec);
let d = g.diameter_lower_bound();
assert!(
d >= 12,
"n={n}: the graph is DEEP (diameter ≥ 12), got {d} — a shell of stars has ~2"
);
}
}
/// **Varied degree.** A bag of depth-1 stars has degree 1 or 2 and nothing else.
#[test]
fn degree_is_varied_not_flat() {
let g = generate(&GraphSpec::sized(4_000));
let mut d = g.degrees();
assert!(!d.is_empty());
d.sort_unstable();
let median = d[d.len() / 2];
let max = *d.last().unwrap();
assert!(median >= 2, "the typical node is wired in, median degree {median}");
assert!(max >= median * 10, "there are real HUBS: max {max} vs median {median}");
assert!(d[0] >= 1, "no orphan nodes");
}
/// The size knob lands near the requested budget (within a factor), so a host
/// can ask for "about 30k" and get about 30k.
#[test]
fn sized_lands_near_the_requested_node_count() {
for n in [1_000usize, 10_000, 100_000] {
let spec = GraphSpec::sized(n);
let got = generate(&spec).nodes.len();
assert_eq!(got, spec.node_count(), "node_count() predicts the generator exactly");
assert!(
got >= n / 2 && got <= n * 2,
"asked for ~{n}, got {got}"
);
}
}
}