Skip to main content

slint_node_editor/
layout.rs

1//! Sugiyama hierarchical graph layout.
2//!
3//! This module provides functions for computing hierarchical (layered) layouts
4//! of directed graphs using the Sugiyama algorithm via the `rust-sugiyama` crate.
5//!
6//! The layout API uses `f64` coordinates because the underlying `rust-sugiyama`
7//! crate operates in `f64`. The rest of this crate uses `f32` (matching Slint),
8//! so callers should convert with `as f32` when applying positions back to nodes.
9//!
10//! Requires the `layout` feature to be enabled.
11
12use std::collections::{BTreeMap, BTreeSet};
13
14use crate::hit_test::NodeGeometry;
15use crate::state::GeometryCache;
16
17/// Layout direction for the Sugiyama algorithm.
18///
19/// Marked `#[non_exhaustive]` so additional directions (e.g. `RightToLeft`,
20/// `BottomToTop`) can be added in future versions without breaking callers.
21#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
22#[non_exhaustive]
23pub enum Direction {
24    /// Layers flow top to bottom (default).
25    #[default]
26    TopToBottom,
27    /// Layers flow left to right.
28    LeftToRight,
29}
30
31/// A positioned node returned by [`sugiyama_layout`].
32#[derive(Debug, Clone, Copy, PartialEq)]
33pub struct NodePosition {
34    /// The node ID (same value passed in via `node_sizes`).
35    pub id: i32,
36    /// X coordinate of the node's top-left corner.
37    pub x: f64,
38    /// Y coordinate of the node's top-left corner.
39    pub y: f64,
40}
41
42/// Configuration for the Sugiyama layout algorithm.
43#[derive(Debug, Clone, Copy, Default)]
44#[non_exhaustive]
45pub struct SugiyamaConfig {
46    /// Minimum spacing between vertices (default: 0.0, which uses the
47    /// `rust-sugiyama` default of 10.0).
48    pub vertex_spacing: f64,
49    /// Minimum edge length between layers (default: 0, which uses the
50    /// `rust-sugiyama` default of 1).
51    pub minimum_length: u32,
52    /// Whether to include dummy vertices in the layout (default: false).
53    pub dummy_vertices: bool,
54    /// Layout direction (default: [`Direction::TopToBottom`]).
55    pub direction: Direction,
56}
57
58/// Compute Sugiyama hierarchical layout positions.
59///
60/// Takes edges as `(source_node_id, target_node_id)` pairs and node sizes as
61/// `(node_id, (width, height))` pairs. Returns a [`NodePosition`] for each node.
62///
63/// Node IDs can be any `i32` values — they are mapped to sequential `u32` indices
64/// internally for `rust-sugiyama` and translated back before returning.
65///
66/// Duplicate node IDs in `node_sizes` are ignored (first occurrence wins),
67/// then nodes are ordered by ID. Nodes whose width or height is non-finite or
68/// not positive are omitted. Edges with an omitted or unknown endpoint,
69/// self-loops, and duplicate edges are ignored; retained edges are ordered by
70/// their node-ID pair. Results are returned in ascending node-ID order.
71pub fn sugiyama_layout(
72    edges: &[(i32, i32)],
73    node_sizes: &[(i32, (f64, f64))],
74    config: &SugiyamaConfig,
75) -> Vec<NodePosition> {
76    let horizontal = config.direction == Direction::LeftToRight;
77
78    // Preserve the documented first occurrence, then let BTreeMap provide the
79    // canonical node-ID order used by every downstream table.
80    let mut nodes_by_id = BTreeMap::new();
81    for &(node_id, size) in node_sizes {
82        nodes_by_id.entry(node_id).or_insert(size);
83    }
84    nodes_by_id.retain(|_, (width, height)| {
85        width.is_finite() && *width > 0.0 && height.is_finite() && *height > 0.0
86    });
87    let nodes: Vec<(i32, (f64, f64))> = nodes_by_id.into_iter().collect();
88    if nodes.is_empty() {
89        return Vec::new();
90    }
91
92    let id_to_idx: BTreeMap<i32, u32> = nodes
93        .iter()
94        .enumerate()
95        .map(|(idx, &(node_id, _))| (node_id, idx as u32))
96        .collect();
97
98    // For horizontal layout, swap width/height so the algorithm spaces layers
99    // along what will become the x-axis.
100    let vertices: Vec<(u32, (f64, f64))> = nodes
101        .iter()
102        .enumerate()
103        .map(|(idx, &(_, (width, height)))| {
104            let size = if horizontal {
105                (height, width)
106            } else {
107                (width, height)
108            };
109            (idx as u32, size)
110        })
111        .collect();
112
113    let mapped_edges: Vec<(u32, u32)> = edges
114        .iter()
115        .filter(|(src, dst)| src != dst)
116        .filter_map(|&(src, dst)| Some((*id_to_idx.get(&src)?, *id_to_idx.get(&dst)?)))
117        .collect::<BTreeSet<_>>()
118        .into_iter()
119        .collect();
120
121    // Configure rust-sugiyama
122    let mut sg_config = rust_sugiyama::configure::Config {
123        dummy_vertices: config.dummy_vertices,
124        ..Default::default()
125    };
126    if config.vertex_spacing > 0.0 {
127        sg_config.vertex_spacing = config.vertex_spacing;
128    }
129    if config.minimum_length > 0 {
130        sg_config.minimum_length = config.minimum_length;
131    }
132
133    // Run layout — returns Vec<(Vec<(usize, (f64, f64))>, f64, f64)> (subgraphs)
134    let mut subgraphs =
135        rust_sugiyama::from_vertices_and_edges(&vertices, &mapped_edges, &sg_config);
136    subgraphs.sort_by_key(|(layout, _, _)| {
137        layout
138            .iter()
139            .filter_map(|(idx, _)| nodes.get(*idx).map(|(node_id, _)| *node_id))
140            .min()
141            .unwrap_or(i32::MAX)
142    });
143
144    // Collect results from all subgraphs, translating indices back to node IDs.
145    // For horizontal layout, swap x/y so layers run left-to-right.
146    // Each subgraph is offset along the perpendicular axis so disconnected
147    // components (and isolated nodes) don't overlap.
148    let spacing = if config.vertex_spacing > 0.0 {
149        config.vertex_spacing
150    } else {
151        10.0
152    };
153    let mut results = Vec::with_capacity(nodes.len());
154    let mut perpendicular_offset = 0.0_f64;
155
156    for (layout, _width, _height) in &subgraphs {
157        // Compute bounding box of this subgraph in output coordinates
158        let mut min_perp = f64::INFINITY;
159        let mut max_perp = f64::NEG_INFINITY;
160
161        let start = results.len();
162        for &(idx, (x, y)) in layout {
163            if let Some(&(node_id, (node_width, node_height))) = nodes.get(idx) {
164                let (px, py) = if horizontal { (y, x) } else { (x, y) };
165                results.push(NodePosition {
166                    id: node_id,
167                    x: px,
168                    y: py,
169                });
170
171                let (perpendicular_position, perpendicular_size) = if horizontal {
172                    (py, node_height)
173                } else {
174                    (px, node_width)
175                };
176                min_perp = min_perp.min(perpendicular_position);
177                max_perp = max_perp.max(perpendicular_position + perpendicular_size);
178            }
179        }
180
181        if start < results.len() {
182            // Shift this subgraph so its perpendicular leading edge sits at
183            // the running offset.
184            let shift = perpendicular_offset - min_perp;
185            for pos in &mut results[start..] {
186                if horizontal {
187                    pos.y += shift;
188                } else {
189                    pos.x += shift;
190                }
191            }
192            perpendicular_offset += max_perp - min_perp + spacing;
193        }
194    }
195
196    results.sort_by_key(|position| position.id);
197    results
198}
199
200/// Compute Sugiyama layout using data from a [`GeometryCache`].
201///
202/// Edges are given as `(start_pin_id, end_pin_id)` pairs — the same format used
203/// by link models. Pin IDs are resolved to node IDs via `cache.pin_positions`,
204/// and node dimensions are read from `cache.node_rects`.
205///
206/// Unknown pins are ignored. Resolved edges then use the raw layout policy:
207/// missing node endpoints, self-loops, and duplicate node pairs are ignored.
208/// Cache `HashMap` iteration cannot affect the result because the raw layout
209/// canonicalizes nodes and edges before invoking the algorithm.
210///
211/// Returns a [`NodePosition`] for each laid-out node.
212pub fn sugiyama_layout_from_cache<N>(
213    cache: &GeometryCache<N>,
214    edges: &[(i32, i32)],
215    config: &SugiyamaConfig,
216) -> Vec<NodePosition>
217where
218    N: NodeGeometry + Copy,
219{
220    // Resolve known pin IDs to node IDs. The raw API owns canonical edge
221    // filtering so both entry points have the same self-loop/duplicate policy.
222    let node_edges: Vec<(i32, i32)> = edges
223        .iter()
224        .filter_map(|&(start_pin, end_pin)| {
225            let src_node = cache.pin_positions.get(&start_pin)?.node_id;
226            let dst_node = cache.pin_positions.get(&end_pin)?.node_id;
227            Some((src_node, dst_node))
228        })
229        .collect();
230
231    // Extract node sizes from cache
232    let node_sizes: Vec<(i32, (f64, f64))> = cache
233        .node_rects
234        .iter()
235        .map(|(&id, geom)| {
236            let (_, _, w, h) = geom.rect();
237            (id, (w as f64, h as f64))
238        })
239        .collect();
240
241    sugiyama_layout(&node_edges, &node_sizes, config)
242}
243
244#[cfg(test)]
245mod tests {
246    use super::*;
247    use std::collections::HashMap;
248
249    /// Helper to collect positions into a HashMap for easy lookup.
250    fn pos_map(positions: Vec<NodePosition>) -> HashMap<i32, (f64, f64)> {
251        positions.into_iter().map(|p| (p.id, (p.x, p.y))).collect()
252    }
253
254    #[test]
255    fn test_empty_input() {
256        let result = sugiyama_layout(&[], &[], &SugiyamaConfig::default());
257        assert!(result.is_empty());
258    }
259
260    #[test]
261    fn test_single_node_no_edges() {
262        let sizes = vec![(1, (100.0, 50.0))];
263        let result = sugiyama_layout(&[], &sizes, &SugiyamaConfig::default());
264        assert_eq!(result.len(), 1);
265        assert_eq!(result[0].id, 1);
266    }
267
268    #[test]
269    fn test_two_nodes_one_edge() {
270        let sizes = vec![(10, (100.0, 50.0)), (20, (100.0, 50.0))];
271        let edges = vec![(10, 20)];
272        let result = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
273        assert_eq!(result.len(), 2);
274
275        let pos = pos_map(result);
276        assert!(pos.contains_key(&10));
277        assert!(pos.contains_key(&20));
278
279        // Source should be above target in top-to-bottom layout
280        assert!(
281            pos[&10].1 < pos[&20].1,
282            "source node should be in an earlier layer"
283        );
284    }
285
286    #[test]
287    fn test_diamond_dag() {
288        // Diamond: 1 -> 2, 1 -> 3, 2 -> 4, 3 -> 4
289        let sizes = vec![
290            (1, (80.0, 40.0)),
291            (2, (80.0, 40.0)),
292            (3, (80.0, 40.0)),
293            (4, (80.0, 40.0)),
294        ];
295        let edges = vec![(1, 2), (1, 3), (2, 4), (3, 4)];
296        let result = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
297        assert_eq!(result.len(), 4);
298
299        let pos = pos_map(result);
300
301        // Node 1 (root) should be in the first layer, node 4 (sink) in the last
302        assert!(pos[&1].1 < pos[&4].1);
303        // Nodes 2 and 3 should be in the same middle layer
304        assert!((pos[&2].1 - pos[&3].1).abs() < 1.0);
305    }
306
307    #[test]
308    fn test_edges_with_unknown_nodes_are_skipped() {
309        let sizes = vec![(1, (100.0, 50.0))];
310        let edges = vec![(1, 999)]; // 999 not in sizes
311        let result = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
312        // Should still return node 1, just without the edge
313        assert_eq!(result.len(), 1);
314        assert_eq!(result[0].id, 1);
315    }
316
317    #[test]
318    fn test_duplicate_node_ids_first_wins() {
319        let base_sizes = vec![(1, (100.0, 50.0)), (2, (60.0, 30.0))];
320        let duplicate_sizes = vec![(1, (100.0, 50.0)), (1, (500.0, 400.0)), (2, (60.0, 30.0))];
321
322        assert_eq!(
323            sugiyama_layout(&[], &duplicate_sizes, &SugiyamaConfig::default()),
324            sugiyama_layout(&[], &base_sizes, &SugiyamaConfig::default())
325        );
326    }
327
328    #[test]
329    fn invalid_node_dimensions_are_omitted() {
330        let sizes = vec![
331            (1, (100.0, 50.0)),
332            (2, (0.0, 50.0)),
333            (3, (100.0, -1.0)),
334            (4, (f64::NAN, 50.0)),
335            (5, (100.0, f64::INFINITY)),
336            // First occurrence wins even when it is invalid.
337            (2, (100.0, 50.0)),
338        ];
339
340        let result = sugiyama_layout(&[(1, 2)], &sizes, &SugiyamaConfig::default());
341        assert_eq!(result.len(), 1);
342        assert_eq!(result[0].id, 1);
343        assert!(result[0].x.is_finite());
344        assert!(result[0].y.is_finite());
345    }
346
347    #[test]
348    fn raw_layout_ignores_duplicate_self_and_unknown_edges() {
349        let sizes = vec![(1, (80.0, 40.0)), (2, (80.0, 40.0)), (3, (80.0, 40.0))];
350        let expected = sugiyama_layout(&[(1, 2)], &sizes, &SugiyamaConfig::default());
351        let noisy = sugiyama_layout(
352            &[(1, 2), (1, 2), (1, 1), (3, 3), (1, 999), (999, 2)],
353            &sizes,
354            &SugiyamaConfig::default(),
355        );
356
357        assert_eq!(noisy, expected);
358    }
359
360    #[test]
361    fn equivalent_input_permutations_have_identical_positions_and_order() {
362        let sizes = vec![
363            (30, (70.0, 35.0)),
364            (10, (80.0, 40.0)),
365            (40, (90.0, 45.0)),
366            (20, (60.0, 30.0)),
367        ];
368        let mut reversed_sizes = sizes.clone();
369        reversed_sizes.reverse();
370        let edges = vec![(10, 20), (10, 30), (20, 40), (30, 40)];
371        let mut reversed_edges = edges.clone();
372        reversed_edges.reverse();
373
374        for direction in [Direction::TopToBottom, Direction::LeftToRight] {
375            let config = SugiyamaConfig {
376                direction,
377                ..Default::default()
378            };
379            let expected = sugiyama_layout(&edges, &sizes, &config);
380            let actual = sugiyama_layout(&reversed_edges, &reversed_sizes, &config);
381
382            assert_eq!(actual, expected);
383            assert_eq!(
384                actual
385                    .iter()
386                    .map(|position| position.id)
387                    .collect::<Vec<_>>(),
388                vec![10, 20, 30, 40]
389            );
390        }
391    }
392
393    #[test]
394    fn test_config_default() {
395        let config = SugiyamaConfig::default();
396        assert_eq!(config.vertex_spacing, 0.0);
397        assert_eq!(config.minimum_length, 0);
398        assert!(!config.dummy_vertices);
399        assert_eq!(config.direction, Direction::TopToBottom);
400    }
401
402    #[test]
403    fn test_direction_default_is_top_to_bottom() {
404        assert_eq!(Direction::default(), Direction::TopToBottom);
405    }
406
407    #[test]
408    fn test_node_position_fields() {
409        let sizes = vec![(42, (80.0, 40.0))];
410        let result = sugiyama_layout(&[], &sizes, &SugiyamaConfig::default());
411        assert_eq!(result.len(), 1);
412        let pos = result[0];
413        assert_eq!(pos.id, 42);
414        // x and y should be finite numbers
415        assert!(pos.x.is_finite());
416        assert!(pos.y.is_finite());
417    }
418
419    #[test]
420    fn test_left_to_right_swaps_axes() {
421        let sizes = vec![(10, (100.0, 50.0)), (20, (100.0, 50.0))];
422        let edges = vec![(10, 20)];
423
424        let ttb = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
425        let ltr = sugiyama_layout(
426            &edges,
427            &sizes,
428            &SugiyamaConfig {
429                direction: Direction::LeftToRight,
430                ..Default::default()
431            },
432        );
433
434        let ttb_pos = pos_map(ttb);
435        let ltr_pos = pos_map(ltr);
436
437        // In top-to-bottom, layers differ in y; in left-to-right, layers differ in x
438        let ttb_dy = (ttb_pos[&20].1 - ttb_pos[&10].1).abs();
439        let ltr_dx = (ltr_pos[&20].0 - ltr_pos[&10].0).abs();
440
441        assert!(ttb_dy > 1.0, "top-to-bottom should separate layers in y");
442        assert!(ltr_dx > 1.0, "left-to-right should separate layers in x");
443    }
444
445    #[test]
446    fn test_left_to_right_diamond() {
447        let sizes = vec![
448            (1, (80.0, 40.0)),
449            (2, (80.0, 40.0)),
450            (3, (80.0, 40.0)),
451            (4, (80.0, 40.0)),
452        ];
453        let edges = vec![(1, 2), (1, 3), (2, 4), (3, 4)];
454        let config = SugiyamaConfig {
455            direction: Direction::LeftToRight,
456            ..Default::default()
457        };
458        let result = sugiyama_layout(&edges, &sizes, &config);
459        let pos = pos_map(result);
460
461        // Root should be leftmost, sink rightmost
462        assert!(pos[&1].0 < pos[&4].0);
463        // Middle nodes should be at the same x (same layer)
464        assert!((pos[&2].0 - pos[&3].0).abs() < 1.0);
465    }
466
467    #[test]
468    fn test_disconnected_graph() {
469        // Two separate subgraphs: 1->2 and 3->4
470        let sizes = vec![
471            (1, (80.0, 40.0)),
472            (2, (80.0, 40.0)),
473            (3, (80.0, 40.0)),
474            (4, (80.0, 40.0)),
475        ];
476        let edges = vec![(1, 2), (3, 4)];
477        let result = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
478
479        assert_eq!(result.len(), 4);
480        let pos = pos_map(result);
481        assert!(pos.contains_key(&1));
482        assert!(pos.contains_key(&2));
483        assert!(pos.contains_key(&3));
484        assert!(pos.contains_key(&4));
485        // Each subgraph should respect layer ordering
486        assert!(pos[&1].1 < pos[&2].1);
487        assert!(pos[&3].1 < pos[&4].1);
488    }
489
490    #[test]
491    fn test_isolated_nodes_are_packed_on_the_perpendicular_axis() {
492        let sizes = vec![(1, (100.0, 50.0)), (2, (100.0, 50.0)), (3, (100.0, 50.0))];
493
494        let top_to_bottom = sugiyama_layout(&[], &sizes, &SugiyamaConfig::default());
495        assert!(top_to_bottom
496            .windows(2)
497            .all(|pair| pair[0].x + 110.0 <= pair[1].x));
498        assert!(top_to_bottom.windows(2).all(|pair| pair[0].y == pair[1].y));
499
500        let left_to_right = sugiyama_layout(
501            &[],
502            &sizes,
503            &SugiyamaConfig {
504                direction: Direction::LeftToRight,
505                ..Default::default()
506            },
507        );
508        assert!(left_to_right
509            .windows(2)
510            .all(|pair| pair[0].y + 60.0 <= pair[1].y));
511        assert!(left_to_right.windows(2).all(|pair| pair[0].x == pair[1].x));
512    }
513
514    #[test]
515    fn disconnected_components_do_not_overlap_in_either_direction() {
516        let sizes = vec![
517            (1, (100.0, 30.0)),
518            (2, (60.0, 80.0)),
519            (3, (120.0, 40.0)),
520            (4, (50.0, 90.0)),
521        ];
522        let edges = vec![(1, 2), (3, 4)];
523
524        for direction in [Direction::TopToBottom, Direction::LeftToRight] {
525            let positions = pos_map(sugiyama_layout(
526                &edges,
527                &sizes,
528                &SugiyamaConfig {
529                    direction,
530                    ..Default::default()
531                },
532            ));
533            for left_id in [1, 2] {
534                for right_id in [3, 4] {
535                    let (left_x, left_y) = positions[&left_id];
536                    let (right_x, right_y) = positions[&right_id];
537                    let (_, (left_width, left_height)) = sizes
538                        .iter()
539                        .find(|(id, _)| *id == left_id)
540                        .copied()
541                        .unwrap();
542                    let (_, (right_width, right_height)) = sizes
543                        .iter()
544                        .find(|(id, _)| *id == right_id)
545                        .copied()
546                        .unwrap();
547                    assert!(
548                        left_x + left_width <= right_x
549                            || right_x + right_width <= left_x
550                            || left_y + left_height <= right_y
551                            || right_y + right_height <= left_y,
552                        "components overlap in {direction:?}: {left_id} and {right_id}"
553                    );
554                }
555            }
556        }
557    }
558
559    #[test]
560    fn test_cycle_does_not_panic() {
561        // rust-sugiyama handles cycles internally; verify we don't break
562        let sizes = vec![(1, (80.0, 40.0)), (2, (80.0, 40.0)), (3, (80.0, 40.0))];
563        let edges = vec![(1, 2), (2, 3), (3, 1)];
564        let result = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
565
566        // All nodes should still get positions
567        assert_eq!(result.len(), 3);
568        let pos = pos_map(result);
569        assert!(pos[&1].0.is_finite());
570        assert!(pos[&2].0.is_finite());
571        assert!(pos[&3].0.is_finite());
572    }
573
574    // ========================================================================
575    // sugiyama_layout_from_cache() tests
576    // ========================================================================
577
578    use crate::hit_test::SimpleNodeGeometry;
579    use crate::state::StoredPin;
580
581    /// Build a GeometryCache with the given nodes and pins.
582    fn make_cache(
583        nodes: &[(i32, f32, f32, f32, f32)],
584        pins: &[(i32, i32, i32, f32, f32)],
585    ) -> GeometryCache<SimpleNodeGeometry> {
586        let mut cache = GeometryCache::default();
587        for &(id, x, y, w, h) in nodes {
588            cache.node_rects.insert(
589                id,
590                SimpleNodeGeometry {
591                    id,
592                    x,
593                    y,
594                    width: w,
595                    height: h,
596                },
597            );
598        }
599        for &(pin_id, node_id, pin_type, rel_x, rel_y) in pins {
600            cache.pin_positions.insert(
601                pin_id,
602                StoredPin {
603                    node_id,
604                    pin_type,
605                    rel_x,
606                    rel_y,
607                },
608            );
609        }
610        cache
611    }
612
613    #[test]
614    fn test_from_cache_resolves_pins_to_nodes() {
615        // Two nodes with one output pin each and one input pin each
616        // Pin encoding: output = id*2+1, input = id*2
617        let cache = make_cache(
618            &[(1, 0.0, 0.0, 100.0, 50.0), (2, 200.0, 0.0, 100.0, 50.0)],
619            &[
620                (3, 1, 2, 100.0, 25.0), // output pin on node 1
621                (4, 2, 1, 0.0, 25.0),   // input pin on node 2
622            ],
623        );
624        // Edge from pin 3 (node 1 output) → pin 4 (node 2 input)
625        let result = sugiyama_layout_from_cache(&cache, &[(3, 4)], &SugiyamaConfig::default());
626        let pos = pos_map(result);
627
628        assert_eq!(pos.len(), 2);
629        assert!(pos.contains_key(&1));
630        assert!(pos.contains_key(&2));
631        // Node 1 should be above node 2 (top-to-bottom default)
632        assert!(pos[&1].1 < pos[&2].1, "source should be in earlier layer");
633    }
634
635    #[test]
636    fn test_from_cache_skips_self_loops() {
637        // Two pins on the same node — edge between them is a self-loop
638        let cache = make_cache(
639            &[(1, 0.0, 0.0, 100.0, 50.0)],
640            &[
641                (10, 1, 2, 100.0, 25.0), // output pin on node 1
642                (11, 1, 1, 0.0, 25.0),   // input pin on node 1
643            ],
644        );
645        let result = sugiyama_layout_from_cache(&cache, &[(10, 11)], &SugiyamaConfig::default());
646
647        // Node should still appear (it exists in cache), but with no edges
648        assert_eq!(result.len(), 1);
649        assert_eq!(result[0].id, 1);
650    }
651
652    #[test]
653    fn test_from_cache_deduplicates_edges() {
654        // Two separate pin-pairs connecting node 1 → node 2
655        let cache = make_cache(
656            &[(1, 0.0, 0.0, 100.0, 50.0), (2, 200.0, 0.0, 100.0, 50.0)],
657            &[
658                (10, 1, 2, 100.0, 10.0), // output pin A on node 1
659                (11, 1, 2, 100.0, 40.0), // output pin B on node 1
660                (20, 2, 1, 0.0, 10.0),   // input pin A on node 2
661                (21, 2, 1, 0.0, 40.0),   // input pin B on node 2
662            ],
663        );
664        // Two edges that both resolve to (node 1 → node 2)
665        let result =
666            sugiyama_layout_from_cache(&cache, &[(10, 20), (11, 21)], &SugiyamaConfig::default());
667
668        // Should produce exactly 2 positioned nodes, not crash or duplicate
669        assert_eq!(result.len(), 2);
670        let pos = pos_map(result);
671        assert!(pos.contains_key(&1));
672        assert!(pos.contains_key(&2));
673    }
674
675    #[test]
676    fn test_from_cache_skips_unknown_pins() {
677        let cache = make_cache(&[(1, 0.0, 0.0, 100.0, 50.0)], &[(10, 1, 2, 100.0, 25.0)]);
678        // Edge references pin 999 which doesn't exist
679        let result = sugiyama_layout_from_cache(&cache, &[(10, 999)], &SugiyamaConfig::default());
680
681        // Node 1 still appears (from cache), edge is just ignored
682        assert_eq!(result.len(), 1);
683        assert_eq!(result[0].id, 1);
684    }
685
686    #[test]
687    fn test_from_cache_empty() {
688        let cache: GeometryCache<SimpleNodeGeometry> = GeometryCache::default();
689        let result = sugiyama_layout_from_cache(&cache, &[], &SugiyamaConfig::default());
690        assert!(result.is_empty());
691    }
692
693    #[test]
694    fn test_from_cache_reads_node_dimensions() {
695        // Nodes with different sizes — layout should use cache dimensions
696        let cache = make_cache(
697            &[
698                (1, 0.0, 0.0, 200.0, 30.0), // wide node
699                (2, 0.0, 0.0, 50.0, 100.0), // tall node
700            ],
701            &[(10, 1, 2, 200.0, 15.0), (20, 2, 1, 0.0, 50.0)],
702        );
703        let result = sugiyama_layout_from_cache(&cache, &[(10, 20)], &SugiyamaConfig::default());
704        assert_eq!(result.len(), 2);
705
706        let pos = pos_map(result);
707        // Both nodes should have valid positions
708        assert!(pos[&1].0.is_finite());
709        assert!(pos[&2].0.is_finite());
710    }
711
712    #[test]
713    fn test_from_cache_with_direction() {
714        let cache = make_cache(
715            &[(1, 0.0, 0.0, 100.0, 50.0), (2, 200.0, 0.0, 100.0, 50.0)],
716            &[(10, 1, 2, 100.0, 25.0), (20, 2, 1, 0.0, 25.0)],
717        );
718        let config = SugiyamaConfig {
719            direction: Direction::LeftToRight,
720            ..Default::default()
721        };
722        let result = sugiyama_layout_from_cache(&cache, &[(10, 20)], &config);
723        let pos = pos_map(result);
724
725        // In left-to-right, source should be left of target
726        assert!(
727            pos[&1].0 < pos[&2].0,
728            "source should be left of target in LTR layout"
729        );
730    }
731
732    #[test]
733    fn cache_insertion_and_edge_order_do_not_change_layout() {
734        let nodes = vec![
735            (30, 0.0, 0.0, 70.0, 35.0),
736            (10, 0.0, 0.0, 80.0, 40.0),
737            (40, 0.0, 0.0, 90.0, 45.0),
738            (20, 0.0, 0.0, 60.0, 30.0),
739        ];
740        let pins = vec![
741            (101, 10, 2, 80.0, 20.0),
742            (201, 20, 1, 0.0, 15.0),
743            (102, 10, 2, 80.0, 20.0),
744            (301, 30, 1, 0.0, 17.5),
745            (202, 20, 2, 60.0, 15.0),
746            (401, 40, 1, 0.0, 22.5),
747            (302, 30, 2, 70.0, 17.5),
748            (402, 40, 1, 0.0, 22.5),
749        ];
750        let mut reversed_nodes = nodes.clone();
751        reversed_nodes.reverse();
752        let mut reversed_pins = pins.clone();
753        reversed_pins.reverse();
754        let cache = make_cache(&nodes, &pins);
755        let reversed_cache = make_cache(&reversed_nodes, &reversed_pins);
756        let edges = vec![(101, 201), (102, 301), (202, 401), (302, 402)];
757        let mut reversed_edges = edges.clone();
758        reversed_edges.reverse();
759
760        for direction in [Direction::TopToBottom, Direction::LeftToRight] {
761            let config = SugiyamaConfig {
762                direction,
763                ..Default::default()
764            };
765            assert_eq!(
766                sugiyama_layout_from_cache(&reversed_cache, &reversed_edges, &config),
767                sugiyama_layout_from_cache(&cache, &edges, &config)
768            );
769        }
770    }
771}