tawasuyu/brahman

1//! Layout force-directed (Fruchterman-Reingold).
2//!
3//! Repulsión entre todo par de nodos + atracción a lo largo de las
4//! aristas, integrado con cooling. Implementación naïve O(n²); Barnes-Hut
5//! es la optimización de escala (millones de nodos) — pendiente.
6
7use crate::buffers::{EdgeBuffer, NodeBuffer};
8
9/// Parámetros de la simulación.
10#[derive(Debug, Clone, Copy)]
11pub struct ForceParams {
12    /// Distancia ideal entre nodos conectados.
13    pub k: f32,
14    /// Desplazamiento máximo inicial por paso (se enfría).
15    pub temperature: f32,
16    /// Factor de enfriamiento aplicado cada paso (`0 < cooling < 1`).
17    pub cooling: f32,
18}
19
20impl Default for ForceParams {
21    fn default() -> Self {
22        Self { k: 50.0, temperature: 50.0, cooling: 0.95 }
23    }
24}
25
26/// Estado de una simulación force-directed.
27pub struct ForceLayout {
28    params: ForceParams,
29    temp: f32,
30}
31
32impl ForceLayout {
33    pub fn new(params: ForceParams) -> Self {
34        let temp = params.temperature;
35        Self { params, temp }
36    }
37
38    /// Temperatura actual (baja con cada paso — útil para detectar fin).
39    pub fn temperature(&self) -> f32 {
40        self.temp
41    }
42
43    /// Un paso de simulación. Muta las posiciones de `nodes`. Devuelve el
44    /// desplazamiento total aplicado (converge hacia 0).
45    pub fn step(&mut self, nodes: &mut NodeBuffer, edges: &EdgeBuffer) -> f32 {
46        let n = nodes.len();
47        if n == 0 {
48            return 0.0;
49        }
50        let k = self.params.k.max(1e-3);
51        let mut disp = vec![(0.0f32, 0.0f32); n];
52
53        // Repulsión: todo par. f_r = k² / d.
54        for i in 0..n {
55            let (xi, yi) = nodes.pos(i);
56            for j in (i + 1)..n {
57                let (xj, yj) = nodes.pos(j);
58                let mut dx = xi - xj;
59                let mut dy = yi - yj;
60                let mut dist = (dx * dx + dy * dy).sqrt();
61                if dist < 1e-3 {
62                    // Jitter determinista para despegar nodos coincidentes.
63                    dx = ((i as f32) - (j as f32)) * 0.01 + 0.01;
64                    dy = 0.01;
65                    dist = (dx * dx + dy * dy).sqrt();
66                }
67                let f = k * k / dist;
68                let (ux, uy) = (dx / dist, dy / dist);
69                disp[i].0 += ux * f;
70                disp[i].1 += uy * f;
71                disp[j].0 -= ux * f;
72                disp[j].1 -= uy * f;
73            }
74        }
75
76        // Atracción: a lo largo de cada arista. f_a = d² / k.
77        for (u, v) in edges.iter() {
78            if u >= n || v >= n || u == v {
79                continue;
80            }
81            let (xu, yu) = nodes.pos(u);
82            let (xv, yv) = nodes.pos(v);
83            let dx = xu - xv;
84            let dy = yu - yv;
85            let dist = (dx * dx + dy * dy).sqrt().max(1e-3);
86            let f = dist * dist / k;
87            let (ux, uy) = (dx / dist, dy / dist);
88            disp[u].0 -= ux * f;
89            disp[u].1 -= uy * f;
90            disp[v].0 += ux * f;
91            disp[v].1 += uy * f;
92        }
93
94        // Integración con cap de temperatura.
95        let mut total = 0.0f32;
96        for i in 0..n {
97            let (dx, dy) = disp[i];
98            let len = (dx * dx + dy * dy).sqrt();
99            if len < 1e-6 {
100                continue;
101            }
102            let capped = len.min(self.temp);
103            let (mx, my) = (dx / len * capped, dy / len * capped);
104            let (x, y) = nodes.pos(i);
105            nodes.set_pos(i, x + mx, y + my);
106            total += capped;
107        }
108        self.temp *= self.params.cooling;
109        total
110    }
111}
112
113#[cfg(test)]
114mod tests {
115    use super::*;
116
117    #[test]
118    fn two_connected_nodes_settle_near_k() {
119        let mut nb = NodeBuffer::new();
120        nb.push(0.0, 0.0, 5.0);
121        nb.push(500.0, 0.0, 5.0); // arrancan muy lejos
122        let mut eb = EdgeBuffer::new();
123        eb.push(0, 1);
124        let mut fl = ForceLayout::new(ForceParams::default());
125        for _ in 0..400 {
126            fl.step(&mut nb, &eb);
127        }
128        let (x0, y0) = nb.pos(0);
129        let (x1, y1) = nb.pos(1);
130        let dist = ((x1 - x0).powi(2) + (y1 - y0).powi(2)).sqrt();
131        // No deberían quedar ni pegados ni a 500 de distancia.
132        assert!(dist > 5.0 && dist < 300.0, "dist tras converger = {dist}");
133    }
134
135    #[test]
136    fn coincident_nodes_do_not_nan() {
137        let mut nb = NodeBuffer::new();
138        nb.push(10.0, 10.0, 5.0);
139        nb.push(10.0, 10.0, 5.0);
140        let eb = EdgeBuffer::new();
141        let mut fl = ForceLayout::new(ForceParams::default());
142        fl.step(&mut nb, &eb);
143        let (x, y) = nb.pos(0);
144        assert!(x.is_finite() && y.is_finite());
145    }
146
147    #[test]
148    fn empty_graph_is_noop() {
149        let mut nb = NodeBuffer::new();
150        let eb = EdgeBuffer::new();
151        let mut fl = ForceLayout::new(ForceParams::default());
152        assert_eq!(fl.step(&mut nb, &eb), 0.0);
153    }
154}