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)]
33pub struct NodePosition {
34 pub id: i32,
36 pub x: f64,
38 pub y: f64,
40}
41
42#[derive(Debug, Clone, Copy, Default)]
44#[non_exhaustive]
45pub struct SugiyamaConfig {
46 pub vertex_spacing: f64,
49 pub minimum_length: u32,
52 pub dummy_vertices: bool,
54 pub direction: Direction,
56}
57
58pub 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 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 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 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 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 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 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 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
200pub 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 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 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 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 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 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 assert!(pos[&1].1 < pos[&4].1);
303 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)]; let result = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
312 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 (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 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 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 assert!(pos[&1].0 < pos[&4].0);
463 assert!((pos[&2].0 - pos[&3].0).abs() < 1.0);
465 }
466
467 #[test]
468 fn test_disconnected_graph() {
469 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 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 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 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 use crate::hit_test::SimpleNodeGeometry;
579 use crate::state::StoredPin;
580
581 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 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), (4, 2, 1, 0.0, 25.0), ],
623 );
624 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 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 let cache = make_cache(
639 &[(1, 0.0, 0.0, 100.0, 50.0)],
640 &[
641 (10, 1, 2, 100.0, 25.0), (11, 1, 1, 0.0, 25.0), ],
644 );
645 let result = sugiyama_layout_from_cache(&cache, &[(10, 11)], &SugiyamaConfig::default());
646
647 assert_eq!(result.len(), 1);
649 assert_eq!(result[0].id, 1);
650 }
651
652 #[test]
653 fn test_from_cache_deduplicates_edges() {
654 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), (11, 1, 2, 100.0, 40.0), (20, 2, 1, 0.0, 10.0), (21, 2, 1, 0.0, 40.0), ],
663 );
664 let result =
666 sugiyama_layout_from_cache(&cache, &[(10, 20), (11, 21)], &SugiyamaConfig::default());
667
668 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 let result = sugiyama_layout_from_cache(&cache, &[(10, 999)], &SugiyamaConfig::default());
680
681 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 let cache = make_cache(
697 &[
698 (1, 0.0, 0.0, 200.0, 30.0), (2, 0.0, 0.0, 50.0, 100.0), ],
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 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 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}