flutmax_codegen/
layout.rs

1/// Sugiyama (layered graph drawing) auto-layout algorithm.
2///
3/// 4-phase approach:
4/// 1. Layer assignment (longest path from sources)
5/// 2. Build layer structure
6/// 3. Crossing reduction (barycenter heuristic)
7/// 4. Coordinate assignment
8use std::collections::{HashMap, VecDeque};
9
10use flutmax_sema::graph::{PatchGraph, PatchNode};
11
12/// Layout result: node positions and patcher dimensions.
13pub struct LayoutResult {
14    /// node_id -> (x, y) position
15    pub positions: HashMap<String, (f64, f64)>,
16    /// Computed patcher dimensions (width, height)
17    pub patcher_size: (f64, f64),
18}
19
20// ─── Layout constants ───
21
22const LAYER_SPACING: f64 = 70.0;
23const NODE_SPACING: f64 = 130.0;
24const MARGIN_X: f64 = 50.0;
25const MARGIN_Y: f64 = 50.0;
26
27/// Compute a Sugiyama layered layout for the given patch graph.
28pub fn sugiyama_layout(graph: &PatchGraph) -> LayoutResult {
29    if graph.nodes.is_empty() {
30        return LayoutResult {
31            positions: HashMap::new(),
32            patcher_size: (200.0, 200.0),
33        };
34    }
35
36    // Phase 1: Assign layers (longest path from sources)
37    let node_layers = assign_layers(graph);
38
39    // Phase 2: Build layer structure
40    let mut layers = build_layers(&node_layers, graph);
41
42    // Phase 3: Reduce crossings (barycenter heuristic)
43    reduce_crossings(&mut layers, graph);
44
45    // Phase 4: Assign coordinates
46    assign_coordinates(&layers)
47}
48
49// ─── Phase 1: Layer Assignment ───
50
51fn assign_layers(graph: &PatchGraph) -> HashMap<String, usize> {
52    // Build adjacency (forward edges only, skip feedback)
53    let mut in_degree: HashMap<&str, usize> = HashMap::new();
54    let mut adjacency: HashMap<&str, Vec<&str>> = HashMap::new();
55
56    for node in &graph.nodes {
57        in_degree.entry(node.id.as_str()).or_insert(0);
58        adjacency.entry(node.id.as_str()).or_default();
59    }
60
61    for edge in &graph.edges {
62        if edge.is_feedback {
63            continue;
64        }
65        *in_degree.entry(edge.dest_id.as_str()).or_insert(0) += 1;
66        adjacency
67            .entry(edge.source_id.as_str())
68            .or_default()
69            .push(edge.dest_id.as_str());
70    }
71
72    // Find source nodes (in_degree == 0)
73    let sources: Vec<&str> = in_degree
74        .iter()
75        .filter(|(_, &deg)| deg == 0)
76        .map(|(&id, _)| id)
77        .collect();
78
79    // BFS longest-path layer assignment
80    let mut layers: HashMap<String, usize> = HashMap::new();
81    let mut queue: VecDeque<&str> = VecDeque::new();
82
83    for &src in &sources {
84        layers.insert(src.to_string(), 0);
85        queue.push_back(src);
86    }
87
88    // Process nodes: for each node, propagate max(current_layer + 1) to successors
89    let mut visited_counts: HashMap<&str, usize> = HashMap::new();
90
91    while let Some(current) = queue.pop_front() {
92        let current_layer = layers.get(current).copied().unwrap_or(0);
93
94        if let Some(neighbors) = adjacency.get(current) {
95            for &next in neighbors {
96                let new_layer = current_layer + 1;
97                let existing = layers.get(next).copied().unwrap_or(0);
98                if new_layer > existing {
99                    layers.insert(next.to_string(), new_layer);
100                }
101
102                // Track visit count to know when all predecessors are processed
103                let count = visited_counts.entry(next).or_insert(0);
104                *count += 1;
105                let needed = in_degree.get(next).copied().unwrap_or(0);
106                if *count >= needed {
107                    queue.push_back(next);
108                }
109            }
110        }
111    }
112
113    // Handle isolated nodes (no edges at all)
114    for node in &graph.nodes {
115        layers.entry(node.id.clone()).or_insert(0);
116    }
117
118    layers
119}
120
121// ─── Phase 2: Build Layer Structure ───
122
123fn build_layers<'a>(
124    node_layers: &HashMap<String, usize>,
125    graph: &'a PatchGraph,
126) -> Vec<Vec<&'a PatchNode>> {
127    let max_layer = node_layers.values().copied().max().unwrap_or(0);
128    let mut layers: Vec<Vec<&PatchNode>> = vec![vec![]; max_layer + 1];
129
130    for node in &graph.nodes {
131        let layer = node_layers.get(&node.id).copied().unwrap_or(0);
132        layers[layer].push(node);
133    }
134
135    // Initial ordering: inlets first, then signal objects, then control, then outlets
136    for layer in &mut layers {
137        layer.sort_by(|a, b| {
138            let a_priority = node_sort_priority(a);
139            let b_priority = node_sort_priority(b);
140            a_priority.cmp(&b_priority).then(a.id.cmp(&b.id))
141        });
142    }
143
144    layers
145}
146
147fn node_sort_priority(node: &PatchNode) -> u32 {
148    match node.object_name.as_str() {
149        "inlet" | "inlet~" => 0,
150        "outlet" | "outlet~" => 3,
151        _ if node.is_signal => 1,
152        _ => 2,
153    }
154}
155
156// ─── Phase 3: Crossing Reduction ───
157
158fn reduce_crossings(layers: &mut [Vec<&PatchNode>], graph: &PatchGraph) {
159    if layers.len() < 2 {
160        return;
161    }
162
163    // Build up/down adjacency maps (non-feedback edges only)
164    let mut down_adj: HashMap<&str, Vec<&str>> = HashMap::new();
165    let mut up_adj: HashMap<&str, Vec<&str>> = HashMap::new();
166
167    for edge in &graph.edges {
168        if edge.is_feedback {
169            continue;
170        }
171        down_adj
172            .entry(edge.source_id.as_str())
173            .or_default()
174            .push(edge.dest_id.as_str());
175        up_adj
176            .entry(edge.dest_id.as_str())
177            .or_default()
178            .push(edge.source_id.as_str());
179    }
180
181    // Barycenter heuristic: sweep down then up, repeat 4 times
182    for _iteration in 0..4 {
183        // Down sweep
184        for layer_idx in 1..layers.len() {
185            let prev_positions: HashMap<&str, f64> = layers[layer_idx - 1]
186                .iter()
187                .enumerate()
188                .map(|(i, n)| (n.id.as_str(), i as f64))
189                .collect();
190
191            layers[layer_idx].sort_by(|a, b| {
192                let a_bary = barycenter(a.id.as_str(), &up_adj, &prev_positions);
193                let b_bary = barycenter(b.id.as_str(), &up_adj, &prev_positions);
194                a_bary
195                    .partial_cmp(&b_bary)
196                    .unwrap_or(std::cmp::Ordering::Equal)
197            });
198        }
199
200        // Up sweep
201        for layer_idx in (0..layers.len().saturating_sub(1)).rev() {
202            let next_positions: HashMap<&str, f64> = layers[layer_idx + 1]
203                .iter()
204                .enumerate()
205                .map(|(i, n)| (n.id.as_str(), i as f64))
206                .collect();
207
208            layers[layer_idx].sort_by(|a, b| {
209                let a_bary = barycenter(a.id.as_str(), &down_adj, &next_positions);
210                let b_bary = barycenter(b.id.as_str(), &down_adj, &next_positions);
211                a_bary
212                    .partial_cmp(&b_bary)
213                    .unwrap_or(std::cmp::Ordering::Equal)
214            });
215        }
216    }
217}
218
219fn barycenter(
220    node_id: &str,
221    adj: &HashMap<&str, Vec<&str>>,
222    positions: &HashMap<&str, f64>,
223) -> f64 {
224    let neighbors = match adj.get(node_id) {
225        Some(n) if !n.is_empty() => n,
226        _ => return f64::MAX, // No connections -> place at end
227    };
228
229    let mut sum: f64 = 0.0;
230    let mut count: usize = 0;
231
232    for &n in neighbors {
233        if let Some(&pos) = positions.get(n) {
234            sum += pos;
235            count += 1;
236        }
237    }
238
239    if count == 0 {
240        f64::MAX
241    } else {
242        sum / count as f64
243    }
244}
245
246// ─── Phase 4: Coordinate Assignment ───
247
248fn assign_coordinates(layers: &[Vec<&PatchNode>]) -> LayoutResult {
249    let mut positions = HashMap::new();
250    let mut max_x: f64 = 0.0;
251    let mut max_y: f64 = 0.0;
252
253    for (layer_idx, layer) in layers.iter().enumerate() {
254        let y = MARGIN_Y + (layer_idx as f64) * LAYER_SPACING;
255
256        for (node_idx, node) in layer.iter().enumerate() {
257            let x = MARGIN_X + (node_idx as f64) * NODE_SPACING;
258            positions.insert(node.id.clone(), (x, y));
259            if x > max_x {
260                max_x = x;
261            }
262        }
263        if y > max_y {
264            max_y = y;
265        }
266    }
267
268    LayoutResult {
269        positions,
270        patcher_size: (
271            max_x + NODE_SPACING + MARGIN_X,
272            max_y + LAYER_SPACING + MARGIN_Y,
273        ),
274    }
275}
276
277#[cfg(test)]
278mod tests {
279    use super::*;
280    use flutmax_sema::graph::{NodePurity, PatchEdge, PatchGraph, PatchNode};
281
282    fn make_node(id: &str, object_name: &str, is_signal: bool) -> PatchNode {
283        PatchNode {
284            id: id.into(),
285            object_name: object_name.into(),
286            args: vec![],
287            num_inlets: if object_name.starts_with("inlet") {
288                0
289            } else {
290                1
291            },
292            num_outlets: if object_name.starts_with("outlet") {
293                0
294            } else {
295                1
296            },
297            is_signal,
298            varname: None,
299            hot_inlets: vec![],
300            purity: NodePurity::Unknown,
301            attrs: vec![],
302            code: None,
303        }
304    }
305
306    fn make_edge(src: &str, dst: &str) -> PatchEdge {
307        PatchEdge {
308            source_id: src.into(),
309            source_outlet: 0,
310            dest_id: dst.into(),
311            dest_inlet: 0,
312            is_feedback: false,
313            order: None,
314        }
315    }
316
317    #[test]
318    fn test_empty_graph() {
319        let graph = PatchGraph::new();
320        let result = sugiyama_layout(&graph);
321        assert!(result.positions.is_empty());
322        assert_eq!(result.patcher_size, (200.0, 200.0));
323    }
324
325    #[test]
326    fn test_single_node() {
327        let mut graph = PatchGraph::new();
328        graph.add_node(make_node("a", "cycle~", true));
329
330        let result = sugiyama_layout(&graph);
331        assert_eq!(result.positions.len(), 1);
332        let (x, y) = result.positions["a"];
333        assert_eq!(x, MARGIN_X);
334        assert_eq!(y, MARGIN_Y);
335    }
336
337    #[test]
338    fn test_linear_chain() {
339        // A -> B -> C: 3 layers, 1 node each
340        let mut graph = PatchGraph::new();
341        graph.add_node(make_node("a", "cycle~", true));
342        graph.add_node(make_node("b", "*~", true));
343        graph.add_node(make_node("c", "ezdac~", true));
344        graph.add_edge(make_edge("a", "b"));
345        graph.add_edge(make_edge("b", "c"));
346
347        let result = sugiyama_layout(&graph);
348        assert_eq!(result.positions.len(), 3);
349
350        let (ax, ay) = result.positions["a"];
351        let (bx, by) = result.positions["b"];
352        let (cx, cy) = result.positions["c"];
353
354        // All should be in the same column (x = MARGIN_X)
355        assert_eq!(ax, MARGIN_X);
356        assert_eq!(bx, MARGIN_X);
357        assert_eq!(cx, MARGIN_X);
358
359        // Each layer is deeper
360        assert!(ay < by);
361        assert!(by < cy);
362
363        // Spacing should be LAYER_SPACING
364        assert!((by - ay - LAYER_SPACING).abs() < 0.01);
365        assert!((cy - by - LAYER_SPACING).abs() < 0.01);
366    }
367
368    #[test]
369    fn test_diamond_graph() {
370        // A -> B, A -> C, B -> D, C -> D
371        // Layer 0: A, Layer 1: B,C, Layer 2: D
372        let mut graph = PatchGraph::new();
373        graph.add_node(make_node("a", "button", false));
374        graph.add_node(make_node("b", "+", false));
375        graph.add_node(make_node("c", "*", false));
376        graph.add_node(make_node("d", "print", false));
377        graph.add_edge(make_edge("a", "b"));
378        graph.add_edge(make_edge("a", "c"));
379        graph.add_edge(make_edge("b", "d"));
380        graph.add_edge(make_edge("c", "d"));
381
382        let result = sugiyama_layout(&graph);
383        assert_eq!(result.positions.len(), 4);
384
385        let (_, ay) = result.positions["a"];
386        let (_, by) = result.positions["b"];
387        let (_, cy) = result.positions["c"];
388        let (_, dy) = result.positions["d"];
389
390        // A in layer 0, B and C in layer 1, D in layer 2
391        assert!((ay - MARGIN_Y).abs() < 0.01);
392        assert!((by - (MARGIN_Y + LAYER_SPACING)).abs() < 0.01);
393        assert!((cy - (MARGIN_Y + LAYER_SPACING)).abs() < 0.01);
394        assert!((dy - (MARGIN_Y + 2.0 * LAYER_SPACING)).abs() < 0.01);
395
396        // B and C should be side by side (different x)
397        let (bx, _) = result.positions["b"];
398        let (cx, _) = result.positions["c"];
399        assert!((bx - cx).abs() > 1.0, "B and C should have different x");
400    }
401
402    #[test]
403    fn test_fanout() {
404        // A -> B, A -> C, A -> D
405        // Layer 0: A, Layer 1: B, C, D
406        let mut graph = PatchGraph::new();
407        graph.add_node(make_node("a", "button", false));
408        graph.add_node(make_node("b", "print", false));
409        graph.add_node(make_node("c", "int", false));
410        graph.add_node(make_node("d", "float", false));
411        graph.add_edge(make_edge("a", "b"));
412        graph.add_edge(make_edge("a", "c"));
413        graph.add_edge(make_edge("a", "d"));
414
415        let result = sugiyama_layout(&graph);
416        assert_eq!(result.positions.len(), 4);
417
418        let (_, ay) = result.positions["a"];
419        let (_, by) = result.positions["b"];
420        let (_, cy) = result.positions["c"];
421        let (_, dy) = result.positions["d"];
422
423        // A in layer 0, B/C/D in layer 1
424        assert!((ay - MARGIN_Y).abs() < 0.01);
425        assert!((by - (MARGIN_Y + LAYER_SPACING)).abs() < 0.01);
426        assert!((cy - (MARGIN_Y + LAYER_SPACING)).abs() < 0.01);
427        assert!((dy - (MARGIN_Y + LAYER_SPACING)).abs() < 0.01);
428
429        // Collect x positions of B, C, D - they should all be distinct
430        let bx = result.positions["b"].0;
431        let cx = result.positions["c"].0;
432        let dx = result.positions["d"].0;
433        let mut xs = vec![bx, cx, dx];
434        xs.sort_by(|a, b| a.partial_cmp(b).unwrap());
435        assert!(xs[1] - xs[0] > 1.0, "nodes in same layer should be spread");
436        assert!(xs[2] - xs[1] > 1.0, "nodes in same layer should be spread");
437    }
438
439    #[test]
440    fn test_inlet_outlet_placement() {
441        // inlet -> cycle~ -> outlet~
442        // inlets should be in layer 0 (top), outlets in the last layer (bottom)
443        let mut graph = PatchGraph::new();
444        graph.add_node(make_node("in0", "inlet", false));
445        graph.add_node(make_node("osc", "cycle~", true));
446        graph.add_node(make_node("out0", "outlet~", true));
447        graph.add_edge(make_edge("in0", "osc"));
448        graph.add_edge(make_edge("osc", "out0"));
449
450        let result = sugiyama_layout(&graph);
451        let (_, in_y) = result.positions["in0"];
452        let (_, osc_y) = result.positions["osc"];
453        let (_, out_y) = result.positions["out0"];
454
455        // inlet at top, outlet at bottom
456        assert!(in_y < osc_y, "inlet should be above cycle~");
457        assert!(osc_y < out_y, "cycle~ should be above outlet~");
458    }
459
460    #[test]
461    fn test_feedback_edges_excluded() {
462        // A -> B (normal), B -> A (feedback)
463        // Without feedback exclusion, this would be a cycle.
464        // With feedback exclusion, A is layer 0, B is layer 1.
465        let mut graph = PatchGraph::new();
466        graph.add_node(make_node("a", "tapin~", true));
467        graph.add_node(make_node("b", "tapout~", true));
468        graph.add_edge(PatchEdge {
469            source_id: "a".into(),
470            source_outlet: 0,
471            dest_id: "b".into(),
472            dest_inlet: 0,
473            is_feedback: false,
474            order: None,
475        });
476        graph.add_edge(PatchEdge {
477            source_id: "b".into(),
478            source_outlet: 0,
479            dest_id: "a".into(),
480            dest_inlet: 0,
481            is_feedback: true,
482            order: None,
483        });
484
485        let result = sugiyama_layout(&graph);
486        let (_, ay) = result.positions["a"];
487        let (_, by) = result.positions["b"];
488        assert!(
489            ay < by,
490            "tapin~ should be above tapout~ (feedback edge excluded)"
491        );
492    }
493
494    #[test]
495    fn test_isolated_nodes() {
496        // Two disconnected nodes
497        let mut graph = PatchGraph::new();
498        graph.add_node(make_node("a", "cycle~", true));
499        graph.add_node(make_node("b", "noise~", true));
500
501        let result = sugiyama_layout(&graph);
502        assert_eq!(result.positions.len(), 2);
503
504        // Both should be in layer 0 (no edges)
505        let (_, ay) = result.positions["a"];
506        let (_, by) = result.positions["b"];
507        assert!((ay - MARGIN_Y).abs() < 0.01);
508        assert!((by - MARGIN_Y).abs() < 0.01);
509
510        // But at different x positions
511        let ax = result.positions["a"].0;
512        let bx = result.positions["b"].0;
513        assert!(
514            (ax - bx).abs() > 1.0,
515            "isolated nodes should be side by side"
516        );
517    }
518
519    #[test]
520    fn test_crossing_reduction_improves_layout() {
521        // Graph: A -> C, B -> D, A -> D, B -> C
522        // Without crossing reduction, if layer 1 is [C, D],
523        // edges A->D and B->C would cross.
524        // Barycenter heuristic should swap to minimize crossings.
525        let mut graph = PatchGraph::new();
526        graph.add_node(make_node("a", "button", false));
527        graph.add_node(make_node("b", "toggle", false));
528        graph.add_node(make_node("c", "print", false));
529        graph.add_node(make_node("d", "int", false));
530        graph.add_edge(make_edge("a", "c"));
531        graph.add_edge(make_edge("a", "d"));
532        graph.add_edge(make_edge("b", "d"));
533
534        let result = sugiyama_layout(&graph);
535
536        // a and b should be in layer 0, c and d in layer 1
537        let (_, ay) = result.positions["a"];
538        let (_, by) = result.positions["b"];
539        assert!((ay - by).abs() < 0.01, "a and b should be in same layer");
540
541        let (_, cy) = result.positions["c"];
542        let (_, dy) = result.positions["d"];
543        assert!((cy - dy).abs() < 0.01, "c and d should be in same layer");
544    }
545
546    #[test]
547    fn test_patcher_size_scales_with_graph() {
548        let mut graph = PatchGraph::new();
549        graph.add_node(make_node("a", "button", false));
550        graph.add_node(make_node("b", "+", false));
551        graph.add_node(make_node("c", "*", false));
552        graph.add_node(make_node("d", "print", false));
553        graph.add_edge(make_edge("a", "b"));
554        graph.add_edge(make_edge("a", "c"));
555        graph.add_edge(make_edge("b", "d"));
556        graph.add_edge(make_edge("c", "d"));
557
558        let result = sugiyama_layout(&graph);
559
560        // Patcher should be at least big enough to contain all nodes
561        let (pw, ph) = result.patcher_size;
562        for (_, (x, y)) in &result.positions {
563            assert!(*x < pw, "node x should be within patcher width");
564            assert!(*y < ph, "node y should be within patcher height");
565        }
566    }
567}
flutmax_codegen/layout.rs

flutmax_codegen/
layout.rs
