trueno_graph/algorithms/
louvain.rs

1//! Louvain community detection algorithm
2//!
3//! Community detection for identifying code modules based on graph structure.
4//! Based on the Louvain method (Blondel et al., 2008) via aprender integration.
5//!
6//! # References
7//! - Blondel et al. (2008): "Fast unfolding of communities in large networks"
8//! - Girvan & Newman (2002): "Community structure in social and biological networks"
9
10use crate::{CsrGraph, NodeId};
11use anyhow::Result;
12use aprender::graph::Graph as AprenderGraph;
13
14/// Community detection result
15#[derive(Debug, Clone)]
16pub struct CommunityDetectionResult {
17    /// Communities, each containing a list of node IDs
18    pub communities: Vec<Vec<NodeId>>,
19
20    /// Total number of communities found
21    pub num_communities: usize,
22
23    /// Modularity score (quality metric for community structure)
24    pub modularity: f64,
25}
26
27impl CommunityDetectionResult {
28    /// Get the community ID for a given node
29    ///
30    /// Returns None if node not found in any community
31    #[must_use]
32    pub fn get_community(&self, node: NodeId) -> Option<usize> {
33        for (comm_id, community) in self.communities.iter().enumerate() {
34            if community.contains(&node) {
35                return Some(comm_id);
36            }
37        }
38        None
39    }
40
41    /// Get all nodes in a specific community
42    #[must_use]
43    pub fn get_community_nodes(&self, comm_id: usize) -> Option<&[NodeId]> {
44        self.communities.get(comm_id).map(Vec::as_slice)
45    }
46
47    /// Get size of a specific community
48    #[must_use]
49    pub fn community_size(&self, comm_id: usize) -> Option<usize> {
50        self.communities.get(comm_id).map(Vec::len)
51    }
52}
53
54/// Detect communities using the Louvain algorithm
55///
56/// The Louvain method is a greedy modularity optimization algorithm that:
57/// 1. Starts with each node in its own community
58/// 2. Iteratively moves nodes to neighboring communities to maximize modularity
59/// 3. Aggregates communities into super-nodes and repeats
60///
61/// # Arguments
62///
63/// * `graph` - The graph to analyze
64///
65/// # Returns
66///
67/// `CommunityDetectionResult` containing communities and modularity score
68///
69/// # Errors
70///
71/// Returns error if graph conversion fails (typically won't happen)
72///
73/// # Example
74///
75/// ```ignore
76/// # use trueno_graph::{CsrGraph, NodeId};
77/// # use trueno_graph::louvain;
78/// let mut graph = CsrGraph::new();
79/// graph.add_edge(NodeId(0), NodeId(1), 1.0)?;
80/// graph.add_edge(NodeId(1), NodeId(2), 1.0)?;
81/// graph.add_edge(NodeId(3), NodeId(4), 1.0)?; // Separate component
82///
83/// let result = louvain(&graph)?;
84/// println!("Found {} communities", result.num_communities);
85/// println!("Modularity: {:.3}", result.modularity);
86/// ```
87pub fn louvain(graph: &CsrGraph) -> Result<CommunityDetectionResult> {
88    // Convert trueno-graph CSR to aprender Graph
89    let aprender_graph = convert_to_aprender(graph);
90
91    // Run Louvain algorithm
92    let communities = aprender_graph.louvain();
93
94    // Calculate modularity
95    let modularity = aprender_graph.modularity(&communities);
96
97    // Convert aprender NodeId (usize) to trueno NodeId (u32)
98    let converted_communities: Vec<Vec<NodeId>> = communities
99        .into_iter()
100        .map(|community| {
101            community
102                .into_iter()
103                .filter_map(|node_id| u32::try_from(node_id).ok().map(NodeId))
104                .collect()
105        })
106        .filter(|community: &Vec<NodeId>| !community.is_empty()) // Remove empty communities
107        .collect();
108
109    let num_communities = converted_communities.len();
110
111    Ok(CommunityDetectionResult { communities: converted_communities, num_communities, modularity })
112}
113
114/// Convert `CsrGraph` to aprender `Graph` format
115fn convert_to_aprender(graph: &CsrGraph) -> AprenderGraph {
116    // Build edge list
117    let mut edges = Vec::new();
118
119    for (src, targets, weights) in graph.iter_adjacency() {
120        for (dst, weight) in targets.iter().zip(weights.iter()) {
121            edges.push((src.0 as usize, *dst as usize, f64::from(*weight)));
122        }
123    }
124
125    // Create undirected graph from edge list
126    AprenderGraph::from_weighted_edges(&edges, false)
127}
128
129#[cfg(test)]
130mod tests {
131    use super::*;
132
133    #[test]
134    fn test_louvain_empty_graph() {
135        let graph = CsrGraph::new();
136        let result = louvain(&graph).unwrap();
137
138        assert_eq!(result.num_communities, 0);
139        assert_eq!(result.communities.len(), 0);
140    }
141
142    #[test]
143    fn test_louvain_single_triangle() {
144        // Single triangle - should form one community
145        let mut graph = CsrGraph::new();
146        graph.add_edge(NodeId(0), NodeId(1), 1.0).unwrap();
147        graph.add_edge(NodeId(1), NodeId(2), 1.0).unwrap();
148        graph.add_edge(NodeId(2), NodeId(0), 1.0).unwrap();
149
150        let result = louvain(&graph).unwrap();
151
152        assert_eq!(result.num_communities, 1, "Triangle should form 1 community");
153
154        // All nodes should be in the same community
155        let comm_0 = result.get_community(NodeId(0));
156        let comm_1 = result.get_community(NodeId(1));
157        let comm_2 = result.get_community(NodeId(2));
158
159        assert_eq!(comm_0, comm_1);
160        assert_eq!(comm_1, comm_2);
161    }
162
163    #[test]
164    fn test_louvain_two_triangles_connected() {
165        // Two triangles with a single connecting edge
166        // Triangle 1: 0-1-2
167        // Triangle 2: 3-4-5
168        // Bridge: 2-3
169        let mut graph = CsrGraph::new();
170
171        // Triangle 1
172        graph.add_edge(NodeId(0), NodeId(1), 1.0).unwrap();
173        graph.add_edge(NodeId(1), NodeId(2), 1.0).unwrap();
174        graph.add_edge(NodeId(2), NodeId(0), 1.0).unwrap();
175
176        // Triangle 2
177        graph.add_edge(NodeId(3), NodeId(4), 1.0).unwrap();
178        graph.add_edge(NodeId(4), NodeId(5), 1.0).unwrap();
179        graph.add_edge(NodeId(5), NodeId(3), 1.0).unwrap();
180
181        // Bridge edge
182        graph.add_edge(NodeId(2), NodeId(3), 1.0).unwrap();
183
184        let result = louvain(&graph).unwrap();
185
186        // Should find 2 communities (one per triangle)
187        assert!(result.num_communities >= 1, "Should find at least 1 community");
188
189        // Modularity should be positive (indicates good community structure)
190        assert!(result.modularity > 0.0, "Modularity should be positive for community structure");
191    }
192
193    #[test]
194    fn test_louvain_disconnected_components() {
195        // Two completely disconnected triangles
196        // Triangle 1: 0-1-2
197        // Triangle 2: 3-4-5
198        let mut graph = CsrGraph::new();
199
200        // Triangle 1
201        graph.add_edge(NodeId(0), NodeId(1), 1.0).unwrap();
202        graph.add_edge(NodeId(1), NodeId(2), 1.0).unwrap();
203        graph.add_edge(NodeId(2), NodeId(0), 1.0).unwrap();
204
205        // Triangle 2
206        graph.add_edge(NodeId(3), NodeId(4), 1.0).unwrap();
207        graph.add_edge(NodeId(4), NodeId(5), 1.0).unwrap();
208        graph.add_edge(NodeId(5), NodeId(3), 1.0).unwrap();
209
210        let result = louvain(&graph).unwrap();
211
212        // Should find 2 communities (one per disconnected component)
213        assert_eq!(
214            result.num_communities, 2,
215            "Should find 2 communities for 2 disconnected components"
216        );
217
218        // Verify nodes 0,1,2 are in different community than 3,4,5
219        let comm_0 = result.get_community(NodeId(0));
220        let comm_3 = result.get_community(NodeId(3));
221
222        assert!(comm_0.is_some() && comm_3.is_some());
223        assert_ne!(comm_0, comm_3, "Disconnected components should be in different communities");
224    }
225
226    #[test]
227    fn test_community_detection_result_api() {
228        // Test CommunityDetectionResult helper methods
229        let result = CommunityDetectionResult {
230            communities: vec![vec![NodeId(0), NodeId(1), NodeId(2)], vec![NodeId(3), NodeId(4)]],
231            num_communities: 2,
232            modularity: 0.42,
233        };
234
235        // Test get_community
236        assert_eq!(result.get_community(NodeId(0)), Some(0));
237        assert_eq!(result.get_community(NodeId(3)), Some(1));
238        assert_eq!(result.get_community(NodeId(99)), None);
239
240        // Test get_community_nodes
241        assert_eq!(
242            result.get_community_nodes(0),
243            Some(&[NodeId(0), NodeId(1), NodeId(2)] as &[NodeId])
244        );
245        assert_eq!(result.get_community_nodes(1), Some(&[NodeId(3), NodeId(4)] as &[NodeId]));
246        assert_eq!(result.get_community_nodes(2), None);
247
248        // Test community_size
249        assert_eq!(result.community_size(0), Some(3));
250        assert_eq!(result.community_size(1), Some(2));
251        assert_eq!(result.community_size(2), None);
252    }
253
254    #[test]
255    fn test_louvain_all_nodes_assigned() {
256        // Verify every node gets assigned to exactly one community
257        let mut graph = CsrGraph::new();
258
259        // Create a simple graph: 0-1-2-3-4
260        graph.add_edge(NodeId(0), NodeId(1), 1.0).unwrap();
261        graph.add_edge(NodeId(1), NodeId(2), 1.0).unwrap();
262        graph.add_edge(NodeId(2), NodeId(3), 1.0).unwrap();
263        graph.add_edge(NodeId(3), NodeId(4), 1.0).unwrap();
264
265        let result = louvain(&graph).unwrap();
266
267        // Collect all assigned nodes
268        let mut assigned_nodes = std::collections::HashSet::new();
269        for community in &result.communities {
270            for &node in community {
271                assigned_nodes.insert(node);
272            }
273        }
274
275        // All 5 nodes should be assigned
276        assert_eq!(assigned_nodes.len(), 5);
277        assert!(assigned_nodes.contains(&NodeId(0)));
278        assert!(assigned_nodes.contains(&NodeId(1)));
279        assert!(assigned_nodes.contains(&NodeId(2)));
280        assert!(assigned_nodes.contains(&NodeId(3)));
281        assert!(assigned_nodes.contains(&NodeId(4)));
282    }
283}
trueno_graph/algorithms/louvain.rs

trueno_graph/algorithms/
louvain.rs
