notescraft/crates/graph/tests/layout.rs

//! Integration tests for the public API of `notescraft-graph`.

use notescraft_graph::{Error, Graph, Layout, LayoutConfig, components, degrees, layout, local_graph, orphans};

/// A short config so the tests stay fast; the physics is unchanged.
fn config(seed: u64) -> LayoutConfig {
    LayoutConfig { iterations: 40, seed, ..LayoutConfig::default() }
}

fn chain(n: usize) -> Graph {
    let edges = (1..n).map(|i| (i - 1, i)).collect();
    Graph::new(n, edges).expect("chain graph is valid")
}

fn all_finite(positions: &[[f32; 2]]) -> bool {
    positions.iter().all(|p| p[0].is_finite() && p[1].is_finite())
}

fn bits(positions: &[[f32; 2]]) -> Vec<[u32; 2]> {
    positions.iter().map(|p| [p[0].to_bits(), p[1].to_bits()]).collect()
}

// ---------------------------------------------------------------- determinism

#[test]
fn same_seed_gives_bit_identical_output() {
    let g = chain(60);
    let a = layout(&g, &config(1234));
    let b = layout(&g, &config(1234));
    assert_eq!(bits(&a), bits(&b));
}

#[test]
fn different_seeds_give_different_output() {
    let g = chain(60);
    let a = layout(&g, &config(1));
    let b = layout(&g, &config(2));
    assert_ne!(bits(&a), bits(&b));
}

#[test]
fn stepping_manually_matches_run_to_completion() {
    let g = chain(30);
    let cfg = config(77);
    let done = layout(&g, &cfg);
    let mut stepper = Layout::new(&g, &cfg);
    let mut last = 1.0;
    for _ in 0..cfg.iterations {
        last = stepper.step();
    }
    assert!(last >= 0.0);
    assert_eq!(bits(&done), bits(stepper.positions()));
    assert_eq!(stepper.step(), 0.0, "an exhausted layout reports no energy");
}

#[test]
fn energy_decreases_over_time() {
    let g = chain(50);
    let mut l = Layout::new(&g, &config(9));
    let first = l.step();
    for _ in 0..20 {
        l.step();
    }
    let last = l.step();
    assert!(first >= 0.0 && last >= 0.0);
    assert!(last <= first, "energy must not grow: {last} > {first}");
}

// ------------------------------------------------------------ degenerate input

#[test]
fn no_nan_on_degenerate_inputs() {
    let hub_edges: Vec<(usize, usize)> = (1..=200).map(|i| (0, i)).collect();
    let disconnected = Graph::new(8, vec![(0, 1), (1, 2), (5, 6), (6, 7)]).expect("valid");
    let dupes = Graph::new(4, vec![(0, 1), (1, 0), (0, 1), (1, 1), (2, 3)]).expect("valid");

    for g in [
        Graph::new(0, vec![]).expect("valid"),
        Graph::new(1, vec![]).expect("valid"),
        Graph::new(1, vec![(0, 0)]).expect("valid"),
        Graph::new(201, hub_edges).expect("valid"),
        disconnected,
        dupes,
        chain(3),
    ] {
        let positions = layout(&g, &config(5));
        assert_eq!(positions.len(), g.node_count());
        assert!(all_finite(&positions), "non-finite position for {:?}", g.edges());
    }
}

#[test]
fn no_nan_with_hostile_config() {
    let g = chain(10);
    for cfg in [
        LayoutConfig { area: f32::NAN, ..config(1) },
        LayoutConfig { area: -1.0, ..config(1) },
        LayoutConfig { area: f32::INFINITY, ..config(1) },
        LayoutConfig { repulsion: f32::NAN, ..config(1) },
        LayoutConfig { attraction: f32::INFINITY, ..config(1) },
        LayoutConfig { gravity: f32::NAN, ..config(1) },
        LayoutConfig { cooling: 0.0, ..config(1) },
        LayoutConfig { cooling: 1.5, ..config(1) },
        LayoutConfig { iterations: 0, ..config(1) },
    ] {
        assert!(all_finite(&layout(&g, &cfg)));
    }
}

// ---------------------------------------------------------------- pinning

#[test]
fn pinned_nodes_never_move() {
    let g = chain(20);
    let pinned_pos = [12.5_f32, -3.25];
    let cfg = LayoutConfig { pinned: vec![(3, pinned_pos), (7, [-1.0, 1.0])], ..config(3) };
    let positions = layout(&g, &cfg);
    assert_eq!(positions[3], pinned_pos);
    assert_eq!(positions[7], [-1.0, 1.0]);
}

#[test]
fn pin_unpin_and_set_position() {
    let g = chain(10);
    let mut l = Layout::new(&g, &config(11));
    l.pin(2, [5.0, 5.0]).expect("node 2 exists");
    l.step();
    assert_eq!(l.positions()[2], [5.0, 5.0]);
    l.step();
    assert_eq!(l.positions()[2], [5.0, 5.0]);

    l.unpin(2).expect("node 2 exists");
    l.step();
    assert_ne!(l.positions()[2], [5.0, 5.0]);

    l.set_position(4, [1.0, 2.0]).expect("node 4 exists");
    assert_eq!(l.positions()[4], [1.0, 2.0]);

    assert!(matches!(l.pin(99, [0.0, 0.0]), Err(Error::NodeOutOfRange { .. })));
    assert!(matches!(l.unpin(99), Err(Error::NodeOutOfRange { .. })));
    assert!(matches!(l.set_position(99, [0.0, 0.0]), Err(Error::NodeOutOfRange { .. })));
}

// ---------------------------------------------------------------- graph

#[test]
fn graph_drops_self_loops_and_duplicates() {
    let g = Graph::new(4, vec![(0, 0), (0, 1), (1, 0), (0, 1), (2, 3), (3, 2)]).expect("valid");
    assert_eq!(g.node_count(), 4);
    assert_eq!(g.edges(), &[(0, 1), (2, 3)]);
}

#[test]
fn graph_rejects_out_of_range_edges() {
    assert!(matches!(Graph::new(3, vec![(0, 3)]), Err(Error::EdgeOutOfRange { from: 0, to: 3, count: 3 })));
    assert!(matches!(Graph::new(0, vec![(0, 0)]), Err(Error::EdgeOutOfRange { .. })));
}

#[test]
fn graph_caps_node_count() {
    assert!(matches!(Graph::new(200_001, vec![]), Err(Error::TooManyNodes { .. })));
    assert!(Graph::new(200_000, vec![]).is_ok());
}

#[test]
fn graph_caps_edge_count() {
    let edges = vec![(0usize, 1usize); 8_000_001];
    assert!(matches!(Graph::new(4, edges), Err(Error::TooManyEdges { .. })));
}

#[test]
fn degrees_and_orphans() {
    let g = Graph::new(6, vec![(0, 1), (1, 2), (2, 0), (3, 1)]).expect("valid");
    assert_eq!(degrees(&g), vec![2, 3, 2, 1, 0, 0]);
    assert_eq!(orphans(&g), vec![4, 5]);
    assert_eq!(degrees(&Graph::new(0, vec![]).expect("valid")), Vec::<u32>::new());
    assert_eq!(orphans(&Graph::new(0, vec![]).expect("valid")), Vec::<usize>::new());
}

#[test]
fn components_labels_each_connected_component() {
    let g = Graph::new(7, vec![(0, 1), (1, 2), (3, 4)]).expect("valid");
    assert_eq!(components(&g), vec![0, 0, 0, 1, 1, 2, 3]);
    assert_eq!(components(&Graph::new(0, vec![]).expect("valid")), Vec::<usize>::new());
    let single = Graph::new(1, vec![]).expect("valid");
    assert_eq!(components(&single), vec![0]);
}

// ---------------------------------------------------------------- local graph

fn sample() -> Graph {
    // 0-1-2-3-4 chain, 5 isolated, 6-7 pair.
    Graph::new(8, vec![(0, 1), (1, 2), (2, 3), (3, 4), (6, 7)]).expect("valid")
}

#[test]
fn local_graph_depth_limits_the_neighbourhood() {
    let g = sample();

    let (d1, ids1) = local_graph(&g, 0, 1);
    assert_eq!(ids1, vec![0, 1]);
    assert_eq!(d1.node_count(), 2);
    assert_eq!(d1.edges(), &[(0, 1)]);

    let (d2, ids2) = local_graph(&g, 0, 2);
    assert_eq!(ids2, vec![0, 1, 2]);
    assert_eq!(d2.edges(), &[(0, 1), (1, 2)]);

    let (d3, ids3) = local_graph(&g, 2, 3);
    assert_eq!(ids3, vec![2, 1, 3, 0, 4]);
    assert_eq!(d3.node_count(), 5);
    // edges are remapped into BFS discovery order and keep the original order
    assert_eq!(d3.edges(), &[(3, 1), (1, 0), (0, 2), (2, 4)]);
}

#[test]
fn local_graph_depth_zero_is_just_the_centre() {
    let (g, ids) = local_graph(&sample(), 3, 0);
    assert_eq!(ids, vec![3]);
    assert_eq!(g.node_count(), 1);
    assert_eq!(g.edges(), []);
}

#[test]
fn local_graph_isolated_centre_and_bad_centre() {
    let (g, ids) = local_graph(&sample(), 5, 3);
    assert_eq!(ids, vec![5]);
    assert_eq!(g.edges(), []);

    let (g, ids) = local_graph(&sample(), 99, 3);
    assert_eq!(g.node_count(), 0);
    assert_eq!(ids, [] as [usize; 0]);
}

#[test]
fn local_graph_depth_is_capped_and_lays_out() {
    let g = chain(200);
    let (sub, ids) = local_graph(&g, 0, usize::MAX);
    assert_eq!(ids.len(), sub.node_count());
    assert!(sub.node_count() <= g.node_count());
    assert!(all_finite(&layout(&sub, &config(2))));
}

// ---------------------------------------------------------------- quality

#[test]
fn edges_end_up_closer_than_random_pairs() {
    // A binary tree: leaves hang off their parent, so linked nodes must settle
    // closer together than unrelated ones.
    let n = 200;
    let edges: Vec<(usize, usize)> = (1..n).map(|i| (i / 2, i)).collect();
    let g = Graph::new(n, edges).expect("valid");
    let p = layout(&g, &LayoutConfig::default());

    let distance = |a: [f32; 2], b: [f32; 2]| (a[0] - b[0]).hypot(a[1] - b[1]);
    let linked: f32 = g.edges().iter().map(|&(a, b)| distance(p[a], p[b])).sum();
    let mut pairs = Vec::new();
    for i in 0..n {
        for j in (i + 1)..n {
            pairs.push(distance(p[i], p[j]));
        }
    }
    let count = |v: usize| f32::from(u16::try_from(v).expect("small enough here"));
    let mean_all = pairs.iter().sum::<f32>() / count(pairs.len());
    assert!(linked / count(g.edges().len()) < mean_all * 0.8, "linked nodes must be closer than the average pair");
}

// ---------------------------------------------------------------- performance

#[test]
#[ignore = "performance budget; run with: cargo test -p notescraft-graph --release -- --ignored"]
fn five_thousand_nodes_lay_out_under_two_seconds() {
    const N: usize = 5000;
    const M: usize = 15000;
    let mut state: u64 = 0x2545_f491_4f6c_dd1d;
    let mut next = move || {
        state ^= state << 13;
        state ^= state >> 7;
        state ^= state << 17;
        state
    };
    let bound = u64::try_from(N).expect("node count fits");
    let mut edges = Vec::with_capacity(M);
    for _ in 0..M {
        let a = usize::try_from(next() % bound).expect("in range");
        let mut b = usize::try_from(next() % bound).expect("in range");
        if a == b {
            b = (b + 1) % N;
        }
        edges.push((a, b));
    }
    let g = Graph::new(N, edges).expect("random graph is in range");

    let started = std::time::Instant::now();
    let positions = layout(&g, &LayoutConfig::default());
    let elapsed = started.elapsed();

    eprintln!("layout: {} nodes, {} edges, {} iterations -> {elapsed:?}", g.node_count(), g.edges().len(), LayoutConfig::default().iterations);
    assert_eq!(positions.len(), N);
    assert!(all_finite(&positions));
    assert!(elapsed.as_secs_f64() < 2.0, "layout took {elapsed:?}, budget is 2 s");
}