facett-core/src/layered.rs
//! Deterministic, iterative layered layout for dense node indices.
//!
//! An edge `(a, b)` means that `a` belongs to the left of `b`. Invalid indices
//! are ignored. Cycles are reported and back edges ignored when assigning ranks;
//! every edge of a DAG advances at least one column.
/// Which end of paths is aligned across disconnected or unequal branches.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub enum Align {
#[default]
Sources,
Sinks,
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub enum RowOrder {
#[default]
Input,
/// At most 32 alternating sweeps, retaining the best crossing count found.
Barycenter { sweeps: u8 },
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct LayeredOpts {
pub align: Align,
pub rows: RowOrder,
}
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct Layered {
pub col: Vec<u32>,
pub row: Vec<u32>,
pub cols: u32,
pub rows_max: u32,
pub cyclic: bool,
}
/// Compute longest-path ranks without recursion, in O(nodes + edges).
pub fn ranks(n: usize, edges: &[(u32, u32)], align: Align) -> (Vec<u32>, bool) {
let mut adjacent = vec![Vec::new(); n];
for &(a, b) in edges {
if (a as usize) < n && (b as usize) < n {
let (from, to) = match align {
Align::Sources => (b, a),
Align::Sinks => (a, b),
};
adjacent[from as usize].push(to as usize);
}
}
let mut rank = vec![0u32; n];
let mut state = vec![0u8; n];
let mut stack = Vec::new();
let mut cyclic = false;
for root in 0..n {
if state[root] != 0 {
continue;
}
state[root] = 1;
stack.push((root, 0usize));
while let Some(&mut (node, ref mut next)) = stack.last_mut() {
if *next == adjacent[node].len() {
state[node] = 2;
stack.pop();
if let Some(&(parent, _)) = stack.last() {
rank[parent] = rank[parent].max(rank[node].saturating_add(1));
}
continue;
}
let child = adjacent[node][*next];
*next += 1;
match state[child] {
0 => {
state[child] = 1;
stack.push((child, 0));
}
1 => {
// Ignore back edges entirely: assigning a distance here adds
// a phantom node, making an n-node cycle occupy n+1 columns.
cyclic = true;
}
_ => rank[node] = rank[node].max(rank[child].saturating_add(1)),
}
}
}
if align == Align::Sinks {
let max = rank.iter().copied().max().unwrap_or(0);
for value in &mut rank {
*value = max - *value;
}
}
(rank, cyclic)
}
pub fn layered(n: usize, edges: &[(u32, u32)], opts: LayeredOpts) -> Layered {
let (col, cyclic) = ranks(n, edges, opts.align);
let cols = col.iter().max().map_or(0, |c| c + 1);
let mut columns = vec![Vec::new(); cols as usize];
let mut row = vec![0; n];
for (i, &c) in col.iter().enumerate() {
row[i] = columns[c as usize].len() as u32;
columns[c as usize].push(i);
}
let rows_max = columns.iter().map(Vec::len).max().unwrap_or(0) as u32;
let mut layout = Layered {
col,
row,
cols,
rows_max,
cyclic,
};
if let RowOrder::Barycenter { sweeps } = opts.rows {
barycenter_rows(&mut layout, edges, sweeps);
}
layout
}
/// **Reorder the rows of an already-columned `layout`** by alternating barycenter sweeps
/// (at most 32), keeping the row order with the fewest [`crossings`]. The columns are
/// the caller's: [`layered`] uses it for [`RowOrder::Barycenter`], and a host that
/// places its own columns (e.g. a pinned first column) orders its rows with it.
pub fn barycenter_rows(layout: &mut Layered, edges: &[(u32, u32)], sweeps: u8) {
let n = layout.col.len();
let cols = layout.col.iter().max().map_or(0, |c| c + 1) as usize;
let mut columns: Vec<Vec<usize>> = vec![Vec::new(); cols];
let mut by_row: Vec<usize> = (0..n).collect();
by_row.sort_by_key(|&i| (layout.row[i], i));
for i in by_row {
columns[layout.col[i] as usize].push(i);
}
let mut incoming = vec![Vec::new(); n];
let mut outgoing = vec![Vec::new(); n];
for &(a, b) in edges {
let (a, b) = (a as usize, b as usize);
if a < n && b < n && layout.col[a] < layout.col[b] {
outgoing[a].push(b);
incoming[b].push(a);
}
}
let mut best_rows = layout.row.clone();
let mut best_crossings = crossings(layout, edges);
for sweep in 0..sweeps.min(32) {
if best_crossings == 0 {
break;
}
let forward = sweep % 2 == 0;
for index in 0..columns.len() {
let c = if forward {
index
} else {
columns.len() - 1 - index
};
let neighbors = if forward { &incoming } else { &outgoing };
let score = |node: usize| {
let ns = &neighbors[node];
if ns.is_empty() {
layout.row[node] as f64
} else {
ns.iter().map(|&j| layout.row[j] as f64).sum::<f64>() / ns.len() as f64
}
};
columns[c].sort_by(|&a, &b| {
score(a)
.total_cmp(&score(b))
.then_with(|| layout.row[a].cmp(&layout.row[b]))
.then(a.cmp(&b))
});
for (r, &node) in columns[c].iter().enumerate() {
layout.row[node] = r as u32;
}
}
let count = crossings(layout, edges);
if count < best_crossings {
best_crossings = count;
best_rows.clone_from(&layout.row);
}
}
layout.row = best_rows;
}
/// Map column/row coordinates to world coordinates; callers choose their pitch.
pub fn place(layout: &Layered, pitch: [f32; 2], pad: [f32; 2]) -> Vec<[f32; 2]> {
layout
.col
.iter()
.zip(&layout.row)
.map(|(&c, &r)| [pad[0] + c as f32 * pitch[0], pad[1] + r as f32 * pitch[1]])
.collect()
}
/// Count strict edge crossings between each pair of columns, in O(E log E).
/// Shared endpoints and edges within a column do not count as crossings.
pub fn crossings(layout: &Layered, edges: &[(u32, u32)]) -> u64 {
let mut pairs = Vec::with_capacity(edges.len());
for &(a, b) in edges {
let (mut a, mut b) = (a as usize, b as usize);
if a >= layout.col.len()
|| b >= layout.col.len()
|| a >= layout.row.len()
|| b >= layout.row.len()
{
continue;
}
if layout.col[a] > layout.col[b] {
std::mem::swap(&mut a, &mut b);
}
if layout.col[a] != layout.col[b] {
pairs.push((layout.col[a], layout.col[b], layout.row[a], layout.row[b]));
}
}
pairs.sort_unstable();
let mut count = 0;
let mut begin = 0;
while begin < pairs.len() {
let key = (pairs[begin].0, pairs[begin].1);
let mut end = begin + 1;
while end < pairs.len() && (pairs[end].0, pairs[end].1) == key {
end += 1;
}
let mut targets: Vec<_> = pairs[begin..end].iter().map(|p| p.3).collect();
targets.sort_unstable();
targets.dedup();
let mut tree = vec![0u64; targets.len() + 1];
let mut seen = 0;
let mut i = begin;
while i < end {
let mut j = i + 1;
while j < end && pairs[j].2 == pairs[i].2 {
j += 1;
}
for p in &pairs[i..j] {
let mut index = targets.binary_search(&p.3).unwrap() + 1;
let mut below_or_equal = 0;
while index > 0 {
below_or_equal += tree[index];
index &= index - 1;
}
count += seen - below_or_equal;
}
for p in &pairs[i..j] {
let mut index = targets.binary_search(&p.3).unwrap() + 1;
while index < tree.len() {
tree[index] += 1;
index += index.isolate_lowest_one();
}
seen += 1;
}
i = j;
}
begin = end;
}
count
}