bixverse-rs 0.7.0

//! Implementations to generate shared nearest-neighbour graphs from kNN graphs.

use rayon::prelude::*;
use std::time::Instant;

use crate::graph::graph_structures::{UnionFind, edge_pairs_to_sparse_graph};
use crate::prelude::*;

///////////
// Enums //
///////////

/// SNN similarity method
#[derive(Clone, Copy, Default, Debug)]
pub enum SnnSimilarityMethod {
    /// This will calculate the Jaccard similarity as weight
    #[default]
    Intersection,
    /// This will calculate the Rank version as a weight
    Rank,
}

/// Type of shared nearest neighbour graph to create
#[derive(Clone, Copy, Default, Debug)]
pub enum SnnType {
    /// Creates connections between nodes that share nearest neighbours
    #[default]
    FullConnection,
    /// Creates only connections between nodes that are also connected in the
    /// kNN graph
    LimitedConnection,
}

/// Helper function to get the type of sNN similarity
///
/// ### Params
///
/// * `s` - Type of SNN similarity to use
///
/// ### Returns
///
/// Option of the [SnnSimilarityMethod]
pub fn parse_snn_similiarity_method(s: &str) -> Option<SnnSimilarityMethod> {
    match s.to_lowercase().as_str() {
        "jaccard" => Some(SnnSimilarityMethod::Intersection),
        "rank" => Some(SnnSimilarityMethod::Rank),
        _ => None,
    }
}

/// Helper function to get the type of sNN graph construction
///
/// ### Params
///
/// * `s` - Type of sNN graph to create
///
/// ### Returns
///
/// Option of the [SnnType]
pub fn parse_snn_type(s: &str) -> Option<SnnType> {
    match s.to_lowercase().as_str() {
        "full" => Some(SnnType::FullConnection),
        "limited" => Some(SnnType::LimitedConnection),
        _ => None,
    }
}

/////////////
// Helpers //
/////////////

/// Transpose the column-major kNN indices into row-major, `k` per cell
///
/// ### Params
///
/// * `flat_knn` - kNN indices, column-major (`k` columns of `n_samples`).
/// * `k` - Number of neighbours per cell.
/// * `n_samples` - Number of cells.
///
/// ### Returns
///
/// Row-major indices, `k` per cell.
fn row_major_knn(flat_knn: &[usize], k: usize, n_samples: usize) -> Vec<usize> {
    let mut v = vec![0usize; n_samples * k];
    if k > 0 {
        v.par_chunks_mut(k).enumerate().for_each(|(i, row)| {
            for (nb, slot) in row.iter_mut().enumerate() {
                *slot = flat_knn[nb * n_samples + i];
            }
        });
    }
    v
}

/// sNN weight between two cells from their kNN rows
///
/// Builds the self-inclusive neighbour sets on the fly, so it is only meant
/// for the handful of pairs the component rescue looks at.
///
/// ### Params
///
/// * `knn_rm` - kNN indices, row-major, `k` per cell, self excluded
/// * `k` - Number of neighbours per cell
/// * `a` - First cell
/// * `b` - Second cell
/// * `method` - Which similarity method to use
///
/// ### Returns
///
/// The weight, identical to what `generate_snn_full` would assign the pair.
fn pair_snn_weight(
    knn_rm: &[usize],
    k: usize,
    a: usize,
    b: usize,
    method: SnnSimilarityMethod,
) -> f32 {
    let ranked = |c: usize| -> Vec<(usize, usize)> {
        let mut v: Vec<(usize, usize)> = std::iter::once((c, 0))
            .chain(
                knn_rm[c * k..(c + 1) * k]
                    .iter()
                    .enumerate()
                    .map(|(r, &nb)| (nb, r + 1)),
            )
            .collect();
        v.sort_unstable();
        v
    };
    let (sa, sb) = (ranked(a), ranked(b));

    let (mut pa, mut pb) = (0usize, 0usize);
    let mut count = 0usize;
    let mut min_combined = 2 * k;
    while pa < sa.len() && pb < sb.len() {
        match sa[pa].0.cmp(&sb[pb].0) {
            std::cmp::Ordering::Equal => {
                count += 1;
                min_combined = min_combined.min(sa[pa].1 + sb[pb].1);
                pa += 1;
                pb += 1;
            }
            std::cmp::Ordering::Less => pa += 1,
            std::cmp::Ordering::Greater => pb += 1,
        }
    }

    match method {
        SnnSimilarityMethod::Intersection => {
            let c = count as f32;
            c / (2.0 * (k as f32 + 1.0) - c)
        }
        SnnSimilarityMethod::Rank => (k as f32 - min_combined as f32 / 2.0).max(1e-6) / k as f32,
    }
}

/// Components below this size after pruning get reconnected
const MIN_COMPONENT_SIZE: usize = 10;

/// Reconnect the small components that pruning cut off
///
/// Leiden turns every disconnected component into its own cluster, and on
/// large data sets the default pruning leaves hundreds of them, mostly pairs
/// of cells that are each other's strongest neighbour. Every component below
/// [MIN_COMPONENT_SIZE] gets its strongest kNN edge to a node outside it,
/// repeated until none is left or the remaining ones have no kNN edge leaving
/// them. A kNN pair always shares at least one neighbour (the partner itself),
/// so the edge exists in the full and in the limited graph alike, pruning
/// aside.
///
/// ### Params
///
/// * `knn_rm` - kNN indices, row-major, `k` per cell, self excluded
/// * `k` - Number of neighbours per cell
/// * `n_samples` - Number of cells
/// * `method` - Which similarity method to use
/// * `edges` - Flat edge pairs after pruning; rescue edges are appended
/// * `weights` - Edge weights after pruning; rescue weights are appended
///
/// ### Returns
///
/// Number of rescue edges added.
fn rescue_small_components(
    knn_rm: &[usize],
    k: usize,
    n_samples: usize,
    method: SnnSimilarityMethod,
    edges: &mut Vec<usize>,
    weights: &mut Vec<f32>,
) -> usize {
    if k == 0 {
        return 0;
    }

    let mut uf = UnionFind::new(n_samples);
    for e in edges.chunks_exact(2) {
        uf.union(e[0] as u32, e[1] as u32);
    }

    let mut n_rescued = 0;
    loop {
        let roots: Vec<u32> = (0..n_samples as u32).map(|i| uf.find(i)).collect();
        let mut size = vec![0usize; n_samples];
        for &r in &roots {
            size[r as usize] += 1;
        }

        // (root, weight, node, partner); ties go to the closer neighbour
        let mut candidates: Vec<(u32, f32, usize, usize)> = (0..n_samples)
            .into_par_iter()
            .filter(|&i| size[roots[i] as usize] < MIN_COMPONENT_SIZE)
            .filter_map(|i| {
                knn_rm[i * k..(i + 1) * k]
                    .iter()
                    .filter(|&&nb| roots[nb] != roots[i])
                    .map(|&nb| (pair_snn_weight(knn_rm, k, i, nb, method), nb))
                    .fold(None, |acc: Option<(f32, usize)>, cur| match acc {
                        Some(a) if a.0 >= cur.0 => Some(a),
                        _ => Some(cur),
                    })
                    .map(|(w, nb)| (roots[i], w, i, nb))
            })
            .collect();

        candidates
            .sort_unstable_by(|a, b| a.0.cmp(&b.0).then(b.1.total_cmp(&a.1)).then(a.2.cmp(&b.2)));
        candidates.dedup_by_key(|c| c.0);

        let before = n_rescued;
        for (_, w, i, nb) in candidates {
            // two components can pick each other in the same round
            if uf.union(i as u32, nb as u32) {
                edges.push(i.min(nb));
                edges.push(i.max(nb));
                weights.push(w);
                n_rescued += 1;
            }
        }
        if n_rescued == before {
            break;
        }
    }

    n_rescued
}

///////////////////
// sNN functions //
///////////////////

/// Generate an sNN graph based on the kNN graph (full)
///
/// This version will compare all cells against all cells and generate an edge
/// if any neighbours are shared. This yields way denser graphs and is the
/// approach taken in the `bluster` R package to generate the sNN.
///
/// ### Params
///
/// * `knn_graph` - K-nearest neighbours data as a flat vector in column-major.
/// * `no_neighbours` - Number of neighbours in the kNN graph
/// * `pruning` - Below which Jaccard similarity to prune the edge. Components
///   that pruning leaves below ten cells are reconnected regardless, see
///   [rescue_small_components].
/// * `method` - Which similarity method to use
/// * `verbose` - If `0` -> silent or `1` for normal verbosity, `2` for detailed
///   verbosity.
///
/// ### Returns
///
/// A tuple with `(<edges>, <weights>)`. The edges are stored in a way that the
/// the first edge points goes from the first element to the second, the second
/// edge from the third to the fourth, etc.
pub fn generate_snn_full(
    flat_knn: &[usize],
    k: usize,
    n_samples: usize,
    pruning: f32,
    method: SnnSimilarityMethod,
    verbose: usize,
) -> (Vec<usize>, Vec<f32>) {
    let verbosity = parse_verbosity_level(verbose);

    let start_time = Instant::now();

    let knn_rm = row_major_knn(flat_knn, k, n_samples);

    // CSR of (cell, rank) per neighbour node, filled in cell order with each
    // cell's own entry ahead of its neighbour entries.
    let mut rev_ptr = vec![0usize; n_samples + 1];
    for node in 0..n_samples {
        rev_ptr[node + 1] += 1;
    }
    for &neighbor in flat_knn.iter().take(k * n_samples) {
        rev_ptr[neighbor + 1] += 1;
    }
    for node in 0..n_samples {
        rev_ptr[node + 1] += rev_ptr[node];
    }
    let mut reverse_flat = vec![(0usize, 0usize); rev_ptr[n_samples]];
    let mut cursor = rev_ptr.clone();
    for i in 0..n_samples {
        reverse_flat[cursor[i]] = (i, 0);
        cursor[i] += 1;
        for nb in 0..k {
            let neighbor = flat_knn[nb * n_samples + i];
            reverse_flat[cursor[neighbor]] = (i, nb + 1);
            cursor[neighbor] += 1;
        }
    }

    let results: Vec<(usize, usize, f32)> = (0..n_samples)
        .into_par_iter()
        .map_init(
            || (vec![0.0f32; n_samples], Vec::<usize>::with_capacity(64)),
            |(scores, added), j| {
                added.clear();

                for i in 0..=k {
                    let cur_neighbor = if i == 0 { j } else { knn_rm[j * k + (i - 1)] };

                    for &(othernode, other_rank) in
                        &reverse_flat[rev_ptr[cur_neighbor]..rev_ptr[cur_neighbor + 1]]
                    {
                        if othernode < j {
                            match method {
                                SnnSimilarityMethod::Rank => {
                                    let combined_rank = (i + other_rank) as f32;
                                    if scores[othernode] == 0.0 {
                                        scores[othernode] = combined_rank;
                                        added.push(othernode);
                                    } else if combined_rank < scores[othernode] {
                                        scores[othernode] = combined_rank;
                                    }
                                }
                                SnnSimilarityMethod::Intersection => {
                                    if scores[othernode] == 0.0 {
                                        added.push(othernode);
                                    }
                                    scores[othernode] += 1.0;
                                }
                            }
                        }
                    }
                }

                let out: Vec<(usize, usize, f32)> = added
                    .iter()
                    .filter_map(|&othernode| {
                        let weight = match method {
                            SnnSimilarityMethod::Rank => {
                                let preliminary = k as f32 - scores[othernode] / 2.0;
                                let raw_weight = preliminary.max(1e-6);
                                raw_weight / k as f32
                            }
                            SnnSimilarityMethod::Intersection => {
                                scores[othernode] / (2.0 * (k as f32 + 1.0) - scores[othernode])
                            }
                        };
                        (weight >= pruning).then_some((j, othernode, weight))
                    })
                    .collect();

                for &othernode in added.iter() {
                    scores[othernode] = 0.0;
                }

                out
            },
        )
        .flatten()
        .collect();

    let mut edges = Vec::with_capacity(results.len() * 2);
    let mut weights = Vec::with_capacity(results.len());

    for (i, j, weight) in results {
        edges.push(i);
        edges.push(j);
        weights.push(weight);
    }

    let n_rescued =
        rescue_small_components(&knn_rm, k, n_samples, method, &mut edges, &mut weights);

    let end_snn = start_time.elapsed();

    if verbosity.normal_verbosity() {
        println!("Transformed kNN into a full sNN graph: {:.2?}", end_snn);
        println!(
            "Added {} edges to reconnect components that pruning cut off.",
            n_rescued
        );
    }

    (edges, weights)
}

/// Generate an sNN graph based on the kNN graph (limited)
///
/// This version will only compare cells to the neighbouring cells and
/// deduplicate edges in taking the maximum weight between two given cells.
///
/// ### Params
///
/// * `knn_graph` - K-nearest neighbours data as a flat vector in column-major.
/// * `k` - Number of neighbours in the kNN graph
/// * `n_samples` - Number of samples in the data
/// * `pruning` - Below which Jaccard similarity to prune the edge. Components
///   that pruning leaves below ten cells are reconnected regardless, see
///   [rescue_small_components].
/// * `method` - Which similarity method to use.
/// * `verbose` - If `0` -> silent or `1` for normal verbosity, `2` for detailed
///   verbosity.
///
/// ### Returns
///
/// A tuple with `(<edges>, <weights>)`. The edges are stored in a way that the
/// the first edge points goes from the first element to the second, the second
/// edge from the third to the fourth, etc.
pub fn generate_snn_limited(
    flat_knn: &[usize],
    k: usize,
    n_samples: usize,
    pruning: f32,
    method: SnnSimilarityMethod,
    verbose: usize,
) -> (Vec<usize>, Vec<f32>) {
    let verbosity = parse_verbosity_level(verbose);
    let start_time = Instant::now();

    let knn_rm = row_major_knn(flat_knn, k, n_samples);

    let attached: Vec<Vec<(usize, u32)>> = (0..n_samples)
        .into_par_iter()
        .map(|c| {
            let mut v: Vec<(usize, u32)> = Vec::with_capacity(k + 1);
            v.push((c, 0));
            let row_start = c * k;
            for r in 0..k {
                v.push((knn_rm[row_start + r], (r + 1) as u32));
            }
            v.sort_unstable_by_key(|&(node, _)| node);
            v
        })
        .collect();

    // Weights are symmetric, so a mutual pair is emitted by its lower node only.
    // What is left is sorted and deduplicated on the canonical key, keeping the
    // largest weight.
    let mut candidates: Vec<(usize, usize, f32)> = (0..n_samples)
        .into_par_iter()
        .flat_map_iter(|i| {
            let ai = &attached[i];
            let row_start = i * k;
            let attached = &attached;
            let knn_rm = &knn_rm;

            (0..k).filter_map(move |r| {
                let j = knn_rm[row_start + r];
                let aj = &attached[j];

                let mutual = knn_rm[j * k..(j + 1) * k].contains(&i);
                if mutual && j < i {
                    return None;
                }

                let weight = match method {
                    SnnSimilarityMethod::Intersection => {
                        let (mut pi, mut pj) = (0usize, 0usize);
                        let mut count: u32 = 0;
                        while pi < ai.len() && pj < aj.len() {
                            let ni = ai[pi].0;
                            let nj = aj[pj].0;
                            if ni == nj {
                                count += 1;
                                pi += 1;
                                pj += 1;
                            } else if ni < nj {
                                pi += 1;
                            } else {
                                pj += 1;
                            }
                        }
                        let c = count as f32;
                        c / (2.0 * (k as f32 + 1.0) - c)
                    }
                    SnnSimilarityMethod::Rank => {
                        let (mut pi, mut pj) = (0usize, 0usize);
                        let mut min_combined: u32 = 2 * (k as u32);
                        while pi < ai.len() && pj < aj.len() {
                            let (ni, ri) = ai[pi];
                            let (nj, rj) = aj[pj];
                            if ni == nj {
                                let combined = ri + rj;
                                if combined < min_combined {
                                    min_combined = combined;
                                }
                                pi += 1;
                                pj += 1;
                            } else if ni < nj {
                                pi += 1;
                            } else {
                                pj += 1;
                            }
                        }
                        let preliminary = k as f32 - min_combined as f32 / 2.0;
                        preliminary.max(1e-6) / k as f32
                    }
                };

                (weight >= pruning).then_some((i.min(j), i.max(j), weight))
            })
        })
        .collect();

    candidates.par_sort_unstable_by(|a, b| {
        (a.0, a.1)
            .cmp(&(b.0, b.1))
            .then_with(|| b.2.total_cmp(&a.2))
    });
    candidates.dedup_by_key(|c| (c.0, c.1));

    let mut edges = Vec::with_capacity(candidates.len() * 2);
    let mut weights = Vec::with_capacity(candidates.len());

    for (i, j, weight) in candidates {
        edges.push(i);
        edges.push(j);
        weights.push(weight);
    }

    let n_rescued =
        rescue_small_components(&knn_rm, k, n_samples, method, &mut edges, &mut weights);

    let end_snn = start_time.elapsed();

    if verbosity.normal_verbosity() {
        println!("Transformed kNN into an sNN graph: {:.2?}", end_snn);
        println!(
            "Added {} edges to reconnect components that pruning cut off.",
            n_rescued
        );
    }

    (edges, weights)
}

////////////
// Others //
////////////

/// Build an undirected SparseGraph from sNN output.
///
/// ### Params
///
/// * `edges` - Flat edge list as produced by `generate_snn_full` /
///   `generate_snn_limited` (pairs `[u, v, u, v, ...]`).
/// * `weights` - Edge weights, one per pair.
/// * `n_nodes` - Number of nodes in the graph.
///
/// ### Returns
///
/// Undirected graph with a symmetric, row-sorted CSR
pub fn snn_edges_to_sparse_graph(
    edges: &[usize],
    weights: &[f32],
    n_nodes: usize,
) -> SparseGraph<f32> {
    edge_pairs_to_sparse_graph(edges, weights, n_nodes)
}

///////////
// Tests //
///////////

#[cfg(test)]
mod tests {
    use super::*;
    use rustc_hash::FxHashMap;

    // tiny fixture, 4 nodes, k=2:
    //   node 0 -> [1, 2]
    //   node 1 -> [0, 2]
    //   node 2 -> [0, 1]
    //   node 3 -> [0, 1]
    // column-major: flat_knn[neighbor_idx * n_samples + i]
    fn small_knn() -> (Vec<usize>, usize, usize) {
        let flat_knn = vec![1, 0, 0, 0, 2, 2, 1, 1];
        (flat_knn, 2, 4)
    }

    fn edge_map(edges: &[usize], weights: &[f32]) -> FxHashMap<(usize, usize), f32> {
        edges
            .chunks(2)
            .zip(weights.iter())
            .map(|(p, &w)| ((p[0].min(p[1]), p[0].max(p[1])), w))
            .collect()
    }

    /// Jaccard weights on a fixture small enough to check by hand.
    #[test]
    fn snn_full_jaccard_known_weights() {
        let (knn, k, n) = small_knn();
        let (edges, weights) =
            generate_snn_full(&knn, k, n, 0.0, SnnSimilarityMethod::Intersection, 0);
        let m = edge_map(&edges, &weights);

        // all C(4,2)=6 pairs share at least one neighbour
        assert_eq!(m.len(), 6);

        // (0,1): both have neighbour-sets {0,1,2} -> intersection 3, weight 3/(6-3)=1.0
        assert!((m[&(0, 1)] - 1.0).abs() < 1e-6);
        // (0,3): {0,1,2} vs {0,1,3} -> intersection 2, weight 2/(6-2)=0.5
        assert!((m[&(0, 3)] - 0.5).abs() < 1e-6);

        for &w in &weights {
            assert!(w > 0.0 && w <= 1.0);
        }
    }

    /// The prune threshold drops edges. The only survivor below it is the
    /// rescue edge of node 3, which pruning would otherwise isolate: it ties
    /// at 0.5 with 0 and 1 and keeps the closer one.
    #[test]
    fn snn_pruning() {
        let (knn, k, n) = small_knn();
        let (_, w_unpruned) =
            generate_snn_full(&knn, k, n, 0.0, SnnSimilarityMethod::Intersection, 0);
        for f in [generate_snn_full, generate_snn_limited] {
            let (e_pruned, w_pruned) = f(&knn, k, n, 0.6, SnnSimilarityMethod::Intersection, 0);
            let m = edge_map(&e_pruned, &w_pruned);

            assert!(w_pruned.len() < w_unpruned.len());
            assert_eq!(m.len(), 4);
            assert!((m[&(0, 3)] - 0.5).abs() < 1e-6);
            assert!(m.iter().all(|(&p, &w)| p == (0, 3) || w >= 0.6));
        }
    }

    /// The limited graph is a subgraph of the full one, with the same weights.
    #[test]
    fn snn_limited_is_subset_of_full() {
        let (knn, k, n) = small_knn();
        let (fe, fw) = generate_snn_full(&knn, k, n, 0.0, SnnSimilarityMethod::Intersection, 0);
        let (le, lw) = generate_snn_limited(&knn, k, n, 0.0, SnnSimilarityMethod::Intersection, 0);

        let full = edge_map(&fe, &fw);
        let lim = edge_map(&le, &lw);

        assert!(lim.len() <= full.len());
        for (k, w) in &lim {
            assert!(full.contains_key(k));
            assert!((full[k] - w).abs() < 1e-6);
        }
        // 2 and 3 are not kNN of each other -> not in the limited graph
        assert!(!lim.contains_key(&(2, 3)));
    }

    /// Rank weighting stays inside (0, 1] on both the full and the limited path.
    #[test]
    fn snn_rank_weights_valid() {
        let (knn, k, n) = small_knn();
        for f in [generate_snn_full, generate_snn_limited] {
            let (_, weights) = f(&knn, k, n, 0.0, SnnSimilarityMethod::Rank, 0);
            assert!(!weights.is_empty());
            assert!(weights.iter().all(|&w| w > 0.0 && w <= 1.0));
        }
    }

    /// The method parser is case-insensitive and refuses names it does not know.
    #[test]
    fn method_parser() {
        assert!(matches!(
            parse_snn_similiarity_method("jaccard"),
            Some(SnnSimilarityMethod::Intersection)
        ));
        assert!(matches!(
            parse_snn_similiarity_method("RANK"),
            Some(SnnSimilarityMethod::Rank)
        ));
        assert!(parse_snn_similiarity_method("nope").is_none());
    }

    // ---- helper tests ----

    /// Edge pairs and their weights land on the right nodes in the built graph.
    #[test]
    fn helper_round_trip() {
        // (0,1) w=0.5, (1,2) w=0.7, (0,2) w=0.3
        let edges = vec![0, 1, 1, 2, 0, 2];
        let weights = vec![0.5, 0.7, 0.3];
        let g = snn_edges_to_sparse_graph(&edges, &weights, 3);

        assert_eq!(g.get_node_number(), 3);
        assert!(!g.is_directed());

        let (n0, w0) = g.get_neighbours(0);
        assert_eq!(n0, &[1, 2]);
        assert_eq!(w0, &[0.5, 0.3]);

        let (n1, w1) = g.get_neighbours(1);
        assert_eq!(n1, &[0, 2]);
        assert_eq!(w1, &[0.5, 0.7]);
    }

    /// Neighbour indices come out sorted whatever order the edges arrived in.
    #[test]
    fn helper_indices_sorted() {
        // deliberately scramble the order in which node 0's edges are inserted
        let edges = vec![0, 5, 0, 2, 0, 4, 0, 1, 0, 3];
        let weights = vec![0.1, 0.2, 0.3, 0.4, 0.5];
        let g = snn_edges_to_sparse_graph(&edges, &weights, 6);

        let (nbrs, _) = g.get_neighbours(0);
        assert_eq!(nbrs, &[1, 2, 3, 4, 5]);
    }

    /// Every edge is stored in both directions with the same weight.
    #[test]
    fn helper_symmetric() {
        let edges = vec![0, 2, 1, 3, 0, 3];
        let weights = vec![0.4, 0.6, 0.2];
        let g = snn_edges_to_sparse_graph(&edges, &weights, 4);

        for u in 0..4 {
            let (nbrs, ws) = g.get_neighbours(u);
            for (&v, &w) in nbrs.iter().zip(ws.iter()) {
                let (rn, rw) = g.get_neighbours(v);
                let p = rn
                    .iter()
                    .position(|&x| x == u)
                    .expect("reverse edge missing");
                assert!((rw[p] - w).abs() < 1e-6);
            }
        }
    }

    /// Total weight recovers the input sum rather than the doubled adjacency sum.
    #[test]
    fn helper_total_weight() {
        let edges = vec![0, 1, 1, 2];
        let weights = vec![0.4, 0.6];
        let g = snn_edges_to_sparse_graph(&edges, &weights, 3);

        // undirected -> total_weight halves the doubled adjacency sum, recovers input sum
        assert!((g.total_weight() - 1.0).abs() < 1e-6);
    }

    /// No edges still gives a graph of the requested size, with every degree zero.
    #[test]
    fn helper_empty() {
        let g = snn_edges_to_sparse_graph(&[], &[], 5);
        assert_eq!(g.get_node_number(), 5);
        for i in 0..5 {
            assert_eq!(g.get_node_degree(i), 0);
        }
    }

    /// SNN output feeds the graph builder directly: degrees double, indices stay sorted.
    #[test]
    fn helper_end_to_end() {
        let (knn, k, n) = small_knn();
        let (edges, weights) =
            generate_snn_full(&knn, k, n, 0.0, SnnSimilarityMethod::Intersection, 0);
        let g = snn_edges_to_sparse_graph(&edges, &weights, n);

        let total_degree: usize = (0..n).map(|i| g.get_node_degree(i)).sum();
        assert_eq!(total_degree, 2 * weights.len());

        for i in 0..n {
            let (nbrs, _) = g.get_neighbours(i);
            let mut sorted = nbrs.to_vec();
            sorted.sort();
            assert_eq!(nbrs, &sorted[..]);
        }
    }
}