crates/mimir-graph/tests/ops.rs
//! Every op on tiny hand-made graphs with known answers.
use std::sync::Arc;
use arrow_array::{ArrayRef, Int64Array, RecordBatch, UInt64Array};
use mimir_graph::arrow::{ImportPath, from_arrow_edge_batches, from_arrow_edges};
use mimir_graph::{Error, Matrix, Vector, ops, runtime};
fn g(n: u64, edges: &[(u64, u64)]) -> Matrix<bool> {
let (r, c): (Vec<u64>, Vec<u64>) = edges.iter().copied().unzip();
Matrix::<bool>::from_edges(n, n, &r, &c).unwrap()
}
fn seeds(n: u64, s: &[u64]) -> Vector<bool> {
Vector::<bool>::from_indices(n, s).unwrap()
}
fn idx(v: &Vector<bool>) -> Vec<u64> {
v.indices().unwrap()
}
fn tup(v: &Vector<u64>) -> Vec<(u64, u64)> {
let (i, x) = v.to_tuples().unwrap();
i.into_iter().zip(x).collect()
}
const CHAIN: &[(u64, u64)] = &[(0, 1), (1, 2), (2, 3), (3, 4)];
const DIAMOND: &[(u64, u64)] = &[(0, 1), (0, 2), (1, 3), (2, 3)];
const CYCLE: &[(u64, u64)] = &[(0, 1), (1, 2), (2, 0)];
const TWO: &[(u64, u64)] = &[(0, 1), (2, 1), (4, 3)];
#[test]
fn runtime_version_and_threads() {
let (major, _, _) = runtime::library_version().unwrap();
assert_eq!(major, runtime::EXPECTED_MAJOR);
runtime::set_threads(3).unwrap();
assert_eq!(runtime::threads().unwrap(), 3);
assert!(runtime::set_threads(0).is_err());
}
#[test]
fn reach_chain_bounded_and_unbounded() {
let a = g(5, CHAIN);
assert_eq!(
idx(&ops::reach(&seeds(5, &[0]), &a, None).unwrap()),
vec![0, 1, 2, 3, 4]
);
assert_eq!(
idx(&ops::reach(&seeds(5, &[0]), &a, Some(2)).unwrap()),
vec![0, 1, 2]
);
assert_eq!(
idx(&ops::reach(&seeds(5, &[0]), &a, Some(0)).unwrap()),
vec![0]
);
assert_eq!(
idx(&ops::reach(&seeds(5, &[4]), &a, None).unwrap()),
vec![4]
);
}
#[test]
fn reverse_reach_chain_and_diamond() {
let a = g(5, CHAIN);
assert_eq!(
idx(&ops::reverse_reach(&seeds(5, &[4]), &a, None).unwrap()),
vec![0, 1, 2, 3, 4]
);
assert_eq!(
idx(&ops::reverse_reach(&seeds(5, &[2]), &a, Some(1)).unwrap()),
vec![1, 2]
);
let d = g(4, DIAMOND);
assert_eq!(
idx(&ops::reverse_reach(&seeds(4, &[3]), &d, None).unwrap()),
vec![0, 1, 2, 3]
);
assert_eq!(
idx(&ops::reverse_reach(&seeds(4, &[1]), &d, None).unwrap()),
vec![0, 1]
);
// same answer as forward reach on the materialised transpose
let dt = d.transpose().unwrap();
assert_eq!(
idx(&ops::reach(&seeds(4, &[3]), &dt, None).unwrap()),
vec![0, 1, 2, 3]
);
}
#[test]
fn reach_cycle_terminates() {
let a = g(3, CYCLE);
assert_eq!(
idx(&ops::reach(&seeds(3, &[1]), &a, None).unwrap()),
vec![0, 1, 2]
);
assert_eq!(
idx(&ops::reverse_reach(&seeds(3, &[1]), &a, None).unwrap()),
vec![0, 1, 2]
);
}
#[test]
fn unreachable_node_stays_out() {
// diamond plus isolated 4 and a node 5 that only points INTO the diamond
let mut e = DIAMOND.to_vec();
e.push((5, 3));
let a = g(6, &e);
assert_eq!(
idx(&ops::reach(&seeds(6, &[0]), &a, None).unwrap()),
vec![0, 1, 2, 3]
);
assert_eq!(
idx(&ops::reverse_reach(&seeds(6, &[3]), &a, None).unwrap()),
vec![0, 1, 2, 3, 5]
);
let h = ops::min_hops(&seeds(6, &[0]), &a, None).unwrap();
assert_eq!(h.get(4).unwrap(), None);
assert_eq!(h.get(5).unwrap(), None);
}
#[test]
fn many_seeds_at_once() {
let a = g(5, TWO);
assert_eq!(
idx(&ops::reach(&seeds(5, &[0, 4]), &a, None).unwrap()),
vec![0, 1, 3, 4]
);
assert_eq!(
idx(&ops::reverse_reach(&seeds(5, &[1, 3]), &a, None).unwrap()),
vec![0, 1, 2, 3, 4]
);
}
#[test]
fn fan_in_fan_out_diamond() {
let a = g(4, DIAMOND);
assert_eq!(
tup(&ops::fan_out(&a).unwrap()),
vec![(0, 2), (1, 1), (2, 1)]
);
assert_eq!(tup(&ops::fan_in(&a).unwrap()), vec![(1, 1), (2, 1), (3, 2)]);
}
#[test]
fn min_hops_chain_diamond_multiseed() {
let a = g(5, CHAIN);
assert_eq!(
tup(&ops::min_hops(&seeds(5, &[0]), &a, None).unwrap()),
vec![(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
);
assert_eq!(
tup(&ops::min_hops(&seeds(5, &[0, 3]), &a, None).unwrap()),
vec![(0, 0), (1, 1), (2, 2), (3, 0), (4, 1)]
);
assert_eq!(
tup(&ops::min_hops(&seeds(5, &[0]), &a, Some(2)).unwrap()),
vec![(0, 0), (1, 1), (2, 2)]
);
let d = g(4, DIAMOND);
assert_eq!(
tup(&ops::min_hops(&seeds(4, &[0]), &d, None).unwrap()),
vec![(0, 0), (1, 1), (2, 1), (3, 2)]
);
// shortcut wins over the long way round
let s = g(4, &[(0, 1), (1, 2), (2, 3), (0, 3)]);
assert_eq!(
ops::min_hops(&seeds(4, &[0]), &s, None)
.unwrap()
.get(3)
.unwrap(),
Some(1)
);
let c = g(3, CYCLE);
assert_eq!(
tup(&ops::min_hops(&seeds(3, &[2]), &c, None).unwrap()),
vec![(0, 1), (1, 2), (2, 0)]
);
}
#[test]
fn max_on_path_chain_cycle_and_zero() {
let a = g(5, CHAIN);
let v = Vector::<u64>::from_tuples(5, &[2, 4], &[5, 3]).unwrap();
assert_eq!(
tup(&ops::max_on_path(&a, &v).unwrap()),
vec![(0, 5), (1, 5), (2, 5), (3, 3), (4, 3)]
);
let c = g(4, CYCLE); // node 3 isolated, no value
let v = Vector::<u64>::from_tuples(4, &[0], &[7]).unwrap();
assert_eq!(
tup(&ops::max_on_path(&c, &v).unwrap()),
vec![(0, 7), (1, 7), (2, 7)]
);
// a value of 0 still propagates as a present value
let v = Vector::<u64>::from_tuples(5, &[3], &[0]).unwrap();
assert_eq!(
tup(&ops::max_on_path(&a, &v).unwrap()),
vec![(0, 0), (1, 0), (2, 0), (3, 0)]
);
let d = g(4, DIAMOND);
let v = Vector::<u64>::from_tuples(4, &[1, 2, 3], &[9, 2, 4]).unwrap();
assert_eq!(
tup(&ops::max_on_path(&d, &v).unwrap()),
vec![(0, 9), (1, 9), (2, 4), (3, 4)]
);
}
/// (max, min) over node weights: known answers, then a reference check.
#[test]
fn bottleneck_is_the_best_weakest_hop() {
// chain 0→1→2→3→4, weights 9 5 7 2 8: every hop can only lower the value
let a = g(5, CHAIN);
let w = Vector::<u64>::from_dense(&[9, 5, 7, 2, 8]).unwrap();
assert_eq!(
tup(&ops::bottleneck(&seeds(5, &[0]), &a, &w).unwrap()),
vec![(0, 9), (1, 5), (2, 5), (3, 2), (4, 2)]
);
// a seed further down starts from its own weight; upstream is not reached
assert_eq!(
tup(&ops::bottleneck(&seeds(5, &[2]), &a, &w).unwrap()),
vec![(2, 7), (3, 2), (4, 2)]
);
// diamond 0→{1,2}→3: the better of the two routes wins (max over paths)
let d = g(4, DIAMOND);
let w = Vector::<u64>::from_dense(&[10, 3, 6, 8]).unwrap();
assert_eq!(
tup(&ops::bottleneck(&seeds(4, &[0]), &d, &w).unwrap()),
vec![(0, 10), (1, 3), (2, 6), (3, 6)],
"3 through 2 (6), not through 1 (3)"
);
// a cycle converges; an isolated node stays absent
let c = g(4, CYCLE);
let w = Vector::<u64>::from_dense(&[4, 9, 6, 1]).unwrap();
assert_eq!(
tup(&ops::bottleneck(&seeds(4, &[1]), &c, &w).unwrap()),
vec![(0, 4), (1, 9), (2, 6)]
);
// a node without a weight cannot be passed: 0→1→2 with 1 unweighted
let a = g(3, &[(0, 1), (1, 2)]);
let w = Vector::<u64>::from_tuples(3, &[0, 2], &[5, 5]).unwrap();
assert_eq!(
tup(&ops::bottleneck(&seeds(3, &[0]), &a, &w).unwrap()),
vec![(0, 5)]
);
// a late better route RAISES an already reached node and its successors:
// 0→3 direct (seed 0 weight 2), and 1→2→3 from seed 1 (weight 9, 2 = 8)
let a = g(5, &[(0, 3), (1, 2), (2, 3), (3, 4)]);
let w = Vector::<u64>::from_dense(&[2, 9, 8, 7, 6]).unwrap();
assert_eq!(
tup(&ops::bottleneck(&seeds(5, &[0, 1]), &a, &w).unwrap()),
vec![(0, 2), (1, 9), (2, 8), (3, 7), (4, 6)]
);
assert!(ops::bottleneck(&seeds(4, &[0]), &a, &w).is_err(), "seed size");
}
/// Reference: widest-path relaxation to a fixpoint in plain Rust.
#[test]
fn bottleneck_matches_a_plain_relaxation_on_random_graphs() {
let mut x = 0x9e37_79b9_7f4a_7c15u64;
let mut rnd = move |m: u64| {
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
x % m
};
for round in 0..40 {
let n = 2 + rnd(30);
let m = rnd(4 * n);
let mut edges: Vec<(u64, u64)> = (0..m).map(|_| (rnd(n), rnd(n))).collect();
edges.sort_unstable();
edges.dedup();
let w: Vec<u64> = (0..n).map(|_| rnd(6)).collect();
let s: Vec<u64> = (0..n).filter(|_| rnd(4) == 0).collect();
let mut want: Vec<Option<u64>> = vec![None; n as usize];
for i in &s {
want[*i as usize] = Some(w[*i as usize]);
}
loop {
let mut moved = false;
for (f, t) in &edges {
if let Some(v) = want[*f as usize] {
let c = v.min(w[*t as usize]);
if want[*t as usize].is_none_or(|old| c > old) {
want[*t as usize] = Some(c);
moved = true;
}
}
}
if !moved {
break;
}
}
let want: Vec<(u64, u64)> = want
.iter()
.enumerate()
.filter_map(|(i, v)| v.map(|v| (i as u64, v)))
.collect();
let got = ops::bottleneck(
&seeds(n, &s),
&g(n, &edges),
&Vector::<u64>::from_dense(&w).unwrap(),
)
.unwrap();
assert_eq!(tup(&got), want, "round {round}: n {n} edges {edges:?} w {w:?} seeds {s:?}");
}
}
#[test]
fn mask_by_keeps_inner_edges_only() {
let a = g(4, DIAMOND);
let m = ops::mask_by(&a, &seeds(4, &[0, 1, 3])).unwrap();
assert_eq!(m.edges().unwrap(), vec![(0, 1), (1, 3)]);
assert_eq!(m.nrows().unwrap(), 4);
let fo = ops::fan_out(&a).unwrap();
let scoped = ops::mask_vector(&fo, &seeds(4, &[0, 3])).unwrap();
assert_eq!(tup(&scoped), vec![(0, 2)]);
}
#[test]
fn similarity_diamond() {
let a = g(4, DIAMOND);
let c = ops::similarity(&a).unwrap();
assert_eq!(c.get(1, 2).unwrap(), Some(1)); // both call 3
assert_eq!(c.get(2, 1).unwrap(), Some(1));
assert_eq!(c.get(0, 0).unwrap(), Some(2)); // out-degree
assert_eq!(c.get(0, 1).unwrap(), None); // 0 → {1,2}, 1 → {3}: nothing shared
assert_eq!(c.get(3, 3).unwrap(), None);
}
#[test]
fn components_two_and_isolated() {
let a = g(5, TWO);
assert_eq!(
ops::components(&a).unwrap().to_tuples().unwrap().1,
vec![0, 0, 0, 3, 3]
);
// long reversed chain, labels must reach the far end; plus isolated node 6
let a = g(7, &[(5, 4), (4, 3), (3, 2), (2, 1), (1, 0)]);
assert_eq!(
ops::components(&a).unwrap().to_tuples().unwrap().1,
vec![0, 0, 0, 0, 0, 0, 6]
);
let c = g(3, CYCLE);
assert_eq!(
ops::components(&c).unwrap().to_tuples().unwrap().1,
vec![0, 0, 0]
);
}
#[test]
fn diff_two_snapshots() {
let x = g(5, CHAIN);
let y = g(5, &[(0, 1), (2, 3), (3, 4), (0, 4)]);
let (added, removed) = ops::diff(&x, &y).unwrap();
assert_eq!(added.edges().unwrap(), vec![(0, 4)]);
assert_eq!(removed.edges().unwrap(), vec![(1, 2)]);
let (a2, r2) = ops::diff(&x, &x).unwrap();
assert_eq!((a2.nvals().unwrap(), r2.nvals().unwrap()), (0, 0));
assert!(ops::diff(&x, &g(4, DIAMOND)).is_err());
}
#[test]
fn union_of_two_kinds() {
let a = g(5, &[(0, 1), (1, 2)]);
let b = g(5, &[(1, 2), (3, 4)]);
let u = ops::union(&a, &b).unwrap();
assert_eq!(u.edges().unwrap(), vec![(0, 1), (1, 2), (3, 4)]);
assert!(ops::union(&a, &g(4, &[])).is_err());
}
#[test]
fn mask_rows_keeps_out_edges_of_the_set() {
let a = g(4, DIAMOND);
let m = ops::mask_rows(&a, &seeds(4, &[1, 2])).unwrap();
assert_eq!(m.edges().unwrap(), vec![(1, 3), (2, 3)]);
}
#[test]
fn shape_errors_are_errors() {
let a = g(5, CHAIN);
assert!(matches!(
ops::reach(&seeds(4, &[0]), &a, None),
Err(Error::Invalid(_))
));
let rect = Matrix::<bool>::new(3, 4).unwrap();
assert!(ops::reach(&seeds(3, &[0]), &rect, None).is_err());
}
#[test]
fn csr_import_both_paths_agree() {
// diamond as CSR, row 0 jumbled on purpose
let off = [0u64, 2, 3, 4, 4];
let cols = [2u64, 1, 3, 3];
let p = Matrix::<bool>::from_csr(4, 4, &off, &cols, None).unwrap();
let i = Matrix::<bool>::from_csr_import(4, 4, &off, &cols, None).unwrap();
assert_eq!(p.edges().unwrap(), g(4, DIAMOND).edges().unwrap());
assert_eq!(i.edges().unwrap(), p.edges().unwrap());
// valued
let w = Matrix::<u64>::from_csr(4, 4, &off, &cols, Some(&[7, 8, 9, 10])).unwrap();
assert_eq!(w.get(0, 2).unwrap(), Some(7));
assert_eq!(w.get(2, 3).unwrap(), Some(10));
let f = Matrix::<f64>::from_csr(4, 4, &off, &cols, None).unwrap();
assert_eq!(f.get(1, 3).unwrap(), Some(1.0));
// empty graph
let e = Matrix::<bool>::from_csr(3, 3, &[0, 0, 0, 0], &[], None).unwrap();
assert_eq!(e.nvals().unwrap(), 0);
}
#[test]
fn csr_import_rejects_bad_input() {
let bad =
|off: &[u64], cols: &[u64]| Matrix::<bool>::from_csr(3, 3, off, cols, None).unwrap_err();
assert!(matches!(bad(&[0, 1, 2], &[0, 1]), Error::Invalid(_))); // short offsets
assert!(matches!(bad(&[1, 1, 2, 2], &[0, 1]), Error::Invalid(_))); // offsets[0] != 0
assert!(matches!(bad(&[0, 2, 1, 2], &[0, 1]), Error::Invalid(_))); // not monotone
assert!(matches!(bad(&[0, 1, 2, 3], &[0, 1]), Error::Invalid(_))); // last != nnz
assert!(matches!(bad(&[0, 1, 1, 1], &[3]), Error::Invalid(_))); // col out of range
assert!(matches!(bad(&[0, 2, 2, 2], &[1, 1]), Error::Invalid(_))); // duplicate in row
assert!(Matrix::<u64>::from_csr(3, 3, &[0, 1, 1, 1], &[0], Some(&[1, 2])).is_err());
}
fn batch(from: Vec<u64>, to: Vec<u64>) -> RecordBatch {
RecordBatch::try_from_iter([
("from_ord", Arc::new(UInt64Array::from(from)) as ArrayRef),
("to_ord", Arc::new(UInt64Array::from(to)) as ArrayRef),
])
.unwrap()
}
#[test]
fn arrow_paths() {
let want = g(4, DIAMOND).edges().unwrap();
let run = |b: &[RecordBatch]| {
let (m, p) = from_arrow_edge_batches(b, "from_ord", "to_ord", 4).unwrap();
(m.edges().unwrap(), p)
};
// sorted by (from, to)
assert_eq!(
run(&[batch(vec![0, 0, 1, 2], vec![1, 2, 3, 3])]),
(want.clone(), ImportPath::SortedPack)
);
// sorted by from only (row 0 jumbled)
assert_eq!(
run(&[batch(vec![0, 0, 1, 2], vec![2, 1, 3, 3])]),
(want.clone(), ImportPath::FromSortedPack)
);
// sorted by from but with a duplicate edge → build, duplicate collapses
assert_eq!(
run(&[batch(vec![0, 0, 0, 1, 2], vec![2, 1, 2, 3, 3])]),
(want.clone(), ImportPath::Build)
);
// unsorted
assert_eq!(
run(&[batch(vec![2, 0, 1, 0], vec![3, 2, 3, 1])]),
(want.clone(), ImportPath::Build)
);
// sorted across two batches
assert_eq!(
run(&[batch(vec![0, 0], vec![1, 2]), batch(vec![1, 2], vec![3, 3])]),
(want.clone(), ImportPath::SortedPack)
);
// unsorted across two batches
assert_eq!(
run(&[batch(vec![1, 2], vec![3, 3]), batch(vec![0, 0], vec![1, 2])]),
(want.clone(), ImportPath::Build)
);
// single-batch convenience
let m = from_arrow_edges(
&batch(vec![0, 0, 1, 2], vec![1, 2, 3, 3]),
"from_ord",
"to_ord",
4,
)
.unwrap();
assert_eq!(m.edges().unwrap(), want);
// empty
let (m, _) =
from_arrow_edge_batches(&[batch(vec![], vec![])], "from_ord", "to_ord", 4).unwrap();
assert_eq!(m.nvals().unwrap(), 0);
}
#[test]
fn arrow_rejects_bad_batches() {
let b = batch(vec![0, 5], vec![1, 2]);
assert!(matches!(
from_arrow_edges(&b, "from_ord", "to_ord", 4),
Err(Error::Invalid(_))
));
assert!(matches!(
from_arrow_edges(&b, "nope", "to_ord", 6),
Err(Error::Arrow(_))
));
let signed = RecordBatch::try_from_iter([
(
"from_ord",
Arc::new(Int64Array::from(vec![0i64])) as ArrayRef,
),
(
"to_ord",
Arc::new(UInt64Array::from(vec![1u64])) as ArrayRef,
),
])
.unwrap();
assert!(matches!(
from_arrow_edges(&signed, "from_ord", "to_ord", 4),
Err(Error::Arrow(_))
));
let nulls = RecordBatch::try_from_iter([
(
"from_ord",
Arc::new(UInt64Array::from(vec![Some(0u64), None])) as ArrayRef,
),
(
"to_ord",
Arc::new(UInt64Array::from(vec![1u64, 2])) as ArrayRef,
),
])
.unwrap();
assert!(matches!(
from_arrow_edges(&nulls, "from_ord", "to_ord", 4),
Err(Error::Arrow(_))
));
// out of range in an unsorted batch is caught too
let b = batch(vec![2, 0, 9], vec![1, 2, 0]);
assert!(from_arrow_edges(&b, "from_ord", "to_ord", 4).is_err());
}
/// One FastRP step: `y = A·x` over a weighted (row-normalised) adjacency is
/// the mean of the neighbours' values; a row without neighbours has none.
#[test]
fn propagate_is_the_weighted_neighbour_sum() {
// 0 → {1, 2} at ½ each, 1 → {2} at 1, 2 → nothing
let a = mimir_graph::Matrix::<f64>::from_csr(3, 3, &[0, 2, 3, 3], &[1, 2, 2], Some(&[0.5, 0.5, 1.0])).unwrap();
let x = mimir_graph::Vector::<f64>::from_dense(&[10.0, 2.0, 4.0]).unwrap();
let y = ops::propagate(&a, &x).unwrap();
assert_eq!(y.to_tuples().unwrap(), (vec![0, 1], vec![3.0, 4.0]));
let wrong = mimir_graph::Vector::<f64>::from_dense(&[1.0, 2.0]).unwrap();
assert!(ops::propagate(&a, &wrong).is_err());
}
/// **A nearly empty kind matrix costs edges, not nodes.** The room holds one
/// n×n matrix per edge kind; a kind with a handful of edges must not keep the
/// full CSR row-pointer array ((n+1)·8 bytes — 64 MB at 8 M nodes). After the
/// import the matrix conforms to hypersparse, and a filled matrix still
/// answers identically.
#[test]
fn a_nearly_empty_kind_matrix_costs_edges_not_nodes() {
let n: u64 = 8_000_000;
let edges: Vec<(u64, u64)> = (0..1000u64).map(|i| (i * 7919 % n, i * 104729 % n)).collect();
let mut sorted = edges.clone();
sorted.sort_unstable();
let (f, t): (Vec<u64>, Vec<u64>) = sorted.iter().copied().unzip();
let (m, path) = mimir_graph::arrow::from_edge_chunks(&[(&f[..], &t[..])], n).unwrap();
assert_eq!(path, ImportPath::SortedPack, "the fast path is still taken");
let bytes = m.memory_bytes().unwrap();
assert!(bytes < 4_000_000, "1000 edges over 8M nodes keep {bytes} bytes — the row pointers were not freed");
// the matrix still answers: the known from-node has its fan-out
let fo = ops::fan_out(&m).unwrap();
assert!(tup(&fo).iter().any(|&(i, c)| i == f[0] && c >= 1), "the hypersparse matrix answers as before");
}
#[test]
fn row_edges_is_the_row_filter_of_edges() {
let a = g(5, &[(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 0)]);
let all = a.edges().unwrap();
for rows in [vec![], vec![0], vec![1, 3], vec![0, 2, 4], vec![0, 1, 2, 3, 4]] {
let want: Vec<(u64, u64)> = all.iter().copied().filter(|(f, _)| rows.contains(f)).collect();
assert_eq!(a.row_edges(&rows).unwrap(), want, "{rows:?}");
}
}
#[test]
fn min_hops_to_stops_at_the_first_layer_holding_a_target() {
let a = g(6, &[(0, 1), (1, 2), (2, 3), (3, 4), (0, 5), (5, 3)]);
let full = tup(&ops::min_hops(&seeds(6, &[0]), &a, None).unwrap());
// nearest target at hop 2 (node 2): everything up to hop 2 as min_hops says, nothing past it
let near = tup(&ops::min_hops_to(&seeds(6, &[0]), &a, None, &[4, 2]).unwrap());
let want: Vec<(u64, u64)> = full.iter().copied().filter(|(_, d)| *d <= 2).collect();
assert_eq!(near, want);
// a seed that is a target: the zero-hop answer
assert_eq!(tup(&ops::min_hops_to(&seeds(6, &[0]), &a, None, &[0]).unwrap()), vec![(0, 0)]);
// no target reachable: the whole walk
assert_eq!(tup(&ops::min_hops_to(&seeds(6, &[3]), &a, None, &[0]).unwrap()), tup(&ops::min_hops(&seeds(6, &[3]), &a, None).unwrap()));
}