use std::collections::{BTreeMap, BTreeSet};
use crate::hit_test::NodeGeometry;
use crate::state::GeometryCache;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[non_exhaustive]
pub enum Direction {
#[default]
TopToBottom,
LeftToRight,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[non_exhaustive]
pub enum RankAlignment {
#[default]
Center,
Start,
}
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct NodePosition {
pub id: i32,
pub x: f64,
pub y: f64,
}
#[derive(Debug, Clone, Copy, Default)]
#[non_exhaustive]
pub struct SugiyamaConfig {
pub vertex_spacing: f64,
pub minimum_length: u32,
pub dummy_vertices: bool,
pub direction: Direction,
pub rank_alignment: RankAlignment,
}
pub fn sugiyama_layout(
edges: &[(i32, i32)],
node_sizes: &[(i32, (f64, f64))],
config: &SugiyamaConfig,
) -> Vec<NodePosition> {
let horizontal = config.direction == Direction::LeftToRight;
let mut nodes_by_id = BTreeMap::new();
for &(node_id, size) in node_sizes {
nodes_by_id.entry(node_id).or_insert(size);
}
nodes_by_id.retain(|_, (width, height)| {
width.is_finite() && *width > 0.0 && height.is_finite() && *height > 0.0
});
let nodes: Vec<(i32, (f64, f64))> = nodes_by_id.into_iter().collect();
if nodes.is_empty() {
return Vec::new();
}
let id_to_idx: BTreeMap<i32, u32> = nodes
.iter()
.enumerate()
.map(|(idx, &(node_id, _))| (node_id, idx as u32))
.collect();
let extents = |(width, height): (f64, f64)| {
if horizontal {
(height, width)
} else {
(width, height)
}
};
let vertices: Vec<(u32, (f64, f64))> = nodes
.iter()
.enumerate()
.map(|(idx, &(_, size))| (idx as u32, extents(size)))
.collect();
let mapped_edges: Vec<(u32, u32)> = edges
.iter()
.filter(|(src, dst)| src != dst)
.filter_map(|&(src, dst)| Some((*id_to_idx.get(&src)?, *id_to_idx.get(&dst)?)))
.collect::<BTreeSet<_>>()
.into_iter()
.collect();
let mut sg_config = rust_sugiyama::configure::Config {
dummy_vertices: config.dummy_vertices,
..Default::default()
};
if config.vertex_spacing > 0.0 {
sg_config.vertex_spacing = config.vertex_spacing;
}
if config.minimum_length > 0 {
sg_config.minimum_length = config.minimum_length;
}
let mut subgraphs =
rust_sugiyama::from_vertices_and_edges(&vertices, &mapped_edges, &sg_config);
subgraphs.sort_by_key(|(layout, _, _)| {
layout
.iter()
.filter_map(|(idx, _)| nodes.get(*idx).map(|(node_id, _)| *node_id))
.min()
.unwrap_or(i32::MAX)
});
let spacing = if config.vertex_spacing > 0.0 {
config.vertex_spacing
} else {
10.0
};
let mut results = Vec::with_capacity(nodes.len());
let mut perpendicular_offset = 0.0_f64;
for (layout, _width, _height) in &subgraphs {
let mut min_perp = f64::INFINITY;
let mut max_perp = f64::NEG_INFINITY;
let mut min_layer = f64::INFINITY;
let mut rank_extents: BTreeMap<u64, f64> = BTreeMap::new();
if config.rank_alignment == RankAlignment::Start {
for &(idx, (_, layer_centre)) in layout {
if let Some(&(_, size)) = nodes.get(idx) {
let rank_extent = rank_extents.entry(layer_centre.to_bits()).or_insert(0.0);
*rank_extent = rank_extent.max(extents(size).1);
}
}
}
let start = results.len();
for &(idx, (in_layer_centre, layer_centre)) in layout {
if let Some(&(node_id, size)) = nodes.get(idx) {
let (in_layer_extent, layer_extent) = extents(size);
let aligned_extent = match config.rank_alignment {
RankAlignment::Center => layer_extent,
RankAlignment::Start => rank_extents[&layer_centre.to_bits()],
};
let in_layer_position = in_layer_centre - in_layer_extent / 2.0;
let layer_position = layer_centre - aligned_extent / 2.0;
let (x, y) = if horizontal {
(layer_position, in_layer_position)
} else {
(in_layer_position, layer_position)
};
results.push(NodePosition { id: node_id, x, y });
min_perp = min_perp.min(in_layer_position);
max_perp = max_perp.max(in_layer_position + in_layer_extent);
min_layer = min_layer.min(layer_position);
}
}
if start < results.len() {
let perpendicular_shift = perpendicular_offset - min_perp;
let layer_shift = -min_layer;
for pos in &mut results[start..] {
if horizontal {
pos.x += layer_shift;
pos.y += perpendicular_shift;
} else {
pos.x += perpendicular_shift;
pos.y += layer_shift;
}
}
perpendicular_offset += max_perp - min_perp + spacing;
}
}
results.sort_by_key(|position| position.id);
results
}
pub fn sugiyama_layout_from_cache<N>(
cache: &GeometryCache<N>,
edges: &[(i32, i32)],
config: &SugiyamaConfig,
) -> Vec<NodePosition>
where
N: NodeGeometry + Copy,
{
let node_edges: Vec<(i32, i32)> = edges
.iter()
.filter_map(|&(start_pin, end_pin)| {
let src_node = cache.pin_positions.get(&start_pin)?.node_id;
let dst_node = cache.pin_positions.get(&end_pin)?.node_id;
Some((src_node, dst_node))
})
.collect();
let node_sizes: Vec<(i32, (f64, f64))> = cache
.node_rects
.iter()
.map(|(&id, geom)| {
let (_, _, w, h) = geom.rect();
(id, (w as f64, h as f64))
})
.collect();
sugiyama_layout(&node_edges, &node_sizes, config)
}
#[cfg(test)]
mod tests {
use super::*;
use std::collections::HashMap;
fn pos_map(positions: Vec<NodePosition>) -> HashMap<i32, (f64, f64)> {
positions.into_iter().map(|p| (p.id, (p.x, p.y))).collect()
}
#[test]
fn test_empty_input() {
let result = sugiyama_layout(&[], &[], &SugiyamaConfig::default());
assert!(result.is_empty());
}
#[test]
fn test_single_node_no_edges() {
let sizes = vec![(1, (100.0, 50.0))];
let result = sugiyama_layout(&[], &sizes, &SugiyamaConfig::default());
assert_eq!(result.len(), 1);
assert_eq!(result[0].id, 1);
}
#[test]
fn test_two_nodes_one_edge() {
let sizes = vec![(10, (100.0, 50.0)), (20, (100.0, 50.0))];
let edges = vec![(10, 20)];
let result = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
assert_eq!(result.len(), 2);
let pos = pos_map(result);
assert!(pos.contains_key(&10));
assert!(pos.contains_key(&20));
assert!(
pos[&10].1 < pos[&20].1,
"source node should be in an earlier layer"
);
}
#[test]
fn test_diamond_dag() {
let sizes = vec![
(1, (80.0, 40.0)),
(2, (80.0, 40.0)),
(3, (80.0, 40.0)),
(4, (80.0, 40.0)),
];
let edges = vec![(1, 2), (1, 3), (2, 4), (3, 4)];
let result = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
assert_eq!(result.len(), 4);
let pos = pos_map(result);
assert!(pos[&1].1 < pos[&4].1);
assert!((pos[&2].1 - pos[&3].1).abs() < 1.0);
}
#[test]
fn test_edges_with_unknown_nodes_are_skipped() {
let sizes = vec![(1, (100.0, 50.0))];
let edges = vec![(1, 999)]; let result = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
assert_eq!(result.len(), 1);
assert_eq!(result[0].id, 1);
}
#[test]
fn test_duplicate_node_ids_first_wins() {
let base_sizes = vec![(1, (100.0, 50.0)), (2, (60.0, 30.0))];
let duplicate_sizes = vec![(1, (100.0, 50.0)), (1, (500.0, 400.0)), (2, (60.0, 30.0))];
assert_eq!(
sugiyama_layout(&[], &duplicate_sizes, &SugiyamaConfig::default()),
sugiyama_layout(&[], &base_sizes, &SugiyamaConfig::default())
);
}
#[test]
fn invalid_node_dimensions_are_omitted() {
let sizes = vec![
(1, (100.0, 50.0)),
(2, (0.0, 50.0)),
(3, (100.0, -1.0)),
(4, (f64::NAN, 50.0)),
(5, (100.0, f64::INFINITY)),
(2, (100.0, 50.0)),
];
let result = sugiyama_layout(&[(1, 2)], &sizes, &SugiyamaConfig::default());
assert_eq!(result.len(), 1);
assert_eq!(result[0].id, 1);
assert!(result[0].x.is_finite());
assert!(result[0].y.is_finite());
}
#[test]
fn raw_layout_ignores_duplicate_self_and_unknown_edges() {
let sizes = vec![(1, (80.0, 40.0)), (2, (80.0, 40.0)), (3, (80.0, 40.0))];
let expected = sugiyama_layout(&[(1, 2)], &sizes, &SugiyamaConfig::default());
let noisy = sugiyama_layout(
&[(1, 2), (1, 2), (1, 1), (3, 3), (1, 999), (999, 2)],
&sizes,
&SugiyamaConfig::default(),
);
assert_eq!(noisy, expected);
}
#[test]
fn equivalent_input_permutations_have_identical_positions_and_order() {
let sizes = vec![
(30, (70.0, 35.0)),
(10, (80.0, 40.0)),
(40, (90.0, 45.0)),
(20, (60.0, 30.0)),
];
let mut reversed_sizes = sizes.clone();
reversed_sizes.reverse();
let edges = vec![(10, 20), (10, 30), (20, 40), (30, 40)];
let mut reversed_edges = edges.clone();
reversed_edges.reverse();
for direction in [Direction::TopToBottom, Direction::LeftToRight] {
let config = SugiyamaConfig {
direction,
..Default::default()
};
let expected = sugiyama_layout(&edges, &sizes, &config);
let actual = sugiyama_layout(&reversed_edges, &reversed_sizes, &config);
assert_eq!(actual, expected);
assert_eq!(
actual
.iter()
.map(|position| position.id)
.collect::<Vec<_>>(),
vec![10, 20, 30, 40]
);
}
}
#[test]
fn test_config_default() {
let config = SugiyamaConfig::default();
assert_eq!(config.vertex_spacing, 0.0);
assert_eq!(config.minimum_length, 0);
assert!(!config.dummy_vertices);
assert_eq!(config.direction, Direction::TopToBottom);
assert_eq!(config.rank_alignment, RankAlignment::Center);
}
#[test]
fn test_direction_default_is_top_to_bottom() {
assert_eq!(Direction::default(), Direction::TopToBottom);
}
#[test]
fn test_node_position_fields() {
let sizes = vec![(42, (80.0, 40.0))];
let result = sugiyama_layout(&[], &sizes, &SugiyamaConfig::default());
assert_eq!(result.len(), 1);
let pos = result[0];
assert_eq!(pos.id, 42);
assert!(pos.x.is_finite());
assert!(pos.y.is_finite());
}
#[test]
fn test_left_to_right_swaps_axes() {
let sizes = vec![(10, (100.0, 50.0)), (20, (100.0, 50.0))];
let edges = vec![(10, 20)];
let ttb = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
let ltr = sugiyama_layout(
&edges,
&sizes,
&SugiyamaConfig {
direction: Direction::LeftToRight,
..Default::default()
},
);
let ttb_pos = pos_map(ttb);
let ltr_pos = pos_map(ltr);
let ttb_dy = (ttb_pos[&20].1 - ttb_pos[&10].1).abs();
let ltr_dx = (ltr_pos[&20].0 - ltr_pos[&10].0).abs();
assert!(ttb_dy > 1.0, "top-to-bottom should separate layers in y");
assert!(ltr_dx > 1.0, "left-to-right should separate layers in x");
}
#[test]
fn test_left_to_right_diamond() {
let sizes = vec![
(1, (80.0, 40.0)),
(2, (80.0, 40.0)),
(3, (80.0, 40.0)),
(4, (80.0, 40.0)),
];
let edges = vec![(1, 2), (1, 3), (2, 4), (3, 4)];
let config = SugiyamaConfig {
direction: Direction::LeftToRight,
..Default::default()
};
let result = sugiyama_layout(&edges, &sizes, &config);
let pos = pos_map(result);
assert!(pos[&1].0 < pos[&4].0);
assert!((pos[&2].0 - pos[&3].0).abs() < 1.0);
}
#[test]
fn test_disconnected_graph() {
let sizes = vec![
(1, (80.0, 40.0)),
(2, (80.0, 40.0)),
(3, (80.0, 40.0)),
(4, (80.0, 40.0)),
];
let edges = vec![(1, 2), (3, 4)];
let result = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
assert_eq!(result.len(), 4);
let pos = pos_map(result);
assert!(pos.contains_key(&1));
assert!(pos.contains_key(&2));
assert!(pos.contains_key(&3));
assert!(pos.contains_key(&4));
assert!(pos[&1].1 < pos[&2].1);
assert!(pos[&3].1 < pos[&4].1);
}
#[test]
fn test_isolated_nodes_are_packed_on_the_perpendicular_axis() {
let sizes = vec![(1, (100.0, 50.0)), (2, (100.0, 50.0)), (3, (100.0, 50.0))];
let top_to_bottom = sugiyama_layout(&[], &sizes, &SugiyamaConfig::default());
assert!(top_to_bottom
.windows(2)
.all(|pair| pair[0].x + 110.0 <= pair[1].x));
assert!(top_to_bottom.windows(2).all(|pair| pair[0].y == pair[1].y));
let left_to_right = sugiyama_layout(
&[],
&sizes,
&SugiyamaConfig {
direction: Direction::LeftToRight,
..Default::default()
},
);
assert!(left_to_right
.windows(2)
.all(|pair| pair[0].y + 60.0 <= pair[1].y));
assert!(left_to_right.windows(2).all(|pair| pair[0].x == pair[1].x));
}
#[test]
fn disconnected_components_do_not_overlap_in_either_direction() {
let sizes = vec![
(1, (100.0, 30.0)),
(2, (60.0, 80.0)),
(3, (120.0, 40.0)),
(4, (50.0, 90.0)),
];
let edges = vec![(1, 2), (3, 4)];
for direction in [Direction::TopToBottom, Direction::LeftToRight] {
let positions = pos_map(sugiyama_layout(
&edges,
&sizes,
&SugiyamaConfig {
direction,
..Default::default()
},
));
for left_id in [1, 2] {
for right_id in [3, 4] {
let (left_x, left_y) = positions[&left_id];
let (right_x, right_y) = positions[&right_id];
let (_, (left_width, left_height)) = sizes
.iter()
.find(|(id, _)| *id == left_id)
.copied()
.unwrap();
let (_, (right_width, right_height)) = sizes
.iter()
.find(|(id, _)| *id == right_id)
.copied()
.unwrap();
assert!(
left_x + left_width <= right_x
|| right_x + right_width <= left_x
|| left_y + left_height <= right_y
|| right_y + right_height <= left_y,
"components overlap in {direction:?}: {left_id} and {right_id}"
);
}
}
}
}
const DIRECTIONS: [Direction; 2] = [Direction::TopToBottom, Direction::LeftToRight];
fn size_along(direction: Direction, layer: f64, in_layer: f64) -> (f64, f64) {
match direction {
Direction::LeftToRight => (layer, in_layer),
Direction::TopToBottom => (in_layer, layer),
}
}
fn axes(direction: Direction, position: (f64, f64)) -> (f64, f64) {
match direction {
Direction::LeftToRight => position,
Direction::TopToBottom => (position.1, position.0),
}
}
const ALIGNMENTS: [RankAlignment; 2] = [RankAlignment::Center, RankAlignment::Start];
fn spaced(direction: Direction) -> SugiyamaConfig {
SugiyamaConfig {
vertex_spacing: 60.0,
direction,
..Default::default()
}
}
#[test]
fn cards_in_one_rank_do_not_overlap() {
for direction in DIRECTIONS {
for (extent_2, extent_3) in [(300.0, 100.0), (100.0, 300.0)] {
let sizes = vec![
(1, size_along(direction, 100.0, 100.0)),
(2, size_along(direction, 100.0, extent_2)),
(3, size_along(direction, 100.0, extent_3)),
];
let positions = pos_map(sugiyama_layout(
&[(1, 2), (1, 3)],
&sizes,
&spaced(direction),
));
let (layer_2, in_layer_2) = axes(direction, positions[&2]);
let (layer_3, in_layer_3) = axes(direction, positions[&3]);
assert_eq!(layer_2, layer_3, "2 and 3 share a rank in {direction:?}");
let ((first, first_extent), second) = if in_layer_2 < in_layer_3 {
((in_layer_2, extent_2), in_layer_3)
} else {
((in_layer_3, extent_3), in_layer_2)
};
assert!(
second - (first + first_extent) >= 60.0 - 1e-9,
"rank members closer than the spacing in {direction:?}: {positions:?}"
);
}
}
}
#[test]
fn consecutive_ranks_do_not_overlap() {
for direction in DIRECTIONS {
for rank_alignment in ALIGNMENTS {
let sizes = vec![
(1, size_along(direction, 600.0, 100.0)),
(2, size_along(direction, 100.0, 100.0)),
];
let positions = pos_map(sugiyama_layout(
&[(1, 2)],
&sizes,
&SugiyamaConfig {
rank_alignment,
..spaced(direction)
},
));
let (layer_1, _) = axes(direction, positions[&1]);
let (layer_2, _) = axes(direction, positions[&2]);
assert!(
layer_2 - (layer_1 + 600.0) >= 60.0 - 1e-9,
"ranks closer than the spacing in {direction:?}, {rank_alignment:?}: \
{positions:?}"
);
}
}
}
#[test]
fn every_component_starts_at_0_on_the_layer_axis() {
for direction in DIRECTIONS {
for rank_alignment in ALIGNMENTS {
let sizes = vec![
(1, size_along(direction, 600.0, 100.0)),
(2, size_along(direction, 100.0, 100.0)),
(3, size_along(direction, 100.0, 100.0)),
(4, size_along(direction, 300.0, 100.0)),
];
let positions = pos_map(sugiyama_layout(
&[(1, 2), (3, 4)],
&sizes,
&SugiyamaConfig {
rank_alignment,
..spaced(direction)
},
));
for component in [[1, 2], [3, 4]] {
let leading_edge = component
.iter()
.map(|id| axes(direction, positions[id]).0)
.fold(f64::INFINITY, f64::min);
assert_eq!(
leading_edge, 0.0,
"component {component:?} in {direction:?}, {rank_alignment:?}: \
{positions:?}"
);
}
}
}
}
#[test]
fn start_alignment_shares_each_ranks_leading_edge() {
for direction in DIRECTIONS {
let sizes = vec![
(1, size_along(direction, 600.0, 100.0)),
(2, size_along(direction, 100.0, 100.0)),
(3, size_along(direction, 100.0, 100.0)),
];
let layout = |rank_alignment| {
let positions = pos_map(sugiyama_layout(
&[(1, 3), (2, 3)],
&sizes,
&SugiyamaConfig {
rank_alignment,
..spaced(direction)
},
));
let layer_1 = axes(direction, positions[&1]).0;
let layer_2 = axes(direction, positions[&2]).0;
(layer_1, layer_2, positions)
};
let (layer_1, layer_2, positions) = layout(RankAlignment::Start);
assert_eq!(
layer_1, layer_2,
"leading edges differ in {direction:?}: {positions:?}"
);
let layer_3 = axes(direction, positions[&3]).0;
assert!(
layer_3 - (layer_1 + 600.0) >= 60.0 - 1e-9,
"the next rank is closer than the spacing in {direction:?}: {positions:?}"
);
let (layer_1, layer_2, positions) = layout(RankAlignment::Center);
assert_eq!(
layer_1 + 300.0,
layer_2 + 50.0,
"centres differ in {direction:?}: {positions:?}"
);
}
}
#[test]
fn test_cycle_does_not_panic() {
let sizes = vec![(1, (80.0, 40.0)), (2, (80.0, 40.0)), (3, (80.0, 40.0))];
let edges = vec![(1, 2), (2, 3), (3, 1)];
let result = sugiyama_layout(&edges, &sizes, &SugiyamaConfig::default());
assert_eq!(result.len(), 3);
let pos = pos_map(result);
assert!(pos[&1].0.is_finite());
assert!(pos[&2].0.is_finite());
assert!(pos[&3].0.is_finite());
}
use crate::hit_test::SimpleNodeGeometry;
use crate::state::StoredPin;
fn make_cache(
nodes: &[(i32, f32, f32, f32, f32)],
pins: &[(i32, i32, i32, f32, f32)],
) -> GeometryCache<SimpleNodeGeometry> {
let mut cache = GeometryCache::default();
for &(id, x, y, w, h) in nodes {
cache.node_rects.insert(
id,
SimpleNodeGeometry {
id,
x,
y,
width: w,
height: h,
},
);
}
for &(pin_id, node_id, pin_type, rel_x, rel_y) in pins {
cache.pin_positions.insert(
pin_id,
StoredPin {
node_id,
pin_type,
rel_x,
rel_y,
},
);
}
cache
}
#[test]
fn test_from_cache_resolves_pins_to_nodes() {
let cache = make_cache(
&[(1, 0.0, 0.0, 100.0, 50.0), (2, 200.0, 0.0, 100.0, 50.0)],
&[
(3, 1, 2, 100.0, 25.0), (4, 2, 1, 0.0, 25.0), ],
);
let result = sugiyama_layout_from_cache(&cache, &[(3, 4)], &SugiyamaConfig::default());
let pos = pos_map(result);
assert_eq!(pos.len(), 2);
assert!(pos.contains_key(&1));
assert!(pos.contains_key(&2));
assert!(pos[&1].1 < pos[&2].1, "source should be in earlier layer");
}
#[test]
fn test_from_cache_skips_self_loops() {
let cache = make_cache(
&[(1, 0.0, 0.0, 100.0, 50.0)],
&[
(10, 1, 2, 100.0, 25.0), (11, 1, 1, 0.0, 25.0), ],
);
let result = sugiyama_layout_from_cache(&cache, &[(10, 11)], &SugiyamaConfig::default());
assert_eq!(result.len(), 1);
assert_eq!(result[0].id, 1);
}
#[test]
fn test_from_cache_deduplicates_edges() {
let cache = make_cache(
&[(1, 0.0, 0.0, 100.0, 50.0), (2, 200.0, 0.0, 100.0, 50.0)],
&[
(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), ],
);
let result =
sugiyama_layout_from_cache(&cache, &[(10, 20), (11, 21)], &SugiyamaConfig::default());
assert_eq!(result.len(), 2);
let pos = pos_map(result);
assert!(pos.contains_key(&1));
assert!(pos.contains_key(&2));
}
#[test]
fn test_from_cache_skips_unknown_pins() {
let cache = make_cache(&[(1, 0.0, 0.0, 100.0, 50.0)], &[(10, 1, 2, 100.0, 25.0)]);
let result = sugiyama_layout_from_cache(&cache, &[(10, 999)], &SugiyamaConfig::default());
assert_eq!(result.len(), 1);
assert_eq!(result[0].id, 1);
}
#[test]
fn test_from_cache_empty() {
let cache: GeometryCache<SimpleNodeGeometry> = GeometryCache::default();
let result = sugiyama_layout_from_cache(&cache, &[], &SugiyamaConfig::default());
assert!(result.is_empty());
}
#[test]
fn test_from_cache_reads_node_dimensions() {
let cache = make_cache(
&[
(1, 0.0, 0.0, 200.0, 30.0), (2, 0.0, 0.0, 50.0, 100.0), ],
&[(10, 1, 2, 200.0, 15.0), (20, 2, 1, 0.0, 50.0)],
);
let result = sugiyama_layout_from_cache(&cache, &[(10, 20)], &SugiyamaConfig::default());
assert_eq!(result.len(), 2);
let pos = pos_map(result);
assert!(pos[&1].0.is_finite());
assert!(pos[&2].0.is_finite());
}
#[test]
fn test_from_cache_with_direction() {
let cache = make_cache(
&[(1, 0.0, 0.0, 100.0, 50.0), (2, 200.0, 0.0, 100.0, 50.0)],
&[(10, 1, 2, 100.0, 25.0), (20, 2, 1, 0.0, 25.0)],
);
let config = SugiyamaConfig {
direction: Direction::LeftToRight,
..Default::default()
};
let result = sugiyama_layout_from_cache(&cache, &[(10, 20)], &config);
let pos = pos_map(result);
assert!(
pos[&1].0 < pos[&2].0,
"source should be left of target in LTR layout"
);
}
#[test]
fn cache_insertion_and_edge_order_do_not_change_layout() {
let nodes = vec![
(30, 0.0, 0.0, 70.0, 35.0),
(10, 0.0, 0.0, 80.0, 40.0),
(40, 0.0, 0.0, 90.0, 45.0),
(20, 0.0, 0.0, 60.0, 30.0),
];
let pins = vec![
(101, 10, 2, 80.0, 20.0),
(201, 20, 1, 0.0, 15.0),
(102, 10, 2, 80.0, 20.0),
(301, 30, 1, 0.0, 17.5),
(202, 20, 2, 60.0, 15.0),
(401, 40, 1, 0.0, 22.5),
(302, 30, 2, 70.0, 17.5),
(402, 40, 1, 0.0, 22.5),
];
let mut reversed_nodes = nodes.clone();
reversed_nodes.reverse();
let mut reversed_pins = pins.clone();
reversed_pins.reverse();
let cache = make_cache(&nodes, &pins);
let reversed_cache = make_cache(&reversed_nodes, &reversed_pins);
let edges = vec![(101, 201), (102, 301), (202, 401), (302, 402)];
let mut reversed_edges = edges.clone();
reversed_edges.reverse();
for direction in [Direction::TopToBottom, Direction::LeftToRight] {
let config = SugiyamaConfig {
direction,
..Default::default()
};
assert_eq!(
sugiyama_layout_from_cache(&reversed_cache, &reversed_edges, &config),
sugiyama_layout_from_cache(&cache, &edges, &config)
);
}
}
}