graph-explorer-layout 0.1.0

Barnes-Hut force simulation and radial layout for graph-explorer.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

mod radial;
pub use radial::{RadialInput, RadialLayout, RadialPositions};

mod quadtree;
pub use quadtree::QuadTree;

mod force_sim;
pub use force_sim::{ForceSimulation, SimulationSpec};

pub type Position = [f32; 2];

#[cfg(test)]
mod layout_quality_tests {
    use crate::{ForceSimulation, SimulationSpec};
    use graph_explorer_core::{Graph, Node, Edge};
    use std::collections::HashMap;

    /// Ring of hub-and-spoke clusters, mirroring the demo's stress shape.
    fn clustered(n: usize) -> Graph {
        let mut g = Graph::default();
        let cluster = 50;
        let hubs = n.div_ceil(cluster);
        for c in 0..hubs {
            let hub = format!("h{c}");
            g.add_node(Node::new(hub.clone()));
            if c > 0 { g.add_edge(Edge::new(format!("ih{c}"), format!("h{}", c - 1), hub.clone())); }
            for k in 1..cluster {
                if g.nodes().count() >= n { break; }
                let id = format!("n{c}x{k}");
                g.add_node(Node::new(id.clone()));
                g.add_edge(Edge::new(format!("e{c}x{k}"), hub.clone(), id));
            }
        }
        if hubs > 1 { g.add_edge(Edge::new("ring", format!("h{}", hubs - 1), "h0")); }
        g
    }

    fn settled_positions(g: &Graph) -> HashMap<String, [f32; 2]> {
        let mut s = ForceSimulation::new(SimulationSpec::default());
        s.sync(g, &HashMap::new()); // no seeds: pure phyllotaxis start
        s.reheat_full();
        s.settle(600);
        assert!(!s.is_active(), "must converge within the settle bound");
        s.positions().map(|(id, p)| (id.clone(), p)).collect()
    }

    #[test]
    fn settle_from_phyllotaxis_yields_a_real_layout() {
        let g = clustered(500);
        let pos = settled_positions(&g);
        assert_eq!(pos.len(), 500);
        for p in pos.values() {
            assert!(p[0].is_finite() && p[1].is_finite(), "NaN/inf position");
        }
        let (mut min, mut max) = ([f32::MAX; 2], [f32::MIN; 2]);
        for p in pos.values() {
            min[0] = min[0].min(p[0]); min[1] = min[1].min(p[1]);
            max[0] = max[0].max(p[0]); max[1] = max[1].max(p[1]);
        }
        assert!(max[0] - min[0] > 100.0 && max[1] - min[1] > 100.0, "degenerate spread");
        let g_edges: Vec<_> = g.edges().collect();
        let mean_linked: f32 = g_edges.iter()
            .map(|e| dist(pos[&e.source], pos[&e.target]))
            .sum::<f32>() / g_edges.len() as f32;
        let ids: Vec<_> = pos.keys().cloned().collect();
        let mut sum = 0.0f32; let mut cnt = 0u32;
        for i in (0..ids.len()).step_by(7) {
            let j = (i * 31 + 17) % ids.len();
            if i == j { continue; }
            sum += dist(pos[&ids[i]], pos[&ids[j]]); cnt += 1;
        }
        let mean_sampled = sum / cnt as f32;
        assert!(mean_linked < mean_sampled * 0.75,
            "linked pairs ({mean_linked}) not meaningfully closer than sampled pairs ({mean_sampled})");
    }

    #[test]
    fn settle_is_deterministic_for_identical_inputs() {
        let g = clustered(300);
        let a = settled_positions(&g);
        let b = settled_positions(&g);
        assert_eq!(a.len(), b.len());
        for (id, pa) in &a {
            let pb = b[id];
            assert!((pa[0] - pb[0]).abs() < 1e-6 && (pa[1] - pb[1]).abs() < 1e-6,
                "nondeterministic settle at {id}");
        }
    }

    fn dist(a: [f32; 2], b: [f32; 2]) -> f32 { ((a[0]-b[0]).powi(2) + (a[1]-b[1]).powi(2)).sqrt() }
}