nordisk/facett

facett-graphview/src/analysis/stats.rs

//! **Whole-graph statistics** — the scalar summaries a stats panel shows, computed on
//! the undirected view: the **clustering coefficient** (how tightly neighbourhoods
//! close into triangles) and the **diameter** / **average path length** (the graph's
//! reach). These fill the two gaps the rest of [`super`] left open.
//!
//! All are undirected + deterministic (BFS-based, `O(n·(n+m))` for the distance
//! measures — fine for the interactive graphs a navigator holds).

use std::collections::VecDeque;

use super::Adjacency;

/// The **average local clustering coefficient** (Watts–Strogatz). For each node with
/// undirected degree `k ≥ 2`, the local coefficient is `2·e / (k·(k−1))` where `e` is
/// the number of edges among its neighbours; nodes with `k < 2` contribute `0`. The
/// result is the mean over all nodes, in `[0, 1]`. `0.0` for `n = 0`.
#[must_use]
pub fn average_clustering(g: &Adjacency) -> f32 {
    if g.n == 0 {
        return 0.0;
    }
    let mut sum = 0.0f32;
    for i in 0..g.n {
        let nbrs: Vec<usize> = g.und[i].iter().map(|&(j, _)| j).collect();
        let k = nbrs.len();
        if k < 2 {
            continue;
        }
        // Count undirected links among the neighbours.
        let mut links = 0usize;
        for (a, &u) in nbrs.iter().enumerate() {
            for &v in &nbrs[a + 1..] {
                if g.und[u].iter().any(|&(w, _)| w == v) {
                    links += 1;
                }
            }
        }
        sum += 2.0 * links as f32 / (k * (k - 1)) as f32;
    }
    sum / g.n as f32
}

/// The **global clustering coefficient** (transitivity) = `3·triangles / triads`,
/// where a triad is a connected path of two edges (a node with an ordered pair of
/// neighbours). `0.0` when there are no triads.
#[must_use]
pub fn transitivity(g: &Adjacency) -> f32 {
    let mut triangles = 0usize;
    let mut triads = 0usize;
    for i in 0..g.n {
        let nbrs: Vec<usize> = g.und[i].iter().map(|&(j, _)| j).collect();
        let k = nbrs.len();
        if k >= 2 {
            triads += k * (k - 1) / 2;
        }
        for (a, &u) in nbrs.iter().enumerate() {
            for &v in &nbrs[a + 1..] {
                if g.und[u].iter().any(|&(w, _)| w == v) {
                    triangles += 1;
                }
            }
        }
    }
    if triads == 0 {
        0.0
    } else {
        triangles as f32 / triads as f32
    }
}

/// Undirected BFS hop-distances from `src` to every node (`usize::MAX` = unreachable).
fn bfs_dist(g: &Adjacency, src: usize) -> Vec<usize> {
    let mut dist = vec![usize::MAX; g.n];
    let mut q = VecDeque::new();
    dist[src] = 0;
    q.push_back(src);
    while let Some(v) = q.pop_front() {
        for &(w, _) in &g.und[v] {
            if dist[w] == usize::MAX {
                dist[w] = dist[v] + 1;
                q.push_back(w);
            }
        }
    }
    dist
}

/// The **diameter** — the longest shortest path (in hops) between any two *connected*
/// nodes (undirected). A disconnected graph reports the max over its components (∞
/// pairs are ignored). `0` for a graph with no edges.
#[must_use]
pub fn diameter(g: &Adjacency) -> usize {
    let mut d = 0;
    for s in 0..g.n {
        for dist in bfs_dist(g, s) {
            if dist != usize::MAX {
                d = d.max(dist);
            }
        }
    }
    d
}

/// The **average shortest-path length** over all ordered pairs of *distinct, connected*
/// nodes (undirected). `0.0` when no pair is connected.
#[must_use]
pub fn average_path_length(g: &Adjacency) -> f32 {
    let mut total = 0u64;
    let mut pairs = 0u64;
    for s in 0..g.n {
        for (t, dist) in bfs_dist(g, s).into_iter().enumerate() {
            if t != s && dist != usize::MAX {
                total += dist as u64;
                pairs += 1;
            }
        }
    }
    if pairs == 0 {
        0.0
    } else {
        total as f32 / pairs as f32
    }
}

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

    #[test]
    fn triangle_is_fully_clustered() {
        // K3: every neighbourhood closes → clustering 1.0, diameter 1, avg path 1.0.
        let g = Adjacency::from_edges(3, &[(0, 1), (1, 2), (2, 0)]);
        assert!((average_clustering(&g) - 1.0).abs() < 1e-6);
        assert!((transitivity(&g) - 1.0).abs() < 1e-6);
        assert_eq!(diameter(&g), 1);
        assert!((average_path_length(&g) - 1.0).abs() < 1e-6);
    }

    #[test]
    fn path_graph_has_no_clustering() {
        // 0-1-2-3 chain: no triangles, diameter 3.
        let g = Adjacency::from_edges(4, &[(0, 1), (1, 2), (2, 3)]);
        assert!(average_clustering(&g) < 1e-6);
        assert_eq!(diameter(&g), 3);
        // avg path length of a 4-path = (1+2+3 + 1+2 + 1)*2 / (4*3) = 20/12.
        assert!((average_path_length(&g) - 20.0 / 12.0).abs() < 1e-4);
    }

    #[test]
    fn disconnected_ignores_infinite_pairs() {
        // Two separate edges: finite distances only within each component.
        let g = Adjacency::from_edges(4, &[(0, 1), (2, 3)]);
        assert_eq!(diameter(&g), 1);
        assert!((average_path_length(&g) - 1.0).abs() < 1e-6);
    }

    #[test]
    fn empty_graph_is_zero() {
        let g = Adjacency::from_edges(0, &[]);
        assert_eq!(average_clustering(&g), 0.0);
        assert_eq!(diameter(&g), 0);
        assert_eq!(average_path_length(&g), 0.0);
    }
}