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/// How the nodes of one rank line up on the layer axis.
32///
33/// A rank's nodes can differ in extent along the layer axis (height for
34/// [`Direction::TopToBottom`], width for [`Direction::LeftToRight`]). Either
35/// they share a centre line, or they share the rank's leading edge.
36///
37/// Marked `#[non_exhaustive]` so further alignments (e.g. `End`) can be added
38/// without breaking callers.
39#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
40#[non_exhaustive]
41pub enum RankAlignment {
42    /// Each node is centred on its rank's centre line (default).
43    #[default]
44    Center,
45    /// Each node starts at its rank's leading edge: the rank's top for
46    /// [`Direction::TopToBottom`], its left for [`Direction::LeftToRight`].
47    Start,
48}
49
50/// A positioned node returned by [`sugiyama_layout`].
51#[derive(Debug, Clone, Copy, PartialEq)]
52pub struct NodePosition {
53    /// The node ID (same value passed in via `node_sizes`).
54    pub id: i32,
55    /// X coordinate of the node's top-left corner.
56    pub x: f64,
57    /// Y coordinate of the node's top-left corner.
58    pub y: f64,
59}
60
61/// Configuration for the Sugiyama layout algorithm.
62#[derive(Debug, Clone, Copy, Default)]
63#[non_exhaustive]
64pub struct SugiyamaConfig {
65    /// Minimum spacing between vertices (default: 0.0, which uses the
66    /// `rust-sugiyama` default of 10.0).
67    pub vertex_spacing: f64,
68    /// Minimum edge length between layers (default: 0, which uses the
69    /// `rust-sugiyama` default of 1).
70    pub minimum_length: u32,
71    /// Whether to include dummy vertices in the layout (default: false).
72    pub dummy_vertices: bool,
73    /// Layout direction (default: [`Direction::TopToBottom`]).
74    pub direction: Direction,
75    /// How a rank's nodes line up on the layer axis (default:
76    /// [`RankAlignment::Center`]).
77    pub rank_alignment: RankAlignment,
78}
79
80/// Compute Sugiyama hierarchical layout positions.
81///
82/// Takes edges as `(source_node_id, target_node_id)` pairs and node sizes as
83/// `(node_id, (width, height))` pairs. Returns a [`NodePosition`] for each node.
84///
85/// Node IDs can be any `i32` values — they are mapped to sequential `u32` indices
86/// internally for `rust-sugiyama` and translated back before returning.
87///
88/// Duplicate node IDs in `node_sizes` are ignored (first occurrence wins),
89/// then nodes are ordered by ID. Nodes whose width or height is non-finite or
90/// not positive are omitted. Edges with an omitted or unknown endpoint,
91/// self-loops, and duplicate edges are ignored; retained edges are ordered by
92/// their node-ID pair. Results are returned in ascending node-ID order.
93///
94/// Disconnected components are packed side by side on the axis perpendicular
95/// to the layers, and each component's first rank starts at 0 on the layer
96/// axis.
97pub fn sugiyama_layout(
98    edges: &[(i32, i32)],
99    node_sizes: &[(i32, (f64, f64))],
100    config: &SugiyamaConfig,
101) -> Vec<NodePosition> {
102    let horizontal = config.direction == Direction::LeftToRight;
103
104    // Preserve the documented first occurrence, then let BTreeMap provide the
105    // canonical node-ID order used by every downstream table.
106    let mut nodes_by_id = BTreeMap::new();
107    for &(node_id, size) in node_sizes {
108        nodes_by_id.entry(node_id).or_insert(size);
109    }
110    nodes_by_id.retain(|_, (width, height)| {
111        width.is_finite() && *width > 0.0 && height.is_finite() && *height > 0.0
112    });
113    let nodes: Vec<(i32, (f64, f64))> = nodes_by_id.into_iter().collect();
114    if nodes.is_empty() {
115        return Vec::new();
116    }
117
118    let id_to_idx: BTreeMap<i32, u32> = nodes
119        .iter()
120        .enumerate()
121        .map(|(idx, &(node_id, _))| (node_id, idx as u32))
122        .collect();
123
124    // A node's (in-layer, layer-axis) extents, the frame rust-sugiyama lays
125    // out in: for horizontal layout, width and height swap so the algorithm
126    // spaces layers along what will become the x-axis.
127    let extents = |(width, height): (f64, f64)| {
128        if horizontal {
129            (height, width)
130        } else {
131            (width, height)
132        }
133    };
134
135    let vertices: Vec<(u32, (f64, f64))> = nodes
136        .iter()
137        .enumerate()
138        .map(|(idx, &(_, size))| (idx as u32, extents(size)))
139        .collect();
140
141    let mapped_edges: Vec<(u32, u32)> = edges
142        .iter()
143        .filter(|(src, dst)| src != dst)
144        .filter_map(|&(src, dst)| Some((*id_to_idx.get(&src)?, *id_to_idx.get(&dst)?)))
145        .collect::<BTreeSet<_>>()
146        .into_iter()
147        .collect();
148
149    // Configure rust-sugiyama
150    let mut sg_config = rust_sugiyama::configure::Config {
151        dummy_vertices: config.dummy_vertices,
152        ..Default::default()
153    };
154    if config.vertex_spacing > 0.0 {
155        sg_config.vertex_spacing = config.vertex_spacing;
156    }
157    if config.minimum_length > 0 {
158        sg_config.minimum_length = config.minimum_length;
159    }
160
161    // Run layout — returns Vec<(Vec<(usize, (f64, f64))>, f64, f64)> (subgraphs)
162    let mut subgraphs =
163        rust_sugiyama::from_vertices_and_edges(&vertices, &mapped_edges, &sg_config);
164    subgraphs.sort_by_key(|(layout, _, _)| {
165        layout
166            .iter()
167            .filter_map(|(idx, _)| nodes.get(*idx).map(|(node_id, _)| *node_id))
168            .min()
169            .unwrap_or(i32::MAX)
170    });
171
172    // Collect results from all subgraphs, translating indices back to node IDs.
173    // For horizontal layout, swap x/y so layers run left-to-right.
174    // Each subgraph is offset along the perpendicular axis so disconnected
175    // components (and isolated nodes) don't overlap.
176    let spacing = if config.vertex_spacing > 0.0 {
177        config.vertex_spacing
178    } else {
179        10.0
180    };
181    let mut results = Vec::with_capacity(nodes.len());
182    let mut perpendicular_offset = 0.0_f64;
183
184    for (layout, _width, _height) in &subgraphs {
185        // Compute bounding box of this subgraph in output coordinates
186        let mut min_perp = f64::INFINITY;
187        let mut max_perp = f64::NEG_INFINITY;
188        let mut min_layer = f64::INFINITY;
189
190        // Each rank's largest layer-axis extent, keyed by the rank's centre
191        // line. rust-sugiyama gives every vertex of a rank the same layer
192        // coordinate from one lookup, so its bits identify the rank exactly.
193        let mut rank_extents: BTreeMap<u64, f64> = BTreeMap::new();
194        if config.rank_alignment == RankAlignment::Start {
195            for &(idx, (_, layer_centre)) in layout {
196                if let Some(&(_, size)) = nodes.get(idx) {
197                    let rank_extent = rank_extents.entry(layer_centre.to_bits()).or_insert(0.0);
198                    *rank_extent = rank_extent.max(extents(size).1);
199                }
200            }
201        }
202
203        let start = results.len();
204        for &(idx, (in_layer_centre, layer_centre)) in layout {
205            if let Some(&(node_id, size)) = nodes.get(idx) {
206                // rust-sugiyama returns each vertex's centre: its rank's
207                // centre line on the layer axis, and its centre in-layer.
208                let (in_layer_extent, layer_extent) = extents(size);
209                let aligned_extent = match config.rank_alignment {
210                    RankAlignment::Center => layer_extent,
211                    RankAlignment::Start => rank_extents[&layer_centre.to_bits()],
212                };
213                let in_layer_position = in_layer_centre - in_layer_extent / 2.0;
214                let layer_position = layer_centre - aligned_extent / 2.0;
215                let (x, y) = if horizontal {
216                    (layer_position, in_layer_position)
217                } else {
218                    (in_layer_position, layer_position)
219                };
220                results.push(NodePosition { id: node_id, x, y });
221
222                min_perp = min_perp.min(in_layer_position);
223                max_perp = max_perp.max(in_layer_position + in_layer_extent);
224                min_layer = min_layer.min(layer_position);
225            }
226        }
227
228        if start < results.len() {
229            // Shift this subgraph so its perpendicular leading edge sits at
230            // the running offset. On the layer axis its first rank's centre
231            // line is at 0, which leaves that rank's corners negative; each
232            // component is re-based on its own so no component starts
233            // indented by another's wider first rank.
234            let perpendicular_shift = perpendicular_offset - min_perp;
235            let layer_shift = -min_layer;
236            for pos in &mut results[start..] {
237                if horizontal {
238                    pos.x += layer_shift;
239                    pos.y += perpendicular_shift;
240                } else {
241                    pos.x += perpendicular_shift;
242                    pos.y += layer_shift;
243                }
244            }
245            perpendicular_offset += max_perp - min_perp + spacing;
246        }
247    }
248
249    results.sort_by_key(|position| position.id);
250    results
251}
252
253/// Compute Sugiyama layout using data from a [`GeometryCache`].
254///
255/// Edges are given as `(start_pin_id, end_pin_id)` pairs — the same format used
256/// by link models. Pin IDs are resolved to node IDs via `cache.pin_positions`,
257/// and node dimensions are read from `cache.node_rects`.
258///
259/// Unknown pins are ignored. Resolved edges then use the raw layout policy:
260/// missing node endpoints, self-loops, and duplicate node pairs are ignored.
261/// Cache `HashMap` iteration cannot affect the result because the raw layout
262/// canonicalizes nodes and edges before invoking the algorithm.
263///
264/// Returns a [`NodePosition`] for each laid-out node.
265pub fn sugiyama_layout_from_cache<N>(
266    cache: &GeometryCache<N>,
267    edges: &[(i32, i32)],
268    config: &SugiyamaConfig,
269) -> Vec<NodePosition>
270where
271    N: NodeGeometry + Copy,
272{
273    // Resolve known pin IDs to node IDs. The raw API owns canonical edge
274    // filtering so both entry points have the same self-loop/duplicate policy.
275    let node_edges: Vec<(i32, i32)> = edges
276        .iter()
277        .filter_map(|&(start_pin, end_pin)| {
278            let src_node = cache.pin_positions.get(&start_pin)?.node_id;
279            let dst_node = cache.pin_positions.get(&end_pin)?.node_id;
280            Some((src_node, dst_node))
281        })
282        .collect();
283
284    // Extract node sizes from cache
285    let node_sizes: Vec<(i32, (f64, f64))> = cache
286        .node_rects
287        .iter()
288        .map(|(&id, geom)| {
289            let (_, _, w, h) = geom.rect();
290            (id, (w as f64, h as f64))
291        })
292        .collect();
293
294    sugiyama_layout(&node_edges, &node_sizes, config)
295}
296
297#[cfg(test)]
298mod tests {
299    use super::*;
300    use std::collections::HashMap;
301
302    /// Helper to collect positions into a HashMap for easy lookup.
303    fn pos_map(positions: Vec<NodePosition>) -> HashMap<i32, (f64, f64)> {
304        positions.into_iter().map(|p| (p.id, (p.x, p.y))).collect()
305    }
306
307    #[test]
308    fn test_empty_input() {
309        let result = sugiyama_layout(&[], &[], &SugiyamaConfig::default());
310        assert!(result.is_empty());
311    }
312
313    #[test]
314    fn test_single_node_no_edges() {
315        let sizes = vec![(1, (100.0, 50.0))];
316        let result = sugiyama_layout(&[], &sizes, &SugiyamaConfig::default());
317        assert_eq!(result.len(), 1);
318        assert_eq!(result[0].id, 1);
319    }
320
321    #[test]
322    fn test_two_nodes_one_edge() {
323        let sizes = vec![(10, (100.0, 50.0)), (20, (100.0, 50.0))];
324        let edges = vec![(10, 20)];
325        let result = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
326        assert_eq!(result.len(), 2);
327
328        let pos = pos_map(result);
329        assert!(pos.contains_key(&10));
330        assert!(pos.contains_key(&20));
331
332        // Source should be above target in top-to-bottom layout
333        assert!(
334            pos[&10].1 < pos[&20].1,
335            "source node should be in an earlier layer"
336        );
337    }
338
339    #[test]
340    fn test_diamond_dag() {
341        // Diamond: 1 -> 2, 1 -> 3, 2 -> 4, 3 -> 4
342        let sizes = vec![
343            (1, (80.0, 40.0)),
344            (2, (80.0, 40.0)),
345            (3, (80.0, 40.0)),
346            (4, (80.0, 40.0)),
347        ];
348        let edges = vec![(1, 2), (1, 3), (2, 4), (3, 4)];
349        let result = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
350        assert_eq!(result.len(), 4);
351
352        let pos = pos_map(result);
353
354        // Node 1 (root) should be in the first layer, node 4 (sink) in the last
355        assert!(pos[&1].1 < pos[&4].1);
356        // Nodes 2 and 3 should be in the same middle layer
357        assert!((pos[&2].1 - pos[&3].1).abs() < 1.0);
358    }
359
360    #[test]
361    fn test_edges_with_unknown_nodes_are_skipped() {
362        let sizes = vec![(1, (100.0, 50.0))];
363        let edges = vec![(1, 999)]; // 999 not in sizes
364        let result = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
365        // Should still return node 1, just without the edge
366        assert_eq!(result.len(), 1);
367        assert_eq!(result[0].id, 1);
368    }
369
370    #[test]
371    fn test_duplicate_node_ids_first_wins() {
372        let base_sizes = vec![(1, (100.0, 50.0)), (2, (60.0, 30.0))];
373        let duplicate_sizes = vec![(1, (100.0, 50.0)), (1, (500.0, 400.0)), (2, (60.0, 30.0))];
374
375        assert_eq!(
376            sugiyama_layout(&[], &duplicate_sizes, &SugiyamaConfig::default()),
377            sugiyama_layout(&[], &base_sizes, &SugiyamaConfig::default())
378        );
379    }
380
381    #[test]
382    fn invalid_node_dimensions_are_omitted() {
383        let sizes = vec![
384            (1, (100.0, 50.0)),
385            (2, (0.0, 50.0)),
386            (3, (100.0, -1.0)),
387            (4, (f64::NAN, 50.0)),
388            (5, (100.0, f64::INFINITY)),
389            // First occurrence wins even when it is invalid.
390            (2, (100.0, 50.0)),
391        ];
392
393        let result = sugiyama_layout(&[(1, 2)], &sizes, &SugiyamaConfig::default());
394        assert_eq!(result.len(), 1);
395        assert_eq!(result[0].id, 1);
396        assert!(result[0].x.is_finite());
397        assert!(result[0].y.is_finite());
398    }
399
400    #[test]
401    fn raw_layout_ignores_duplicate_self_and_unknown_edges() {
402        let sizes = vec![(1, (80.0, 40.0)), (2, (80.0, 40.0)), (3, (80.0, 40.0))];
403        let expected = sugiyama_layout(&[(1, 2)], &sizes, &SugiyamaConfig::default());
404        let noisy = sugiyama_layout(
405            &[(1, 2), (1, 2), (1, 1), (3, 3), (1, 999), (999, 2)],
406            &sizes,
407            &SugiyamaConfig::default(),
408        );
409
410        assert_eq!(noisy, expected);
411    }
412
413    #[test]
414    fn equivalent_input_permutations_have_identical_positions_and_order() {
415        let sizes = vec![
416            (30, (70.0, 35.0)),
417            (10, (80.0, 40.0)),
418            (40, (90.0, 45.0)),
419            (20, (60.0, 30.0)),
420        ];
421        let mut reversed_sizes = sizes.clone();
422        reversed_sizes.reverse();
423        let edges = vec![(10, 20), (10, 30), (20, 40), (30, 40)];
424        let mut reversed_edges = edges.clone();
425        reversed_edges.reverse();
426
427        for direction in [Direction::TopToBottom, Direction::LeftToRight] {
428            let config = SugiyamaConfig {
429                direction,
430                ..Default::default()
431            };
432            let expected = sugiyama_layout(&edges, &sizes, &config);
433            let actual = sugiyama_layout(&reversed_edges, &reversed_sizes, &config);
434
435            assert_eq!(actual, expected);
436            assert_eq!(
437                actual
438                    .iter()
439                    .map(|position| position.id)
440                    .collect::<Vec<_>>(),
441                vec![10, 20, 30, 40]
442            );
443        }
444    }
445
446    #[test]
447    fn test_config_default() {
448        let config = SugiyamaConfig::default();
449        assert_eq!(config.vertex_spacing, 0.0);
450        assert_eq!(config.minimum_length, 0);
451        assert!(!config.dummy_vertices);
452        assert_eq!(config.direction, Direction::TopToBottom);
453        assert_eq!(config.rank_alignment, RankAlignment::Center);
454    }
455
456    #[test]
457    fn test_direction_default_is_top_to_bottom() {
458        assert_eq!(Direction::default(), Direction::TopToBottom);
459    }
460
461    #[test]
462    fn test_node_position_fields() {
463        let sizes = vec![(42, (80.0, 40.0))];
464        let result = sugiyama_layout(&[], &sizes, &SugiyamaConfig::default());
465        assert_eq!(result.len(), 1);
466        let pos = result[0];
467        assert_eq!(pos.id, 42);
468        // x and y should be finite numbers
469        assert!(pos.x.is_finite());
470        assert!(pos.y.is_finite());
471    }
472
473    #[test]
474    fn test_left_to_right_swaps_axes() {
475        let sizes = vec![(10, (100.0, 50.0)), (20, (100.0, 50.0))];
476        let edges = vec![(10, 20)];
477
478        let ttb = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
479        let ltr = sugiyama_layout(
480            &edges,
481            &sizes,
482            &SugiyamaConfig {
483                direction: Direction::LeftToRight,
484                ..Default::default()
485            },
486        );
487
488        let ttb_pos = pos_map(ttb);
489        let ltr_pos = pos_map(ltr);
490
491        // In top-to-bottom, layers differ in y; in left-to-right, layers differ in x
492        let ttb_dy = (ttb_pos[&20].1 - ttb_pos[&10].1).abs();
493        let ltr_dx = (ltr_pos[&20].0 - ltr_pos[&10].0).abs();
494
495        assert!(ttb_dy > 1.0, "top-to-bottom should separate layers in y");
496        assert!(ltr_dx > 1.0, "left-to-right should separate layers in x");
497    }
498
499    #[test]
500    fn test_left_to_right_diamond() {
501        let sizes = vec![
502            (1, (80.0, 40.0)),
503            (2, (80.0, 40.0)),
504            (3, (80.0, 40.0)),
505            (4, (80.0, 40.0)),
506        ];
507        let edges = vec![(1, 2), (1, 3), (2, 4), (3, 4)];
508        let config = SugiyamaConfig {
509            direction: Direction::LeftToRight,
510            ..Default::default()
511        };
512        let result = sugiyama_layout(&edges, &sizes, &config);
513        let pos = pos_map(result);
514
515        // Root should be leftmost, sink rightmost
516        assert!(pos[&1].0 < pos[&4].0);
517        // Middle nodes should be at the same x (same layer)
518        assert!((pos[&2].0 - pos[&3].0).abs() < 1.0);
519    }
520
521    #[test]
522    fn test_disconnected_graph() {
523        // Two separate subgraphs: 1->2 and 3->4
524        let sizes = vec![
525            (1, (80.0, 40.0)),
526            (2, (80.0, 40.0)),
527            (3, (80.0, 40.0)),
528            (4, (80.0, 40.0)),
529        ];
530        let edges = vec![(1, 2), (3, 4)];
531        let result = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
532
533        assert_eq!(result.len(), 4);
534        let pos = pos_map(result);
535        assert!(pos.contains_key(&1));
536        assert!(pos.contains_key(&2));
537        assert!(pos.contains_key(&3));
538        assert!(pos.contains_key(&4));
539        // Each subgraph should respect layer ordering
540        assert!(pos[&1].1 < pos[&2].1);
541        assert!(pos[&3].1 < pos[&4].1);
542    }
543
544    #[test]
545    fn test_isolated_nodes_are_packed_on_the_perpendicular_axis() {
546        let sizes = vec![(1, (100.0, 50.0)), (2, (100.0, 50.0)), (3, (100.0, 50.0))];
547
548        let top_to_bottom = sugiyama_layout(&[], &sizes, &SugiyamaConfig::default());
549        assert!(top_to_bottom
550            .windows(2)
551            .all(|pair| pair[0].x + 110.0 <= pair[1].x));
552        assert!(top_to_bottom.windows(2).all(|pair| pair[0].y == pair[1].y));
553
554        let left_to_right = sugiyama_layout(
555            &[],
556            &sizes,
557            &SugiyamaConfig {
558                direction: Direction::LeftToRight,
559                ..Default::default()
560            },
561        );
562        assert!(left_to_right
563            .windows(2)
564            .all(|pair| pair[0].y + 60.0 <= pair[1].y));
565        assert!(left_to_right.windows(2).all(|pair| pair[0].x == pair[1].x));
566    }
567
568    #[test]
569    fn disconnected_components_do_not_overlap_in_either_direction() {
570        let sizes = vec![
571            (1, (100.0, 30.0)),
572            (2, (60.0, 80.0)),
573            (3, (120.0, 40.0)),
574            (4, (50.0, 90.0)),
575        ];
576        let edges = vec![(1, 2), (3, 4)];
577
578        for direction in [Direction::TopToBottom, Direction::LeftToRight] {
579            let positions = pos_map(sugiyama_layout(
580                &edges,
581                &sizes,
582                &SugiyamaConfig {
583                    direction,
584                    ..Default::default()
585                },
586            ));
587            for left_id in [1, 2] {
588                for right_id in [3, 4] {
589                    let (left_x, left_y) = positions[&left_id];
590                    let (right_x, right_y) = positions[&right_id];
591                    let (_, (left_width, left_height)) = sizes
592                        .iter()
593                        .find(|(id, _)| *id == left_id)
594                        .copied()
595                        .unwrap();
596                    let (_, (right_width, right_height)) = sizes
597                        .iter()
598                        .find(|(id, _)| *id == right_id)
599                        .copied()
600                        .unwrap();
601                    assert!(
602                        left_x + left_width <= right_x
603                            || right_x + right_width <= left_x
604                            || left_y + left_height <= right_y
605                            || right_y + right_height <= left_y,
606                        "components overlap in {direction:?}: {left_id} and {right_id}"
607                    );
608                }
609            }
610        }
611    }
612
613    const DIRECTIONS: [Direction; 2] = [Direction::TopToBottom, Direction::LeftToRight];
614
615    /// A node's `(width, height)` from its extent along the layer axis and
616    /// its extent within its layer.
617    fn size_along(direction: Direction, layer: f64, in_layer: f64) -> (f64, f64) {
618        match direction {
619            Direction::LeftToRight => (layer, in_layer),
620            Direction::TopToBottom => (in_layer, layer),
621        }
622    }
623
624    /// A corner's `(layer axis, in-layer axis)` coordinates.
625    fn axes(direction: Direction, position: (f64, f64)) -> (f64, f64) {
626        match direction {
627            Direction::LeftToRight => position,
628            Direction::TopToBottom => (position.1, position.0),
629        }
630    }
631
632    const ALIGNMENTS: [RankAlignment; 2] = [RankAlignment::Center, RankAlignment::Start];
633
634    fn spaced(direction: Direction) -> SugiyamaConfig {
635        SugiyamaConfig {
636            vertex_spacing: 60.0,
637            direction,
638            ..Default::default()
639        }
640    }
641
642    #[test]
643    fn cards_in_one_rank_do_not_overlap() {
644        // A centre read as a corner overlaps only when the larger card comes
645        // first in its rank, and crossing minimisation picks that order, so
646        // the larger extent goes to each of the two rank members in turn.
647        for direction in DIRECTIONS {
648            for (extent_2, extent_3) in [(300.0, 100.0), (100.0, 300.0)] {
649                // 2 and 3 share the rank after 1.
650                let sizes = vec![
651                    (1, size_along(direction, 100.0, 100.0)),
652                    (2, size_along(direction, 100.0, extent_2)),
653                    (3, size_along(direction, 100.0, extent_3)),
654                ];
655                let positions = pos_map(sugiyama_layout(
656                    &[(1, 2), (1, 3)],
657                    &sizes,
658                    &spaced(direction),
659                ));
660                let (layer_2, in_layer_2) = axes(direction, positions[&2]);
661                let (layer_3, in_layer_3) = axes(direction, positions[&3]);
662                assert_eq!(layer_2, layer_3, "2 and 3 share a rank in {direction:?}");
663
664                let ((first, first_extent), second) = if in_layer_2 < in_layer_3 {
665                    ((in_layer_2, extent_2), in_layer_3)
666                } else {
667                    ((in_layer_3, extent_3), in_layer_2)
668                };
669                assert!(
670                    second - (first + first_extent) >= 60.0 - 1e-9,
671                    "rank members closer than the spacing in {direction:?}: {positions:?}"
672                );
673            }
674        }
675    }
676
677    #[test]
678    fn consecutive_ranks_do_not_overlap() {
679        for direction in DIRECTIONS {
680            for rank_alignment in ALIGNMENTS {
681                let sizes = vec![
682                    (1, size_along(direction, 600.0, 100.0)),
683                    (2, size_along(direction, 100.0, 100.0)),
684                ];
685                let positions = pos_map(sugiyama_layout(
686                    &[(1, 2)],
687                    &sizes,
688                    &SugiyamaConfig {
689                        rank_alignment,
690                        ..spaced(direction)
691                    },
692                ));
693                let (layer_1, _) = axes(direction, positions[&1]);
694                let (layer_2, _) = axes(direction, positions[&2]);
695                assert!(
696                    layer_2 - (layer_1 + 600.0) >= 60.0 - 1e-9,
697                    "ranks closer than the spacing in {direction:?}, {rank_alignment:?}: \
698                     {positions:?}"
699                );
700            }
701        }
702    }
703
704    #[test]
705    fn every_component_starts_at_0_on_the_layer_axis() {
706        for direction in DIRECTIONS {
707            for rank_alignment in ALIGNMENTS {
708                // Two components whose first ranks differ in layer-axis extent.
709                let sizes = vec![
710                    (1, size_along(direction, 600.0, 100.0)),
711                    (2, size_along(direction, 100.0, 100.0)),
712                    (3, size_along(direction, 100.0, 100.0)),
713                    (4, size_along(direction, 300.0, 100.0)),
714                ];
715                let positions = pos_map(sugiyama_layout(
716                    &[(1, 2), (3, 4)],
717                    &sizes,
718                    &SugiyamaConfig {
719                        rank_alignment,
720                        ..spaced(direction)
721                    },
722                ));
723                for component in [[1, 2], [3, 4]] {
724                    let leading_edge = component
725                        .iter()
726                        .map(|id| axes(direction, positions[id]).0)
727                        .fold(f64::INFINITY, f64::min);
728                    assert_eq!(
729                        leading_edge, 0.0,
730                        "component {component:?} in {direction:?}, {rank_alignment:?}: \
731                         {positions:?}"
732                    );
733                }
734            }
735        }
736    }
737
738    #[test]
739    fn start_alignment_shares_each_ranks_leading_edge() {
740        for direction in DIRECTIONS {
741            // 1 and 2 share the rank before 3 and differ in layer-axis extent.
742            let sizes = vec![
743                (1, size_along(direction, 600.0, 100.0)),
744                (2, size_along(direction, 100.0, 100.0)),
745                (3, size_along(direction, 100.0, 100.0)),
746            ];
747            let layout = |rank_alignment| {
748                let positions = pos_map(sugiyama_layout(
749                    &[(1, 3), (2, 3)],
750                    &sizes,
751                    &SugiyamaConfig {
752                        rank_alignment,
753                        ..spaced(direction)
754                    },
755                ));
756                let layer_1 = axes(direction, positions[&1]).0;
757                let layer_2 = axes(direction, positions[&2]).0;
758                (layer_1, layer_2, positions)
759            };
760
761            let (layer_1, layer_2, positions) = layout(RankAlignment::Start);
762            assert_eq!(
763                layer_1, layer_2,
764                "leading edges differ in {direction:?}: {positions:?}"
765            );
766            // The shared edge must come from the rank's largest extent, or
767            // the 600 card reaches into the next rank.
768            let layer_3 = axes(direction, positions[&3]).0;
769            assert!(
770                layer_3 - (layer_1 + 600.0) >= 60.0 - 1e-9,
771                "the next rank is closer than the spacing in {direction:?}: {positions:?}"
772            );
773
774            let (layer_1, layer_2, positions) = layout(RankAlignment::Center);
775            assert_eq!(
776                layer_1 + 300.0,
777                layer_2 + 50.0,
778                "centres differ in {direction:?}: {positions:?}"
779            );
780        }
781    }
782
783    #[test]
784    fn test_cycle_does_not_panic() {
785        // rust-sugiyama handles cycles internally; verify we don't break
786        let sizes = vec![(1, (80.0, 40.0)), (2, (80.0, 40.0)), (3, (80.0, 40.0))];
787        let edges = vec![(1, 2), (2, 3), (3, 1)];
788        let result = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
789
790        // All nodes should still get positions
791        assert_eq!(result.len(), 3);
792        let pos = pos_map(result);
793        assert!(pos[&1].0.is_finite());
794        assert!(pos[&2].0.is_finite());
795        assert!(pos[&3].0.is_finite());
796    }
797
798    // ========================================================================
799    // sugiyama_layout_from_cache() tests
800    // ========================================================================
801
802    use crate::hit_test::SimpleNodeGeometry;
803    use crate::state::StoredPin;
804
805    /// Build a GeometryCache with the given nodes and pins.
806    fn make_cache(
807        nodes: &[(i32, f32, f32, f32, f32)],
808        pins: &[(i32, i32, i32, f32, f32)],
809    ) -> GeometryCache<SimpleNodeGeometry> {
810        let mut cache = GeometryCache::default();
811        for &(id, x, y, w, h) in nodes {
812            cache.node_rects.insert(
813                id,
814                SimpleNodeGeometry {
815                    id,
816                    x,
817                    y,
818                    width: w,
819                    height: h,
820                },
821            );
822        }
823        for &(pin_id, node_id, pin_type, rel_x, rel_y) in pins {
824            cache.pin_positions.insert(
825                pin_id,
826                StoredPin {
827                    node_id,
828                    pin_type,
829                    rel_x,
830                    rel_y,
831                },
832            );
833        }
834        cache
835    }
836
837    #[test]
838    fn test_from_cache_resolves_pins_to_nodes() {
839        // Two nodes with one output pin each and one input pin each
840        // Pin encoding: output = id*2+1, input = id*2
841        let cache = make_cache(
842            &[(1, 0.0, 0.0, 100.0, 50.0), (2, 200.0, 0.0, 100.0, 50.0)],
843            &[
844                (3, 1, 2, 100.0, 25.0), // output pin on node 1
845                (4, 2, 1, 0.0, 25.0),   // input pin on node 2
846            ],
847        );
848        // Edge from pin 3 (node 1 output) → pin 4 (node 2 input)
849        let result = sugiyama_layout_from_cache(&cache, &[(3, 4)], &SugiyamaConfig::default());
850        let pos = pos_map(result);
851
852        assert_eq!(pos.len(), 2);
853        assert!(pos.contains_key(&1));
854        assert!(pos.contains_key(&2));
855        // Node 1 should be above node 2 (top-to-bottom default)
856        assert!(pos[&1].1 < pos[&2].1, "source should be in earlier layer");
857    }
858
859    #[test]
860    fn test_from_cache_skips_self_loops() {
861        // Two pins on the same node — edge between them is a self-loop
862        let cache = make_cache(
863            &[(1, 0.0, 0.0, 100.0, 50.0)],
864            &[
865                (10, 1, 2, 100.0, 25.0), // output pin on node 1
866                (11, 1, 1, 0.0, 25.0),   // input pin on node 1
867            ],
868        );
869        let result = sugiyama_layout_from_cache(&cache, &[(10, 11)], &SugiyamaConfig::default());
870
871        // Node should still appear (it exists in cache), but with no edges
872        assert_eq!(result.len(), 1);
873        assert_eq!(result[0].id, 1);
874    }
875
876    #[test]
877    fn test_from_cache_deduplicates_edges() {
878        // Two separate pin-pairs connecting node 1 → node 2
879        let cache = make_cache(
880            &[(1, 0.0, 0.0, 100.0, 50.0), (2, 200.0, 0.0, 100.0, 50.0)],
881            &[
882                (10, 1, 2, 100.0, 10.0), // output pin A on node 1
883                (11, 1, 2, 100.0, 40.0), // output pin B on node 1
884                (20, 2, 1, 0.0, 10.0),   // input pin A on node 2
885                (21, 2, 1, 0.0, 40.0),   // input pin B on node 2
886            ],
887        );
888        // Two edges that both resolve to (node 1 → node 2)
889        let result =
890            sugiyama_layout_from_cache(&cache, &[(10, 20), (11, 21)], &SugiyamaConfig::default());
891
892        // Should produce exactly 2 positioned nodes, not crash or duplicate
893        assert_eq!(result.len(), 2);
894        let pos = pos_map(result);
895        assert!(pos.contains_key(&1));
896        assert!(pos.contains_key(&2));
897    }
898
899    #[test]
900    fn test_from_cache_skips_unknown_pins() {
901        let cache = make_cache(&[(1, 0.0, 0.0, 100.0, 50.0)], &[(10, 1, 2, 100.0, 25.0)]);
902        // Edge references pin 999 which doesn't exist
903        let result = sugiyama_layout_from_cache(&cache, &[(10, 999)], &SugiyamaConfig::default());
904
905        // Node 1 still appears (from cache), edge is just ignored
906        assert_eq!(result.len(), 1);
907        assert_eq!(result[0].id, 1);
908    }
909
910    #[test]
911    fn test_from_cache_empty() {
912        let cache: GeometryCache<SimpleNodeGeometry> = GeometryCache::default();
913        let result = sugiyama_layout_from_cache(&cache, &[], &SugiyamaConfig::default());
914        assert!(result.is_empty());
915    }
916
917    #[test]
918    fn test_from_cache_reads_node_dimensions() {
919        // Nodes with different sizes — layout should use cache dimensions
920        let cache = make_cache(
921            &[
922                (1, 0.0, 0.0, 200.0, 30.0), // wide node
923                (2, 0.0, 0.0, 50.0, 100.0), // tall node
924            ],
925            &[(10, 1, 2, 200.0, 15.0), (20, 2, 1, 0.0, 50.0)],
926        );
927        let result = sugiyama_layout_from_cache(&cache, &[(10, 20)], &SugiyamaConfig::default());
928        assert_eq!(result.len(), 2);
929
930        let pos = pos_map(result);
931        // Both nodes should have valid positions
932        assert!(pos[&1].0.is_finite());
933        assert!(pos[&2].0.is_finite());
934    }
935
936    #[test]
937    fn test_from_cache_with_direction() {
938        let cache = make_cache(
939            &[(1, 0.0, 0.0, 100.0, 50.0), (2, 200.0, 0.0, 100.0, 50.0)],
940            &[(10, 1, 2, 100.0, 25.0), (20, 2, 1, 0.0, 25.0)],
941        );
942        let config = SugiyamaConfig {
943            direction: Direction::LeftToRight,
944            ..Default::default()
945        };
946        let result = sugiyama_layout_from_cache(&cache, &[(10, 20)], &config);
947        let pos = pos_map(result);
948
949        // In left-to-right, source should be left of target
950        assert!(
951            pos[&1].0 < pos[&2].0,
952            "source should be left of target in LTR layout"
953        );
954    }
955
956    #[test]
957    fn cache_insertion_and_edge_order_do_not_change_layout() {
958        let nodes = vec![
959            (30, 0.0, 0.0, 70.0, 35.0),
960            (10, 0.0, 0.0, 80.0, 40.0),
961            (40, 0.0, 0.0, 90.0, 45.0),
962            (20, 0.0, 0.0, 60.0, 30.0),
963        ];
964        let pins = vec![
965            (101, 10, 2, 80.0, 20.0),
966            (201, 20, 1, 0.0, 15.0),
967            (102, 10, 2, 80.0, 20.0),
968            (301, 30, 1, 0.0, 17.5),
969            (202, 20, 2, 60.0, 15.0),
970            (401, 40, 1, 0.0, 22.5),
971            (302, 30, 2, 70.0, 17.5),
972            (402, 40, 1, 0.0, 22.5),
973        ];
974        let mut reversed_nodes = nodes.clone();
975        reversed_nodes.reverse();
976        let mut reversed_pins = pins.clone();
977        reversed_pins.reverse();
978        let cache = make_cache(&nodes, &pins);
979        let reversed_cache = make_cache(&reversed_nodes, &reversed_pins);
980        let edges = vec![(101, 201), (102, 301), (202, 401), (302, 402)];
981        let mut reversed_edges = edges.clone();
982        reversed_edges.reverse();
983
984        for direction in [Direction::TopToBottom, Direction::LeftToRight] {
985            let config = SugiyamaConfig {
986                direction,
987                ..Default::default()
988            };
989            assert_eq!(
990                sugiyama_layout_from_cache(&reversed_cache, &reversed_edges, &config),
991                sugiyama_layout_from_cache(&cache, &edges, &config)
992            );
993        }
994    }
995}