nordisk/facett

facett-graphview/src/analysis/mod.rs

//! **Graph analysis** — the pure-algorithm core of the graph-DB IDE (V.G / G.V()).
//!
//! Every algorithm works on the **index-based** representation `(n, edges)` — `n`
//! nodes numbered `0..n` and `edges: &[(usize, usize)]` (directed `from → to`) — the
//! same shape [`crate::community::louvain`] already uses, so a caller maps its
//! `GraphModel` (String ids) to indices once and runs the whole toolbox. Results are
//! plain `Vec`s keyed by node index. No egui, no GPU, no RNG — deterministic and
//! headless-testable.
//!
//! Groups:
//! - [`centrality`] — degree / betweenness / closeness / pagerank / eigenvector.
//! - [`community`] — Louvain (re-exported) + label propagation.
//! - [`pathfinding`] — BFS / DFS / shortest path / all simple paths.
//! - [`cycles`] — cycle detection + topological sort.
//! - [`components`] — connected (undirected) + strongly-connected (Tarjan).
//! - [`kcore`] — k-core decomposition (core numbers).
//! - [`similarity`] — Jaccard / common-neighbours / Adamic–Adar / cosine.
//! - [`stats`] — whole-graph clustering coefficient + diameter / average path length.

pub mod centrality;
pub mod community;
pub mod components;
pub mod cycles;
pub mod kcore;
pub mod pathfinding;
pub mod similarity;
pub mod stats;

/// A built adjacency over `n` indexed nodes: directed out / in neighbour lists plus an
/// undirected view, each carrying an edge weight (`1.0` for unweighted input). Built
/// once from `(n, edges)` and shared by the analysis algorithms.
#[derive(Clone, Debug)]
pub struct Adjacency {
    /// Node count (indices `0..n`).
    pub n: usize,
    /// `out[i]` = directed out-neighbours of `i` as `(j, weight)`.
    pub out: Vec<Vec<(usize, f32)>>,
    /// `inc[i]` = directed in-neighbours of `i` as `(j, weight)`.
    pub inc: Vec<Vec<(usize, f32)>>,
    /// `und[i]` = undirected neighbours of `i` as `(j, weight)` (each edge both ways).
    pub und: Vec<Vec<(usize, f32)>>,
}

impl Adjacency {
    /// Build from unweighted directed edges (each `(a, b)` has weight `1.0`).
    /// Out-of-range endpoints and self-loops are dropped.
    #[must_use]
    pub fn from_edges(n: usize, edges: &[(usize, usize)]) -> Self {
        let weighted: Vec<(usize, usize, f32)> = edges.iter().map(|&(a, b)| (a, b, 1.0)).collect();
        Self::from_weighted(n, &weighted)
    }

    /// Build from weighted directed edges. Out-of-range endpoints and self-loops are
    /// dropped; parallel edges accumulate their weight.
    #[must_use]
    pub fn from_weighted(n: usize, edges: &[(usize, usize, f32)]) -> Self {
        let mut out = vec![Vec::new(); n];
        let mut inc = vec![Vec::new(); n];
        let mut und = vec![Vec::new(); n];
        for &(a, b, w) in edges {
            if a == b || a >= n || b >= n {
                continue;
            }
            accumulate(&mut out[a], b, w);
            accumulate(&mut inc[b], a, w);
            accumulate(&mut und[a], b, w);
            accumulate(&mut und[b], a, w);
        }
        Self { n, out, inc, und }
    }

    /// Out-degree of `i` (count of distinct out-neighbours).
    #[must_use]
    pub fn out_degree(&self, i: usize) -> usize {
        self.out.get(i).map_or(0, Vec::len)
    }
    /// In-degree of `i`.
    #[must_use]
    pub fn in_degree(&self, i: usize) -> usize {
        self.inc.get(i).map_or(0, Vec::len)
    }
    /// Undirected degree of `i`.
    #[must_use]
    pub fn degree(&self, i: usize) -> usize {
        self.und.get(i).map_or(0, Vec::len)
    }
}

/// Add `w` to node `j`'s weight in a neighbour list, inserting if absent.
fn accumulate(list: &mut Vec<(usize, f32)>, j: usize, w: f32) {
    if let Some(e) = list.iter_mut().find(|(k, _)| *k == j) {
        e.1 += w;
    } else {
        list.push((j, w));
    }
}

/// A tiny directed test fixture reused across the analysis unit tests:
///
/// ```text
/// 0 → 1 → 2 → 0   (a 3-cycle)     3 → 4   (a separate 2-chain)
/// ```
#[cfg(test)]
pub(crate) fn fixture() -> (usize, Vec<(usize, usize)>) {
    (5, vec![(0, 1), (1, 2), (2, 0), (3, 4)])
}

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

    #[test]
    fn adjacency_builds_directed_and_undirected_views() {
        let (n, edges) = fixture();
        let g = Adjacency::from_edges(n, &edges);
        assert_eq!(g.n, 5);
        assert_eq!(g.out_degree(0), 1); // 0→1
        assert_eq!(g.in_degree(0), 1); // 2→0
        assert_eq!(g.degree(0), 2); // undirected: 1 and 2
        assert_eq!(g.degree(3), 1);
        assert_eq!(g.degree(4), 1);
    }

    #[test]
    fn self_loops_and_out_of_range_dropped_parallel_accumulate() {
        let g = Adjacency::from_weighted(3, &[(0, 0, 1.0), (0, 5, 1.0), (0, 1, 2.0), (0, 1, 3.0)]);
        assert_eq!(g.out_degree(0), 1); // only 0→1 survives
        assert_eq!(g.out[0][0], (1, 5.0)); // parallel weights accumulate
    }
}