use std::f32::consts::TAU;
use crate::graph::{NodeIndex, SimTopology};
use crate::particle::Particle;
use super::layering::{compute_bfs_layering, compute_layering, DepthMetric, Layering};
use super::{Layout, LayoutTickResult};
const DEFAULT_LEAF_WEIGHT_BLEND: f32 = 0.7;
#[derive(Debug, Clone)]
pub struct RadialParams {
pub base_radius: f32,
pub ring_spacing: f32,
pub roots: Vec<NodeIndex>,
pub leaf_weight_blend: f32,
pub depth_metric: DepthMetric,
pub radius_aware_spacing: bool,
}
impl Default for RadialParams {
fn default() -> Self {
Self {
base_radius: 60.0,
ring_spacing: 90.0,
roots: Vec::new(),
leaf_weight_blend: DEFAULT_LEAF_WEIGHT_BLEND,
depth_metric: DepthMetric::LongestPath,
radius_aware_spacing: true,
}
}
}
#[derive(Debug, Clone, Default)]
pub struct RadialLayout {
params: RadialParams,
computed: bool,
}
impl RadialLayout {
pub fn new(params: RadialParams) -> Self {
Self { params, computed: false }
}
pub fn params(&self) -> &RadialParams {
&self.params
}
pub fn set_params(&mut self, params: RadialParams) {
self.params = params;
self.computed = false;
}
}
fn leaf_counts(layering: &Layering) -> Vec<u32> {
let n = layering.layer.len();
let mut counts = vec![0u32; n];
let mut order: Vec<usize> = (0..n).collect();
order.sort_by_key(|&i| std::cmp::Reverse(layering.layer[i]));
for node in order {
counts[node] = if layering.children[node].is_empty() {
1
} else {
layering.children[node].iter().map(|&c| counts[c]).sum::<u32>().max(1)
};
}
counts
}
fn assign_ring_angles(ring: &[usize], leaf: &[u32], leaf_weight_blend: f32, radii: Option<&[f32]>) -> Vec<f32> {
let len = ring.len();
if len == 0 {
return Vec::new();
}
let total: f32 = ring.iter().map(|&n| leaf[n] as f32).sum::<f32>().max(1.0);
let uniform_share = (1.0 - leaf_weight_blend) / len as f32;
let base_shares: Vec<f32> = ring.iter().map(|&node| uniform_share + leaf_weight_blend * (leaf[node] as f32) / total).collect();
let shares: Vec<f32> = match radii {
None => base_shares,
Some(radii) => {
let own_radius = |node: usize| radii.get(node).copied().unwrap_or(1.0).max(1e-3);
let avg_radius = (ring.iter().map(|&n| own_radius(n)).sum::<f32>() / len as f32).max(1e-3);
let raw: Vec<f32> = ring.iter().zip(base_shares.iter()).map(|(&node, &base)| base * (own_radius(node) / avg_radius)).collect();
let raw_total: f32 = raw.iter().sum::<f32>().max(1e-6);
raw.into_iter().map(|v| v / raw_total).collect()
}
};
let mut angles = Vec::with_capacity(len);
let mut offset = 0.0f32;
for &share in &shares {
let width = TAU * share;
angles.push(offset + width * 0.5);
offset += width;
}
angles
}
impl Layout for RadialLayout {
fn tick(&mut self, topo: &SimTopology<'_>, particles: &mut [Particle], _dt: f32) -> LayoutTickResult {
if self.computed {
return LayoutTickResult { alpha: 0.0, max_displacement: 0.0, settled: true };
}
let layering = match self.params.depth_metric {
DepthMetric::LongestPath => compute_layering(topo, &self.params.roots),
DepthMetric::ShortestPath => compute_bfs_layering(topo, &self.params.roots),
};
let leaf = leaf_counts(&layering);
let radii_for_angles = self.params.radius_aware_spacing.then(|| topo.radii.as_slice());
for row in &layering.layers {
let angles = assign_ring_angles(row, &leaf, self.params.leaf_weight_blend, radii_for_angles);
for (&node, &angle) in row.iter().zip(angles.iter()) {
let Some(p) = particles.get_mut(node) else { continue };
if let (Some(fx), Some(fy)) = (p.fx, p.fy) {
p.x = fx;
p.y = fy;
p.vx = 0.0;
p.vy = 0.0;
continue;
}
let radius = self.params.base_radius + layering.layer[node] as f32 * self.params.ring_spacing;
p.x = radius * angle.cos();
p.y = radius * angle.sin();
p.vx = 0.0;
p.vy = 0.0;
}
}
self.computed = true;
LayoutTickResult { alpha: 0.0, max_displacement: 0.0, settled: true }
}
fn reheat(&mut self, _alpha: f32) {
self.computed = false;
}
fn is_settled(&self) -> bool {
true
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::graph::SimEdge;
fn topo(node_count: usize, edges: &[SimEdge]) -> SimTopology<'_> {
SimTopology { node_count, edges, degree: &[], radii: vec![1.0; node_count] }
}
fn e(from: u32, to: u32) -> SimEdge {
SimEdge { from: NodeIndex(from), to: NodeIndex(to), weight: 1.0 }
}
fn radius_of(p: &Particle) -> f32 {
(p.x * p.x + p.y * p.y).sqrt()
}
fn angle_of(p: &Particle) -> f32 {
let a = p.y.atan2(p.x);
if a < 0.0 {
a + TAU
} else {
a
}
}
#[test]
fn ring_radius_strictly_increases_with_depth() {
let edges = [e(0, 1), e(1, 2)];
let t = topo(3, &edges);
let mut particles = vec![Particle::default(); 3];
let mut layout = RadialLayout::default();
layout.tick(&t, &mut particles, 1.0 / 60.0);
let r0 = radius_of(&particles[0]);
let r1 = radius_of(&particles[1]);
let r2 = radius_of(&particles[2]);
assert!(r0 < r1, "depth 0 ring must sit inside depth 1's: {r0} vs {r1}");
assert!(r1 < r2, "depth 1 ring must sit inside depth 2's: {r1} vs {r2}");
}
#[test]
fn every_angle_is_within_0_to_tau_and_finite() {
let edges = [e(0, 1), e(0, 2), e(0, 3), e(0, 4)];
let t = topo(5, &edges);
let mut particles = vec![Particle::default(); 5];
let mut layout = RadialLayout::default();
layout.tick(&t, &mut particles, 1.0 / 60.0);
for p in &particles {
assert!(p.x.is_finite() && !p.x.is_nan());
assert!(p.y.is_finite() && !p.y.is_nan());
let a = angle_of(p);
assert!((0.0..TAU).contains(&a), "angle {a} out of [0, TAU)");
}
}
#[test]
fn siblings_in_the_same_ring_never_collide() {
let edges = [e(0, 1), e(0, 2), e(0, 3), e(0, 4), e(0, 5)];
let t = topo(6, &edges);
let mut particles = vec![Particle::default(); 6];
let mut layout = RadialLayout::default();
layout.tick(&t, &mut particles, 1.0 / 60.0);
let mut angles: Vec<f32> = (1..=5).map(|i| angle_of(&particles[i])).collect();
angles.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal));
let min_expected_gap = (1.0 - DEFAULT_LEAF_WEIGHT_BLEND) / 5.0 * TAU;
for pair in angles.windows(2) {
let gap = pair[1] - pair[0];
assert!(gap >= min_expected_gap - 1e-4, "adjacent siblings too close: gap {gap} < floor {min_expected_gap}");
}
}
#[test]
fn leaf_weight_blend_of_zero_widens_the_uniform_floor_for_a_skewed_ring() {
let edges = [e(0, 1), e(0, 2), e(0, 3), e(0, 4), e(0, 5), e(1, 6), e(1, 7), e(1, 8), e(1, 9), e(1, 10)];
let t = topo(11, &edges);
let mut default_particles = vec![Particle::default(); 11];
let mut default_layout = RadialLayout::default();
default_layout.tick(&t, &mut default_particles, 1.0 / 60.0);
let mut default_angles: Vec<f32> = (1..=5).map(|i| angle_of(&default_particles[i])).collect();
default_angles.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal));
let default_min_gap = default_angles.windows(2).map(|p| p[1] - p[0]).fold(f32::MAX, f32::min);
let mut uniform_particles = vec![Particle::default(); 11];
let mut uniform_layout = RadialLayout::new(RadialParams { leaf_weight_blend: 0.0, ..RadialParams::default() });
uniform_layout.tick(&t, &mut uniform_particles, 1.0 / 60.0);
let mut uniform_angles: Vec<f32> = (1..=5).map(|i| angle_of(&uniform_particles[i])).collect();
uniform_angles.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal));
let uniform_min_gap = uniform_angles.windows(2).map(|p| p[1] - p[0]).fold(f32::MAX, f32::min);
assert!(
uniform_min_gap > default_min_gap + 1e-4,
"leaf_weight_blend=0.0 must widen the minimum sibling gap vs. the default 0.7 blend on a leaf-skewed ring: uniform={uniform_min_gap} default={default_min_gap}"
);
}
#[test]
fn radial_layout_is_deterministic_across_repeated_ticks_after_reheat() {
let edges = [e(0, 1), e(0, 2), e(1, 3)];
let t = topo(4, &edges);
let mut particles = vec![Particle::default(); 4];
let mut layout = RadialLayout::default();
layout.tick(&t, &mut particles, 1.0 / 60.0);
let first: Vec<(f32, f32)> = particles.iter().map(|p| (p.x, p.y)).collect();
layout.reheat(1.0);
layout.tick(&t, &mut particles, 1.0 / 60.0);
let second: Vec<(f32, f32)> = particles.iter().map(|p| (p.x, p.y)).collect();
assert_eq!(first, second);
}
#[test]
fn radial_params_default_depth_metric_is_longest_path_and_radius_aware_spacing_is_on() {
let p = RadialParams::default();
assert_eq!(p.depth_metric, DepthMetric::LongestPath, "RadialLayout's pre-existing behavior — must not change silently");
assert!(p.radius_aware_spacing, "must default ON — graph-strengthening arc owner-approved flip");
}
#[test]
fn depth_metric_shortest_path_places_a_multi_parent_node_on_a_different_ring_than_longest_path() {
let edges = [e(0, 1), e(2, 3), e(3, 4), e(1, 5), e(4, 5)];
let t = topo(6, &edges);
let mut longest_particles = vec![Particle::default(); 6];
let mut longest_layout = RadialLayout::default(); longest_layout.tick(&t, &mut longest_particles, 1.0 / 60.0);
let mut shortest_particles = vec![Particle::default(); 6];
let mut shortest_layout = RadialLayout::new(RadialParams { depth_metric: DepthMetric::ShortestPath, ..RadialParams::default() });
shortest_layout.tick(&t, &mut shortest_particles, 1.0 / 60.0);
let r_longest = radius_of(&longest_particles[5]); let r_shortest = radius_of(&shortest_particles[5]);
assert!(r_longest > r_shortest, "D's LongestPath layer (3) must sit on a strictly larger ring than its ShortestPath depth (2): {r_longest} vs {r_shortest}");
let default_params = RadialParams::default();
let expected_longest = default_params.base_radius + 3.0 * default_params.ring_spacing;
let expected_shortest = default_params.base_radius + 2.0 * default_params.ring_spacing;
assert!((r_longest - expected_longest).abs() < 1e-2, "got {r_longest}, expected {expected_longest}");
assert!((r_shortest - expected_shortest).abs() < 1e-2, "got {r_shortest}, expected {expected_shortest}");
}
#[test]
fn matched_depth_metric_gives_2d_and_3d_radial_layouts_the_same_depth_for_the_layering_fixture() {
use super::super::radial_3d::{RadialLayout3D, RadialParams3D};
let edges = [e(0, 1), e(2, 3), e(3, 4), e(1, 5), e(4, 5)];
let t = topo(6, &edges);
for (metric, expected_depth) in [(DepthMetric::LongestPath, 3.0f32), (DepthMetric::ShortestPath, 2.0f32)] {
let mut particles_2d = vec![Particle::default(); 6];
let mut layout_2d = RadialLayout::new(RadialParams { base_radius: 0.0, ring_spacing: 1.0, depth_metric: metric, ..RadialParams::default() });
layout_2d.tick(&t, &mut particles_2d, 1.0 / 60.0);
let r2d = radius_of(&particles_2d[5]);
assert!((r2d - expected_depth).abs() < 1e-3, "2D radial depth mismatch for {metric:?}: got {r2d}, expected {expected_depth}");
let mut particles_3d = vec![Particle::default(); 6];
let mut layout_3d = RadialLayout3D::new(RadialParams3D {
shell_spacing: 1.0,
depth_metric: metric,
radius_aware_spacing: false,
..RadialParams3D::default()
});
layout_3d.tick(&t, &mut particles_3d, 1.0 / 60.0);
let r3d = (particles_3d[5].x.powi(2) + particles_3d[5].y.powi(2) + particles_3d[5].z.powi(2)).sqrt();
assert!((r3d - expected_depth).abs() < 1e-3, "3D radial depth mismatch for {metric:?}: got {r3d}, expected {expected_depth}");
}
}
#[test]
fn assign_ring_angles_with_radii_none_matches_the_leaf_only_baseline_exactly() {
let leaf = vec![1u32, 1, 1, 1, 1];
let ring: Vec<usize> = (0..5).collect();
let angles = assign_ring_angles(&ring, &leaf, DEFAULT_LEAF_WEIGHT_BLEND, None);
let step = TAU / ring.len() as f32;
for (i, &a) in angles.iter().enumerate() {
let expected = step * i as f32 + step * 0.5;
assert!((a - expected).abs() < 1e-4, "angle {i}: {a} vs {expected}");
}
}
#[test]
fn assign_ring_angles_radius_aware_widens_the_span_around_a_larger_member() {
let leaf = vec![1u32; 5];
let ring: Vec<usize> = (0..5).collect();
let radii = vec![1.0f32, 4.0, 1.0, 1.0, 1.0];
let off = assign_ring_angles(&ring, &leaf, DEFAULT_LEAF_WEIGHT_BLEND, None);
let gap01_off = off[1] - off[0];
let gap23_off = off[3] - off[2];
assert!((gap01_off - gap23_off).abs() < 1e-4, "without radius-awareness every gap must be identical (uniform leaf counts)");
let on = assign_ring_angles(&ring, &leaf, DEFAULT_LEAF_WEIGHT_BLEND, Some(&radii));
let gap01_on = on[1] - on[0];
let gap12_on = on[2] - on[1];
let gap23_on = on[3] - on[2];
assert!(gap01_on > gap01_off, "the gap approaching the larger member must widen: {gap01_on} vs baseline {gap01_off}");
assert!(gap12_on > gap23_off, "the gap leaving the larger member must widen too: {gap12_on} vs an ordinary gap {gap23_off}");
assert!(gap23_on < gap23_off, "an ordinary same-size gap must shrink slightly — every span still sums to exactly TAU: {gap23_on} vs baseline {gap23_off}");
}
#[test]
fn radial_layout_radius_aware_spacing_actually_changes_output_when_node_radii_vary() {
let edges = [e(0, 1), e(0, 2), e(0, 3), e(0, 4), e(0, 5)];
let mut radii = vec![1.0f32; 6];
radii[1] = 6.0; let t = SimTopology { node_count: 6, edges: &edges, degree: &[], radii };
let mut off_particles = vec![Particle::default(); 6];
let mut off_layout = RadialLayout::new(RadialParams { radius_aware_spacing: false, ..RadialParams::default() });
off_layout.tick(&t, &mut off_particles, 1.0 / 60.0);
let mut on_particles = vec![Particle::default(); 6];
let mut on_layout = RadialLayout::new(RadialParams { radius_aware_spacing: true, ..RadialParams::default() });
on_layout.tick(&t, &mut on_particles, 1.0 / 60.0);
assert_ne!(
(off_particles[1].x, off_particles[1].y),
(on_particles[1].x, on_particles[1].y),
"turning radius_aware_spacing on must actually move the big-radius member, not silently do nothing"
);
assert!(
(radius_of(&off_particles[1]) - radius_of(&on_particles[1])).abs() < 1e-3,
"ring RADIUS itself must stay untouched by this item — only the angular allocation changes"
);
}
#[test]
fn radius_aware_spacing_is_a_true_no_op_on_a_uniform_radius_graph_through_a_full_tick() {
let edges = [e(0, 1), e(0, 2), e(0, 3), e(0, 4), e(0, 5)];
let radii = vec![250.0f32; 6]; let t = SimTopology { node_count: 6, edges: &edges, degree: &[], radii };
let mut off_particles = vec![Particle::default(); 6];
let mut off_layout = RadialLayout::new(RadialParams { radius_aware_spacing: false, ..RadialParams::default() });
off_layout.tick(&t, &mut off_particles, 1.0 / 60.0);
let mut on_particles = vec![Particle::default(); 6];
let mut on_layout = RadialLayout::new(RadialParams { radius_aware_spacing: true, ..RadialParams::default() });
on_layout.tick(&t, &mut on_particles, 1.0 / 60.0);
for i in 0..6 {
assert!(
(off_particles[i].x - on_particles[i].x).abs() < 1e-3 && (off_particles[i].y - on_particles[i].y).abs() < 1e-3,
"node {i}: a uniform-radius graph must produce (near-)identical positions regardless of radius_aware_spacing: off=({}, {}) on=({}, {})",
off_particles[i].x, off_particles[i].y, on_particles[i].x, on_particles[i].y
);
}
}
}