facett_graphview/analysis/
stats.rs

1//! **Whole-graph statistics** — the scalar summaries a stats panel shows, computed on
2//! the undirected view: the **clustering coefficient** (how tightly neighbourhoods
3//! close into triangles) and the **diameter** / **average path length** (the graph's
4//! reach). These fill the two gaps the rest of [`super`] left open.
5//!
6//! All are undirected + deterministic (BFS-based, `O(n·(n+m))` for the distance
7//! measures — fine for the interactive graphs a navigator holds).
8
9use std::collections::VecDeque;
10
11use super::Adjacency;
12
13/// The **average local clustering coefficient** (Watts–Strogatz). For each node with
14/// undirected degree `k ≥ 2`, the local coefficient is `2·e / (k·(k−1))` where `e` is
15/// the number of edges among its neighbours; nodes with `k < 2` contribute `0`. The
16/// result is the mean over all nodes, in `[0, 1]`. `0.0` for `n = 0`.
17#[must_use]
18pub fn average_clustering(g: &Adjacency) -> f32 {
19    if g.n == 0 {
20        return 0.0;
21    }
22    let mut sum = 0.0f32;
23    for i in 0..g.n {
24        let nbrs: Vec<usize> = g.und[i].iter().map(|&(j, _)| j).collect();
25        let k = nbrs.len();
26        if k < 2 {
27            continue;
28        }
29        // Count undirected links among the neighbours.
30        let mut links = 0usize;
31        for (a, &u) in nbrs.iter().enumerate() {
32            for &v in &nbrs[a + 1..] {
33                if g.und[u].iter().any(|&(w, _)| w == v) {
34                    links += 1;
35                }
36            }
37        }
38        sum += 2.0 * links as f32 / (k * (k - 1)) as f32;
39    }
40    sum / g.n as f32
41}
42
43/// The **global clustering coefficient** (transitivity) = `3·triangles / triads`,
44/// where a triad is a connected path of two edges (a node with an ordered pair of
45/// neighbours). `0.0` when there are no triads.
46#[must_use]
47pub fn transitivity(g: &Adjacency) -> f32 {
48    let mut triangles = 0usize;
49    let mut triads = 0usize;
50    for i in 0..g.n {
51        let nbrs: Vec<usize> = g.und[i].iter().map(|&(j, _)| j).collect();
52        let k = nbrs.len();
53        if k >= 2 {
54            triads += k * (k - 1) / 2;
55        }
56        for (a, &u) in nbrs.iter().enumerate() {
57            for &v in &nbrs[a + 1..] {
58                if g.und[u].iter().any(|&(w, _)| w == v) {
59                    triangles += 1;
60                }
61            }
62        }
63    }
64    if triads == 0 {
65        0.0
66    } else {
67        triangles as f32 / triads as f32
68    }
69}
70
71/// Undirected BFS hop-distances from `src` to every node (`usize::MAX` = unreachable).
72fn bfs_dist(g: &Adjacency, src: usize) -> Vec<usize> {
73    let mut dist = vec![usize::MAX; g.n];
74    let mut q = VecDeque::new();
75    dist[src] = 0;
76    q.push_back(src);
77    while let Some(v) = q.pop_front() {
78        for &(w, _) in &g.und[v] {
79            if dist[w] == usize::MAX {
80                dist[w] = dist[v] + 1;
81                q.push_back(w);
82            }
83        }
84    }
85    dist
86}
87
88/// The **diameter** — the longest shortest path (in hops) between any two *connected*
89/// nodes (undirected). A disconnected graph reports the max over its components (∞
90/// pairs are ignored). `0` for a graph with no edges.
91#[must_use]
92pub fn diameter(g: &Adjacency) -> usize {
93    let mut d = 0;
94    for s in 0..g.n {
95        for dist in bfs_dist(g, s) {
96            if dist != usize::MAX {
97                d = d.max(dist);
98            }
99        }
100    }
101    d
102}
103
104/// The **average shortest-path length** over all ordered pairs of *distinct, connected*
105/// nodes (undirected). `0.0` when no pair is connected.
106#[must_use]
107pub fn average_path_length(g: &Adjacency) -> f32 {
108    let mut total = 0u64;
109    let mut pairs = 0u64;
110    for s in 0..g.n {
111        for (t, dist) in bfs_dist(g, s).into_iter().enumerate() {
112            if t != s && dist != usize::MAX {
113                total += dist as u64;
114                pairs += 1;
115            }
116        }
117    }
118    if pairs == 0 {
119        0.0
120    } else {
121        total as f32 / pairs as f32
122    }
123}
124
125#[cfg(test)]
126mod tests {
127    use super::*;
128
129    #[test]
130    fn triangle_is_fully_clustered() {
131        // K3: every neighbourhood closes → clustering 1.0, diameter 1, avg path 1.0.
132        let g = Adjacency::from_edges(3, &[(0, 1), (1, 2), (2, 0)]);
133        assert!((average_clustering(&g) - 1.0).abs() < 1e-6);
134        assert!((transitivity(&g) - 1.0).abs() < 1e-6);
135        assert_eq!(diameter(&g), 1);
136        assert!((average_path_length(&g) - 1.0).abs() < 1e-6);
137    }
138
139    #[test]
140    fn path_graph_has_no_clustering() {
141        // 0-1-2-3 chain: no triangles, diameter 3.
142        let g = Adjacency::from_edges(4, &[(0, 1), (1, 2), (2, 3)]);
143        assert!(average_clustering(&g) < 1e-6);
144        assert_eq!(diameter(&g), 3);
145        // avg path length of a 4-path = (1+2+3 + 1+2 + 1)*2 / (4*3) = 20/12.
146        assert!((average_path_length(&g) - 20.0 / 12.0).abs() < 1e-4);
147    }
148
149    #[test]
150    fn disconnected_ignores_infinite_pairs() {
151        // Two separate edges: finite distances only within each component.
152        let g = Adjacency::from_edges(4, &[(0, 1), (2, 3)]);
153        assert_eq!(diameter(&g), 1);
154        assert!((average_path_length(&g) - 1.0).abs() < 1e-6);
155    }
156
157    #[test]
158    fn empty_graph_is_zero() {
159        let g = Adjacency::from_edges(0, &[]);
160        assert_eq!(average_clustering(&g), 0.0);
161        assert_eq!(diameter(&g), 0);
162        assert_eq!(average_path_length(&g), 0.0);
163    }
164}
facett_graphview/analysis/stats.rs

facett_graphview/analysis/
stats.rs
