Skip to main content

ggplot_rs/
graph_layout.rs

1//! Layered (Sugiyama-style) layout of a directed graph of boxes — nodes in
2//! layers (stages) along one axis, ordered across it to keep crossings low.
3//!
4//! The steps: cycles broken by a DFS in input order; ranks by longest path
5//! (a pinned layer wins; sources pulled up to just before their nearest
6//! successor); a dummy vertex per layer a long edge passes; barycenter sweeps
7//! plus adjacent transposition, the fewest crossings kept (counted per layer
8//! pair with a Fenwick tree); a weighted least-squares (isotonic) placement
9//! along each layer; ports spread along a box's side; optional swimlanes as
10//! bands. A graph whose every node is pinned in both axes is drawn on a grid
11//! where it is placed, with straight edges.
12//!
13//! Node sizes come from the caller (the box contents are the drawing's
14//! business); the result is in px with the origin at the top-left margin.
15//! Moved here from anofox-visualization's `::DIAGRAM` (sipemu/ggplot-rs#497,
16//! DataZooDE/anofox-visualization#1153).
17
18/// Which way the layers run.
19#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
20pub enum Direction {
21    /// Layers left to right (the default).
22    #[default]
23    LeftRight,
24    /// Layers top to bottom.
25    TopBottom,
26}
27
28/// A node: its box size, its swimlane, and optional pins (a layer, and a
29/// position across it; both pinned on every node → the grid layout).
30#[derive(Clone, Debug, Default)]
31pub struct GraphNode {
32    pub w: f64,
33    pub h: f64,
34    /// Index of the node's swimlane (< [`LayeredParams::lanes`]), if any.
35    pub lane: Option<usize>,
36    /// Pinned layer and pinned position (grid units in the explicit layout).
37    pub pin: (Option<f64>, Option<f64>),
38}
39
40/// A directed edge; `label_w` is the width (px) of its label, if it has one:
41/// left to right, the gap between two layers is at least as wide as the
42/// labels that cross it.
43#[derive(Clone, Debug, Default)]
44pub struct GraphEdge {
45    pub from: usize,
46    pub to: usize,
47    pub label_w: Option<f64>,
48}
49
50/// Spacing and options; the defaults are anofox-visualization's diagram.
51#[derive(Clone, Debug)]
52pub struct LayeredParams {
53    pub direction: Direction,
54    /// Number of swimlanes (nodes carry the index).
55    pub lanes: usize,
56    pub margin: f64,
57    /// Arrowhead length (an edge label's gap leaves room for two).
58    pub arrow: f64,
59    /// A self-loop's reach beyond its box.
60    pub loop_size: f64,
61    /// Extra space between swimlanes, and a lane's label strip.
62    pub lane_gap: f64,
63    pub lane_head: f64,
64}
65
66impl Default for LayeredParams {
67    fn default() -> Self {
68        LayeredParams {
69            direction: Direction::LeftRight,
70            lanes: 0,
71            margin: 10.0,
72            arrow: 7.0,
73            loop_size: 16.0,
74            lane_gap: 22.0,
75            lane_head: 16.0,
76        }
77    }
78}
79
80/// A placed node: centre, size, layer, and rank in reading order (layer by
81/// layer, then along it).
82#[derive(Clone, Debug, PartialEq)]
83pub struct PlacedNode {
84    pub cx: f64,
85    pub cy: f64,
86    pub w: f64,
87    pub h: f64,
88    pub layer: usize,
89    pub order: usize,
90}
91
92/// The laid-out graph.
93#[derive(Clone, Debug, PartialEq)]
94pub struct GraphLayout {
95    pub w: f64,
96    pub h: f64,
97    pub nodes: Vec<PlacedNode>,
98    /// Per edge (input order): its points, source → target.
99    pub edges: Vec<Vec<(f64, f64)>>,
100    /// Edges drawn against the layer order (they close a cycle).
101    pub back: Vec<bool>,
102    /// Per edge: routed orthogonally around other boxes (`banded`'s bus);
103    /// a drawing may leave such an edge's label to its tooltip.
104    pub routed: Vec<bool>,
105    pub layers: usize,
106    /// Swimlane bands: (lane, x0, y0, x1, y1).
107    pub bands: Vec<(usize, f64, f64, f64, f64)>,
108}
109
110/// Lay out `nodes` and `edges` in layers (see the module docs).
111pub fn layered(nodes: &[GraphNode], edges: &[GraphEdge], p: &LayeredParams) -> GraphLayout {
112    let explicit =
113        !nodes.is_empty() && nodes.iter().all(|n| n.pin.0.is_some() && n.pin.1.is_some());
114    if explicit {
115        layout_explicit(nodes, edges, p)
116    } else {
117        layout(nodes, edges, p)
118    }
119}
120
121/// Spacing of [`banded`].
122#[derive(Clone, Debug)]
123pub struct BandedParams {
124    /// Number of bands (nodes carry the index in [`GraphNode::lane`]; a
125    /// node without one goes in band 0).
126    pub bands: usize,
127    pub margin: f64,
128    /// Space between columns, and between stacked nodes in a band.
129    pub col_gap: f64,
130    pub row_gap: f64,
131    /// Space between bands, and a band's label strip.
132    pub band_gap: f64,
133    pub band_head: f64,
134}
135
136impl Default for BandedParams {
137    fn default() -> Self {
138        BandedParams {
139            bands: 0,
140            margin: 10.0,
141            col_gap: 36.0,
142            row_gap: 18.0,
143            band_gap: 22.0,
144            band_head: 16.0,
145        }
146    }
147}
148
149/// Lay out a graph in horizontal bands (a factor graph's layers: control,
150/// parameters, states, observations, …), left to right. A column is a step
151/// along an edge **within** a band; an edge into another band keeps the
152/// column, so a branch drops straight down (or up) into its band — the
153/// state chain stays one straight row with each observation below its
154/// state. A leaf hanging off one node of its band (an observed variable
155/// under its factor) sits right below it; nodes dropping in from other
156/// bands side by side fan out over the band's free columns. Nodes that
157/// still share a band and a column stack in tracks, a node staying on the
158/// track of the node before it in its band. A source is
159/// pulled right to just before its first successor in its band (a
160/// constant next to its factor). Edges are straight; a cycle's closing
161/// edge is drawn as is and marked `back`.
162pub fn banded(nodes: &[GraphNode], edges: &[GraphEdge], p: &BandedParams) -> GraphLayout {
163    let n = nodes.len();
164    let band = |v: usize| nodes[v].lane.unwrap_or(0).min(p.bands.saturating_sub(1));
165    let (dag, loops) = break_cycles(n, edges);
166    let mut preds: Vec<Vec<usize>> = vec![Vec::new(); n];
167    let mut succs: Vec<Vec<usize>> = vec![Vec::new(); n];
168    for &(u, v, _, _) in &dag {
169        preds[v].push(u);
170        succs[u].push(v);
171    }
172    // topological order, the first ready node in input order each time
173    let mut indeg: Vec<usize> = preds.iter().map(Vec::len).collect();
174    let mut done = vec![false; n];
175    let mut topo = Vec::with_capacity(n);
176    while let Some(v) = (0..n).find(|&v| !done[v] && indeg[v] == 0) {
177        done[v] = true;
178        topo.push(v);
179        for &w in &succs[v] {
180            indeg[w] -= 1;
181        }
182    }
183    let step = |u: usize, v: usize| usize::from(band(u) == band(v));
184    // a leaf hanging off one node of its own band (an observed variable
185    // under its factor): same column, the track below it
186    let below =
187        |v: usize| succs[v].is_empty() && preds[v].len() == 1 && band(preds[v][0]) == band(v);
188    // a node fed only from other bands (a branch dropping in): it fans out
189    // to the next free column of its band rather than stacking
190    let drops = |v: usize| !preds[v].is_empty() && preds[v].iter().all(|&u| band(u) != band(v));
191    let mut col = vec![0usize; n];
192    let mut used: std::collections::HashSet<(usize, usize)> = Default::default();
193    for &v in &topo {
194        col[v] = if below(v) {
195            col[preds[v][0]]
196        } else {
197            preds[v]
198                .iter()
199                .map(|&u| col[u] + step(u, v))
200                .max()
201                .unwrap_or(0)
202        };
203        if drops(v) {
204            while used.contains(&(band(v), col[v])) {
205                col[v] += 1;
206            }
207        }
208        used.insert((band(v), col[v]));
209    }
210    for &v in topo.iter().rev() {
211        if preds[v].is_empty() {
212            if let Some(m) = succs[v]
213                .iter()
214                .map(|&w| col[w].saturating_sub(step(v, w)))
215                .min()
216            {
217                col[v] = col[v].max(m);
218            }
219        }
220    }
221    // tracks: per (band, column) the slots taken
222    let mut track = vec![0usize; n];
223    let mut taken: std::collections::HashSet<(usize, usize, usize)> = Default::default();
224    for &v in &topo {
225        let want = if below(v) {
226            track[preds[v][0]] + 1
227        } else {
228            preds[v]
229                .iter()
230                .filter(|&&u| band(u) == band(v))
231                .map(|&u| track[u])
232                .min()
233                .unwrap_or(0)
234        };
235        let mut t = want;
236        while taken.contains(&(band(v), col[v], t)) {
237            t += 1;
238        }
239        taken.insert((band(v), col[v], t));
240        track[v] = t;
241    }
242    // geometry: column widths over all bands, track heights per band
243    let ncol = col.iter().max().map_or(0, |m| m + 1);
244    let mut col_w = vec![0.0f64; ncol];
245    for v in 0..n {
246        col_w[col[v]] = col_w[col[v]].max(nodes[v].w);
247    }
248    // the gap after each column: wide enough for the label of an edge that
249    // crosses it within a band (a factor's interface name, anofox-visualization#1238)
250    let mut gap = vec![p.col_gap; ncol];
251    for e in edges {
252        let (u, v) = (e.from, e.to);
253        if let Some(lw) = e
254            .label_w
255            .filter(|_| band(u) == band(v) && col[u].abs_diff(col[v]) == 1)
256        {
257            let c = col[u].min(col[v]);
258            gap[c] = gap[c].max(lw + 2.0 * LABEL_CLEAR + 4.0);
259        }
260    }
261    let mut col_x = vec![0.0f64; ncol];
262    let mut x = 0.0;
263    for c in 0..ncol {
264        col_x[c] = x + col_w[c] / 2.0;
265        x += col_w[c] + gap[c];
266    }
267    let nb = p.bands.max(1);
268    let ntr: Vec<usize> = (0..nb)
269        .map(|b| {
270            (0..n)
271                .filter(|&v| band(v) == b)
272                .map(|v| track[v] + 1)
273                .max()
274                .unwrap_or(0)
275        })
276        .collect();
277    let mut track_h: Vec<Vec<f64>> = ntr.iter().map(|&k| vec![0.0; k]).collect();
278    for v in 0..n {
279        let h = &mut track_h[band(v)][track[v]];
280        *h = h.max(nodes[v].h);
281    }
282    let lanes = p.bands > 0;
283    let mut track_y: Vec<Vec<f64>> = Vec::with_capacity(nb);
284    let mut band_span: Vec<(f64, f64)> = Vec::with_capacity(nb);
285    let mut y = 0.0;
286    for heights in &track_h {
287        if lanes {
288            y += p.band_head;
289        }
290        let top = y;
291        let mut ys = Vec::new();
292        for &h in heights {
293            ys.push(y + h / 2.0);
294            y += h + p.row_gap;
295        }
296        let bottom = if heights.is_empty() { y } else { y - p.row_gap };
297        band_span.push((top, bottom));
298        track_y.push(ys);
299        y = bottom + if lanes { p.band_gap } else { p.row_gap };
300    }
301    let mut order: Vec<usize> = (0..n).collect();
302    order.sort_by_key(|&v| (col[v], band(v), track[v], v));
303    let mut rank = vec![0usize; n];
304    for (i, &v) in order.iter().enumerate() {
305        rank[v] = i;
306    }
307    let pn: Vec<PlacedNode> = (0..n)
308        .map(|v| PlacedNode {
309            cx: col_x[col[v]],
310            cy: track_y[band(v)][track[v]],
311            w: nodes[v].w,
312            h: nodes[v].h,
313            layer: col[v],
314            order: rank[v],
315        })
316        .collect();
317    let mut edge_pts = vec![Vec::new(); edges.len()];
318    let mut back = vec![false; edges.len()];
319    let mut routed = vec![false; edges.len()];
320    // An edge into another band and another column (a parameter feeding
321    // factors along a chain) runs orthogonally, like a bus: out of its node's
322    // side into the gap beside its column, along a lane of the channel
323    // between the bands (one lane per source), then into the top (bottom) of
324    // a target in the next band, or down (up) the gap beside a farther
325    // target's column and into its side — so it crosses no box.
326    // In the same column it runs straight down (up), unless another box of
327    // the column is in the way or the target takes several such edges: then
328    // it takes the bus too, so the lines don't run on top of each other
329    // (anofox-visualization#1238).
330    let same_col_in = |v: usize| {
331        dag.iter()
332            .filter(|&&(a, b, _, _)| b == v && band(a) != band(v) && col[a] == col[v])
333            .count()
334    };
335    let blocked = |u: usize, v: usize| {
336        let (lo, hi) = if pn[u].cy < pn[v].cy {
337            (pn[u].cy, pn[v].cy)
338        } else {
339            (pn[v].cy, pn[u].cy)
340        };
341        (0..n).any(|w| w != u && w != v && col[w] == col[u] && pn[w].cy > lo && pn[w].cy < hi)
342    };
343    let bussed = |u: usize, v: usize| {
344        band(u) != band(v) && (col[u] != col[v] || same_col_in(v) > 1 || blocked(u, v))
345    };
346    let mut lanes_of: Vec<((usize, bool), Vec<usize>)> = Vec::new();
347    for &(_, _, k, _) in &dag {
348        let (u, v) = (edges[k].from, edges[k].to);
349        if !bussed(u, v) {
350            continue;
351        }
352        let key = (band(u), band(v) > band(u));
353        match lanes_of.iter_mut().find(|(c, _)| *c == key) {
354            Some((_, us)) if !us.contains(&u) => us.push(u),
355            Some(_) => {}
356            None => lanes_of.push((key, vec![u])),
357        }
358    }
359    const LANE: f64 = 8.0;
360    let route = |u: usize, v: usize| -> Vec<(f64, f64)> {
361        let (a, b) = (&pn[u], &pn[v]);
362        let down = band(v) > band(u);
363        let (top, bottom) = band_span[band(u)];
364        let channel = if down {
365            bottom + p.band_gap / 2.0
366        } else {
367            top - (if lanes { p.band_head } else { 0.0 }) - p.band_gap / 2.0
368        };
369        let us = lanes_of
370            .iter()
371            .find(|(c, _)| *c == (band(u), down))
372            .map_or(&[][..], |(_, us)| &us[..]);
373        let i = us.iter().position(|&x| x == u).unwrap_or(0) as f64;
374        let y = channel + (i - (us.len().max(1) - 1) as f64 / 2.0) * LANE;
375        let right = col[v] >= col[u];
376        let side = |n: &PlacedNode, c: usize, r: bool| {
377            if r {
378                (n.cx + n.w / 2.0, col_x[c] + col_w[c] / 2.0 + gap[c] / 2.0)
379            } else {
380                (
381                    n.cx - n.w / 2.0,
382                    col_x[c] - col_w[c] / 2.0 - gap[c.saturating_sub(1)] / 2.0,
383                )
384            }
385        };
386        let (sx, sg) = side(a, col[u], right);
387        // each source descends its own line of the gap, as it has its own lane
388        let sg = sg + (i - (us.len().max(1) - 1) as f64 / 2.0) * LANE;
389        let mut pts = vec![(sx, a.cy), (sg, a.cy), (sg, y)];
390        let next_band = band(v).abs_diff(band(u)) == 1;
391        let facing = if down {
392            track[v] == 0
393        } else {
394            track[v] + 1 == ntr[band(v)]
395        };
396        if next_band && facing {
397            let ey = if down {
398                b.cy - b.h / 2.0
399            } else {
400                b.cy + b.h / 2.0
401            };
402            // each bus enters a shared target on its own line, as on its lane
403            let off = ((i - (us.len().max(1) - 1) as f64 / 2.0) * LANE)
404                .clamp(-b.w / 2.0 + 3.0, b.w / 2.0 - 3.0);
405            pts.extend([(b.cx + off, y), (b.cx + off, ey)]);
406        } else {
407            let (ex, tg) = side(b, col[v], !right);
408            pts.extend([(tg, y), (tg, b.cy), (ex, b.cy)]);
409        }
410        pts
411    };
412    for &(_, _, k, rev) in &dag {
413        let (u, v) = (edges[k].from, edges[k].to);
414        routed[k] = bussed(u, v);
415        edge_pts[k] = if bussed(u, v) {
416            route(u, v)
417        } else {
418            straight(&pn, u, v)
419        };
420        back[k] = rev;
421    }
422    for &k in &loops {
423        edge_pts[k] = self_loop(&pn[edges[k].from], true, 16.0);
424    }
425    let straight_edges: Vec<(usize, usize, usize)> = dag
426        .iter()
427        .filter(|&&(u, v, _, _)| !bussed(u, v))
428        .map(|&(u, v, k, _)| (k, u, v))
429        .collect();
430    spread_ports(&pn, &mut edge_pts, &straight_edges);
431    let bands = if lanes {
432        let (x0, x1) = (-12.0, x - gap.last().copied().unwrap_or(p.col_gap) + 12.0);
433        (0..nb)
434            .filter(|&b| ntr[b] > 0)
435            .map(|b| {
436                let (top, bottom) = band_span[b];
437                (b, x0, top - p.band_head - 4.0, x1, bottom + 8.0)
438            })
439            .collect()
440    } else {
441        Vec::new()
442    };
443    let mut g = finish(pn, edge_pts, back, ncol, bands, p.margin);
444    g.routed = routed;
445    g
446}
447
448/// A DAG edge: `(u, v, edge index, reversed)`.
449type DagEdge = (usize, usize, usize, bool);
450
451/// The cycle-free orientation (a DFS in input order reverses every edge
452/// that closes a cycle), and the self-loops (edge indices).
453fn break_cycles(n: usize, edges: &[GraphEdge]) -> (Vec<DagEdge>, Vec<usize>) {
454    let mut out: Vec<Vec<(usize, usize)>> = vec![Vec::new(); n];
455    let mut loops = Vec::new();
456    for (k, e) in edges.iter().enumerate() {
457        if e.from == e.to {
458            loops.push(k);
459        } else {
460            out[e.from].push((e.to, k));
461        }
462    }
463    let mut state = vec![0u8; n]; // 0 new, 1 on the DFS stack, 2 done
464    let mut rev = vec![false; edges.len()];
465    for s in 0..n {
466        if state[s] != 0 {
467            continue;
468        }
469        state[s] = 1;
470        let mut stack = vec![(s, 0usize)];
471        while let Some(top) = stack.last_mut() {
472            let v = top.0;
473            if top.1 < out[v].len() {
474                let (w, k) = out[v][top.1];
475                top.1 += 1;
476                match state[w] {
477                    0 => {
478                        state[w] = 1;
479                        stack.push((w, 0));
480                    }
481                    1 => rev[k] = true,
482                    _ => {}
483                }
484            } else {
485                state[v] = 2;
486                stack.pop();
487            }
488        }
489    }
490    let dag = edges
491        .iter()
492        .enumerate()
493        .filter(|(_, e)| e.from != e.to)
494        .map(|(k, e)| {
495            if rev[k] {
496                (e.to, e.from, k, true)
497            } else {
498                (e.from, e.to, k, false)
499            }
500        })
501        .collect();
502    (dag, loops)
503}
504
505/// `keys` ordered by `(primary, secondary, index)`, as the indices.
506fn ordered(mut keys: Vec<(f64, f64, usize)>) -> Vec<usize> {
507    keys.sort_unstable_by(|a, b| {
508        a.0.total_cmp(&b.0)
509            .then(a.1.total_cmp(&b.1))
510            .then(a.2.cmp(&b.2))
511    });
512    keys.into_iter().map(|k| k.2).collect()
513}
514
515/// Crossings between two adjacent layers (Barth–Mutzel–Jünger: the edges by
516/// their upper end, inversions of the lower ends counted with a Fenwick tree).
517fn layer_crossings(upper: &[usize], succ: &[Vec<usize>], pos: &[usize], lower_len: usize) -> u64 {
518    let mut ends: Vec<(usize, usize)> = Vec::new();
519    for &u in upper {
520        for &v in &succ[u] {
521            ends.push((pos[u], pos[v]));
522        }
523    }
524    let lower: Vec<usize> = ordered(
525        ends.iter()
526            .enumerate()
527            .map(|(i, &(u, v))| (u as f64, v as f64, i))
528            .collect(),
529    )
530    .into_iter()
531    .map(|i| ends[i].1)
532    .collect();
533    let mut tree = vec![0u64; lower_len + 1];
534    let mut c = 0u64;
535    for (seen, &p) in lower.iter().enumerate() {
536        let mut i = p + 1;
537        let mut le = 0u64;
538        while i > 0 {
539            le += tree[i];
540            i -= 1 << i.trailing_zeros();
541        }
542        c += seen as u64 - le;
543        let mut i = p + 1;
544        while i <= lower_len {
545            tree[i] += 1;
546            i += 1 << i.trailing_zeros();
547        }
548    }
549    c
550}
551
552/// Isotonic placement: positions as close as possible (weighted least
553/// squares) to `want`, in the given order, at least `gap[i]` after the
554/// previous one.
555fn place(want: &[f64], weight: &[f64], gap: &[f64]) -> Vec<f64> {
556    let n = want.len();
557    let mut off = vec![0.0; n];
558    for i in 1..n {
559        off[i] = off[i - 1] + gap[i];
560    }
561    let mut blocks: Vec<(f64, f64, usize)> = Vec::new();
562    for i in 0..n {
563        blocks.push((weight[i] * (want[i] - off[i]), weight[i], 1));
564        while blocks.len() >= 2 {
565            let (b, a) = (blocks[blocks.len() - 1], blocks[blocks.len() - 2]);
566            if a.0 / a.1 > b.0 / b.1 {
567                blocks.pop();
568                let last = blocks.last_mut().expect("two blocks");
569                *last = (a.0 + b.0, a.1 + b.1, a.2 + b.2);
570            } else {
571                break;
572            }
573        }
574    }
575    let mut out = Vec::with_capacity(n);
576    for (s, w, c) in blocks {
577        for _ in 0..c {
578            let i = out.len();
579            out.push(s / w + off[i]);
580        }
581    }
582    out
583}
584
585/// Where a line from a box's centre towards `to` leaves the box.
586fn exit(p: &PlacedNode, to: (f64, f64)) -> (f64, f64) {
587    let (dx, dy) = (to.0 - p.cx, to.1 - p.cy);
588    let sx = if dx != 0.0 {
589        p.w / 2.0 / dx.abs()
590    } else {
591        f64::INFINITY
592    };
593    let sy = if dy != 0.0 {
594        p.h / 2.0 / dy.abs()
595    } else {
596        f64::INFINITY
597    };
598    let k = sx.min(sy);
599    if k.is_finite() {
600        (p.cx + dx * k, p.cy + dy * k)
601    } else {
602        (p.cx, p.cy)
603    }
604}
605
606/// Room (px) between an edge label and the box it sits beside.
607pub const LABEL_CLEAR: f64 = 4.0;
608
609/// Straight edges that meet one side of a box at the same point (two
610/// constants into a factor) get ports of their own along that side, in the
611/// order of their other ends; the other end aims at the port
612/// (anofox-visualization#1238). `straight` lists `(edge, u, v)`.
613fn spread_ports(
614    pn: &[PlacedNode],
615    pts: &mut [Vec<(f64, f64)>],
616    straight: &[(usize, usize, usize)],
617) {
618    // the side of `p` that the point on its border lies on: 0 left, 1 right, 2 top, 3 bottom
619    let side_of = |p: &PlacedNode, (x, y): (f64, f64)| {
620        if (x - (p.cx - p.w / 2.0)).abs() < 0.5 {
621            0
622        } else if (x - (p.cx + p.w / 2.0)).abs() < 0.5 {
623            1
624        } else if y < p.cy {
625            2
626        } else {
627            3
628        }
629    };
630    // per (node, side): (edge, its end is the first point, the other node)
631    type Ends = Vec<(usize, bool, usize)>;
632    let mut groups: std::collections::BTreeMap<(usize, u8), Ends> = Default::default();
633    for &(k, u, v) in straight {
634        let e = &pts[k];
635        if e.len() != 2 {
636            continue;
637        }
638        // which end lies on which node (a reversed edge runs v → u)
639        let (iu, iv) = if (e[0].0 - pn[u].cx).abs() <= pn[u].w / 2.0 + 0.5
640            && (e[0].1 - pn[u].cy).abs() <= pn[u].h / 2.0 + 0.5
641        {
642            (0, 1)
643        } else {
644            (1, 0)
645        };
646        groups
647            .entry((u, side_of(&pn[u], e[iu])))
648            .or_default()
649            .push((k, iu == 0, v));
650        groups
651            .entry((v, side_of(&pn[v], e[iv])))
652            .or_default()
653            .push((k, iv == 0, u));
654    }
655    // pass 1: the ports, per (edge, end)
656    let mut port: std::collections::HashMap<(usize, bool), (f64, f64)> = Default::default();
657    for ((node, side), mut list) in groups {
658        let m = list.len();
659        if m < 2 {
660            continue;
661        }
662        let p = &pn[node];
663        let vertical = side < 2;
664        list.sort_by(|a, b| {
665            let (pa, pb) = (&pn[a.2], &pn[b.2]);
666            let (ka, kb) = if vertical {
667                (pa.cy, pb.cy)
668            } else {
669                (pa.cx, pb.cx)
670            };
671            ka.total_cmp(&kb).then(a.0.cmp(&b.0))
672        });
673        let len = if vertical { p.h } else { p.w };
674        let span = (len * 0.6).min(14.0 * (m - 1) as f64);
675        for (i, &(k, first, _)) in list.iter().enumerate() {
676            let off = -span / 2.0 + span * i as f64 / (m - 1) as f64;
677            let at = match side {
678                0 => (p.cx - p.w / 2.0, p.cy + off),
679                1 => (p.cx + p.w / 2.0, p.cy + off),
680                2 => (p.cx + off, p.cy - p.h / 2.0),
681                _ => (p.cx + off, p.cy + p.h / 2.0),
682            };
683            port.insert((k, first), at);
684        }
685    }
686    // pass 2: an end on a port stays there; the other end aims at it
687    for &(k, u, v) in straight {
688        if pts[k].len() != 2 || !(port.contains_key(&(k, true)) || port.contains_key(&(k, false))) {
689            continue;
690        }
691        let first_on_u = (pts[k][0].0 - pn[u].cx).abs() <= pn[u].w / 2.0 + 0.5
692            && (pts[k][0].1 - pn[u].cy).abs() <= pn[u].h / 2.0 + 0.5;
693        let node_of = |first: bool| if first == first_on_u { u } else { v };
694        let p0 = port.get(&(k, true)).copied();
695        let p1 = port.get(&(k, false)).copied();
696        let aim1 = p1.unwrap_or((pn[node_of(false)].cx, pn[node_of(false)].cy));
697        let aim0 = p0.unwrap_or((pn[node_of(true)].cx, pn[node_of(true)].cy));
698        pts[k][0] = p0.unwrap_or_else(|| exit(&pn[node_of(true)], aim1));
699        pts[k][1] = p1.unwrap_or_else(|| exit(&pn[node_of(false)], aim0));
700    }
701}
702
703fn straight(pn: &[PlacedNode], u: usize, v: usize) -> Vec<(f64, f64)> {
704    let (a, b) = (&pn[u], &pn[v]);
705    vec![exit(a, (b.cx, b.cy)), exit(b, (a.cx, a.cy))]
706}
707
708/// A self-loop over (left to right) or beside (top to bottom) its box.
709fn self_loop(p: &PlacedNode, lr: bool, reach: f64) -> Vec<(f64, f64)> {
710    if lr {
711        let top = p.cy - p.h / 2.0;
712        vec![
713            (p.cx + p.w / 4.0, top),
714            (p.cx + p.w / 4.0, top - reach),
715            (p.cx - p.w / 4.0, top - reach),
716            (p.cx - p.w / 4.0, top),
717        ]
718    } else {
719        let right = p.cx + p.w / 2.0;
720        vec![
721            (right, p.cy - p.h / 4.0),
722            (right + reach, p.cy - p.h / 4.0),
723            (right + reach, p.cy + p.h / 4.0),
724            (right, p.cy + p.h / 4.0),
725        ]
726    }
727}
728
729/// Every node pinned in both axes: a grid of the widest / tallest box.
730fn layout_explicit(nodes: &[GraphNode], edges: &[GraphEdge], p: &LayeredParams) -> GraphLayout {
731    let sx = nodes.iter().map(|b| b.w).fold(0.0, f64::max) + 48.0;
732    let sy = nodes.iter().map(|b| b.h).fold(0.0, f64::max) + 24.0;
733    let pin = |v: usize| (nodes[v].pin.0.unwrap_or(0.0), nodes[v].pin.1.unwrap_or(0.0));
734    let mut xs: Vec<f64> = (0..nodes.len()).map(|v| pin(v).0).collect();
735    xs.sort_by(f64::total_cmp);
736    xs.dedup();
737    let reading = ordered((0..nodes.len()).map(|v| (pin(v).0, pin(v).1, v)).collect());
738    let mut pn: Vec<PlacedNode> = nodes
739        .iter()
740        .enumerate()
741        .map(|(v, b)| PlacedNode {
742            cx: pin(v).0 * sx,
743            cy: pin(v).1 * sy,
744            w: b.w,
745            h: b.h,
746            layer: xs.iter().position(|&x| x == pin(v).0).unwrap_or(0),
747            order: 0,
748        })
749        .collect();
750    for (i, &v) in reading.iter().enumerate() {
751        pn[v].order = i;
752    }
753    let lr = p.direction == Direction::LeftRight;
754    let pts = edges
755        .iter()
756        .map(|e| {
757            if e.from == e.to {
758                self_loop(&pn[e.from], lr, p.loop_size)
759            } else {
760                straight(&pn, e.from, e.to)
761            }
762        })
763        .collect();
764    finish(
765        pn,
766        pts,
767        vec![false; edges.len()],
768        xs.len().max(1),
769        Vec::new(),
770        p.margin,
771    )
772}
773
774fn layout(nodes: &[GraphNode], edges: &[GraphEdge], p: &LayeredParams) -> GraphLayout {
775    let n = nodes.len();
776    let (dag, loops) = break_cycles(n, edges);
777    let lr = p.direction == Direction::LeftRight;
778    let along = |b: &GraphNode| if lr { b.w } else { b.h };
779    let across = |b: &GraphNode| if lr { b.h } else { b.w };
780    let (rank_gap, node_gap) = if lr { (64.0, 20.0) } else { (48.0, 28.0) };
781    let (lane_gap, lane_head) = (p.lane_gap, p.lane_head);
782
783    // ranks: longest path in topological order (input order first), then
784    // sources pulled up to just before their nearest successor
785    let mut preds: Vec<Vec<usize>> = vec![Vec::new(); n];
786    let mut succs: Vec<Vec<usize>> = vec![Vec::new(); n];
787    for &(u, v, _, _) in &dag {
788        preds[v].push(u);
789        succs[u].push(v);
790    }
791    let mut indeg: Vec<usize> = preds.iter().map(Vec::len).collect();
792    let mut done = vec![false; n];
793    let mut topo = Vec::with_capacity(n);
794    while let Some(v) = (0..n).find(|&v| !done[v] && indeg[v] == 0) {
795        done[v] = true;
796        topo.push(v);
797        for &w in &succs[v] {
798            indeg[w] -= 1;
799        }
800    }
801    // a pinned layer wins over the longest path
802    let pinned = |v: usize| {
803        nodes[v]
804            .pin
805            .0
806            .map(|x| x.round().clamp(0.0, 1000.0) as usize)
807    };
808    let any_pin = (0..n).any(|v| pinned(v).is_some());
809    let mut rank = vec![0usize; n];
810    for &v in &topo {
811        rank[v] =
812            pinned(v).unwrap_or_else(|| preds[v].iter().map(|&q| rank[q] + 1).max().unwrap_or(0));
813    }
814    for &v in topo.iter().rev() {
815        if preds[v].is_empty() && pinned(v).is_none() {
816            if let Some(m) = succs[v].iter().map(|&s| rank[s]).min() {
817                rank[v] = rank[v].max(m.saturating_sub(1));
818            }
819        }
820    }
821    // drop empty ranks (pinned layers keep their numbers)
822    let mut used = vec![false; rank.iter().max().map_or(1, |m| m + 1)];
823    for &r in &rank {
824        used[r] = true;
825    }
826    let mut renumber = vec![0usize; used.len()];
827    let mut nl = 0;
828    for (r, u) in used.iter().enumerate() {
829        renumber[r] = nl;
830        nl += usize::from(*u || any_pin);
831    }
832    for r in &mut rank {
833        *r = renumber[*r];
834    }
835    let nl = nl.max(1);
836    // edges the pins make run within or against the layers: drawn straight
837    let (dag, free): (Vec<DagEdge>, Vec<DagEdge>) =
838        dag.into_iter().partition(|&(u, v, _, _)| rank[v] > rank[u]);
839
840    // vertices: the nodes, then one dummy per layer an edge passes
841    let mut vrank: Vec<usize> = rank.clone();
842    let mut vsucc: Vec<Vec<usize>> = vec![Vec::new(); n];
843    let mut vpred: Vec<Vec<usize>> = vec![Vec::new(); n];
844    let mut chains: Vec<Vec<usize>> = Vec::with_capacity(dag.len());
845    for &(u, v, _, _) in &dag {
846        let mut chain = vec![u];
847        let mut prev = u;
848        for r in rank[u] + 1..rank[v] {
849            let dmy = vrank.len();
850            vrank.push(r);
851            vsucc.push(Vec::new());
852            vpred.push(Vec::new());
853            vsucc[prev].push(dmy);
854            vpred[dmy].push(prev);
855            chain.push(dmy);
856            prev = dmy;
857        }
858        vsucc[prev].push(v);
859        vpred[v].push(prev);
860        chain.push(v);
861        chains.push(chain);
862    }
863    let nv = vrank.len();
864    let dummy = |v: usize| v >= n;
865    // a vertex's swimlane (unlaned nodes last; a dummy runs in its source's)
866    let mut vlane: Vec<usize> = (0..n).map(|v| nodes[v].lane.unwrap_or(p.lanes)).collect();
867    vlane.resize(nv, 0);
868    for ch in &chains {
869        for &dm in &ch[1..ch.len() - 1] {
870            vlane[dm] = vlane[ch[0]];
871        }
872    }
873    let laned = p.lanes > 0;
874
875    // initial order: DFS from the vertices by (rank, index)
876    let mut layers: Vec<Vec<usize>> = vec![Vec::new(); nl];
877    let mut seen = vec![false; nv];
878    for s in ordered((0..nv).map(|v| (vrank[v] as f64, 0.0, v)).collect()) {
879        if seen[s] {
880            continue;
881        }
882        let mut stack = vec![s];
883        while let Some(v) = stack.pop() {
884            if seen[v] {
885                continue;
886            }
887            seen[v] = true;
888            layers[vrank[v]].push(v);
889            for &w in vsucc[v].iter().rev() {
890                if !seen[w] {
891                    stack.push(w);
892                }
893            }
894        }
895    }
896    if laned {
897        for l in &mut layers {
898            *l = ordered(
899                l.iter()
900                    .enumerate()
901                    .map(|(i, &v)| (vlane[v] as f64, i as f64, v))
902                    .collect(),
903            );
904        }
905    }
906    let mut pos = vec![0usize; nv];
907    let index = |layers: &[Vec<usize>], pos: &mut [usize]| {
908        for l in layers {
909            for (i, &v) in l.iter().enumerate() {
910                pos[v] = i;
911            }
912        }
913    };
914    index(&layers, &mut pos);
915    let crossings = |layers: &[Vec<usize>], pos: &[usize]| -> u64 {
916        (0..layers.len().saturating_sub(1))
917            .map(|r| layer_crossings(&layers[r], &vsucc, pos, layers[r + 1].len()))
918            .sum()
919    };
920
921    // crossing reduction: barycenter sweeps + adjacent transposition, best kept
922    let mut best = layers.clone();
923    let mut best_c = crossings(&layers, &pos);
924    for it in 0..8 {
925        if best_c == 0 {
926            break;
927        }
928        let down = it % 2 == 0;
929        let rs: Vec<usize> = if down {
930            (1..nl).collect()
931        } else {
932            (0..nl.saturating_sub(1)).rev().collect()
933        };
934        for r in rs {
935            let nb = if down { &vpred } else { &vsucc };
936            let keyed: Vec<(f64, f64, usize)> = layers[r]
937                .iter()
938                .map(|&v| {
939                    let k = if nb[v].is_empty() {
940                        pos[v] as f64
941                    } else {
942                        nb[v].iter().map(|&w| pos[w] as f64).sum::<f64>() / nb[v].len() as f64
943                    };
944                    (vlane[v] as f64 * 1e6 + k, pos[v] as f64, v)
945                })
946                .collect();
947            layers[r] = ordered(keyed);
948            for (i, &v) in layers[r].iter().enumerate() {
949                pos[v] = i;
950            }
951        }
952        for _ in 0..4 {
953            let mut better = false;
954            for layer in layers.iter_mut() {
955                for i in 0..layer.len().saturating_sub(1) {
956                    let (a, b) = (layer[i], layer[i + 1]);
957                    if vlane[a] != vlane[b] {
958                        continue;
959                    }
960                    let pair = |x: usize, y: usize| -> usize {
961                        let c = |l: &[Vec<usize>]| {
962                            l[x].iter()
963                                .flat_map(|&q| l[y].iter().map(move |&r| (q, r)))
964                                .filter(|&(q, r)| pos[q] > pos[r])
965                                .count()
966                        };
967                        c(&vpred) + c(&vsucc)
968                    };
969                    if pair(b, a) < pair(a, b) {
970                        layer.swap(i, i + 1);
971                        pos[a] = i + 1;
972                        pos[b] = i;
973                        better = true;
974                    }
975                }
976            }
977            if !better {
978                break;
979            }
980        }
981        let c = crossings(&layers, &pos);
982        if c < best_c {
983            best_c = c;
984            best = layers.clone();
985        }
986    }
987    let layers = best;
988    index(&layers, &mut pos);
989
990    // positions across each layer
991    let size = |v: usize| if dummy(v) { 0.0 } else { across(&nodes[v]) };
992    let gap_between = |a: usize, b: usize| -> f64 {
993        let g = match (dummy(a), dummy(b)) {
994            (true, true) => 8.0,
995            (false, false) => node_gap,
996            _ => 12.0,
997        };
998        let lane = if vlane[a] != vlane[b] {
999            lane_gap + lane_head
1000        } else {
1001            0.0
1002        };
1003        size(a) / 2.0 + g + lane + size(b) / 2.0
1004    };
1005    let mut y = vec![0.0f64; nv];
1006    for l in &layers {
1007        let mut at = 0.0;
1008        for (i, &v) in l.iter().enumerate() {
1009            if i > 0 {
1010                at += gap_between(l[i - 1], v);
1011            }
1012            y[v] = at;
1013        }
1014        let mid = at / 2.0;
1015        for &v in l {
1016            y[v] -= mid;
1017        }
1018    }
1019    let relax = |y: &mut Vec<f64>, r: usize, up: bool, down: bool| {
1020        let l = &layers[r];
1021        if l.is_empty() {
1022            return;
1023        }
1024        let want: Vec<f64> = l
1025            .iter()
1026            .map(|&v| {
1027                let mut nb: Vec<usize> = Vec::new();
1028                if up {
1029                    nb.extend(&vpred[v]);
1030                }
1031                if down {
1032                    nb.extend(&vsucc[v]);
1033                }
1034                if nb.is_empty() {
1035                    y[v]
1036                } else {
1037                    nb.iter().map(|&w| y[w]).sum::<f64>() / nb.len() as f64
1038                }
1039            })
1040            .collect();
1041        let weight: Vec<f64> = l
1042            .iter()
1043            .map(|&v| if dummy(v) { 2.0 } else { 1.0 })
1044            .collect();
1045        let gaps: Vec<f64> = (0..l.len())
1046            .map(|i| {
1047                if i == 0 {
1048                    0.0
1049                } else {
1050                    gap_between(l[i - 1], l[i])
1051                }
1052            })
1053            .collect();
1054        for (&v, q) in l.iter().zip(place(&want, &weight, &gaps)) {
1055            y[v] = q;
1056        }
1057    };
1058    for _ in 0..6 {
1059        for r in 1..nl {
1060            relax(&mut y, r, true, false);
1061        }
1062        for r in (0..nl.saturating_sub(1)).rev() {
1063            relax(&mut y, r, false, true);
1064        }
1065    }
1066    for r in 0..nl {
1067        relax(&mut y, r, true, true);
1068    }
1069    // swimlanes: each lane shifted clear of the one before (across all layers)
1070    let mut lane_span: Vec<(f64, f64)> = Vec::new();
1071    if laned {
1072        let nlanes = p.lanes + 1;
1073        let span = |y: &[f64], l: usize| {
1074            (0..nv)
1075                .filter(|&v| vlane[v] == l)
1076                .map(|v| (y[v] - size(v) / 2.0, y[v] + size(v) / 2.0))
1077                .fold(None, |acc: Option<(f64, f64)>, (a, b)| match acc {
1078                    None => Some((a, b)),
1079                    Some((x, z)) => Some((x.min(a), z.max(b))),
1080                })
1081        };
1082        let mut floor: Option<f64> = None;
1083        for l in 0..nlanes {
1084            let Some((lo, _)) = span(&y, l) else {
1085                lane_span.push((f64::NAN, f64::NAN));
1086                continue;
1087            };
1088            if let Some(f) = floor {
1089                let need = f + lane_gap + lane_head - lo;
1090                if need > 0.0 {
1091                    for v in 0..nv {
1092                        if vlane[v] == l {
1093                            y[v] += need;
1094                        }
1095                    }
1096                }
1097            }
1098            let (lo, hi) = span(&y, l).expect("lane has vertices");
1099            lane_span.push((lo, hi));
1100            floor = Some(hi);
1101        }
1102    }
1103
1104    // positions along the layer axis: each layer as thick as its widest node;
1105    // left to right, a gap is at least as wide as the edge labels crossing it
1106    let mut thick = vec![0.0f64; nl];
1107    for v in 0..n {
1108        thick[rank[v]] = thick[rank[v]].max(along(&nodes[v]));
1109    }
1110    let mut gap: Vec<f64> = vec![rank_gap; nl];
1111    if lr {
1112        for e in edges {
1113            let (a, b) = (rank[e.from].min(rank[e.to]), rank[e.from].max(rank[e.to]));
1114            if b != a + 1 {
1115                continue;
1116            }
1117            if let Some(w) = e.label_w {
1118                gap[a] = gap[a].max(w + 2.0 * p.arrow + 18.0);
1119            }
1120        }
1121    }
1122    let mut start_at = vec![0.0f64; nl];
1123    for r in 1..nl {
1124        start_at[r] = start_at[r - 1] + thick[r - 1] + gap[r - 1];
1125    }
1126    let centre = |r: usize| start_at[r] + thick[r] / 2.0;
1127    let xy = |rk: f64, o: f64| if lr { (rk, o) } else { (o, rk) };
1128
1129    let mut pn: Vec<PlacedNode> = Vec::with_capacity(n);
1130    for (v, b) in nodes.iter().enumerate() {
1131        let (cx, cy) = xy(centre(rank[v]), y[v]);
1132        pn.push(PlacedNode {
1133            cx,
1134            cy,
1135            w: b.w,
1136            h: b.h,
1137            layer: rank[v],
1138            order: 0,
1139        });
1140    }
1141    let reading = ordered((0..n).map(|v| (rank[v] as f64, y[v], v)).collect());
1142    for (i, &v) in reading.iter().enumerate() {
1143        pn[v].order = i;
1144    }
1145
1146    // ports: a node's outgoing (incoming) chains spread along its side,
1147    // sorted by where they go (come from)
1148    let half_along = |v: usize| if lr { pn[v].w / 2.0 } else { pn[v].h / 2.0 };
1149    let side = |v: usize| if lr { pn[v].h } else { pn[v].w };
1150    let mut out_ports: Vec<Vec<usize>> = vec![Vec::new(); n];
1151    let mut in_ports: Vec<Vec<usize>> = vec![Vec::new(); n];
1152    for (c, ch) in chains.iter().enumerate() {
1153        out_ports[ch[0]].push(c);
1154        in_ports[ch[ch.len() - 1]].push(c);
1155    }
1156    for ports in &mut out_ports {
1157        *ports = ordered(ports.iter().map(|&c| (y[chains[c][1]], 0.0, c)).collect());
1158    }
1159    for ports in &mut in_ports {
1160        *ports = ordered(
1161            ports
1162                .iter()
1163                .map(|&c| (y[chains[c][chains[c].len() - 2]], 0.0, c))
1164                .collect(),
1165        );
1166    }
1167    let spread = |list: &[usize], c: usize, v: usize| -> f64 {
1168        let m = list.len();
1169        if m <= 1 {
1170            return 0.0;
1171        }
1172        let k = list.iter().position(|&x| x == c).unwrap_or(0);
1173        let span = (side(v) * 0.6).min(14.0 * (m - 1) as f64);
1174        -span / 2.0 + span * k as f64 / (m - 1) as f64
1175    };
1176    let mut edge_pts: Vec<Vec<(f64, f64)>> = vec![Vec::new(); edges.len()];
1177    let mut back = vec![false; edges.len()];
1178    for (c, ch) in chains.iter().enumerate() {
1179        let (u, v, k, rev) = dag[c];
1180        let mut pts = Vec::with_capacity(ch.len() * 2);
1181        pts.push(xy(
1182            centre(rank[u]) + half_along(u),
1183            y[u] + spread(&out_ports[u], c, u),
1184        ));
1185        for &dm in &ch[1..ch.len() - 1] {
1186            let r = vrank[dm];
1187            pts.push(xy(start_at[r], y[dm]));
1188            pts.push(xy(start_at[r] + thick[r], y[dm]));
1189        }
1190        pts.push(xy(
1191            centre(rank[v]) - half_along(v),
1192            y[v] + spread(&in_ports[v], c, v),
1193        ));
1194        if rev {
1195            pts.reverse();
1196        }
1197        edge_pts[k] = pts;
1198        back[k] = rev;
1199    }
1200    for k in loops {
1201        edge_pts[k] = self_loop(&pn[edges[k].from], lr, p.loop_size);
1202    }
1203    for &(u, v, k, rev) in &free {
1204        let mut pts = straight(&pn, u, v);
1205        if rev {
1206            pts.reverse();
1207        }
1208        edge_pts[k] = pts;
1209        back[k] = rev;
1210    }
1211    // swimlane bands across every layer, with the lane's label strip
1212    let total = start_at[nl - 1] + thick[nl - 1];
1213    let bands = lane_span
1214        .iter()
1215        .enumerate()
1216        .filter(|(l, (lo, _))| *l < p.lanes && lo.is_finite())
1217        .map(|(l, &(lo, hi))| {
1218            let (a, b) = if lr {
1219                xy(-12.0, lo - lane_head - 6.0)
1220            } else {
1221                xy(-lane_head - 10.0, lo - 8.0)
1222            };
1223            let (c, e) = xy(total + 12.0, hi + 8.0);
1224            (l, a, b, c, e)
1225        })
1226        .collect();
1227    finish(pn, edge_pts, back, nl, bands, p.margin)
1228}
1229
1230/// Move a layout to the margin and round it to half pixels.
1231fn finish(
1232    mut pn: Vec<PlacedNode>,
1233    mut edge_pts: Vec<Vec<(f64, f64)>>,
1234    back: Vec<bool>,
1235    layers: usize,
1236    mut bands: Vec<(usize, f64, f64, f64, f64)>,
1237    margin: f64,
1238) -> GraphLayout {
1239    let (mut x0, mut y0, mut x1, mut y1) = (f64::MAX, f64::MAX, f64::MIN, f64::MIN);
1240    for q in &pn {
1241        x0 = x0.min(q.cx - q.w / 2.0);
1242        x1 = x1.max(q.cx + q.w / 2.0);
1243        y0 = y0.min(q.cy - q.h / 2.0);
1244        y1 = y1.max(q.cy + q.h / 2.0);
1245    }
1246    for &(px, py) in edge_pts.iter().flatten() {
1247        x0 = x0.min(px);
1248        x1 = x1.max(px);
1249        y0 = y0.min(py);
1250        y1 = y1.max(py);
1251    }
1252    for &(_, a, b, c, e) in &bands {
1253        x0 = x0.min(a.min(c));
1254        x1 = x1.max(a.max(c));
1255        y0 = y0.min(b.min(e));
1256        y1 = y1.max(b.max(e));
1257    }
1258    if pn.is_empty() {
1259        (x0, y0, x1, y1) = (0.0, 0.0, 0.0, 0.0);
1260    }
1261    let r = |v: f64| (v * 2.0).round() / 2.0;
1262    let (dx, dy) = (margin - x0, margin - y0);
1263    for q in &mut pn {
1264        q.cx = r(q.cx + dx);
1265        q.cy = r(q.cy + dy);
1266    }
1267    for pts in &mut edge_pts {
1268        for pt in pts.iter_mut() {
1269            *pt = (r(pt.0 + dx), r(pt.1 + dy));
1270        }
1271    }
1272    for b in &mut bands {
1273        *b = (b.0, r(b.1 + dx), r(b.2 + dy), r(b.3 + dx), r(b.4 + dy));
1274    }
1275    GraphLayout {
1276        w: r(x1 - x0 + 2.0 * margin),
1277        h: r(y1 - y0 + 2.0 * margin),
1278        routed: vec![false; edge_pts.len()],
1279        nodes: pn,
1280        edges: edge_pts,
1281        back,
1282        layers,
1283        bands,
1284    }
1285}
1286
1287#[cfg(test)]
1288mod tests {
1289    use super::*;
1290
1291    fn node(w: f64, h: f64) -> GraphNode {
1292        GraphNode {
1293            w,
1294            h,
1295            ..Default::default()
1296        }
1297    }
1298    fn edge(from: usize, to: usize) -> GraphEdge {
1299        GraphEdge {
1300            from,
1301            to,
1302            label_w: None,
1303        }
1304    }
1305
1306    #[test]
1307    fn a_chain_runs_left_to_right_in_layers() {
1308        let l = layered(
1309            &[node(100.0, 40.0), node(100.0, 40.0), node(100.0, 40.0)],
1310            &[edge(0, 1), edge(1, 2)],
1311            &LayeredParams::default(),
1312        );
1313        assert_eq!(l.layers, 3);
1314        assert!(l.nodes[0].cx < l.nodes[1].cx && l.nodes[1].cx < l.nodes[2].cx);
1315        assert_eq!(l.nodes[0].cy, l.nodes[1].cy);
1316        // an edge leaves its source's right side and enters its target's left
1317        assert_eq!(l.edges[0][0].0, l.nodes[0].cx + 50.0);
1318        assert_eq!(l.edges[0].last().unwrap().0, l.nodes[1].cx - 50.0);
1319    }
1320
1321    #[test]
1322    fn a_cycle_is_broken_and_marked_back() {
1323        let l = layered(
1324            &[node(80.0, 30.0), node(80.0, 30.0)],
1325            &[edge(0, 1), edge(1, 0)],
1326            &LayeredParams::default(),
1327        );
1328        assert_eq!(l.back, vec![false, true]);
1329        assert_eq!(l.layers, 2);
1330    }
1331
1332    #[test]
1333    fn crossings_are_removed_where_possible() {
1334        // a→d, b→c drawn in input order would cross; the layout uncrosses them
1335        let ns = vec![node(60.0, 30.0); 4];
1336        let l = layered(&ns, &[edge(0, 3), edge(1, 2)], &LayeredParams::default());
1337        let (a, b, c, d) = (&l.nodes[0], &l.nodes[1], &l.nodes[2], &l.nodes[3]);
1338        assert_eq!(a.cy < b.cy, d.cy < c.cy, "{a:?} {b:?} {c:?} {d:?}");
1339    }
1340
1341    #[test]
1342    fn pins_and_the_explicit_grid() {
1343        let mut ns = vec![node(60.0, 30.0); 3];
1344        ns[2].pin.0 = Some(3.0);
1345        let l = layered(&ns, &[edge(0, 1)], &LayeredParams::default());
1346        assert_eq!(l.nodes[2].layer, 3, "a pinned layer keeps its number");
1347        let grid: Vec<GraphNode> = (0..4)
1348            .map(|i| GraphNode {
1349                w: 60.0,
1350                h: 30.0,
1351                pin: (Some((i % 2) as f64), Some((i / 2) as f64)),
1352                ..Default::default()
1353            })
1354            .collect();
1355        let g = layered(&grid, &[edge(0, 3)], &LayeredParams::default());
1356        assert_eq!(g.layers, 2);
1357        assert_eq!(g.nodes[0].cy, g.nodes[1].cy);
1358        assert_eq!(g.edges[0].len(), 2, "straight");
1359    }
1360
1361    #[test]
1362    fn lanes_become_bands_and_top_bottom_swaps_the_axes() {
1363        let mut ns = vec![node(60.0, 30.0); 2];
1364        ns[0].lane = Some(0);
1365        ns[1].lane = Some(1);
1366        let l = layered(
1367            &ns,
1368            &[edge(0, 1)],
1369            &LayeredParams {
1370                lanes: 2,
1371                ..Default::default()
1372            },
1373        );
1374        assert_eq!(l.bands.len(), 2);
1375        let tb = layered(
1376            &ns[..1],
1377            &[],
1378            &LayeredParams {
1379                direction: Direction::TopBottom,
1380                ..Default::default()
1381            },
1382        );
1383        assert_eq!(tb.nodes.len(), 1);
1384        let t = layered(
1385            &[node(60.0, 30.0), node(60.0, 30.0)],
1386            &[edge(0, 1)],
1387            &LayeredParams {
1388                direction: Direction::TopBottom,
1389                ..Default::default()
1390            },
1391        );
1392        assert!(t.nodes[0].cy < t.nodes[1].cy && t.nodes[0].cx == t.nodes[1].cx);
1393    }
1394
1395    #[test]
1396    fn edge_cases_loops_labels_ports_lanes_and_empty() {
1397        let p = LayeredParams::default();
1398        let empty = layered(&[], &[], &p);
1399        assert!(empty.nodes.is_empty() && empty.layers == 1);
1400        // self-loops left to right and top to bottom, in layers and on a grid
1401        for dir in [Direction::LeftRight, Direction::TopBottom] {
1402            let q = LayeredParams {
1403                direction: dir,
1404                ..Default::default()
1405            };
1406            let l = layered(
1407                &[node(60.0, 30.0), node(60.0, 30.0)],
1408                &[edge(0, 0), edge(0, 1)],
1409                &q,
1410            );
1411            assert_eq!(l.edges[0].len(), 4, "a self-loop");
1412            let g: Vec<GraphNode> = (0..2)
1413                .map(|i| GraphNode {
1414                    w: 60.0,
1415                    h: 30.0,
1416                    pin: (Some(i as f64), Some(0.0)),
1417                    ..Default::default()
1418                })
1419                .collect();
1420            let gl = layered(&g, &[edge(1, 1), edge(0, 1)], &q);
1421            assert_eq!(gl.edges[0].len(), 4);
1422        }
1423        // an edge label widens its gap; a long edge gets dummies (bends)
1424        let ns = vec![node(60.0, 30.0); 4];
1425        let plain = layered(
1426            &ns,
1427            &[edge(0, 1), edge(1, 2), edge(0, 2), edge(0, 3), edge(2, 3)],
1428            &p,
1429        );
1430        let labelled = layered(
1431            &ns,
1432            &[
1433                GraphEdge {
1434                    from: 0,
1435                    to: 1,
1436                    label_w: Some(300.0),
1437                },
1438                edge(1, 2),
1439                edge(0, 2),
1440                edge(0, 3),
1441                edge(2, 3),
1442            ],
1443            &p,
1444        );
1445        assert!(
1446            labelled.nodes[1].cx - labelled.nodes[0].cx > plain.nodes[1].cx - plain.nodes[0].cx
1447        );
1448        assert!(
1449            plain.edges[3].len() > 2,
1450            "a long edge bends through its dummies"
1451        );
1452        // several edges leave one node: their ports spread along its side
1453        let starts: Vec<f64> = [0, 2, 3].iter().map(|&k| plain.edges[k][0].1).collect();
1454        assert!(starts.windows(2).any(|w| w[0] != w[1]), "{starts:?}");
1455        // a pinned layer against the flow: a straight edge drawn back
1456        let mut pn = vec![node(60.0, 30.0); 3];
1457        pn[0].pin.0 = Some(2.0);
1458        pn[1].pin.0 = Some(0.0);
1459        let back = layered(&pn, &[edge(0, 1), edge(1, 2)], &p);
1460        assert_eq!(back.edges[0].len(), 2);
1461        // swimlanes top to bottom, an unlaned node, crossings between lanes
1462        let mut lanes = vec![node(60.0, 30.0); 5];
1463        for (i, n) in lanes.iter_mut().enumerate().take(4) {
1464            n.lane = Some(i % 2);
1465        }
1466        let q = LayeredParams {
1467            direction: Direction::TopBottom,
1468            lanes: 2,
1469            ..Default::default()
1470        };
1471        let tb = layered(
1472            &lanes,
1473            &[edge(0, 3), edge(1, 2), edge(2, 4), edge(3, 4)],
1474            &q,
1475        );
1476        assert_eq!(tb.bands.len(), 2);
1477        assert!(tb.bands.iter().all(|b| b.3 > b.1 && b.4 > b.2));
1478    }
1479
1480    /// A coin toss in bands param / obs: the Bernoulli factors dropping from
1481    /// θ fan out side by side, each observation right below its factor.
1482    #[test]
1483    fn banded_two_priors_keep_their_edges_and_labels_apart() {
1484        // anofox-visualization#1238: μ ~ Normal(12, v0), τ ~ Gamma(k0, r0),
1485        // yᵢ ~ Normal(μ, τ). Param band: 0 m0, 1 v0 → 2 N → 3 μ;
1486        // 4 k0, 5 r0 → 6 Γ → 7 τ. Obs band: 8..=10 N, 11..=13 y.
1487        let node = |lane, w| GraphNode {
1488            w,
1489            h: if w > 30.0 { 30.0 } else { 14.0 },
1490            lane: Some(lane),
1491            ..Default::default()
1492        };
1493        let mut nodes = vec![node(0, 24.0), node(0, 24.0), node(0, 34.0), node(0, 14.0)];
1494        nodes.extend([node(0, 24.0), node(0, 24.0), node(0, 34.0), node(0, 14.0)]);
1495        nodes.extend((0..3).map(|_| node(1, 34.0)));
1496        nodes.extend((0..3).map(|_| node(1, 14.0)));
1497        let edge = |from, to, label_w| GraphEdge { from, to, label_w };
1498        let mut edges = vec![
1499            edge(0, 2, Some(30.0)),
1500            edge(1, 2, Some(52.0)),
1501            edge(2, 3, Some(18.0)),
1502            edge(4, 6, Some(34.0)),
1503            edge(5, 6, Some(22.0)),
1504            edge(6, 7, Some(18.0)),
1505        ];
1506        for i in 0..3 {
1507            edges.push(edge(3, 8 + i, Some(30.0)));
1508            edges.push(edge(7, 8 + i, Some(52.0)));
1509            edges.push(edge(8 + i, 11 + i, Some(18.0)));
1510        }
1511        let l = banded(
1512            &nodes,
1513            &edges,
1514            &BandedParams {
1515                bands: 2,
1516                ..Default::default()
1517            },
1518        );
1519        let end = |k: usize| *l.edges[k].last().unwrap();
1520        // the two constants enter the factor at ports of their own
1521        assert_ne!(end(0), end(1), "m0 and v0 share a port");
1522        assert_ne!(end(3), end(4), "k0 and r0 share a port");
1523        // room for the longest interface label between a constant and its factor
1524        let (c, f) = (&l.nodes[1], &l.nodes[2]);
1525        assert!(
1526            (f.cx - f.w / 2.0) - (c.cx + c.w / 2.0) >= 52.0 + 2.0 * LABEL_CLEAR,
1527            "gap {}",
1528            (f.cx - f.w / 2.0) - (c.cx + c.w / 2.0)
1529        );
1530        // μ and τ reach every observation's factor apart
1531        for i in 0..3 {
1532            let (km, kt) = (6 + 3 * i, 7 + 3 * i);
1533            assert!(
1534                (end(km).0 - end(kt).0).abs() >= 4.0,
1535                "obs {i}: {:?} {:?}",
1536                end(km),
1537                end(kt)
1538            );
1539        }
1540        // and μ's edge passes through no other box (τ sits below μ)
1541        let crosses = |pts: &[(f64, f64)], b: &PlacedNode| {
1542            pts.windows(2).any(|w| {
1543                (0..=20).any(|s| {
1544                    let t = s as f64 / 20.0;
1545                    let (x, y) = (
1546                        w[0].0 + (w[1].0 - w[0].0) * t,
1547                        w[0].1 + (w[1].1 - w[0].1) * t,
1548                    );
1549                    (x - b.cx).abs() < b.w / 2.0 - 0.5 && (y - b.cy).abs() < b.h / 2.0 - 0.5
1550                })
1551            })
1552        };
1553        for k in [6, 9, 12] {
1554            for (v, b) in l.nodes.iter().enumerate() {
1555                if v != 3 && v != edges[k].to {
1556                    assert!(!crosses(&l.edges[k], b), "edge {k} crosses node {v}");
1557                }
1558            }
1559        }
1560    }
1561
1562    #[test]
1563    fn banded_fans_out_drops_and_hangs_leaves_below() {
1564        // 0 θ (param), 1..=3 Bernoulli (obs), 4..=6 y (obs)
1565        let node = |lane| GraphNode {
1566            w: 40.0,
1567            h: 20.0,
1568            lane: Some(lane),
1569            ..Default::default()
1570        };
1571        let mut nodes = vec![node(0)];
1572        nodes.extend((0..3).map(|_| node(1)));
1573        nodes.extend((0..3).map(|_| node(1)));
1574        let edge = |from, to| GraphEdge {
1575            from,
1576            to,
1577            label_w: None,
1578        };
1579        let mut edges = Vec::new();
1580        for i in 0..3 {
1581            edges.push(edge(0, 1 + i));
1582            edges.push(edge(1 + i, 4 + i));
1583        }
1584        let l = banded(
1585            &nodes,
1586            &edges,
1587            &BandedParams {
1588                bands: 2,
1589                ..Default::default()
1590            },
1591        );
1592        let cx: Vec<f64> = (1..=3).map(|i| l.nodes[i].cx).collect();
1593        assert!(cx[0] < cx[1] && cx[1] < cx[2], "fanned out: {cx:?}");
1594        for i in 0..3 {
1595            let (f, y) = (&l.nodes[1 + i], &l.nodes[4 + i]);
1596            assert_eq!(f.cx, y.cx, "y{i} under its factor");
1597            assert!(y.cy > f.cy);
1598        }
1599    }
1600}