bloq_utils/
graph_layout.rs

1//! Shared layered placement and obstacle-aware edge routing for dependency graphs.
2
3use std::collections::HashMap;
4
5use layout::{
6    core::{
7        base::Orientation,
8        format::{ClipHandle, RenderBackend},
9        geometry::{Point, Position},
10        style::StyleAttr,
11    },
12    std_shapes::shapes::{Arrow, Element, ShapeKind},
13    topo::layout::VisualGraph,
14};
15
16/// Cubic Bézier segments, each containing start, two controls, and end.
17pub type CubicSpline = Vec<[(f32, f32); 4]>;
18
19/// Cached geometry at zoom 1.0. Renderers apply pan and zoom without relayout.
20#[derive(Debug)]
21pub struct RelativeLayout {
22    /// Normalized top-left coordinates, keyed by node id.
23    pub positions: HashMap<u32, (f32, f32)>,
24    /// Routed splines in the original input edge order, including parallel edges.
25    pub routes: Vec<CubicSpline>,
26    /// Bounding box covering nodes and routed edges.
27    pub content: (f32, f32),
28}
29
30/// Lay out sized nodes and route their edges with `layout-rs`.
31///
32/// Regions are opaque rectangles; callers size their contents bottom-up.
33/// Node ids must be unique, sizes and gap finite, and all endpoints present.
34/// Compute once per graph edit, rather than per frame.
35///
36/// # Panics
37///
38/// Panics if an edge refers to an absent node.
39pub fn compute_relative(
40    nodes: &[(u32, (f32, f32))],
41    edges: &[(u32, u32)],
42    gap: f32,
43) -> RelativeLayout {
44    if nodes.is_empty() {
45        return RelativeLayout {
46            positions: HashMap::new(),
47            routes: Vec::new(),
48            content: (0.0, 0.0),
49        };
50    }
51
52    let orientation = Orientation::LeftToRight;
53    let mut graph = VisualGraph::new(orientation);
54    let handles = nodes
55        .iter()
56        .map(|&(id, (width, height))| {
57            let size = Point::new(f64::from(width), f64::from(height));
58            let mut element = Element::create(
59                ShapeKind::new_box(""),
60                StyleAttr::simple(),
61                orientation,
62                size,
63            );
64            element.pos = Position::new(
65                Point::zero(),
66                size,
67                Point::zero(),
68                Point::splat(f64::from(gap.max(1.0))),
69            );
70            (id, graph.add_node(element))
71        })
72        .collect::<HashMap<_, _>>();
73    for (index, &(from, to)) in edges.iter().enumerate() {
74        graph.add_edge(
75            Arrow::simple_with_properties("", index.to_string()),
76            handles[&from],
77            handles[&to],
78        );
79    }
80
81    let mut collector = RouteCollector {
82        routes: vec![Vec::new(); edges.len()],
83    };
84    graph.do_it(false, false, false, &mut collector);
85    let columns = graph
86        .dag
87        .ranks()
88        .iter()
89        .map(|rank| {
90            rank.iter().map(|&node| graph.pos(node)).fold(
91                (f32::INFINITY, f32::NEG_INFINITY),
92                |(left, right), pos| {
93                    (
94                        left.min(pos.left(false) as f32),
95                        right.max(pos.right(false) as f32),
96                    )
97                },
98            )
99        })
100        .collect::<Vec<_>>();
101    for (&(from, to), route) in edges.iter().zip(&mut collector.routes) {
102        let from = graph.dag.level(handles[&from]);
103        let to = graph.dag.level(handles[&to]);
104        if from.abs_diff(to) == route.len() && from != to {
105            // Follow the library's dummy lanes through the free column gutters.
106            // Direct smooth interpolation can clip a tall intervening region.
107            let mut routed = Vec::new();
108            for (step, &[start, _, _, end]) in route.iter().enumerate() {
109                let column = if from < to {
110                    from + step
111                } else {
112                    from - step - 1
113                };
114                let gutter = columns[column].1.midpoint(columns[column + 1].0);
115                let (entry, exit) = if from < to {
116                    ((columns[column].1, start.1), (columns[column + 1].0, end.1))
117                } else {
118                    ((columns[column + 1].0, start.1), (columns[column].1, end.1))
119                };
120                let straight = |a: (f32, f32), b: (f32, f32)| {
121                    let control = |t: f32| (a.0 + (b.0 - a.0) * t, a.1 + (b.1 - a.1) * t);
122                    [a, control(1.0 / 3.0), control(2.0 / 3.0), b]
123                };
124                routed.extend(
125                    [
126                        straight(start, entry),
127                        [entry, (gutter, start.1), (gutter, end.1), exit],
128                        straight(exit, end),
129                    ]
130                    .into_iter()
131                    .filter(|segment| segment[0] != segment[3]),
132                );
133            }
134            *route = routed;
135        }
136    }
137    let mut positions = nodes
138        .iter()
139        .map(|&(id, _)| {
140            let pos = graph.pos(handles[&id]);
141            (id, (pos.left(false) as f32, pos.top(false) as f32))
142        })
143        .collect::<HashMap<_, _>>();
144    let points = nodes
145        .iter()
146        .flat_map(|&(id, (width, height))| {
147            let (x, y) = positions[&id];
148            [(x, y), (x + width, y + height)]
149        })
150        .chain(collector.routes.iter().flatten().flatten().copied());
151    let (mut min_x, mut min_y, mut max_x, mut max_y) = (
152        f32::INFINITY,
153        f32::INFINITY,
154        f32::NEG_INFINITY,
155        f32::NEG_INFINITY,
156    );
157    for (x, y) in points {
158        min_x = min_x.min(x);
159        min_y = min_y.min(y);
160        max_x = max_x.max(x);
161        max_y = max_y.max(y);
162    }
163    for (x, y) in positions
164        .values_mut()
165        .chain(collector.routes.iter_mut().flatten().flatten())
166    {
167        *x -= min_x;
168        *y -= min_y;
169    }
170    RelativeLayout {
171        positions,
172        routes: collector.routes,
173        content: (max_x - min_x, max_y - min_y),
174    }
175}
176
177/// Geometry adapter: the library owns placement/routing, callers own rendering.
178struct RouteCollector {
179    routes: Vec<CubicSpline>,
180}
181
182impl RenderBackend for RouteCollector {
183    fn draw_arrow(
184        &mut self,
185        path: &[(Point, Point)],
186        _: bool,
187        head: (bool, bool),
188        _: &StyleAttr,
189        properties: Option<String>,
190        _: &str,
191    ) {
192        let index = properties
193            .expect("edge identity")
194            .parse::<usize>()
195            .expect("edge index");
196        let mut start = path[0].0;
197        let mut control = path[0].1;
198        for &(incoming, end) in &path[1..] {
199            self.routes[index]
200                .push([start, control, incoming, end].map(|p| (p.x as f32, p.y as f32)));
201            start = end;
202            control = end.add(end.sub(incoming));
203        }
204        if head.0 {
205            self.routes[index].reverse();
206            for segment in &mut self.routes[index] {
207                segment.reverse();
208            }
209        }
210    }
211
212    fn draw_rect(
213        &mut self,
214        _: Point,
215        _: Point,
216        _: &StyleAttr,
217        _: Option<String>,
218        _: Option<ClipHandle>,
219    ) {
220    }
221    fn draw_line(&mut self, _: Point, _: Point, _: &StyleAttr, _: Option<String>) {}
222    fn draw_circle(&mut self, _: Point, _: Point, _: &StyleAttr, _: Option<String>) {}
223    fn draw_text(&mut self, _: Point, _: &str, _: &StyleAttr) {}
224    fn create_clip(&mut self, _: Point, _: Point, _: usize) -> ClipHandle {
225        0
226    }
227}
228
229#[cfg(test)]
230mod tests {
231    use super::*;
232
233    // Dependency order advances left to right, including alongside isolated nodes.
234    #[test]
235    fn chain_places_left_to_right_and_keeps_isolated_nodes() {
236        let size = (130.0, 46.0);
237        let nodes = [(0, size), (1, size), (2, size), (3, size)];
238        let edges = [(0, 1), (1, 2)];
239
240        let layout = compute_relative(&nodes, &edges, 28.0);
241
242        assert_eq!(
243            layout.positions.len(),
244            4,
245            "every node, including the isolated one, places"
246        );
247        let col = |id: u32| layout.positions[&id].0;
248        assert!(col(0) < col(1), "successor sits in a later column");
249        assert!(col(1) < col(2), "chain keeps advancing rightwards");
250    }
251
252    // An oversized (region container) tile mixed with default tiles must not
253    // overlap its successor: the content box has to fit both full sizes.
254    #[test]
255    fn mixed_sizes_keep_tiles_disjoint_and_content_covers_them() {
256        let big = (400.0, 300.0);
257        let small = (130.0, 46.0);
258        let nodes = [(0, big), (1, small)];
259        let edges = [(0, 1)];
260
261        let layout = compute_relative(&nodes, &edges, 28.0);
262
263        let (bx, _) = layout.positions[&0];
264        let (sx, _) = layout.positions[&1];
265        assert!(
266            bx + big.0 <= sx + 0.01,
267            "successor starts after the big tile ends: {bx} + {} vs {sx}",
268            big.0
269        );
270        assert!(layout.content.0 >= sx + small.0 - 0.01);
271        assert!(layout.content.1 >= big.1 - 0.01);
272    }
273
274    #[test]
275    fn long_edges_route_around_intervening_nodes() {
276        let nodes = [(0, (180.0, 60.0)), (1, (400.0, 250.0)), (2, (180.0, 60.0))];
277        let edges = [(0, 1), (1, 2), (0, 2)];
278        let layout = compute_relative(&nodes, &edges, 40.0);
279        let (x, y) = layout.positions[&1];
280        assert!(
281            layout.routes[2].len() > 1,
282            "long edge retains its routing waypoints"
283        );
284        assert!(
285            layout.routes[2].iter().any(|[start, first, second, end]| {
286                start.1 != end.1 && first.1 == start.1 && second.1 == end.1
287            }),
288            "route uses smooth curves with horizontal endpoint tangents"
289        );
290        for segment in &layout.routes[2] {
291            for step in 0..=100 {
292                let t = step as f32 / 100.0;
293                let u = 1.0 - t;
294                let weights = [u * u * u, 3.0 * u * u * t, 3.0 * u * t * t, t * t * t];
295                let (px, py) = segment
296                    .iter()
297                    .zip(weights)
298                    .fold((0.0, 0.0), |(px, py), (&(cx, cy), weight)| {
299                        (px + cx * weight, py + cy * weight)
300                    });
301                assert!(
302                    !(x < px && px < x + 400.0 && y < py && py < y + 250.0),
303                    "edge enters intervening region at {px},{py}; box={x},{y}; route={:?}",
304                    layout.routes[2]
305                );
306            }
307        }
308    }
309
310    #[test]
311    fn parallel_cycles_and_self_edges_keep_identity_and_bounds() {
312        let nodes = [(4, (180.0, 60.0)), (9, (180.0, 60.0)), (21, (180.0, 60.0))];
313        let edges = [(4, 9), (4, 9), (9, 21), (21, 4), (9, 9)];
314        let first = compute_relative(&nodes, &edges, 40.0);
315        let second = compute_relative(&nodes, &edges, 40.0);
316        assert_eq!(first.positions, second.positions);
317        assert_eq!(first.routes, second.routes);
318        assert_eq!(first.routes.len(), edges.len());
319        for route in &first.routes {
320            assert!(!route.is_empty());
321            for &(x, y) in route.iter().flatten() {
322                assert!(x.is_finite() && y.is_finite());
323                assert!(x >= 0.0 && x <= first.content.0);
324                assert!(y >= 0.0 && y <= first.content.1);
325            }
326        }
327    }
328}
bloq_utils/graph_layout.rs

bloq_utils/
graph_layout.rs
