crates/mimir-graph/tests/prop_bfs.rs
//! Property test: the GraphBLAS ops agree with plain Rust graph code on
//! random graphs of 1e3–1e4 nodes.
use std::collections::VecDeque;
use mimir_graph::{Matrix, Vector, ops};
use proptest::prelude::*;
#[derive(Debug)]
struct Graph {
n: usize,
edges: Vec<(u64, u64)>,
}
fn adj(n: usize, edges: &[(u64, u64)], reverse: bool) -> Vec<Vec<usize>> {
let mut a = vec![Vec::new(); n];
for &(u, v) in edges {
if reverse {
a[v as usize].push(u as usize);
} else {
a[u as usize].push(v as usize);
}
}
a
}
/// Plain BFS distances from many seeds, bounded.
fn bfs(adj: &[Vec<usize>], seeds: &[u64], max_hops: Option<u32>) -> Vec<Option<u64>> {
let mut d = vec![None; adj.len()];
let mut q = VecDeque::new();
for &s in seeds {
if d[s as usize].is_none() {
d[s as usize] = Some(0);
q.push_back(s as usize);
}
}
while let Some(u) = q.pop_front() {
let du = d[u].unwrap();
if max_hops.is_some_and(|h| du >= h as u64) {
continue;
}
for &v in &adj[u] {
if d[v].is_none() {
d[v] = Some(du + 1);
q.push_back(v);
}
}
}
d
}
fn find(p: &mut [usize], x: usize) -> usize {
let mut r = x;
while p[r] != r {
r = p[r];
}
let mut x = x;
while p[x] != r {
let nx = p[x];
p[x] = r;
x = nx;
}
r
}
fn arb_graph() -> impl Strategy<Value = (Graph, Vec<u64>, Option<u32>)> {
(1_000usize..10_000, 0.5f64..4.0).prop_flat_map(|(n, deg)| {
let m = (n as f64 * deg) as usize;
(
prop::collection::vec((0..n as u64, 0..n as u64), m),
prop::collection::vec(0..n as u64, 1..20),
prop::option::of(1u32..6),
)
.prop_map(move |(edges, seeds, hops)| (Graph { n, edges }, seeds, hops))
})
}
proptest! {
#![proptest_config(ProptestConfig { cases: 24, ..ProptestConfig::default() })]
#[test]
fn ops_match_plain_rust((gr, seeds, hops) in arb_graph()) {
let n = gr.n as u64;
let (r, c): (Vec<u64>, Vec<u64>) = gr.edges.iter().copied().unzip();
let a = Matrix::<bool>::from_edges(n, n, &r, &c).unwrap();
let s = Vector::<bool>::from_indices(n, &seeds).unwrap();
let fwd = adj(gr.n, &gr.edges, false);
let rev = adj(gr.n, &gr.edges, true);
for h in [None, hops] {
let want: Vec<u64> = bfs(&fwd, &seeds, h).iter().enumerate().filter_map(|(i, d)| d.map(|_| i as u64)).collect();
prop_assert_eq!(ops::reach(&s, &a, h).unwrap().indices().unwrap(), want);
let want_rev: Vec<u64> = bfs(&rev, &seeds, h).iter().enumerate().filter_map(|(i, d)| d.map(|_| i as u64)).collect();
prop_assert_eq!(ops::reverse_reach(&s, &a, h).unwrap().indices().unwrap(), want_rev);
let want_d: Vec<(u64, u64)> = bfs(&fwd, &seeds, h).iter().enumerate().filter_map(|(i, d)| d.map(|d| (i as u64, d))).collect();
let (i, x) = ops::min_hops(&s, &a, h).unwrap().to_tuples().unwrap();
prop_assert_eq!(i.into_iter().zip(x).collect::<Vec<_>>(), want_d);
}
// fan-out / fan-in on the de-duplicated edge set
let mut uniq = gr.edges.clone();
uniq.sort_unstable();
uniq.dedup();
let mut outd = vec![0u64; gr.n];
let mut ind = vec![0u64; gr.n];
for &(u, v) in &uniq { outd[u as usize] += 1; ind[v as usize] += 1; }
let dense = |v: Vector<u64>| { let mut d = vec![0u64; gr.n]; let (i, x) = v.to_tuples().unwrap(); for (i, x) in i.into_iter().zip(x) { d[i as usize] = x; } d };
prop_assert_eq!(dense(ops::fan_out(&a).unwrap()), outd);
prop_assert_eq!(dense(ops::fan_in(&a).unwrap()), ind);
// weakly connected components vs union-find (label = min id)
let mut p: Vec<usize> = (0..gr.n).collect();
for &(u, v) in &gr.edges {
let (ru, rv) = (find(&mut p, u as usize), find(&mut p, v as usize));
if ru != rv { let (lo, hi) = if ru < rv { (ru, rv) } else { (rv, ru) }; p[hi] = lo; }
}
let want_cc: Vec<u64> = (0..gr.n).map(|i| find(&mut p, i) as u64).collect();
prop_assert_eq!(ops::components(&a).unwrap().to_tuples().unwrap().1, want_cc);
// CSR import of the same graph agrees with the tuple build
let mut off = vec![0u64; gr.n + 1];
for &(u, _) in &uniq { off[u as usize + 1] += 1; }
for i in 0..gr.n { off[i + 1] += off[i]; }
let cols: Vec<u64> = uniq.iter().map(|e| e.1).collect();
let b = Matrix::<bool>::from_csr(n, n, &off, &cols, None).unwrap();
prop_assert_eq!(b.edges().unwrap(), uniq);
}
/// Many single-seed walks as ONE frontier matrix: row i = the walk from
/// seeds[i], identical to that seed's own `reach`, for every batch size.
#[test]
fn reach_each_is_each_seeds_own_walk((gr, seeds, hops) in arb_graph()) {
let n = gr.n as u64;
let (r, c): (Vec<u64>, Vec<u64>) = gr.edges.iter().copied().unzip();
let a = Matrix::<bool>::from_edges(n, n, &r, &c).unwrap();
let at = a.transpose().unwrap();
// a repeated seed keeps its own row
let mut seeds = seeds;
seeds.push(seeds[0]);
for h in [None, hops] {
for m in [&a, &at] {
let want: Vec<Vec<u64>> = seeds.iter().map(|s| ops::reach(&Vector::<bool>::from_indices(n, &[*s]).unwrap(), m, h).unwrap().indices().unwrap()).collect();
for batch in [1usize, 3, 64] {
prop_assert_eq!(&ops::reach_each(&seeds, m, h, batch).unwrap(), &want);
}
}
}
}
/// Seed SETS per row: row i = the walk from all of sets[i] at once.
#[test]
fn reach_sets_is_each_sets_own_walk((gr, seeds, hops) in arb_graph()) {
let n = gr.n as u64;
let (r, c): (Vec<u64>, Vec<u64>) = gr.edges.iter().copied().unzip();
let a = Matrix::<bool>::from_edges(n, n, &r, &c).unwrap();
let mut sets: Vec<Vec<u64>> = seeds.chunks(3).map(<[u64]>::to_vec).collect();
sets.push(Vec::new());
sets.push(seeds.clone());
let refs: Vec<&[u64]> = sets.iter().map(Vec::as_slice).collect();
for h in [None, hops] {
let want: Vec<Vec<u64>> = sets.iter().map(|s| ops::reach(&Vector::<bool>::from_indices(n, s).unwrap(), &a, h).unwrap().indices().unwrap()).collect();
for batch in [1usize, 2, 64] {
prop_assert_eq!(&ops::reach_sets(&refs, &a, h, batch).unwrap(), &want);
}
}
}
}