kyu_visualizer/graph/
layout.rs

1//! Fruchterman-Reingold force-directed graph layout.
2//!
3//! O(n²) per iteration — acceptable for MVP with ≤2000 nodes.
4//! Runs a few steps per frame; pinned nodes are excluded from displacement.
5
6use crate::state::{GraphData, Vec2};
7
8/// Configuration for the layout algorithm.
9pub struct LayoutConfig {
10    /// Width × Height of the layout area.
11    pub area: f32,
12    /// Cooling factor per step (0.95 typical).
13    pub cooling: f32,
14}
15
16impl Default for LayoutConfig {
17    fn default() -> Self {
18        Self {
19            area: 200_000.0, // ~450 × 450, fits within typical canvas bounds
20            cooling: 0.95,
21        }
22    }
23}
24
25/// Run one iteration of Fruchterman-Reingold layout.
26///
27/// Returns `true` if the temperature is still above threshold (keep running).
28pub fn layout_step(graph: &mut GraphData, temperature: &mut f32, config: &LayoutConfig) -> bool {
29    let n = graph.nodes.len();
30    if n == 0 {
31        return false;
32    }
33
34    let k = (config.area / n as f32).sqrt();
35    let k_sq = k * k;
36
37    // Accumulate displacements.
38    let mut disp: Vec<Vec2> = vec![Vec2::default(); n];
39
40    // 1. Repulsive forces: all pairs push apart.
41    for i in 0..n {
42        for j in (i + 1)..n {
43            let delta = graph.nodes[i].pos - graph.nodes[j].pos;
44            let dist_sq = delta.x * delta.x + delta.y * delta.y;
45            let dist = dist_sq.sqrt().max(0.01);
46            // Repulsive force: k² / dist
47            let force = k_sq / dist;
48            let dir = delta * (force / dist);
49            disp[i] += dir;
50            disp[j] = disp[j] - dir;
51        }
52    }
53
54    // 2. Attractive forces: edges pull connected nodes together.
55    for edge in &graph.edges {
56        let delta = graph.nodes[edge.src].pos - graph.nodes[edge.dst].pos;
57        let dist = delta.length().max(0.01);
58        // Attractive force: dist² / k
59        let force = dist * dist / k;
60        let dir = delta * (force / dist);
61        disp[edge.src] = disp[edge.src] - dir;
62        disp[edge.dst] += dir;
63    }
64
65    // 3. Apply displacement capped by temperature.
66    for (i, d) in disp.iter().enumerate() {
67        if graph.nodes[i].pinned {
68            continue;
69        }
70        let mag = d.length().max(0.01);
71        let capped = mag.min(*temperature);
72        graph.nodes[i].pos += *d * (capped / mag);
73    }
74
75    // 4. Cool temperature.
76    *temperature *= config.cooling;
77
78    *temperature > 0.1
79}
80
81/// Reset layout: randomize positions and set temperature.
82pub fn reset_temperature(node_count: usize) -> f32 {
83    // Initial temperature proportional to sqrt of area.
84    (200_000.0_f32 / node_count.max(1) as f32).sqrt() * 0.5
85}
86
87/// Run multiple layout steps (for per-frame batch).
88pub fn layout_batch(graph: &mut GraphData, temperature: &mut f32, steps: usize) -> bool {
89    let config = LayoutConfig::default();
90    let mut running = true;
91    for _ in 0..steps {
92        running = layout_step(graph, temperature, &config);
93        if !running {
94            break;
95        }
96    }
97    running
98}
99
100/// Center the graph at the origin after layout has converged.
101pub fn center_graph(graph: &mut GraphData) {
102    if graph.nodes.is_empty() {
103        return;
104    }
105    let n = graph.nodes.len() as f32;
106    let cx: f32 = graph.nodes.iter().map(|n| n.pos.x).sum::<f32>() / n;
107    let cy: f32 = graph.nodes.iter().map(|n| n.pos.y).sum::<f32>() / n;
108    for node in &mut graph.nodes {
109        node.pos.x -= cx;
110        node.pos.y -= cy;
111    }
112}
kyu_visualizer/graph/layout.rs

kyu_visualizer/graph/
layout.rs
