nordisk/facett

facett-core/tests/layered.rs

use facett_core::layered::{Align, LayeredOpts, RowOrder, crossings, layered, place, ranks};

#[test]
fn dag_columns_and_input_rows_are_stable() {
    let edges = [(0, 1), (1, 2), (0, 3)];
    assert_eq!(
        ranks(5, &edges, Align::Sources),
        (vec![0, 1, 2, 1, 0], false)
    );
    assert_eq!(ranks(5, &edges, Align::Sinks), (vec![0, 1, 2, 2, 2], false));
    let result = layered(5, &edges, LayeredOpts::default());
    assert_eq!(result.row, [0, 0, 0, 1, 1]);
    assert_eq!((result.cols, result.rows_max), (3, 2));
    assert_eq!(
        place(&result, [20.0, 10.0], [5.0, 7.0]),
        [
            [5.0, 7.0],
            [25.0, 7.0],
            [45.0, 7.0],
            [25.0, 17.0],
            [5.0, 17.0]
        ]
    );
    let diamond = [(0, 1), (0, 2), (1, 3), (2, 3)];
    assert_eq!(ranks(4, &diamond, Align::Sources).0, [0, 1, 1, 2]);
}

#[test]
fn empty_and_invalid_edges_are_safe() {
    assert_eq!(layered(0, &[], LayeredOpts::default()), Default::default());
    assert_eq!(
        ranks(2, &[(0, 99), (99, 1), (0, 1)], Align::Sources),
        (vec![0, 1], false)
    );
}

#[test]
fn cyclic_graphs_terminate_deterministically() {
    for edges in [
        vec![(0, 0)],
        vec![(0, 1), (1, 0)],
        vec![(0, 1), (1, 2), (2, 0), (2, 3)],
    ] {
        for align in [Align::Sources, Align::Sinks] {
            let first = ranks(4, &edges, align);
            assert!(first.1);
            assert_eq!(first, ranks(4, &edges, align));
        }
    }
}

fn dag(n: u32, m: usize, seed: u64) -> Vec<(u32, u32)> {
    let mut state = seed | 1;
    let mut next = || {
        state ^= state << 13;
        state ^= state >> 7;
        state ^= state << 17;
        state as u32 % n
    };
    (0..m)
        .filter_map(|_| {
            let (a, b) = (next(), next());
            (a != b).then_some((a.min(b), a.max(b)))
        })
        .collect()
}

#[test]
fn seeded_dag_ranks_advance_and_barycenter_never_regresses() {
    for seed in 1..=20 {
        let edges = dag(1000, 3000, seed);
        for align in [Align::Sources, Align::Sinks] {
            let input = layered(
                1000,
                &edges,
                LayeredOpts {
                    align,
                    rows: RowOrder::Input,
                },
            );
            assert!(!input.cyclic);
            assert!(
                edges
                    .iter()
                    .all(|&(a, b)| input.col[a as usize] < input.col[b as usize])
            );
            let opts = LayeredOpts {
                align,
                rows: RowOrder::Barycenter { sweeps: 8 },
            };
            let optimized = layered(1000, &edges, opts);
            assert!(crossings(&optimized, &edges) <= crossings(&input, &edges));
            assert_eq!(optimized, layered(1000, &edges, opts));
        }
    }
}

#[test]
fn barycenter_removes_the_crafted_crossing_and_preserves_ties() {
    let edges = [(0, 3), (1, 2)];
    let input = layered(4, &edges, LayeredOpts::default());
    let optimized = layered(
        4,
        &edges,
        LayeredOpts {
            rows: RowOrder::Barycenter { sweeps: 4 },
            ..Default::default()
        },
    );
    assert_eq!(crossings(&input, &edges), 1);
    assert_eq!(crossings(&optimized, &edges), 0);
    assert_eq!(
        layered(
            4,
            &edges,
            LayeredOpts {
                rows: RowOrder::Barycenter { sweeps: 0 },
                ..Default::default()
            }
        ),
        input
    );
    assert_eq!(crossings(&input, &[(0, 3), (0, 2), (1, 2)]), 1);
}

#[test]
fn crossings_match_a_quadratic_reference() {
    for seed in 1..=20 {
        let edges = dag(30, 100, seed);
        let l = layered(30, &edges, LayeredOpts::default());
        let mut expected = 0;
        for (i, &(a, b)) in edges.iter().enumerate() {
            for &(c, d) in &edges[i + 1..] {
                let (a, b, c, d) = (a as usize, b as usize, c as usize, d as usize);
                if l.col[a] == l.col[c]
                    && l.col[b] == l.col[d]
                    && ((l.row[a] < l.row[c] && l.row[b] > l.row[d])
                        || (l.row[a] > l.row[c] && l.row[b] < l.row[d]))
                {
                    expected += 1;
                }
            }
        }
        assert_eq!(crossings(&l, &edges), expected);
    }
}

#[test]
fn a_hundred_thousand_deep_chain_is_iterative() {
    let edges: Vec<_> = (1..100_000).map(|i| (i - 1, i)).collect();
    for align in [Align::Sources, Align::Sinks] {
        let (col, cyclic) = ranks(100_000, &edges, align);
        assert!(!cyclic);
        assert!(col.iter().enumerate().all(|(i, &c)| c as usize == i));
    }
}

#[test]
fn a_hundred_thousand_nodes_and_two_hundred_thousand_edges_fit_the_budget() {
    let edges = dag(100_000, 200_000, 7);
    let start = std::time::Instant::now();
    let layout = layered(100_000, &edges, LayeredOpts::default());
    let elapsed = start.elapsed();
    assert_eq!(layout.col.len(), 100_000);
    assert!(!layout.cyclic);
    assert!(
        elapsed.as_secs_f64() < if cfg!(debug_assertions) { 30.0 } else { 3.0 },
        "{elapsed:?}"
    );
    eprintln!("core layered 100k / 200k: {elapsed:?}");
}

#[test]
fn cyclic_layout_never_invents_extra_columns() {
    for align in [Align::Sources, Align::Sinks] {
        for (n, edges) in [
            (1, vec![(0, 0)]),
            (2, vec![(0, 1), (1, 0)]),
            (4, vec![(0, 1), (1, 2), (2, 0), (2, 3)]),
        ] {
            let (col, cyclic) = ranks(n, &edges, align);
            assert!(cyclic);
            assert!(col.iter().all(|&c| (c as usize) < n), "{col:?}");
        }
    }
}