facett-graph3d/src/callgraph_layouts.rs
//! **Call-graph 3-D layouts** — the seven depth-axis placement strategies from
//! nornir's `viz::callgraph` (the 🕸 Call Graph lens), extracted **generic**: each
//! takes a node count + an undirected edge list and produces one `[f32; 3]`
//! position per node, normalised into a centred cube. The consumer supplies the
//! graph; the warehouse scanning / theming / projection stay in the host.
//!
//! Unlike [`crate::Layout3D`] (the three index-driven sphere/helix/force
//! placements for arbitrary clouds), these are *structure-aware*: they read the
//! graph's communities (Louvain), call depth (topological layering), spectral
//! embedding, hop-distance MDS, and degree centrality. They first lay the graph
//! out in 2-D with a Fruchterman–Reingold force pass (so the x,y axes carry the
//! force structure), then assign the depth axis — except [`CallGraphLayout::Spectral`],
//! [`CallGraphLayout::Mds`] and [`CallGraphLayout::Helix`], which place all three
//! axes themselves.
//!
//! Everything here is **pure + deterministic** (fixed iteration counts, seeded
//! from `sin(index)` so there is no RNG): the same graph yields the same
//! positions every run, which is what the inject-assert tests below pin.
use std::collections::{HashMap, VecDeque};
/// Node count above which classical MDS ([`CallGraphLayout::Mds`]) refuses to build
/// its dense **n×n** distance/Gram matrices (O(n²) memory — ≈3.6 GB of `f32` at
/// 30 000) and falls back to the O(n + e) landmark embedding instead. Sized so the
/// exact path stays well under ~130 MB of scratch.
const MDS_MAX: usize = 4_000;
/// The [`MDS_MAX`] guard threshold — exposed for the OOM-guard test in the sibling
/// module (so it can size a graph just over the fallback boundary).
#[doc(hidden)]
#[must_use]
pub fn mds_max_for_test() -> usize {
MDS_MAX
}
/// The seven structure-aware call-graph depth layouts.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum CallGraphLayout {
/// #1 — extend the 2-D Fruchterman–Reingold force sim into the depth axis.
Force,
/// #2 — Louvain communities → z-shells: biggest community centred at z=0,
/// the rest fanned out in ±z by size.
ClusterZ,
/// #3 — topological layering: z = longest-path call depth (sources front,
/// sinks back), centred.
Topo,
/// #4 — spectral embedding: the 3 lowest non-trivial Laplacian eigenvectors
/// (shifted power iteration) → x, y, z.
Spectral,
/// #5 — classical MDS on BFS hop-distances → x, y, z.
Mds,
/// #6 — z by degree centrality: hubs pushed toward the camera (negative z).
Centrality,
/// #7 — order nodes by degree onto a 3-turn helix around the Y axis.
Helix,
}
impl CallGraphLayout {
/// All seven, with stable human labels (toolbar order).
pub const ALL: [(CallGraphLayout, &'static str); 7] = [
(CallGraphLayout::ClusterZ, "cluster z-shells"),
(CallGraphLayout::Force, "3D force"),
(CallGraphLayout::Topo, "topological"),
(CallGraphLayout::Spectral, "spectral"),
(CallGraphLayout::Mds, "MDS"),
(CallGraphLayout::Centrality, "centrality (hubs front)"),
(CallGraphLayout::Helix, "helix"),
];
pub fn label(self) -> &'static str {
Self::ALL.iter().find(|(l, _)| *l == self).map(|(_, s)| *s).unwrap_or("?")
}
/// Lay out `n` nodes wired by `edges` (undirected for the structure passes;
/// `Topo` reads them as directed `a → b`). Returns one normalised `[f32; 3]`
/// per node, centred at the origin with a consistent cube extent.
pub fn layout(self, n: usize, edges: &[(usize, usize)]) -> Vec<[f32; 3]> {
let mut g = Scene::new(n, edges);
g.force2d();
let adj = g.undirected_adj();
match self {
CallGraphLayout::Force => g.force3d(),
CallGraphLayout::ClusterZ => g.cluster_z(&adj),
CallGraphLayout::Topo => g.topo(),
CallGraphLayout::Spectral => g.spectral(&adj),
CallGraphLayout::Mds => g.mds(&adj),
CallGraphLayout::Centrality => g.centrality(),
CallGraphLayout::Helix => g.helix(),
}
g.normalize();
g.pos
}
}
/// Internal mutable layout scene: per-node `(x, y, z)` + degree, plus the edges.
struct Scene<'e> {
n: usize,
pos: Vec<[f32; 3]>,
deg: Vec<usize>,
edges: &'e [(usize, usize)],
}
impl<'e> Scene<'e> {
fn new(n: usize, edges: &'e [(usize, usize)]) -> Self {
let mut deg = vec![0usize; n];
for &(a, b) in edges {
if a < n && b < n {
deg[a] += 1;
deg[b] += 1;
}
}
// Seed x,y on a ring so the 2-D force pass starts non-degenerate.
let nn = n.max(1) as f32;
let pos = (0..n)
.map(|i| {
let ang = std::f32::consts::TAU * i as f32 / nn;
[220.0 * ang.cos(), 220.0 * ang.sin(), 0.0]
})
.collect();
Self { n, pos, deg, edges }
}
fn undirected_adj(&self) -> Vec<Vec<usize>> {
let mut adj = vec![Vec::new(); self.n];
for &(a, b) in self.edges {
if a < self.n && b < self.n {
adj[a].push(b);
adj[b].push(a);
}
}
adj
}
/// 2-D Fruchterman–Reingold over x,y (z untouched). Shared by ALL seven
/// call-graph layouts (they run this first), so scaling it scales every one:
/// above [`facett_core::barnes_hut::BH_THRESHOLD`] the O(n²) all-pairs repulsion
/// is replaced by the shared Barnes–Hut quadtree (O(n log n), parallel,
/// deterministic); below it the exact loop runs so the determinism goldens hold.
fn force2d(&mut self) {
let n = self.n;
if n < 2 {
return;
}
let area = 640.0 * 480.0;
let k = (area / n as f32).sqrt();
let theta = facett_core::barnes_hut::BH_THETA;
let use_bh = n >= facett_core::barnes_hut::BH_THRESHOLD;
let adj = facett_core::barnes_hut::adjacency(n, self.edges);
// Run the FR step on a 2-D view of x,y (z is set by the per-layout depth pass
// afterwards). The step body — repulsion + per-node attraction gather +
// step-capped integrate — lives ONCE in core: the parallel Barnes–Hut lane
// ([`fr_step`]) at scale, its serial mirror ([`fr_step_serial`]) below the
// threshold. 120 iterations at a fixed 16-unit step cap (no cooling; `normalize`
// fits the final cube).
let mut pts: Vec<[f32; 2]> = self.pos.iter().map(|p| [p[0], p[1]]).collect();
for _ in 0..120 {
pts = if use_bh {
facett_core::barnes_hut::fr_step::<2>(&pts, &adj, k, theta, 16.0)
} else {
facett_core::barnes_hut::fr_step_serial::<2>(&pts, &adj, k, theta, 16.0)
};
}
for (p, q) in self.pos.iter_mut().zip(&pts).take(n) {
p[0] = q[0];
p[1] = q[1];
}
}
/// #1 — a z-only force pass (x,y from the 2-D layout).
fn force3d(&mut self) {
let n = self.n;
for i in 0..n {
self.pos[i][2] = (i as f32 * 7.13).sin() * 120.0;
}
let k = 90.0;
// 1-D Barnes–Hut equivalence: the pairwise z push is `f = k²·0.0016·d/|d|²`,
// i.e. a 1-D N-body with effective length `k·√0.0016 = k·0.04`, so the shared
// repulsion kernel (D=1 segment tree) reproduces it in O(n log n) at scale.
let use_bh = n >= facett_core::barnes_hut::BH_THRESHOLD;
let k_eff = k * 0.04; // √0.0016
for _ in 0..90 {
let mut dz = vec![0.0f32; n];
if use_bh {
let zs: Vec<[f32; 1]> = self.pos.iter().map(|p| [p[2]]).collect();
let rep = facett_core::barnes_hut::repulsion_forces::<1>(&zs, k_eff, facett_core::barnes_hut::BH_THETA);
for i in 0..n {
dz[i] = rep[i][0];
}
} else {
for i in 0..n {
for j in (i + 1)..n {
let mut d = self.pos[i][2] - self.pos[j][2];
if d.abs() < 0.01 {
d = 0.1;
}
let f = (k * k) / d.abs() * d.signum() * 0.0016;
dz[i] += f;
dz[j] -= f;
}
}
}
for &(a, b) in self.edges {
if a >= n || b >= n {
continue;
}
let d = self.pos[a][2] - self.pos[b][2];
dz[a] -= d * 0.05;
dz[b] += d * 0.05;
}
for (p, d) in self.pos.iter_mut().zip(&dz).take(n) {
p[2] += d.clamp(-20.0, 20.0);
}
}
}
/// #2 — Louvain communities → z-shells.
fn cluster_z(&mut self, adj: &[Vec<usize>]) {
let n = self.n;
let comp = louvain(adj);
let nc = comp.iter().copied().max().map(|m| m + 1).unwrap_or(1);
let mut sizes = vec![0usize; nc];
for &c in &comp {
sizes[c] += 1;
}
let mut order: Vec<usize> = (0..sizes.len()).collect();
order.sort_by_key(|&c| std::cmp::Reverse(sizes[c]));
let mut zof = vec![0.0f32; sizes.len()];
for (rank, &c) in order.iter().enumerate() {
let shell = rank.div_ceil(2) as f32;
let sign = if rank % 2 == 1 { 1.0 } else { -1.0 };
zof[c] = sign * shell * 190.0;
}
for i in 0..n {
self.pos[i][2] = zof[comp[i]] + (i as f32 * 12.9898).sin() * 22.0;
}
}
/// #3 — topological layering (z = longest-path call depth), centred. Reads
/// `edges` as directed `a → b`.
fn topo(&mut self) {
let n = self.n;
let mut indeg = vec![0usize; n];
let mut out: Vec<Vec<usize>> = vec![Vec::new(); n];
for &(a, b) in self.edges {
if a >= n || b >= n {
continue;
}
out[a].push(b);
indeg[b] += 1;
}
let mut layer = vec![0i32; n];
let mut seen = vec![false; n];
let mut work: Vec<usize> = (0..n).filter(|&i| indeg[i] == 0).collect();
for &i in &work {
seen[i] = true;
}
while let Some(u) = work.pop() {
for &v in &out[u] {
if layer[v] < layer[u] + 1 {
layer[v] = layer[u] + 1;
}
indeg[v] = indeg[v].saturating_sub(1);
if indeg[v] == 0 && !seen[v] {
seen[v] = true;
work.push(v);
}
}
}
let maxl = layer.iter().cloned().max().unwrap_or(0).max(1) as f32;
for (p, &l) in self.pos.iter_mut().zip(&layer).take(n) {
p[2] = (l as f32 - maxl / 2.0) * 170.0;
}
}
/// #4 — spectral embedding (3 lowest non-trivial Laplacian eigenvectors via
/// shifted power iteration, deflating the constant) → x, y, z.
fn spectral(&mut self, adj: &[Vec<usize>]) {
let n = self.n;
if n < 4 {
return;
}
let deg: Vec<f32> = adj.iter().map(|a| a.len() as f32).collect();
let c = deg.iter().cloned().fold(0.0, f32::max) * 2.0 + 1.0;
let mul = |v: &[f32]| -> Vec<f32> {
let mut r = vec![0.0f32; n];
for i in 0..n {
r[i] = (c - deg[i]) * v[i];
for &j in &adj[i] {
r[i] += v[j];
}
}
r
};
let ortho = |v: &mut Vec<f32>, basis: &[Vec<f32>]| {
for b in basis {
let dot: f32 = v.iter().zip(b).map(|(x, y)| x * y).sum();
for i in 0..n {
v[i] -= dot * b[i];
}
}
let norm = v.iter().map(|x| x * x).sum::<f32>().sqrt().max(1e-6);
for x in v.iter_mut() {
*x /= norm;
}
};
let mut basis = vec![vec![1.0 / (n as f32).sqrt(); n]];
let mut coords: Vec<Vec<f32>> = Vec::new();
for k in 0..3 {
let mut v: Vec<f32> = (0..n).map(|i| ((i * 7 + k * 131 + 1) as f32).sin()).collect();
ortho(&mut v, &basis);
for _ in 0..70 {
let mut nv = mul(&v);
ortho(&mut nv, &basis);
v = nv;
}
basis.push(v.clone());
coords.push(v);
}
for (i, p) in self.pos.iter_mut().enumerate().take(n) {
*p = [coords[0][i] * 320.0, coords[1][i] * 320.0, coords[2][i] * 320.0];
}
}
/// #5 — classical MDS on BFS hop-distances → x, y, z.
///
/// Classical MDS materialises a **dense n×n** hop-distance + Gram matrix — O(n²)
/// MEMORY (≈3.6 GB of `f32` at n = 30 000), so it OOMs long before the force
/// layouts hang. Above [`MDS_MAX`] fall back to a **landmark** embedding
/// ([`mds_landmark`](Self::mds_landmark)) that keeps the force2d x,y and derives z
/// from BFS hop-distance to a landmark — O(n + e) memory, no dense matrix. Below
/// it, the exact classical MDS runs (goldens unchanged).
fn mds(&mut self, adj: &[Vec<usize>]) {
let n = self.n;
if n < 4 {
return;
}
if n > MDS_MAX {
self.mds_landmark(adj);
return;
}
let far = (n as f32).sqrt() + 2.0;
let mut dist = vec![vec![0.0f32; n]; n];
for s in 0..n {
let mut d = vec![-1i32; n];
let mut q = VecDeque::new();
d[s] = 0;
q.push_back(s);
while let Some(u) = q.pop_front() {
for &v in &adj[u] {
if d[v] < 0 {
d[v] = d[u] + 1;
q.push_back(v);
}
}
}
for j in 0..n {
dist[s][j] = if d[j] < 0 { far } else { d[j] as f32 };
}
}
let mut b = vec![vec![0.0f32; n]; n];
let mut rowm = vec![0.0f32; n];
let mut all = 0.0f32;
for i in 0..n {
for j in 0..n {
let d2 = dist[i][j] * dist[i][j];
b[i][j] = d2;
rowm[i] += d2;
all += d2;
}
}
let allm = all / (n * n) as f32;
for r in rowm.iter_mut() {
*r /= n as f32;
}
for i in 0..n {
for j in 0..n {
b[i][j] = -0.5 * (b[i][j] - rowm[i] - rowm[j] + allm);
}
}
let mul = |v: &[f32]| -> Vec<f32> { (0..n).map(|i| (0..n).map(|j| b[i][j] * v[j]).sum()).collect() };
let ortho = |v: &mut Vec<f32>, basis: &[Vec<f32>]| {
for bb in basis {
let dot: f32 = v.iter().zip(bb).map(|(x, y)| x * y).sum();
for i in 0..n {
v[i] -= dot * bb[i];
}
}
let norm = v.iter().map(|x| x * x).sum::<f32>().sqrt().max(1e-6);
for x in v.iter_mut() {
*x /= norm;
}
};
let mut basis: Vec<Vec<f32>> = Vec::new();
let mut coords: Vec<Vec<f32>> = Vec::new();
for k in 0..3 {
let mut v: Vec<f32> = (0..n).map(|i| ((i * 13 + k * 71 + 1) as f32).sin()).collect();
ortho(&mut v, &basis);
for _ in 0..70 {
let mut nv = mul(&v);
ortho(&mut nv, &basis);
v = nv;
}
basis.push(v.clone());
coords.push(v);
}
for (i, p) in self.pos.iter_mut().enumerate().take(n) {
*p = [coords[0][i] * 26.0, coords[1][i] * 26.0, coords[2][i] * 26.0];
}
}
/// **Landmark fallback for [`mds`](Self::mds)** at scale — no dense n×n matrix.
/// Keeps the force2d x,y and sets z from BFS hop-distance to a landmark node (the
/// highest-degree node, a natural centre), so a huge call graph still gets a real
/// 3-D relief in O(n + e) memory instead of OOMing on the O(n²) Gram matrix.
fn mds_landmark(&mut self, adj: &[Vec<usize>]) {
let n = self.n;
if n == 0 {
return;
}
// Landmark = highest-degree node (deterministic; ties break on lowest index).
let mut landmark = 0usize;
for i in 1..n {
if adj[i].len() > adj[landmark].len() {
landmark = i;
}
}
let mut d = vec![-1i32; n];
let mut q = VecDeque::new();
d[landmark] = 0;
q.push_back(landmark);
let mut maxd = 0i32;
while let Some(u) = q.pop_front() {
for &v in &adj[u] {
if d[v] < 0 {
d[v] = d[u] + 1;
maxd = maxd.max(d[v]);
q.push_back(v);
}
}
}
let far = maxd + 2;
let span = far.max(1) as f32;
for (p, &di) in self.pos.iter_mut().zip(&d).take(n) {
let hop = if di < 0 { far } else { di } as f32;
// Centre the depth axis; scale to a comparable extent to the force2d x,y.
p[2] = (hop / span - 0.5) * 320.0;
}
}
/// #6 — z by degree centrality (hubs toward the camera; x,y from the 2-D force).
fn centrality(&mut self) {
let n = self.n;
let maxd = self.deg.iter().copied().max().unwrap_or(1).max(1) as f32;
for i in 0..n {
self.pos[i][2] = -((self.deg[i] as f32 / maxd) - 0.5) * 520.0;
}
}
/// #7 — order by degree onto a 3-turn helix around the Y axis.
fn helix(&mut self) {
let n = self.n;
let mut order: Vec<usize> = (0..n).collect();
order.sort_by_key(|&i| std::cmp::Reverse(self.deg[i]));
let r = 240.0;
let turns = 3.0;
let denom = (n.max(2) - 1) as f32;
for (rank, &i) in order.iter().enumerate() {
let t = rank as f32 / denom;
let ang = t * std::f32::consts::TAU * turns;
self.pos[i] = [r * ang.cos(), (t - 0.5) * 540.0, r * ang.sin()];
}
}
/// Rescale all three axes to a consistent centred cube extent.
fn normalize(&mut self) {
if self.n == 0 {
return;
}
let (mut mn, mut mx) = ([f32::MAX; 3], [f32::MIN; 3]);
for p in &self.pos {
for c in 0..3 {
mn[c] = mn[c].min(p[c]);
mx[c] = mx[c].max(p[c]);
}
}
let span = (mx[0] - mn[0]).max(mx[1] - mn[1]).max(mx[2] - mn[2]).max(1.0);
let scale = 520.0 / span;
let center = [0, 1, 2].map(|c| (mn[c] + mx[c]) / 2.0);
for p in &mut self.pos {
for c in 0..3 {
p[c] = (p[c] - center[c]) * scale;
}
}
}
}
/// Louvain community detection (modularity ascent, single level): assigns each
/// node a community label `0..k`, relabelled compactly. Pure + deterministic
/// (fixed pass cap, node order). Empty graph ⇒ every node its own community.
pub fn louvain(adj: &[Vec<usize>]) -> Vec<usize> {
let n = adj.len();
let m2: f64 = adj.iter().map(|a| a.len()).sum::<usize>() as f64; // 2m
if m2 == 0.0 {
return (0..n).collect();
}
let deg: Vec<f64> = adj.iter().map(|a| a.len() as f64).collect();
let mut comm: Vec<usize> = (0..n).collect();
let mut sigma_tot = deg.clone();
let mut improved = true;
let mut passes = 0;
while improved && passes < 30 {
improved = false;
passes += 1;
for i in 0..n {
let ci = comm[i];
sigma_tot[ci] -= deg[i];
let mut k_in: HashMap<usize, f64> = HashMap::new();
for &j in &adj[i] {
if j != i {
*k_in.entry(comm[j]).or_insert(0.0) += 1.0;
}
}
k_in.entry(ci).or_insert(0.0);
let (mut best_c, mut best_gain) = (ci, f64::MIN);
for (&c, &kic) in &k_in {
let gain = kic - sigma_tot[c] * deg[i] / m2;
if gain > best_gain + 1e-9 {
best_gain = gain;
best_c = c;
}
}
comm[i] = best_c;
sigma_tot[best_c] += deg[i];
if best_c != ci {
improved = true;
}
}
}
let mut relabel: HashMap<usize, usize> = HashMap::new();
comm.iter()
.map(|&c| {
let next = relabel.len();
*relabel.entry(c).or_insert(next)
})
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
/// Two disjoint cliques of size `k`, bridged by a single edge — a textbook
/// two-community graph for the Louvain / cluster test.
fn two_cliques(k: usize) -> (usize, Vec<(usize, usize)>) {
let mut e = Vec::new();
for i in 0..k {
for j in (i + 1)..k {
e.push((i, j));
e.push((k + i, k + j));
}
}
e.push((0, k)); // bridge
(2 * k, e)
}
fn finite(pos: &[[f32; 3]]) -> bool {
pos.iter().all(|p| p.iter().all(|c| c.is_finite()))
}
/// Every layout: finite positions, inside the normalised cube, deterministic.
#[test]
fn all_layouts_finite_bounded_and_deterministic() {
let (n, edges) = two_cliques(6);
for (layout, _) in CallGraphLayout::ALL {
let a = layout.layout(n, &edges);
let b = layout.layout(n, &edges);
assert_eq!(a.len(), n, "{layout:?}: one position per node");
assert!(finite(&a), "{layout:?}: positions finite");
// normalize() centres on the origin within a 520-extent cube → ±260+ε.
for p in &a {
for c in p {
assert!(c.abs() <= 280.0, "{layout:?}: in cube, got {c}");
}
}
assert_eq!(a, b, "{layout:?}: pure/deterministic (same graph ⇒ same positions)");
}
}
/// Louvain on two bridged cliques must find (at least) two communities, with
/// each clique internally agreeing.
#[test]
fn louvain_separates_two_cliques() {
let k = 6;
let (n, edges) = two_cliques(k);
let mut adj = vec![Vec::new(); n];
for &(a, b) in &edges {
adj[a].push(b);
adj[b].push(a);
}
let comm = louvain(&adj);
assert_eq!(comm.len(), n);
let ncomm = comm.iter().copied().max().unwrap() + 1;
assert!(ncomm >= 2, "two bridged cliques ⇒ ≥2 communities, got {ncomm}");
// Each clique's members share a community among themselves.
let first_a = comm[0];
let first_b = comm[k];
assert!((0..k).all(|i| comm[i] == first_a), "clique A coheres");
assert!((k..2 * k).all(|i| comm[i] == first_b), "clique B coheres");
assert_ne!(first_a, first_b, "the two cliques land in different communities");
}
/// ClusterZ: the two communities must separate in depth (distinct mean z).
#[test]
fn cluster_z_separates_communities_in_depth() {
let k = 6;
let (n, edges) = two_cliques(k);
let pos = CallGraphLayout::ClusterZ.layout(n, &edges);
let mean = |range: std::ops::Range<usize>| -> f32 {
let s: f32 = range.clone().map(|i| pos[i][2]).sum();
s / (range.end - range.start) as f32
};
let za = mean(0..k);
let zb = mean(k..2 * k);
assert!((za - zb).abs() > 50.0, "communities separate in z: za={za}, zb={zb}");
}
/// Topo: on a directed chain `0→1→2→…`, z must increase monotonically with
/// call depth (sources front, sinks back).
#[test]
fn topo_orders_chain_by_depth() {
let n = 8;
let edges: Vec<(usize, usize)> = (0..n - 1).map(|i| (i, i + 1)).collect();
let pos = CallGraphLayout::Topo.layout(n, &edges);
for i in 0..n - 1 {
assert!(pos[i][2] < pos[i + 1][2], "z increases along the call chain at {i}");
}
}
/// Centrality: a star graph's hub (highest degree) must sit nearest the
/// camera (most-negative z), the leaves behind it.
#[test]
fn centrality_pushes_hub_to_front() {
let n = 10;
let edges: Vec<(usize, usize)> = (1..n).map(|i| (0, i)).collect(); // 0 is the hub
let pos = CallGraphLayout::Centrality.layout(n, &edges);
let hub_z = pos[0][2];
for (i, p) in pos.iter().enumerate().take(n).skip(1) {
assert!(hub_z < p[2], "hub nearer camera (smaller z) than leaf {i}");
}
}
/// Helix: the highest-degree node anchors one end of the helix and the
/// lowest-degree the other — the Y extent spans the whole strand.
#[test]
fn helix_spans_y_by_degree_order() {
let n = 12;
// node 0 is a hub (degree 11); the rest are leaves (degree 1).
let edges: Vec<(usize, usize)> = (1..n).map(|i| (0, i)).collect();
let pos = CallGraphLayout::Helix.layout(n, &edges);
let ys: Vec<f32> = pos.iter().map(|p| p[1]).collect();
let (mut lo, mut hi) = (f32::MAX, f32::MIN);
for &y in &ys {
lo = lo.min(y);
hi = hi.max(y);
}
assert!(hi - lo > 100.0, "helix spans a real Y extent: {lo}..{hi}");
// The hub (rank 0 by degree) is at one extreme of Y.
let hub_y = pos[0][1];
assert!((hub_y - lo).abs() < 1.0 || (hub_y - hi).abs() < 1.0, "hub anchors a helix end");
}
/// Spectral & MDS rewrite all three axes: the embedding must be non-degenerate
/// (real spread on every axis), finite, and bounded.
#[test]
fn spectral_and_mds_spread_on_all_axes() {
let (n, edges) = two_cliques(8);
for layout in [CallGraphLayout::Spectral, CallGraphLayout::Mds] {
let pos = layout.layout(n, &edges);
assert!(finite(&pos), "{layout:?}: finite");
for c in 0..3 {
let (mut lo, mut hi) = (f32::MAX, f32::MIN);
for p in &pos {
lo = lo.min(p[c]);
hi = hi.max(p[c]);
}
assert!(hi - lo > 1.0, "{layout:?}: axis {c} has real spread ({lo}..{hi})");
}
}
}
/// Force3D: an organic relief — finite, bounded, and a real depth spread.
#[test]
fn force3d_has_depth_relief() {
let (n, edges) = two_cliques(6);
let pos = CallGraphLayout::Force.layout(n, &edges);
assert!(finite(&pos));
let (mut lo, mut hi) = (f32::MAX, f32::MIN);
for p in &pos {
lo = lo.min(p[2]);
hi = hi.max(p[2]);
}
assert!(hi - lo > 1.0, "force3d builds a depth relief: {lo}..{hi}");
}
/// Degenerate inputs (0 and 1 node) never panic.
#[test]
fn tiny_graphs_are_safe() {
for (layout, _) in CallGraphLayout::ALL {
assert_eq!(layout.layout(0, &[]).len(), 0, "{layout:?}: empty");
assert_eq!(layout.layout(1, &[]).len(), 1, "{layout:?}: single node");
}
}
}