facett_graphview/analysis/
mod.rs

1//! **Graph analysis** — the pure-algorithm core of the graph-DB IDE (V.G / G.V()).
2//!
3//! Every algorithm works on the **index-based** representation `(n, edges)` — `n`
4//! nodes numbered `0..n` and `edges: &[(usize, usize)]` (directed `from → to`) — the
5//! same shape [`crate::community::louvain`] already uses, so a caller maps its
6//! `GraphModel` (String ids) to indices once and runs the whole toolbox. Results are
7//! plain `Vec`s keyed by node index. No egui, no GPU, no RNG — deterministic and
8//! headless-testable.
9//!
10//! Groups:
11//! - [`centrality`] — degree / betweenness / closeness / pagerank / eigenvector.
12//! - [`community`] — Louvain (re-exported) + label propagation.
13//! - [`pathfinding`] — BFS / DFS / shortest path / all simple paths.
14//! - [`cycles`] — cycle detection + topological sort.
15//! - [`components`] — connected (undirected) + strongly-connected (Tarjan).
16//! - [`kcore`] — k-core decomposition (core numbers).
17//! - [`similarity`] — Jaccard / common-neighbours / Adamic–Adar / cosine.
18//! - [`stats`] — whole-graph clustering coefficient + diameter / average path length.
19
20pub mod centrality;
21pub mod community;
22pub mod components;
23pub mod cycles;
24pub mod kcore;
25pub mod pathfinding;
26pub mod similarity;
27pub mod stats;
28
29/// A built adjacency over `n` indexed nodes: directed out / in neighbour lists plus an
30/// undirected view, each carrying an edge weight (`1.0` for unweighted input). Built
31/// once from `(n, edges)` and shared by the analysis algorithms.
32#[derive(Clone, Debug)]
33pub struct Adjacency {
34    /// Node count (indices `0..n`).
35    pub n: usize,
36    /// `out[i]` = directed out-neighbours of `i` as `(j, weight)`.
37    pub out: Vec<Vec<(usize, f32)>>,
38    /// `inc[i]` = directed in-neighbours of `i` as `(j, weight)`.
39    pub inc: Vec<Vec<(usize, f32)>>,
40    /// `und[i]` = undirected neighbours of `i` as `(j, weight)` (each edge both ways).
41    pub und: Vec<Vec<(usize, f32)>>,
42}
43
44impl Adjacency {
45    /// Build from unweighted directed edges (each `(a, b)` has weight `1.0`).
46    /// Out-of-range endpoints and self-loops are dropped.
47    #[must_use]
48    pub fn from_edges(n: usize, edges: &[(usize, usize)]) -> Self {
49        let weighted: Vec<(usize, usize, f32)> = edges.iter().map(|&(a, b)| (a, b, 1.0)).collect();
50        Self::from_weighted(n, &weighted)
51    }
52
53    /// Build from weighted directed edges. Out-of-range endpoints and self-loops are
54    /// dropped; parallel edges accumulate their weight.
55    #[must_use]
56    pub fn from_weighted(n: usize, edges: &[(usize, usize, f32)]) -> Self {
57        let mut out = vec![Vec::new(); n];
58        let mut inc = vec![Vec::new(); n];
59        let mut und = vec![Vec::new(); n];
60        for &(a, b, w) in edges {
61            if a == b || a >= n || b >= n {
62                continue;
63            }
64            accumulate(&mut out[a], b, w);
65            accumulate(&mut inc[b], a, w);
66            accumulate(&mut und[a], b, w);
67            accumulate(&mut und[b], a, w);
68        }
69        Self { n, out, inc, und }
70    }
71
72    /// Out-degree of `i` (count of distinct out-neighbours).
73    #[must_use]
74    pub fn out_degree(&self, i: usize) -> usize {
75        self.out.get(i).map_or(0, Vec::len)
76    }
77    /// In-degree of `i`.
78    #[must_use]
79    pub fn in_degree(&self, i: usize) -> usize {
80        self.inc.get(i).map_or(0, Vec::len)
81    }
82    /// Undirected degree of `i`.
83    #[must_use]
84    pub fn degree(&self, i: usize) -> usize {
85        self.und.get(i).map_or(0, Vec::len)
86    }
87}
88
89/// Add `w` to node `j`'s weight in a neighbour list, inserting if absent.
90fn accumulate(list: &mut Vec<(usize, f32)>, j: usize, w: f32) {
91    if let Some(e) = list.iter_mut().find(|(k, _)| *k == j) {
92        e.1 += w;
93    } else {
94        list.push((j, w));
95    }
96}
97
98/// A tiny directed test fixture reused across the analysis unit tests:
99///
100/// ```text
101/// 0 → 1 → 2 → 0   (a 3-cycle)     3 → 4   (a separate 2-chain)
102/// ```
103#[cfg(test)]
104pub(crate) fn fixture() -> (usize, Vec<(usize, usize)>) {
105    (5, vec![(0, 1), (1, 2), (2, 0), (3, 4)])
106}
107
108#[cfg(test)]
109mod tests {
110    use super::*;
111
112    #[test]
113    fn adjacency_builds_directed_and_undirected_views() {
114        let (n, edges) = fixture();
115        let g = Adjacency::from_edges(n, &edges);
116        assert_eq!(g.n, 5);
117        assert_eq!(g.out_degree(0), 1); // 0→1
118        assert_eq!(g.in_degree(0), 1); // 2→0
119        assert_eq!(g.degree(0), 2); // undirected: 1 and 2
120        assert_eq!(g.degree(3), 1);
121        assert_eq!(g.degree(4), 1);
122    }
123
124    #[test]
125    fn self_loops_and_out_of_range_dropped_parallel_accumulate() {
126        let g = Adjacency::from_weighted(3, &[(0, 0, 1.0), (0, 5, 1.0), (0, 1, 2.0), (0, 1, 3.0)]);
127        assert_eq!(g.out_degree(0), 1); // only 0→1 survives
128        assert_eq!(g.out[0][0], (1, 5.0)); // parallel weights accumulate
129    }
130}
facett_graphview/analysis/mod.rs

facett_graphview/analysis/
mod.rs
