lean_ctx/core/community/
graph.rs

1//! Undirected, weighted adjacency representation of the file-level code graph.
2//!
3//! Parallel edges are merged (weights summed) and the adjacency is symmetric so
4//! modularity and connectivity computations are correct. The same structure is
5//! built from the PropertyGraph (SQLite) and from any [`GraphProvider`], which
6//! keeps community detection storage-agnostic.
7
8use std::collections::HashMap;
9
10use rusqlite::Connection;
11
12use crate::core::graph_provider::GraphProvider;
13use crate::core::property_graph::GraphSource;
14
15/// Edge weight by semantic kind. Calls bind tighter than plain imports; purely
16/// structural `defines`/`exports` edges are weak ties. Accepts both the
17/// PropertyGraph kind spelling (`imports`, `calls`) and the graph-index spelling
18/// (`import`, `call`) so either backend yields identical weights.
19pub fn edge_weight(kind: &str) -> f64 {
20    match kind {
21        "imports" | "import" => 1.0,
22        "calls" | "call" => 1.5,
23        "type_ref" | "type" => 0.8,
24        "defines" | "exports" | "export" => 0.3,
25        _ => 0.5,
26    }
27}
28
29pub struct AdjGraph {
30    pub node_ids: Vec<String>,
31    #[cfg_attr(not(test), allow(dead_code))] // read by community integration tests
32    pub node_to_idx: HashMap<String, usize>,
33    /// Symmetric adjacency: every undirected edge `{i,j}` appears as `(i→j)` in
34    /// `adj[i]` and `(j→i)` in `adj[j]`. Neighbor lists are sorted by index.
35    pub adj: Vec<Vec<(usize, f64)>>,
36    pub degree: Vec<f64>,
37    /// Sum of unique undirected edge weights (each edge counted once).
38    pub total_weight: f64,
39}
40
41impl AdjGraph {
42    pub fn node_count(&self) -> usize {
43        self.node_ids.len()
44    }
45
46    /// Number of unique undirected edges.
47    pub fn edge_count(&self) -> usize {
48        self.adj.iter().map(Vec::len).sum::<usize>() / 2
49    }
50
51    /// Build from already-resolved index pairs. `raw` holds `(from, to, weight)`
52    /// in node-index space; self-loops and out-of-range endpoints are dropped and
53    /// duplicate/parallel edges are merged by summing weights.
54    fn from_pairs(node_ids: Vec<String>, raw: &[(usize, usize, f64)]) -> Self {
55        let n = node_ids.len();
56        let mut node_to_idx = HashMap::with_capacity(n);
57        for (idx, name) in node_ids.iter().enumerate() {
58            node_to_idx.insert(name.clone(), idx);
59        }
60
61        let mut merged: HashMap<(usize, usize), f64> = HashMap::new();
62        for &(a, b, w) in raw {
63            if a == b || a >= n || b >= n {
64                continue;
65            }
66            let key = if a < b { (a, b) } else { (b, a) };
67            *merged.entry(key).or_default() += w;
68        }
69
70        let mut adj: Vec<Vec<(usize, f64)>> = vec![Vec::new(); n];
71        let mut degree = vec![0.0; n];
72        let mut total_weight = 0.0;
73
74        let mut entries: Vec<((usize, usize), f64)> = merged.into_iter().collect();
75        entries.sort_by_key(|e| e.0);
76        for ((i, j), w) in entries {
77            adj[i].push((j, w));
78            adj[j].push((i, w));
79            degree[i] += w;
80            degree[j] += w;
81            total_weight += w;
82        }
83        for list in &mut adj {
84            list.sort_by_key(|e| e.0);
85        }
86
87        Self {
88            node_ids,
89            node_to_idx,
90            adj,
91            degree,
92            total_weight,
93        }
94    }
95
96    /// The file graph of `source` among the files it serves now (G04): a
97    /// withdrawn file is no node, so it carries no edge, no degree and no
98    /// weight into the partition, the edge counts, cohesion or modularity.
99    /// Under protection a graph with more files than one request can decide
100    /// yields the empty graph (`GraphGate::ranking_files`, no seeds).
101    pub fn from_property_graph<S: GraphSource + ?Sized>(source: &S) -> Self {
102        let conn = source.store();
103        let edges = query_file_edges(conn);
104        let file_pairs: Vec<(String, String)> = edges
105            .iter()
106            .map(|(a, b, _)| (a.clone(), b.clone()))
107            .collect();
108        let served = source.rankable_files(query_files(conn), &file_pairs, &[]);
109        // `query_files` order (by path) is the node order.
110        let mut files: Vec<String> = served.into_iter().collect();
111        files.sort();
112        let idx: HashMap<&str, usize> = files
113            .iter()
114            .enumerate()
115            .map(|(i, f)| (f.as_str(), i))
116            .collect();
117        let pairs: Vec<(usize, usize, f64)> = edges
118            .iter()
119            .filter_map(|(a, b, w)| Some((*idx.get(a.as_str())?, *idx.get(b.as_str())?, *w)))
120            .collect();
121        Self::from_pairs(files, &pairs)
122    }
123
124    /// As [`Self::from_property_graph`], for either backend: the files and
125    /// edges come from one gated read (`GraphProvider::ranking_graph`).
126    pub fn from_provider(gp: &GraphProvider) -> Self {
127        let (files, edges) = gp.ranking_graph();
128        let idx: HashMap<&str, usize> = files
129            .iter()
130            .enumerate()
131            .map(|(i, f)| (f.as_str(), i))
132            .collect();
133        let pairs: Vec<(usize, usize, f64)> = edges
134            .iter()
135            .filter_map(|e| {
136                let i = *idx.get(e.from.as_str())?;
137                let j = *idx.get(e.to.as_str())?;
138                Some((i, j, edge_weight(&e.kind)))
139            })
140            .collect();
141        Self::from_pairs(files, &pairs)
142    }
143
144    /// Induced subgraph over `members` (global node indices). Returns the
145    /// subgraph plus a `local → global` index map for translating results back.
146    pub fn induced_subgraph(&self, members: &[usize]) -> (AdjGraph, Vec<usize>) {
147        let mut local_of: HashMap<usize, usize> = HashMap::with_capacity(members.len());
148        let mut node_ids = Vec::with_capacity(members.len());
149        let mut local_to_global = Vec::with_capacity(members.len());
150        for &g in members {
151            local_of.insert(g, node_ids.len());
152            node_ids.push(self.node_ids[g].clone());
153            local_to_global.push(g);
154        }
155        let mut pairs = Vec::new();
156        for &g in members {
157            let li = local_of[&g];
158            for &(h, w) in &self.adj[g] {
159                if let Some(&lj) = local_of.get(&h)
160                    && li < lj
161                {
162                    pairs.push((li, lj, w));
163                }
164            }
165        }
166        (AdjGraph::from_pairs(node_ids, &pairs), local_to_global)
167    }
168
169    #[cfg(test)]
170    pub fn from_test_edges(node_ids: Vec<String>, edges: &[(usize, usize, &str)]) -> Self {
171        let pairs: Vec<(usize, usize, f64)> = edges
172            .iter()
173            .map(|&(a, b, kind)| (a, b, edge_weight(kind)))
174            .collect();
175        Self::from_pairs(node_ids, &pairs)
176    }
177}
178
179/// Internal vs. external edge endpoints for a community (symmetric adjacency, so
180/// each internal undirected edge contributes twice — the cohesion ratio is
181/// unaffected).
182pub fn edge_counts(graph: &AdjGraph, members: &[usize]) -> (usize, usize) {
183    let member_set: std::collections::HashSet<usize> = members.iter().copied().collect();
184    let mut internal = 0usize;
185    let mut external = 0usize;
186    for &i in members {
187        for &(j, _) in &graph.adj[i] {
188            if member_set.contains(&j) {
189                internal += 1;
190            } else {
191                external += 1;
192            }
193        }
194    }
195    (internal, external)
196}
197
198/// Fraction of a community's incident edges that stay inside it (`0.0..=1.0`).
199pub fn cohesion_of(graph: &AdjGraph, members: &[usize]) -> f64 {
200    let (internal, external) = edge_counts(graph, members);
201    let total = (internal + external).max(1) as f64;
202    internal as f64 / total
203}
204
205fn query_files(conn: &Connection) -> Vec<String> {
206    let Ok(mut stmt) = conn.prepare(
207        "SELECT DISTINCT p.path
208         FROM nodes n JOIN paths p ON p.id = n.file_id
209         WHERE n.kind = 'file' ORDER BY p.path",
210    ) else {
211        tracing::warn!("community: failed to prepare file query");
212        return Vec::new();
213    };
214    let mut files = Vec::new();
215    match stmt.query_map([], |row| row.get::<_, String>(0)) {
216        Ok(rows) => files.extend(rows.filter_map(std::result::Result::ok)),
217        Err(e) => tracing::warn!("community: file query failed: {e}"),
218    }
219    files
220}
221
222fn query_file_edges(conn: &Connection) -> Vec<(String, String, f64)> {
223    let sql = "
224        SELECT DISTINCT p1.path, p2.path, e.kind
225        FROM edges e
226        JOIN nodes n1 ON e.source_id = n1.id
227        JOIN nodes n2 ON e.target_id = n2.id
228        JOIN paths p1 ON p1.id = n1.file_id
229        JOIN paths p2 ON p2.id = n2.file_id
230        WHERE n1.kind = 'file' AND n2.kind = 'file'
231          AND n1.file_id != n2.file_id
232        ORDER BY p1.path, p2.path
233    ";
234    let Ok(mut stmt) = conn.prepare(sql) else {
235        tracing::warn!("community: failed to prepare edge query");
236        return Vec::new();
237    };
238    let mut edges = Vec::new();
239    match stmt.query_map([], |row| {
240        Ok((
241            row.get::<_, String>(0)?,
242            row.get::<_, String>(1)?,
243            row.get::<_, String>(2)?,
244        ))
245    }) {
246        Ok(rows) => edges.extend(
247            rows.filter_map(std::result::Result::ok)
248                .map(|(a, b, kind)| (a, b, edge_weight(&kind))),
249        ),
250        Err(e) => tracing::warn!("community: edge query failed: {e}"),
251    }
252    edges
253}
lean_ctx/core/community/graph.rs

lean_ctx/core/community/
graph.rs
