1use std::collections::{BTreeMap, BTreeSet};
13
14use crate::hit_test::NodeGeometry;
15use crate::state::GeometryCache;
16
17#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
22#[non_exhaustive]
23pub enum Direction {
24 #[default]
26 TopToBottom,
27 LeftToRight,
29}
30
31#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
40#[non_exhaustive]
41pub enum RankAlignment {
42 #[default]
44 Center,
45 Start,
48}
49
50#[derive(Debug, Clone, Copy, PartialEq)]
52pub struct NodePosition {
53 pub id: i32,
55 pub x: f64,
57 pub y: f64,
59}
60
61#[derive(Debug, Clone, Copy, Default)]
63#[non_exhaustive]
64pub struct SugiyamaConfig {
65 pub vertex_spacing: f64,
68 pub minimum_length: u32,
71 pub dummy_vertices: bool,
73 pub direction: Direction,
75 pub rank_alignment: RankAlignment,
78}
79
80pub 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 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 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 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 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 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 let mut min_perp = f64::INFINITY;
187 let mut max_perp = f64::NEG_INFINITY;
188 let mut min_layer = f64::INFINITY;
189
190 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 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 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
253pub 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 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 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 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 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 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 assert!(pos[&1].1 < pos[&4].1);
356 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)]; let result = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
365 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 (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 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 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 assert!(pos[&1].0 < pos[&4].0);
517 assert!((pos[&2].0 - pos[&3].0).abs() < 1.0);
519 }
520
521 #[test]
522 fn test_disconnected_graph() {
523 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 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 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 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 for direction in DIRECTIONS {
648 for (extent_2, extent_3) in [(300.0, 100.0), (100.0, 300.0)] {
649 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 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 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 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 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 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 use crate::hit_test::SimpleNodeGeometry;
803 use crate::state::StoredPin;
804
805 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 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), (4, 2, 1, 0.0, 25.0), ],
847 );
848 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 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 let cache = make_cache(
863 &[(1, 0.0, 0.0, 100.0, 50.0)],
864 &[
865 (10, 1, 2, 100.0, 25.0), (11, 1, 1, 0.0, 25.0), ],
868 );
869 let result = sugiyama_layout_from_cache(&cache, &[(10, 11)], &SugiyamaConfig::default());
870
871 assert_eq!(result.len(), 1);
873 assert_eq!(result[0].id, 1);
874 }
875
876 #[test]
877 fn test_from_cache_deduplicates_edges() {
878 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), (11, 1, 2, 100.0, 40.0), (20, 2, 1, 0.0, 10.0), (21, 2, 1, 0.0, 40.0), ],
887 );
888 let result =
890 sugiyama_layout_from_cache(&cache, &[(10, 20), (11, 21)], &SugiyamaConfig::default());
891
892 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 let result = sugiyama_layout_from_cache(&cache, &[(10, 999)], &SugiyamaConfig::default());
904
905 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 let cache = make_cache(
921 &[
922 (1, 0.0, 0.0, 200.0, 30.0), (2, 0.0, 0.0, 50.0, 100.0), ],
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 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 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}