lean_ctx/core/graph_analysis/
god_nodes.rs

1//! God-Nodes: the most connected abstractions in the dependency graph.
2
3use std::collections::{HashMap, HashSet};
4
5use serde::Serialize;
6
7use super::dependency_edges;
8use crate::core::graph_provider::EdgeInfo;
9
10/// A highly connected file in the dependency graph.
11#[derive(Debug, Clone, Serialize, PartialEq, Eq)]
12pub struct GodNode {
13    pub path: String,
14    /// Files that depend on this one (fan-in).
15    pub in_degree: usize,
16    /// Files this one depends on (fan-out).
17    pub out_degree: usize,
18    /// `in_degree + out_degree`.
19    pub degree: usize,
20}
21
22/// Ranks files by total dependency degree (fan-in + fan-out) and returns the top
23/// `limit`. Deterministic: ties broken by path so the output is stable across
24/// rebuilds.
25pub fn compute_god_nodes(edges: &[EdgeInfo], limit: usize) -> Vec<GodNode> {
26    let deps = dependency_edges(edges);
27    let mut incoming: HashMap<&str, usize> = HashMap::new();
28    let mut outgoing: HashMap<&str, usize> = HashMap::new();
29    let mut nodes: HashSet<&str> = HashSet::new();
30
31    for (from, to) in &deps {
32        *outgoing.entry(*from).or_default() += 1;
33        *incoming.entry(*to).or_default() += 1;
34        nodes.insert(*from);
35        nodes.insert(*to);
36    }
37
38    let mut ranked: Vec<GodNode> = nodes
39        .into_iter()
40        .map(|n| {
41            let in_degree = incoming.get(n).copied().unwrap_or(0);
42            let out_degree = outgoing.get(n).copied().unwrap_or(0);
43            GodNode {
44                path: n.to_string(),
45                in_degree,
46                out_degree,
47                degree: in_degree + out_degree,
48            }
49        })
50        .collect();
51
52    ranked.sort_by(|a, b| b.degree.cmp(&a.degree).then_with(|| a.path.cmp(&b.path)));
53    ranked.truncate(limit);
54    ranked
55}
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    fn e(from: &str, to: &str, kind: &str) -> EdgeInfo {
62        EdgeInfo {
63            from: from.into(),
64            to: to.into(),
65            kind: kind.into(),
66            weight: 1.0,
67        }
68    }
69
70    #[test]
71    fn ranks_by_total_degree() {
72        let edges = vec![
73            e("a.rs", "b.rs", "import"),
74            e("a.rs", "c.rs", "import"),
75            e("d.rs", "a.rs", "import"),
76        ];
77        let god = compute_god_nodes(&edges, 10);
78        assert_eq!(god[0].path, "a.rs");
79        assert_eq!(god[0].out_degree, 2);
80        assert_eq!(god[0].in_degree, 1);
81        assert_eq!(god[0].degree, 3);
82    }
83
84    #[test]
85    fn ignores_heuristic_edges() {
86        // sibling / cochange are co-location heuristics, not dependencies.
87        let edges = vec![e("a.rs", "b.rs", "sibling"), e("a.rs", "c.rs", "cochange")];
88        assert!(compute_god_nodes(&edges, 10).is_empty());
89    }
90
91    #[test]
92    fn respects_limit_and_is_deterministic() {
93        let edges = vec![
94            e("a.rs", "x.rs", "import"),
95            e("b.rs", "x.rs", "import"),
96            e("c.rs", "x.rs", "import"),
97        ];
98        let god = compute_god_nodes(&edges, 2);
99        assert_eq!(god.len(), 2);
100        // x.rs has degree 3 (top); next are a/b/c with degree 1, tie-broken by path.
101        assert_eq!(god[0].path, "x.rs");
102        assert_eq!(god[1].path, "a.rs");
103    }
104}
lean_ctx/core/graph_analysis/god_nodes.rs

lean_ctx/core/graph_analysis/
god_nodes.rs
