tawasuyu/pineal

1//! Sugiyama-lite — layout layered para DAGs (o casi-DAGs).
2//!
3//! Pipeline en tres etapas, todas O(V + E):
4//! 1. **Cycle removal** (DFS): cualquier back-edge se invierte
5//!    lógicamente para producir un DAG con el que trabajar.
6//! 2. **Layering** (Kahn longest-path): asigna a cada nodo una capa
7//!    `0..L` tal que cada arista va de capa `i` a capa `j > i`.
8//! 3. **Barycenter ordering** (2 pasadas): minimiza cruces sumando
9//!    la posición promedio de los vecinos de la capa anterior y
10//!    re-ordenando.
11//!
12//! Devuelve la posición final `(x, y)` de cada nodo en pixels,
13//! contenida en el `Rect` provisto. La integración con `NodeBuffer`
14//! la hace el caller (`set_pos` por nodo).
15
16use pineal_render::Rect;
17
18/// Resultado del layout: posición por nodo (mismo índice que la
19/// entrada) + información de capas para el caller que quiera dibujar
20/// guías o agrupaciones.
21#[derive(Debug, Clone)]
22pub struct HierarchicalLayout {
23    pub positions: Vec<(f32, f32)>,
24    pub layers: Vec<Vec<usize>>,
25}
26
27/// Calcula el layout. `edges` son pares `(from, to)`; los nodos
28/// existen para todos los índices `0..n`. `area` es el rectángulo
29/// destino; nodos se distribuyen uniformemente dentro.
30pub fn sugiyama_layout(n: usize, edges: &[(usize, usize)], area: Rect) -> HierarchicalLayout {
31    if n == 0 {
32        return HierarchicalLayout { positions: Vec::new(), layers: Vec::new() };
33    }
34
35    // === 1. Cycle removal por DFS — marca back-edges.
36    let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
37    for &(u, v) in edges {
38        if u < n && v < n && u != v {
39            adj[u].push(v);
40        }
41    }
42    let mut state = vec![0u8; n]; // 0=blanco 1=en pila 2=hecho
43    let mut back: Vec<(usize, usize)> = Vec::new();
44    for s in 0..n {
45        if state[s] != 0 {
46            continue;
47        }
48        let mut stack: Vec<(usize, usize)> = vec![(s, 0)];
49        state[s] = 1;
50        while let Some(&mut (u, ref mut i)) = stack.last_mut() {
51            if *i < adj[u].len() {
52                let v = adj[u][*i];
53                *i += 1;
54                match state[v] {
55                    0 => {
56                        state[v] = 1;
57                        stack.push((v, 0));
58                    }
59                    1 => back.push((u, v)),
60                    _ => {}
61                }
62            } else {
63                state[u] = 2;
64                stack.pop();
65            }
66        }
67    }
68
69    // === 2. Longest-path layering (Kahn) sobre el DAG (sin back-edges).
70    let mut dag: Vec<Vec<usize>> = vec![Vec::new(); n];
71    let mut indeg = vec![0usize; n];
72    for &(u, v) in edges {
73        if u < n && v < n && u != v && !back.contains(&(u, v)) {
74            dag[u].push(v);
75            indeg[v] += 1;
76        }
77    }
78    let mut layer = vec![0usize; n];
79    let mut queue: Vec<usize> = (0..n).filter(|&i| indeg[i] == 0).collect();
80    let mut head = 0;
81    while head < queue.len() {
82        let u = queue[head];
83        head += 1;
84        for &v in &dag[u] {
85            layer[v] = layer[v].max(layer[u] + 1);
86            indeg[v] -= 1;
87            if indeg[v] == 0 {
88                queue.push(v);
89            }
90        }
91    }
92    let n_layers = layer.iter().copied().max().unwrap_or(0) + 1;
93    let mut by_layer: Vec<Vec<usize>> = vec![Vec::new(); n_layers];
94    for (i, &l) in layer.iter().enumerate() {
95        by_layer[l].push(i);
96    }
97
98    // === 3. Barycenter — dos pasadas (down + up) para reducir cruces.
99    let mut order = vec![0usize; n];
100    for col in by_layer.iter() {
101        for (pos, &node) in col.iter().enumerate() {
102            order[node] = pos;
103        }
104    }
105    for _ in 0..2 {
106        // Down (capa i mira a sus padres en capa i-1).
107        for c in 1..n_layers {
108            let mut paired: Vec<(usize, f64)> = by_layer[c]
109                .iter()
110                .map(|&node| {
111                    let mut sum = 0.0;
112                    let mut cnt = 0.0;
113                    for &(u, v) in edges {
114                        if v == node && u < n && layer[u] + 1 == c {
115                            sum += order[u] as f64;
116                            cnt += 1.0;
117                        }
118                    }
119                    (node, if cnt > 0.0 { sum / cnt } else { f64::MAX })
120                })
121                .collect();
122            paired.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal));
123            by_layer[c] = paired.into_iter().map(|(n, _)| n).collect();
124            for (pos, &i) in by_layer[c].iter().enumerate() {
125                order[i] = pos;
126            }
127        }
128        // Up (capa i mira a sus hijos en capa i+1).
129        for c in (0..n_layers.saturating_sub(1)).rev() {
130            let mut paired: Vec<(usize, f64)> = by_layer[c]
131                .iter()
132                .map(|&node| {
133                    let mut sum = 0.0;
134                    let mut cnt = 0.0;
135                    for &(u, v) in edges {
136                        if u == node && v < n && layer[v] == c + 1 {
137                            sum += order[v] as f64;
138                            cnt += 1.0;
139                        }
140                    }
141                    (node, if cnt > 0.0 { sum / cnt } else { f64::MAX })
142                })
143                .collect();
144            paired.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal));
145            by_layer[c] = paired.into_iter().map(|(n, _)| n).collect();
146            for (pos, &i) in by_layer[c].iter().enumerate() {
147                order[i] = pos;
148            }
149        }
150    }
151
152    // === 4. Asignar posiciones — `x` por capa, `y` por orden dentro.
153    let mut positions = vec![(0.0f32, 0.0); n];
154    let dx = if n_layers > 1 {
155        area.w / (n_layers - 1) as f32
156    } else {
157        0.0
158    };
159    for (c, col) in by_layer.iter().enumerate() {
160        let dy = if col.len() > 1 {
161            area.h / (col.len() - 1) as f32
162        } else {
163            0.0
164        };
165        let cx = area.x + c as f32 * dx;
166        for (pos, &node) in col.iter().enumerate() {
167            let cy = if col.len() == 1 {
168                area.y + area.h * 0.5
169            } else {
170                area.y + pos as f32 * dy
171            };
172            positions[node] = (cx, cy);
173        }
174    }
175
176    HierarchicalLayout { positions, layers: by_layer }
177}
178
179#[cfg(test)]
180mod tests {
181    use super::*;
182
183    #[test]
184    fn empty_input_returns_empty() {
185        let l = sugiyama_layout(0, &[], Rect::new(0.0, 0.0, 100.0, 100.0));
186        assert!(l.positions.is_empty());
187    }
188
189    #[test]
190    fn chain_assigns_increasing_x() {
191        // 0 → 1 → 2 → 3
192        let edges = [(0, 1), (1, 2), (2, 3)];
193        let l = sugiyama_layout(4, &edges, Rect::new(0.0, 0.0, 300.0, 100.0));
194        assert_eq!(l.layers.len(), 4);
195        let xs: Vec<f32> = l.positions.iter().map(|p| p.0).collect();
196        assert!(xs[0] < xs[1] && xs[1] < xs[2] && xs[2] < xs[3]);
197    }
198
199    #[test]
200    fn cycle_does_not_loop() {
201        // 0 → 1 → 0
202        let edges = [(0, 1), (1, 0)];
203        let l = sugiyama_layout(2, &edges, Rect::new(0.0, 0.0, 100.0, 100.0));
204        assert_eq!(l.positions.len(), 2);
205        assert!(l.positions[0].0.is_finite() && l.positions[0].1.is_finite());
206    }
207
208    #[test]
209    fn fan_out_distributes_children_vertically() {
210        // 0 → {1, 2, 3, 4}
211        let edges = [(0, 1), (0, 2), (0, 3), (0, 4)];
212        let l = sugiyama_layout(5, &edges, Rect::new(0.0, 0.0, 200.0, 200.0));
213        let ys: Vec<f32> = (1..=4).map(|i| l.positions[i].1).collect();
214        let unique_ys: std::collections::HashSet<i32> =
215            ys.iter().map(|y| (*y * 10.0) as i32).collect();
216        assert!(unique_ys.len() >= 3, "ys deberían ser distintos: {ys:?}");
217    }
218
219    #[test]
220    fn positions_fall_within_area() {
221        let edges = [(0, 1), (1, 2), (0, 3), (3, 4)];
222        let area = Rect::new(50.0, 100.0, 400.0, 300.0);
223        let l = sugiyama_layout(5, &edges, area);
224        for &(x, y) in &l.positions {
225            assert!(x >= area.x && x <= area.x + area.w + 1.0);
226            assert!(y >= area.y && y <= area.y + area.h + 1.0);
227        }
228    }
229}