facett-graphnav/src/layout.rs
//! The **layout switcher** — the deterministic 2D layouts a graph-DB IDE offers:
//! grid, circular, hierarchical (layered by BFS depth), radial, force-directed
//! (Fruchterman–Reingold, seeded from the circular layout so it's reproducible) and
//! **geographic** (the node's real place on the host's map plane). Each maps node
//! indices → world positions in a normalised `[-1, 1]²` box.
use serde::{Deserialize, Serialize};
/// The layout algorithm the canvas arranges nodes with.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub enum LayoutKind {
Grid,
Circular,
Hierarchical,
Force,
/// **Radial** — BFS depth from the roots maps to a concentric ring (depth = radius),
/// nodes spread by angle within their ring. The circular sibling of
/// [`LayoutKind::Hierarchical`]: a root-centred tree that reads outward, the classic
/// gdotv radial layout for provenance/dependency DAGs.
Radial,
/// **Geographic** — every node sits where it actually *is*. Not an algorithm over
/// the edge list at all: the host supplies one [`Place`] per node (a point on ITS
/// OWN map plane, already projected), and this layout only fits that point set into
/// the `[-1, 1]²` box **at a single uniform scale**, so a road network draws as a
/// road network instead of a hairball.
///
/// **This crate deliberately owns no projection.** Taking lon/lat here would mean a
/// second Web-Mercator beside the host's map, and two projections that disagree by a
/// metre is a defect waiting; the host projects through the one its map already uses
/// and hands the plane over. That is why this variant is **not in [`ALL`]**: it is
/// data-gated, not a switcher choice — [`places_cover`] is the one answer to "can
/// this scene be laid out geographically", and without places it falls back to
/// [`LayoutKind::Force`].
///
/// [`ALL`]: LayoutKind::ALL
Geographic,
}
impl LayoutKind {
/// The stable lowercase key + the ordered switcher list.
#[must_use]
pub fn key(self) -> &'static str {
match self {
LayoutKind::Grid => "grid",
LayoutKind::Circular => "circular",
LayoutKind::Hierarchical => "hierarchical",
LayoutKind::Force => "force",
LayoutKind::Radial => "radial",
LayoutKind::Geographic => "geographic",
}
}
/// The **switchable** layouts, in switcher order — the ones ANY graph can be put
/// into, because they need nothing but `n` and the edge list. [`Geographic`] is
/// absent on purpose: offering a chip that draws a blank for every graph without
/// coordinates would be a lie. See [`EVERY`](LayoutKind::EVERY).
///
/// [`Geographic`]: LayoutKind::Geographic
pub const ALL: [LayoutKind; 5] =
[LayoutKind::Force, LayoutKind::Hierarchical, LayoutKind::Radial, LayoutKind::Circular, LayoutKind::Grid];
/// **Every** layout, the data-gated ones included. [`ALL`](LayoutKind::ALL) is what
/// the switcher offers; this is what exists.
pub const EVERY: [LayoutKind; 6] = [
LayoutKind::Force,
LayoutKind::Hierarchical,
LayoutKind::Radial,
LayoutKind::Circular,
LayoutKind::Grid,
LayoutKind::Geographic,
];
/// **Does this layout need a [`Place`] per node** (rather than deriving position
/// from the edge list alone)? The one property that separates
/// [`EVERY`](LayoutKind::EVERY) from [`ALL`](LayoutKind::ALL).
#[must_use]
pub fn needs_places(self) -> bool {
matches!(self, LayoutKind::Geographic)
}
/// Parse from a key (`state_json` round-trip / robot control). Reads
/// [`EVERY`](LayoutKind::EVERY), so a layout is parseable even when the switcher
/// does not offer it.
#[must_use]
pub fn from_key(k: &str) -> Option<LayoutKind> {
LayoutKind::EVERY.into_iter().find(|l| l.key() == k)
}
}
/// **One node's place on the host's map plane** — an `[x, y]` the CALLER already
/// projected with its own map projection, or `None` for a node that is nowhere.
///
/// Deliberately not lon/lat: see [`LayoutKind::Geographic`]. The units are the host's;
/// [`geographic`] only ever takes differences and one uniform scale, so any linear
/// planar projection works and the drawn shape is the map's shape.
pub type Place = Option<[f64; 2]>;
/// **THE ONE ANSWER to "can this scene be laid out geographically".** Every node — not
/// most — must carry a place, because a geographic layout with holes in it puts nodes
/// somewhere they are not, and a road network is judged by its shape.
///
/// Used by the host's derivation *and* by [`layout_with`]'s fallback, so the two can
/// never disagree about whether the geographic lane was available.
#[must_use]
pub fn places_cover(n: usize, places: &[Place]) -> bool {
n > 0 && places.len() >= n && places[..n].iter().all(Option::is_some)
}
/// Lay out `n` nodes (with directed `edges` by index) under `kind`, returning
/// `[x, y]` per node in the `[-1, 1]²` box. Deterministic — no RNG.
///
/// The place-free entry point: [`LayoutKind::Geographic`] has nothing to place with
/// here and falls back to [`LayoutKind::Force`]. Callers that hold coordinates want
/// [`layout_with`].
#[must_use]
pub fn layout(kind: LayoutKind, n: usize, edges: &[(usize, usize)]) -> Vec<[f32; 2]> {
layout_with(kind, n, edges, &[])
}
/// [`layout`] with the host's per-node [`Place`] column — the entry point
/// [`LayoutKind::Geographic`] needs.
///
/// `places` is ignored by every other layout, so a host can pass its coordinate column
/// unconditionally. When `kind` is geographic and [`places_cover`] is false, this falls
/// back to [`LayoutKind::Force`] and the caller keeps today's behaviour exactly; ask
/// [`places_cover`] first if you need to *report* which lane ran.
#[must_use]
pub fn layout_with(
kind: LayoutKind,
n: usize,
edges: &[(usize, usize)],
places: &[Place],
) -> Vec<[f32; 2]> {
match kind {
LayoutKind::Grid => grid(n),
LayoutKind::Circular => circular(n),
LayoutKind::Hierarchical => hierarchical(n, edges),
LayoutKind::Force => force_selected(n, edges),
LayoutKind::Radial => radial(n, edges),
LayoutKind::Geographic => {
if places_cover(n, places) {
geographic(n, places)
} else {
force_selected(n, edges)
}
}
}
}
/// The fraction of the `[-1, 1]²` box the geographic fit uses — the same 0.9 margin
/// [`grid`] and [`circular`] leave, so a scene does not touch the pane edge.
const GEO_FILL: f64 = 0.9;
/// **Place every node where it is.** The host's plane, centred on its own bounding box
/// and scaled by ONE factor — `2·GEO_FILL / max(span_x, span_y)` — into `[-1, 1]²`.
///
/// The single scale is the whole point. A per-axis fit would stretch the drawing to the
/// pane and Sweden would come out short and fat; with one factor the picture is the
/// map's picture, and the ratio between any two node distances is the ratio between the
/// real ones (exactly, on the plane the host handed over). That is what
/// `two_junctions_ten_times_apart_land_ten_times_apart` asserts, and what a force
/// layout cannot pass.
///
/// Y is NOT flipped: a Web-Mercator plane already grows southward, which is the same
/// direction the canvas's `+y` grows, so north comes out up. A host whose plane grows
/// northward must negate `y` before calling — the layout takes the plane as given.
///
/// A degenerate set (every node in one spot, or one node) collapses to the origin
/// rather than dividing by a zero span.
#[must_use]
pub fn geographic(n: usize, places: &[Place]) -> Vec<[f32; 2]> {
if n == 0 {
return Vec::new();
}
let mut b: Option<(f64, f64, f64, f64)> = None;
for p in places.iter().take(n).flatten() {
let (x, y) = (p[0], p[1]);
b = Some(match b {
None => (x, y, x, y),
Some((x0, y0, x1, y1)) => (x0.min(x), y0.min(y), x1.max(x), y1.max(y)),
});
}
let Some((x0, y0, x1, y1)) = b else { return vec![[0.0; 2]; n] };
let (cx, cy) = ((x0 + x1) * 0.5, (y0 + y1) * 0.5);
let span = (x1 - x0).max(y1 - y0);
// Every node in one place: no scale can separate them, so say so by collapsing to
// the centre instead of dividing by ~0 and printing infinities.
let s = if span > 1e-12 { 2.0 * GEO_FILL / span } else { 0.0 };
// ALWAYS `n` entries, whatever the column's length: every caller indexes this by
// node index, and a short answer would silently drop the tail of the graph.
(0..n)
.map(|i| match places.get(i).copied().flatten() {
Some([x, y]) => [((x - cx) * s) as f32, ((y - cy) * s) as f32],
None => [0.0, 0.0],
})
.collect()
}
/// BFS depth from the roots → a concentric ring (radius grows with depth); nodes at the
/// same depth spread evenly by angle. Root(s) sit near the centre.
fn radial(n: usize, edges: &[(usize, usize)]) -> Vec<[f32; 2]> {
if n == 0 {
return Vec::new();
}
let depth = bfs_depth(n, edges);
let max_depth = *depth.iter().max().unwrap_or(&0);
// Bucket node indices per depth ring.
let mut rings: Vec<Vec<usize>> = vec![Vec::new(); max_depth + 1];
for (i, &d) in depth.iter().enumerate() {
rings[d].push(i);
}
let mut out = vec![[0.0f32; 2]; n];
for (d, ring) in rings.iter().enumerate() {
// Radius grows with depth; a lone root ring sits at the centre.
let r = if max_depth > 0 { 0.9 * d as f32 / max_depth as f32 } else { 0.0 };
let count = ring.len().max(1);
for (k, &i) in ring.iter().enumerate() {
if d == 0 && ring.len() == 1 {
out[i] = [0.0, 0.0]; // single root at the centre
} else {
let a = std::f32::consts::TAU * k as f32 / count as f32;
out[i] = [r * a.cos(), r * a.sin()];
}
}
}
out
}
/// Shared BFS depth from the roots (in-degree 0, or node 0 if fully cyclic); unreached
/// nodes fall to depth 0. The layered backbone of both hierarchical + radial.
fn bfs_depth(n: usize, edges: &[(usize, usize)]) -> Vec<usize> {
let mut indeg = vec![0usize; n];
let mut out_adj = vec![Vec::new(); n];
for &(a, b) in edges {
if a < n && b < n {
out_adj[a].push(b);
indeg[b] += 1;
}
}
let mut depth = vec![usize::MAX; n];
let mut queue: std::collections::VecDeque<usize> = (0..n).filter(|&i| indeg[i] == 0).collect();
if queue.is_empty() {
queue.push_back(0);
}
for &r in &queue {
depth[r] = 0;
}
while let Some(v) = queue.pop_front() {
let d = depth[v];
for &w in &out_adj[v] {
if depth[w] == usize::MAX {
depth[w] = d + 1;
queue.push_back(w);
}
}
}
for d in depth.iter_mut() {
if *d == usize::MAX {
*d = 0;
}
}
depth
}
/// Square-ish grid, row-major, centred.
fn grid(n: usize) -> Vec<[f32; 2]> {
if n == 0 {
return Vec::new();
}
let cols = (n as f32).sqrt().ceil() as usize;
let rows = n.div_ceil(cols);
let mut out = Vec::with_capacity(n);
for i in 0..n {
let (c, r) = (i % cols, i / cols);
let x = if cols > 1 { -1.0 + 2.0 * c as f32 / (cols - 1) as f32 } else { 0.0 };
let y = if rows > 1 { -1.0 + 2.0 * r as f32 / (rows - 1) as f32 } else { 0.0 };
out.push([x * 0.9, y * 0.9]);
}
out
}
/// Evenly spaced on a circle.
fn circular(n: usize) -> Vec<[f32; 2]> {
(0..n)
.map(|i| {
let a = std::f32::consts::TAU * i as f32 / n.max(1) as f32;
[0.85 * a.cos(), 0.85 * a.sin()]
})
.collect()
}
/// Layered by BFS depth from the roots (in-degree 0, or node 0 if none). Depth sets
/// the row (y); index within the row spreads across x.
fn hierarchical(n: usize, edges: &[(usize, usize)]) -> Vec<[f32; 2]> {
if n == 0 {
return Vec::new();
}
let depth = bfs_depth(n, edges);
let max_depth = *depth.iter().max().unwrap_or(&0);
// Bucket indices per depth.
let mut rows: Vec<Vec<usize>> = vec![Vec::new(); max_depth + 1];
for (i, &d) in depth.iter().enumerate() {
rows[d].push(i);
}
let mut out = vec![[0.0f32; 2]; n];
for (d, row) in rows.iter().enumerate() {
let y = if max_depth > 0 { -0.85 + 1.7 * d as f32 / max_depth as f32 } else { 0.0 };
for (k, &i) in row.iter().enumerate() {
let x = if row.len() > 1 { -0.85 + 1.7 * k as f32 / (row.len() - 1) as f32 } else { 0.0 };
out[i] = [x, y];
}
}
out
}
/// **Fruchterman–Reingold** force layout, seeded from the circular layout so it's
/// deterministic. Repulsion between all pairs + attraction along edges, cooled over a
/// fixed schedule, then re-normalised into the `[-1, 1]²` box.
///
/// Above [`facett_core::barnes_hut::BH_THRESHOLD`] the O(n²) all-pairs repulsion (the
/// 30 000-node killer) is swapped for the shared Barnes–Hut O(n log n) kernel, AND the
/// whole step — repulsion + attraction + integrate — runs across **every core** via the
/// [`fr_step`](facett_core::barnes_hut::fr_step) gatling fork-join lane (the CPU lane of
/// the two-lane layout). Below the threshold the exact serial loop runs so the
/// determinism/golden tests stay byte-identical. Everything else — the circular seed,
/// the cooling schedule, the normalisation — is shared by both paths.
///
/// The parallel lane is the deterministic **reference**: the gatling attraction is a
/// per-node *gather* (fixed neighbour order), so it reproduces the serial per-edge
/// scatter within float tolerance and is byte-stable for any worker count.
fn force(n: usize, edges: &[(usize, usize)]) -> Vec<[f32; 2]> {
force_directed(n, edges, CpuLane::Gatling)
}
/// GPU-lane convergence budget (velocity-integrated Hooke/FR steps in VRAM). The
/// velocity+damping model settles much faster than the CPU lane's overdamped FR: the
/// total edge length is within ~5 % of fully-converged by ~60–80 steps (measured), so
/// 80 is a converged-yet-snappy budget — ~290 ms of warm VRAM iterate at 30k on a 5080.
#[cfg(feature = "gpu")]
pub const FORCE_ITERS_GPU: usize = 80;
/// **Two-lane layout selector** — the runtime pick between the GPU and CPU force lanes.
/// When the crate is built with the `gpu` feature AND a usable wgpu adapter is present
/// at runtime, a large graph is laid out on the GPU (`cs_layout` iterating in VRAM);
/// otherwise it falls through to the CPU gatling lane. The CPU lane is always compiled
/// and is the deterministic golden path (so the default, GPU-less build + every
/// determinism/golden test runs it unchanged).
/// # In the WHEEL this arm does not exist, and the browser pays for it
///
/// MEASURED by reading the build, 2026-09-18: `facet-wrapped` names this crate with
/// no features, and `gpu` is `default = []` — so `#[cfg(feature = "gpu")]` below is
/// compiled OUT of the wasm bundle and every graph takes the CPU lane. On wasm32
/// that lane is **single-threaded**: `available_parallelism()` is `Err(Unsupported)`,
/// gatling resolves to one worker and runs inline (correctly, and silently).
///
/// The compute shader that would fix it IS in that bundle — `facet-wrapped` names
/// `facett-graphview` with `features = ["gpu"]`, so `cs_layout` ships and cannot be
/// dispatched. It would not run as written anyway: `gpu_layout` acquires its own
/// device with `pollster::block_on`, which on the browser's main thread is a
/// deadlock rather than a slow path, while the app already holds an eframe WebGPU
/// device it never offers. Scoped in `.nornir/gpu-prep-in-the-browser.md`.
fn force_selected(n: usize, edges: &[(usize, usize)]) -> Vec<[f32; 2]> {
// NOT on wasm32. `force_layout_gpu` acquires a device with `pollster::block_on`,
// and blocking a browser's main thread on a promise is a deadlock. The browser's
// GPU lane is the non-blocking `LayoutJob` on the host's borrowed device, selected
// one level up in `GraphNav::positions` — by the time control reaches here on
// wasm, the answer is the CPU lane.
#[cfg(all(feature = "gpu", not(target_arch = "wasm32")))]
{
// Only worth the upload/dispatch for graphs at scale; tiny graphs stay on the
// exact CPU path (keeps small goldens on the reference lane).
if n >= facett_core::barnes_hut::BH_THRESHOLD
&& let Some(pos) = facett_graphview::gpu_layout::force_layout_gpu(n, edges, FORCE_ITERS_GPU)
{
return pos;
}
}
force(n, edges)
}
/// Number of cooling iterations the FR driver runs. Exposed so the benchmark reports
/// the same convergence budget the live layout uses.
pub const FORCE_ITERS: usize = 120;
/// Which CPU lane [`force_directed`] runs — the benchmark's two comparison points.
#[doc(hidden)]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum CpuLane {
/// The honest **single-core** baseline: serial Barnes–Hut build + serial per-node
/// query + serial attraction scatter + serial integrate — no gatling anywhere.
Serial,
/// The shipped **gatling** lane: the whole step fanned across every core (parallel
/// forest build, then a fused repulsion+attraction+integrate pass) — attraction as a
/// per-node GATHER.
Gatling,
/// The **scatter-reduce** lane: attraction expressed as a parallel scatter-reduce over
/// edges via the znippy `gatling_reduce` fold primitive (private per-worker disp
/// buffers, deterministically merged). Benchmarked against `Gatling`; the gather wins
/// (fused single pass), so this is the comparison lane, not the shipped default.
GatlingScatter,
}
/// The FR force layout with the CPU lane selectable — [`CpuLane::Gatling`] fans the
/// whole step across all cores (the shipped path at scale); [`CpuLane::Serial`] is the
/// single-core baseline the benchmark measures the speedup against. Below
/// [`facett_core::barnes_hut::BH_THRESHOLD`] both collapse to the identical exact serial
/// loop, so small-graph goldens are untouched either way.
#[doc(hidden)]
#[must_use]
pub fn force_directed(n: usize, edges: &[(usize, usize)], lane: CpuLane) -> Vec<[f32; 2]> {
if n == 0 {
return Vec::new();
}
let mut pos = circular(n);
let k = (4.0 / n as f32).sqrt(); // ideal edge length in the [-1,1]² area
let iters = FORCE_ITERS;
let theta = facett_core::barnes_hut::BH_THETA;
let use_bh = n >= facett_core::barnes_hut::BH_THRESHOLD;
// Fully-parallel lane: build the neighbour lists once, then each iteration is two
// core-saturating gatling passes (parallel forest build, then a fused
// repulsion+attraction+integrate pass).
if use_bh && lane == CpuLane::Gatling {
let adj = facett_core::barnes_hut::adjacency(n, edges);
for it in 0..iters {
let temp = 0.1 * (1.0 - it as f32 / iters as f32); // cooling
pos = facett_core::barnes_hut::fr_step::<2>(&pos, &adj, k, theta, temp);
}
facett_core::barnes_hut::normalize_box(&mut pos);
return pos;
}
// Scatter-reduce lane: attraction via the znippy `gatling_reduce` fold over edges.
if use_bh && lane == CpuLane::GatlingScatter {
for it in 0..iters {
let temp = 0.1 * (1.0 - it as f32 / iters as f32); // cooling
pos = facett_core::barnes_hut::fr_step_scatter::<2>(&pos, edges, k, theta, temp);
}
facett_core::barnes_hut::normalize_box(&mut pos);
return pos;
}
// Serial lane (single-core baseline / small-graph exact path) — the serial mirror of
// the gatling step lives once in core (`fr_step_serial`: exact all-pairs below the BH
// threshold, serial Barnes–Hut above, per-node attraction gather, temp-capped
// integrate). Same cooling schedule and box-fit as both parallel lanes above.
let adj = facett_core::barnes_hut::adjacency(n, edges);
for it in 0..iters {
let temp = 0.1 * (1.0 - it as f32 / iters as f32); // cooling
pos = facett_core::barnes_hut::fr_step_serial::<2>(&pos, &adj, k, theta, temp);
}
facett_core::barnes_hut::normalize_box(&mut pos);
pos
}
/// World-space bounds `(min_x, min_y, max_x, max_y)` of a position set (for the
/// minimap + camera fit). `None` when empty.
#[must_use]
pub fn bounds(pos: &[[f32; 2]]) -> Option<(f32, f32, f32, f32)> {
let mut it = pos.iter();
let f = it.next()?;
let mut b = (f[0], f[1], f[0], f[1]);
for p in it {
b.0 = b.0.min(p[0]);
b.1 = b.1.min(p[1]);
b.2 = b.2.max(p[0]);
b.3 = b.3.max(p[1]);
}
Some(b)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn every_layout_positions_every_node_in_the_box() {
let n = 8;
let edges = vec![(0, 1), (1, 2), (2, 3), (4, 5), (5, 6), (3, 4)];
for kind in LayoutKind::ALL {
let pos = layout(kind, n, &edges);
assert_eq!(pos.len(), n, "{} places every node", kind.key());
for p in &pos {
assert!(p[0].abs() <= 1.01 && p[1].abs() <= 1.01, "{} keeps nodes in the box: {p:?}", kind.key());
assert!(p[0].is_finite() && p[1].is_finite());
}
}
}
#[test]
fn layouts_are_deterministic() {
let edges = vec![(0, 1), (1, 2), (2, 0), (2, 3)];
for kind in LayoutKind::ALL {
assert_eq!(layout(kind, 4, &edges), layout(kind, 4, &edges), "{} is deterministic", kind.key());
}
}
#[test]
fn hierarchical_puts_roots_above_leaves() {
// 0 → 1 → 2: a chain, so depth increases and y increases.
let pos = hierarchical(3, &[(0, 1), (1, 2)]);
assert!(pos[0][1] < pos[1][1] && pos[1][1] < pos[2][1], "depth maps to y: {pos:?}");
}
#[test]
fn radial_grows_radius_with_depth() {
// 0 → 1 → 2: the root sits at the centre; radius increases with BFS depth.
let pos = radial(3, &[(0, 1), (1, 2)]);
let r = |p: [f32; 2]| (p[0] * p[0] + p[1] * p[1]).sqrt();
assert!(r(pos[0]) < 1e-4, "single root is centred");
assert!(r(pos[1]) < r(pos[2]), "deeper nodes sit on outer rings: {pos:?}");
assert!(r(pos[2]) <= 0.91, "outermost ring stays in the box");
}
/// A deterministic sparse graph well above the Barnes–Hut threshold — a ring of
/// triangles wired into a chain, so every node has incident edges (real attraction).
fn ring_graph(triangles: usize) -> (usize, Vec<(usize, usize)>) {
let n = triangles * 3;
let mut edges = Vec::new();
for t in 0..triangles {
let (a, b, c) = (t * 3, t * 3 + 1, t * 3 + 2);
edges.push((a, b));
edges.push((b, c));
edges.push((c, a));
edges.push((a, (a + 3) % n)); // chain to the next triangle
}
(n, edges)
}
/// One serial FR displacement + temperature-capped integrate (the exact large-`n`
/// reference: parallel Barnes–Hut repulsion, then the serial per-edge attraction
/// scatter, then the serial applier). The parity target for [`fr_step`].
fn serial_fr_step(pos: &[[f32; 2]], edges: &[(usize, usize)], k: f32, temp: f32) -> Vec<[f32; 2]> {
let n = pos.len();
let mut disp = facett_core::barnes_hut::repulsion_forces::<2>(pos, k, facett_core::barnes_hut::BH_THETA);
for &(a, b) in edges {
if a >= n || b >= n || a == b {
continue;
}
let dx = pos[a][0] - pos[b][0];
let dy = pos[a][1] - pos[b][1];
let dist = (dx * dx + dy * dy).sqrt().max(1e-3);
let f = dist * dist / k;
let (ux, uy) = (dx / dist, dy / dist);
disp[a][0] -= ux * f;
disp[a][1] -= uy * f;
disp[b][0] += ux * f;
disp[b][1] += uy * f;
}
let mut out = pos.to_vec();
for i in 0..n {
let d = (disp[i][0] * disp[i][0] + disp[i][1] * disp[i][1]).sqrt().max(1e-3);
let cap = d.min(temp);
out[i][0] += disp[i][0] / d * cap;
out[i][1] += disp[i][1] / d * cap;
}
out
}
/// **RED-when-broken (parallel-attraction reduction is correct):** ONE gatling
/// [`fr_step`](facett_core::barnes_hut::fr_step) (parallel repulsion + per-node
/// attraction *gather* + parallel integrate) must equal ONE serial FR step to float
/// tolerance. This isolates the reduction from the 120-iteration chaotic
/// amplification (FR is a sensitive map, so a full run's per-node positions drift
/// under any summation-order change — that is physics, not a bug): a single step
/// only reorders the attraction sum, so it stays tight. A buggy gather (wrong sign,
/// dropped/duplicated neighbour, aliased write) diverges even one step and trips this.
#[test]
fn parallel_fr_step_matches_serial_within_tolerance() {
let (n, edges) = ring_graph(1200); // 3600 nodes, > BH_THRESHOLD
assert!(n >= facett_core::barnes_hut::BH_THRESHOLD, "exercise the parallel BH lane");
let pos = circular(n);
let k = (4.0 / n as f32).sqrt();
let temp = 0.1;
let adj = facett_core::barnes_hut::adjacency(n, &edges);
let par = facett_core::barnes_hut::fr_step::<2>(&pos, &adj, k, facett_core::barnes_hut::BH_THETA, temp);
let ser = serial_fr_step(&pos, &edges, k, temp);
assert_eq!(par.len(), ser.len());
let mut max_err = 0.0f32;
for (p, s) in par.iter().zip(&ser) {
max_err = max_err.max((p[0] - s[0]).abs()).max((p[1] - s[1]).abs());
}
assert!(max_err < 1e-4, "one parallel FR step == one serial FR step; max_err={max_err}");
}
/// **RED-when-broken (full-run topology parity):** across the whole 120-iteration
/// converge, the parallel CPU lane must produce a layout with the SAME global shape
/// as the serial baseline — both fit the `[-1,1]²` box and their bounding-box aspect
/// ratios agree closely. (Per-node positions legitimately drift under float-reorder
/// chaos, so this asserts the invariant that survives: topology/extent, not points.)
/// A broken attraction (edges not contracting) collapses or explodes the box and
/// trips the aspect check.
#[test]
fn parallel_force_full_run_topology_matches_serial() {
let (n, edges) = ring_graph(1200);
let serial = force_directed(n, &edges, CpuLane::Serial);
let parallel = force_directed(n, &edges, CpuLane::Gatling);
let aspect = |p: &[[f32; 2]]| {
let b = bounds(p).unwrap();
(b.2 - b.0) / (b.3 - b.1).max(1e-6)
};
for p in parallel.iter().chain(&serial) {
assert!(p[0].abs() <= 1.01 && p[1].abs() <= 1.01, "both lanes stay in the box");
}
let (sa, pa) = (aspect(&serial), aspect(¶llel));
assert!((sa - pa).abs() / sa.max(1e-6) < 0.15, "same layout extent/aspect (serial {sa} vs parallel {pa})");
}
/// **RED-when-broken (determinism):** the gatling CPU lane is byte-identical run to
/// run regardless of worker count (the property `layouts_are_deterministic` and the
/// freeze-cache goldens depend on). A non-deterministic reduction trips this.
#[test]
fn parallel_force_is_deterministic() {
let (n, edges) = ring_graph(900); // 2700 nodes, > BH_THRESHOLD
let a = force_directed(n, &edges, CpuLane::Gatling);
let b = force_directed(n, &edges, CpuLane::Gatling);
assert_eq!(a, b, "parallel CPU force lane is deterministic (byte-identical)");
}
#[test]
fn circular_is_on_a_circle() {
let pos = circular(6);
for p in &pos {
let r = (p[0] * p[0] + p[1] * p[1]).sqrt();
assert!((r - 0.85).abs() < 1e-4, "on the r=0.85 circle");
}
}
#[test]
fn key_roundtrips() {
for kind in LayoutKind::EVERY {
assert_eq!(LayoutKind::from_key(kind.key()), Some(kind));
}
assert_eq!(LayoutKind::from_key("nope"), None);
}
/// The switcher offers only the layouts that work on ANY graph; `EVERY` is the
/// full roster. A data-gated layout that leaked into `ALL` would paint a chip that
/// draws a blank for most graphs.
#[test]
fn the_switcher_offers_only_what_needs_no_data() {
assert!(LayoutKind::ALL.iter().all(|k| !k.needs_places()));
assert!(LayoutKind::EVERY.iter().any(|k| k.needs_places()));
for k in LayoutKind::ALL {
assert!(LayoutKind::EVERY.contains(&k), "{k:?} missing from EVERY");
}
}
/// **THE GATE the force layout cannot pass.** Three points on one line of latitude
/// at 59.33 °N: A→B is 0.01° of longitude, B→C is 0.10° — ten times as far on the
/// ground. Laid out geographically, the drawn distances must hold the same 10:1.
///
/// The comparison is against the FORCE layout on the same three nodes, which is
/// driven by the edge list and knows nothing about where anything is — it lands
/// them on a circle-seeded blob and the ratio is nowhere near 10.
#[test]
fn ten_times_apart_on_the_ground_is_ten_times_apart_on_the_canvas() {
// A tiny stand-in for korp's `mapquery::merc_xy` — the host projects, the
// layout only fits. At one latitude, Mercator x is linear in longitude, so the
// ground ratio survives exactly.
let merc = |lon: f64, lat: f64| -> [f64; 2] {
let r: f64 = lat.to_radians();
[(lon + 180.0) / 360.0, (1.0 - (r.tan() + 1.0 / r.cos()).ln() / std::f64::consts::PI) / 2.0]
};
let lat = 59.3293;
let places: Vec<Place> =
vec![Some(merc(18.00, lat)), Some(merc(18.01, lat)), Some(merc(18.11, lat))];
let edges = [(0usize, 1usize), (1, 2)];
let d = |p: &[[f32; 2]], i: usize, j: usize| -> f64 {
let (a, b) = (p[i], p[j]);
(f64::from(a[0] - b[0]).powi(2) + f64::from(a[1] - b[1]).powi(2)).sqrt()
};
let geo = layout_with(LayoutKind::Geographic, 3, &edges, &places);
let ratio = d(&geo, 1, 2) / d(&geo, 0, 1);
assert!(
(ratio - 10.0).abs() < 0.05,
"geographic must keep the 10:1 ground ratio, got {ratio:.4}"
);
// RED PROOF, in the test itself: the layout this replaces cannot do it.
let force = layout_with(LayoutKind::Force, 3, &edges, &places);
let fratio = d(&force, 1, 2) / d(&force, 0, 1);
assert!(
(fratio - 10.0).abs() > 1.0,
"the force layout must NOT reproduce the ground ratio — if it does, this gate proves nothing (got {fratio:.4})"
);
}
/// One uniform scale, not a per-axis stretch: a set of places twice as wide as it
/// is tall must still be drawn twice as wide as it is tall. A per-axis fit would
/// square it up and Sweden would come out fat.
#[test]
fn the_fit_is_uniform_so_the_shape_survives() {
let places: Vec<Place> =
vec![Some([0.0, 0.0]), Some([2.0, 0.0]), Some([0.0, 1.0]), Some([2.0, 1.0])];
let p = geographic(4, &places);
let w = f64::from(p[1][0] - p[0][0]);
let h = f64::from(p[2][1] - p[0][1]);
assert!((w / h - 2.0).abs() < 1e-4, "aspect kept: w/h = {:.4}", w / h);
// …and it actually filled the box rather than sitting in a corner.
assert!((w - 2.0 * GEO_FILL).abs() < 1e-4, "the long axis fills the box, got {w:.4}");
}
/// **North is up.** A Web-Mercator plane grows southward and so does the canvas's
/// `+y`, so the layout must NOT flip it: Kiruna has to come out above Malmö.
#[test]
fn north_is_up() {
let merc_y = |lat: f64| -> f64 {
let r: f64 = lat.to_radians();
(1.0 - (r.tan() + 1.0 / r.cos()).ln() / std::f64::consts::PI) / 2.0
};
// Kiruna 67.86 °N, Stockholm 59.33 °N, Malmö 55.60 °N.
let places: Vec<Place> = vec![
Some([0.55, merc_y(67.8558)]),
Some([0.55, merc_y(59.3293)]),
Some([0.55, merc_y(55.6050)]),
];
let p = geographic(3, &places);
assert!(p[0][1] < p[1][1], "Kiruna above Stockholm");
assert!(p[1][1] < p[2][1], "Stockholm above Malmö");
}
/// **A coordinate-less graph keeps today's layout, exactly.** The geographic lane
/// is data-gated: no places (or a hole in them) ⇒ byte-identical to `Force`.
#[test]
fn without_places_geographic_is_the_force_layout_byte_for_byte() {
let (n, edges) = ring_graph(40);
let force = layout_with(LayoutKind::Force, n, &edges, &[]);
assert!(!places_cover(n, &[]), "no places is not covered");
assert_eq!(layout_with(LayoutKind::Geographic, n, &edges, &[]), force);
// A hole is not "mostly covered" — one placeless node out of 120 is enough.
let mut holey: Vec<Place> = (0..n).map(|i| Some([i as f64, 0.0])).collect();
holey[7] = None;
assert!(!places_cover(n, &holey), "a hole is not covered");
assert_eq!(layout_with(LayoutKind::Geographic, n, &edges, &holey), force);
// …and a full column IS covered, and then it is NOT the force layout.
let full: Vec<Place> = (0..n).map(|i| Some([i as f64, (i % 5) as f64])).collect();
assert!(places_cover(n, &full));
assert_ne!(layout_with(LayoutKind::Geographic, n, &edges, &full), force);
}
/// Degenerate sets do not divide by zero: every node in one spot collapses to the
/// origin, an empty scene is empty — and a SHORT column still answers one position
/// per node, because every caller indexes the result by node index and a short
/// answer would drop the tail of the graph off the canvas.
#[test]
fn a_degenerate_place_set_is_the_origin_not_an_infinity() {
let same: Vec<Place> = vec![Some([12.0, 34.0]); 5];
let p = geographic(5, &same);
assert!(p.iter().all(|q| q[0] == 0.0 && q[1] == 0.0));
assert!(geographic(0, &[]).is_empty());
// Three places, ten nodes: ten positions.
let short: Vec<Place> = vec![Some([0.0, 0.0]), Some([1.0, 0.0]), None];
assert_eq!(geographic(10, &short).len(), 10);
}
}