1#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
20pub enum Direction {
21 #[default]
23 LeftRight,
24 TopBottom,
26}
27
28#[derive(Clone, Debug, Default)]
31pub struct GraphNode {
32 pub w: f64,
33 pub h: f64,
34 pub lane: Option<usize>,
36 pub pin: (Option<f64>, Option<f64>),
38}
39
40#[derive(Clone, Debug, Default)]
44pub struct GraphEdge {
45 pub from: usize,
46 pub to: usize,
47 pub label_w: Option<f64>,
48}
49
50#[derive(Clone, Debug)]
52pub struct LayeredParams {
53 pub direction: Direction,
54 pub lanes: usize,
56 pub margin: f64,
57 pub arrow: f64,
59 pub loop_size: f64,
61 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#[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#[derive(Clone, Debug, PartialEq)]
94pub struct GraphLayout {
95 pub w: f64,
96 pub h: f64,
97 pub nodes: Vec<PlacedNode>,
98 pub edges: Vec<Vec<(f64, f64)>>,
100 pub back: Vec<bool>,
102 pub routed: Vec<bool>,
105 pub layers: usize,
106 pub bands: Vec<(usize, f64, f64, f64, f64)>,
108}
109
110pub 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#[derive(Clone, Debug)]
123pub struct BandedParams {
124 pub bands: usize,
127 pub margin: f64,
128 pub col_gap: f64,
130 pub row_gap: f64,
131 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
149pub 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 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 let below =
187 |v: usize| succs[v].is_empty() && preds[v].len() == 1 && band(preds[v][0]) == band(v);
188 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 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 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 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 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 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 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
448type DagEdge = (usize, usize, usize, bool);
450
451fn 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]; 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
505fn 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
515fn 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
552fn 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
585fn 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
606pub const LABEL_CLEAR: f64 = 4.0;
608
609fn spread_ports(
614 pn: &[PlacedNode],
615 pts: &mut [Vec<(f64, f64)>],
616 straight: &[(usize, usize, usize)],
617) {
618 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 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 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 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 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
708fn 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
729fn 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 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 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 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 let (dag, free): (Vec<DagEdge>, Vec<DagEdge>) =
838 dag.into_iter().partition(|&(u, v, _, _)| rank[v] > rank[u]);
839
840 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 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 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 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 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 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 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 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 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
1230fn 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 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 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 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 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 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 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 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 #[test]
1483 fn banded_two_priors_keep_their_edges_and_labels_apart() {
1484 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 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 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 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 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 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}