lean_ctx/core/graph_analysis/
surprising.rs

1//! Surprising connections: dependency edges that bridge otherwise-unrelated
2//! parts of the codebase.
3//!
4//! Composite score per edge `(u, v)`:
5//!   `(1 - jaccard(N(u), N(v))) * cross_community_factor * ln(1 + deg(u) + deg(v))`
6//!
7//! High score = the two files share few neighbours (low overlap), live in
8//! different communities, and are non-trivially connected — i.e. an unexpected
9//! coupling worth a human's attention (graphify-style).
10
11use std::collections::{HashMap, HashSet};
12
13use serde::Serialize;
14
15use super::dependency_edges;
16use crate::core::graph_provider::EdgeInfo;
17
18/// An unexpected coupling between two files.
19#[derive(Debug, Clone, Serialize, PartialEq)]
20pub struct SurprisingConnection {
21    pub from: String,
22    pub to: String,
23    pub score: f64,
24    pub cross_community: bool,
25    pub shared_neighbors: usize,
26}
27
28/// Returns the top `limit` surprising connections, highest score first.
29/// Deterministic. `community` maps file path → community id (may be partial).
30pub fn find_surprising_connections(
31    edges: &[EdgeInfo],
32    community: &HashMap<String, usize>,
33    limit: usize,
34) -> Vec<SurprisingConnection> {
35    let deps = dependency_edges(edges);
36    if deps.is_empty() {
37        return Vec::new();
38    }
39
40    // Undirected neighbour sets over dependency edges.
41    let mut adj: HashMap<&str, HashSet<&str>> = HashMap::new();
42    for (u, v) in &deps {
43        adj.entry(*u).or_default().insert(*v);
44        adj.entry(*v).or_default().insert(*u);
45    }
46
47    let empty: HashSet<&str> = HashSet::new();
48    let mut seen: HashSet<(&str, &str)> = HashSet::new();
49    let mut out: Vec<SurprisingConnection> = Vec::new();
50
51    for (u, v) in &deps {
52        // Canonical undirected key so a↔b is scored once.
53        let key = if u <= v { (*u, *v) } else { (*v, *u) };
54        if !seen.insert(key) {
55            continue;
56        }
57
58        let nu = adj.get(*u).unwrap_or(&empty);
59        let nv = adj.get(*v).unwrap_or(&empty);
60        if nu.len() < 2 || nv.len() < 2 {
61            continue; // trivial leaf edge: not "surprising", just sparse
62        }
63
64        let shared = nu
65            .intersection(nv)
66            .filter(|n| **n != *u && **n != *v)
67            .count();
68        let mut union: HashSet<&str> = nu.iter().copied().collect();
69        union.extend(nv.iter().copied());
70        union.remove(*u);
71        union.remove(*v);
72        let union_len = union.len().max(1);
73        let jaccard = shared as f64 / union_len as f64;
74
75        let cross = match (community.get(*u), community.get(*v)) {
76            (Some(a), Some(b)) => a != b,
77            _ => true,
78        };
79
80        let deg = (nu.len() + nv.len()) as f64;
81        let score = (1.0 - jaccard) * (if cross { 1.0 } else { 0.35 }) * (1.0 + deg).ln();
82
83        out.push(SurprisingConnection {
84            from: (*u).to_string(),
85            to: (*v).to_string(),
86            score: (score * 1000.0).round() / 1000.0,
87            cross_community: cross,
88            shared_neighbors: shared,
89        });
90    }
91
92    out.sort_by(|a, b| {
93        b.score
94            .partial_cmp(&a.score)
95            .unwrap_or(std::cmp::Ordering::Equal)
96            .then_with(|| a.from.cmp(&b.from))
97            .then_with(|| a.to.cmp(&b.to))
98    });
99    out.truncate(limit);
100    out
101}
102
103#[cfg(test)]
104mod tests {
105    use super::*;
106
107    fn e(from: &str, to: &str) -> EdgeInfo {
108        EdgeInfo {
109            from: from.into(),
110            to: to.into(),
111            kind: "import".into(),
112            weight: 1.0,
113        }
114    }
115
116    #[test]
117    fn bridge_edge_ranks_above_intra_cluster_edge() {
118        // Two triangles {a,b,c} and {x,y,z}, joined by a single bridge c<->x.
119        let edges = vec![
120            e("a", "b"),
121            e("b", "c"),
122            e("a", "c"),
123            e("x", "y"),
124            e("y", "z"),
125            e("x", "z"),
126            e("c", "x"), // the surprising bridge
127        ];
128        let mut community = HashMap::new();
129        for n in ["a", "b", "c"] {
130            community.insert(n.to_string(), 0);
131        }
132        for n in ["x", "y", "z"] {
133            community.insert(n.to_string(), 1);
134        }
135
136        let surprising = find_surprising_connections(&edges, &community, 10);
137        assert!(!surprising.is_empty());
138        let top = &surprising[0];
139        assert_eq!((top.from.as_str(), top.to.as_str()), ("c", "x"));
140        assert!(top.cross_community);
141    }
142
143    #[test]
144    fn empty_without_dependency_edges() {
145        let edges = vec![EdgeInfo {
146            from: "a".into(),
147            to: "b".into(),
148            kind: "sibling".into(),
149            weight: 1.0,
150        }];
151        assert!(find_surprising_connections(&edges, &HashMap::new(), 10).is_empty());
152    }
153}
lean_ctx/core/graph_analysis/surprising.rs

lean_ctx/core/graph_analysis/
surprising.rs
