facett-graph3d/tests/dataset_volume.rs
//! **"The sphere only has data around the sphere surface."**
//!
//! [`Layout3D::Force`] seeds every node on a Fibonacci sphere SHELL and then
//! relaxes. 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 what it holds. The demo fed it a bag of depth-1 stars — no paths, no
//! cycles, no hubs — so relaxation moved nothing and every node stayed at radius ≈
//! 1. The pane was a shell because the DATA was a shell.
//!
//! ## The oracle, and the reference it is measured against
//!
//! `interior_fraction(0.6)` = the share of nodes inside 60% of the cloud's radius.
//! There are two meaningful reference values, and using both is what makes this an
//! oracle rather than a tuned threshold:
//!
//! * a **uniformly filled ball** puts `0.6³ = 0.216` of its nodes there — this is
//! what "solid" means, exactly;
//! * a **shell** puts `0` there.
//!
//! Measured on this box, at every swept size:
//!
//! | nodes | depth-1 stars (what the demo fed it) | generated chains + rungs + hubs |
//! |---:|---:|---:|
//! | 2000 | 0.000 | **0.583** |
//! | 20000 | 0.197 | **0.532** |
//! | 100000 | 0.100 | **0.252** |
//!
//! So the assertion is two-sided and needs no tuned constant: the star control is
//! always BELOW the uniform-ball value (hollow) and the generated cloud always
//! ABOVE it (solid). The control is *run in this file* rather than described.
use facett_graph3d::{dataset, Graph3D, Layout3D};
/// `(label, colour)` nodes + index edges, the shape `Graph3D::new` takes.
type NodesEdges = (Vec<(String, egui::Color32)>, Vec<(usize, usize)>);
/// The share of nodes inside `frac` of the cloud's own radius.
///
/// The reference radius is the **95th percentile**, not the max: `Layout3D::Force`
/// normalises into the unit CUBE, so a handful of corner nodes stretch `rmax` to
/// `√3` and would make even a pure shell look partly filled. p95 is the radius the
/// bulk of the cloud actually reaches.
fn interior_fraction(g: &Graph3D, frac: f32) -> f32 {
if g.nodes.is_empty() {
return 0.0;
}
let mut r: Vec<f32> = g
.nodes
.iter()
.map(|n| (n.pos[0] * n.pos[0] + n.pos[1] * n.pos[1] + n.pos[2] * n.pos[2]).sqrt())
.collect();
r.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal));
let p95 = r[(r.len() * 95 / 100).min(r.len() - 1)].max(1e-6);
r.iter().filter(|&&x| x < frac * p95).count() as f32 / r.len() as f32
}
/// The uniform-ball reference at `frac = 0.6`.
const UNIFORM_BALL: f32 = 0.6 * 0.6 * 0.6;
/// The dataset the demo used to build: shallow depth-1 stars. Kept here as the
/// **control**, so the oracle is demonstrated to separate the two rather than
/// merely asserted to.
fn star_dataset(n: usize) -> NodesEdges {
let nodes: Vec<(String, egui::Color32)> =
(0..n).map(|i| (format!("n{i}"), egui::Color32::from_rgb(0, 200, 220))).collect();
// Every 5 nodes: one hub + 4 leaves. Depth 1, degree 1 or 4. No cycles.
let edges: Vec<(usize, usize)> = (0..n).map(|i| (i - i % 5, i)).filter(|&(a, b)| a != b).collect();
(nodes, edges)
}
/// **THE ORACLE + ITS CONTROL.** The generated dataset relaxes into a solid; the
/// star dataset it replaces relaxes into a shell.
#[test]
fn the_generated_dataset_fills_the_volume_and_stars_do_not() {
for n in [2_000usize, 20_000, 100_000] {
// CONTROL: what the demo had. Measured 0.000 / 0.197 / 0.100 — always
// BELOW the uniform-ball reference, i.e. hollow.
let (sn, se) = star_dataset(n);
let stars = Graph3D::new(sn, se, Layout3D::Force);
let shell = interior_fraction(&stars, 0.6);
assert!(
shell < UNIFORM_BALL,
"n={n}: the CONTROL must really be HOLLOW ({shell:.3} < {UNIFORM_BALL:.3}) — if \
this stops being true the oracle below has lost its teeth"
);
// The generated dataset. Measured 0.583 / 0.532 / 0.252 — always ABOVE.
let d = dataset::generate(&dataset::GraphSpec::sized(n));
let solid_graph = Graph3D::new(d.nodes, d.edges, Layout3D::Force);
let solid = interior_fraction(&solid_graph, 0.6);
assert!(
solid >= UNIFORM_BALL,
"n={n}: the cloud must be at least as solid as a UNIFORM BALL \
({solid:.3} >= {UNIFORM_BALL:.3}); the shell it replaces scores {shell:.3}"
);
// …and the two are separated by a wide margin, not by rounding.
assert!(
solid > shell * 2.0,
"n={n}: the generated cloud is far more solid than the star control \
({solid:.3} vs {shell:.3})"
);
}
}
/// Depth is what does the folding, so assert the generated cloud really has it —
/// and that the shallow control does not. Measured from the edge list (BFS double
/// sweep), so it is a property of the graph and not of the spec.
#[test]
fn the_generated_dataset_has_long_chains_and_stars_do_not() {
let n = 20_000;
let (_, se) = star_dataset(n);
let star_graph = dataset::GeneratedGraph {
nodes: (0..n).map(|i| (format!("n{i}"), egui::Color32::WHITE)).collect(),
edges: se,
};
assert!(
star_graph.diameter_lower_bound() <= 3,
"the star control is SHALLOW (depth {})",
star_graph.diameter_lower_bound()
);
let d = dataset::generate(&dataset::GraphSpec::sized(n));
let depth = d.diameter_lower_bound();
assert!(depth >= 20, "the generated graph has LONG CHAINS, got diameter {depth}");
}
/// The size knob works end to end: a bigger budget really produces a bigger cloud,
/// still deterministic, still solid, still deep.
#[test]
fn the_size_knob_scales_the_whole_property_set() {
let mut last = 0usize;
for n in [4_000usize, 30_000, 100_000] {
let spec = dataset::GraphSpec::sized(n);
let d = dataset::generate(&spec);
assert!(d.nodes.len() > last, "the knob really grows the cloud");
last = d.nodes.len();
assert!(d.diameter_lower_bound() >= 20, "n={n}: still deep");
assert!(spec.chain_len >= dataset::MIN_CHAIN_LEN, "n={n}: chains stay long");
// Determinism holds at every size (demo data must be reproducible).
let again = dataset::generate(&spec);
assert_eq!(again.edges, d.edges, "n={n}: deterministic");
}
}