1use std::cmp::Ordering;
4use std::collections::{BTreeMap, BTreeSet};
5
6use code_system_graph_model::{
7 Community, CommunityAlgorithm, CommunityChange, CommunityChangeKind, CommunityConfig, CommunityDelta, CommunityEdgeWeight, CommunityId, CommunityLabelEvidence, CommunityMetrics, CommunityScope, CommunitySnapshot, Edge, EdgeKind, EpistemicStatus, Node, NodeId, NodeKind, RepoId, stable_id
8};
9use thiserror::Error;
10
11const ENGINE_VERSION: &str = "1.0.0";
12const EPSILON: f64 = 1.0e-12;
13const PAGE_RANK_DAMPING: f64 = 0.85;
14const PAGE_RANK_ITERATIONS: usize = 64;
15const RELATED_OVERLAP: f64 = 0.25;
16const STABLE_OVERLAP: f64 = 0.80;
17const EDGE_KIND_COUNT: usize = 25;
18
19#[derive(Debug, Error, PartialEq)]
21pub enum CommunityError {
22 #[error("community resolution must be finite and positive, found {0}")]
24 InvalidResolution(f64),
25 #[error("community max_iterations must be in 1..=10_000, found {0}")]
27 InvalidMaxIterations(u32),
28 #[error("community minimum_confidence must be finite and in 0..=1, found {0}")]
30 InvalidMinimumConfidence(f32),
31 #[error("edge `{edge_id}` confidence must be finite and in 0..=1, found {confidence}")]
33 InvalidEdgeConfidence {
34 edge_id: String,
36 confidence: f32,
38 },
39 #[error("community edge weight for `{kind:?}` must be finite and non-negative, found {weight}")]
41 InvalidEdgeWeight {
42 kind: EdgeKind,
44 weight: f64,
46 },
47 #[error("community edge weight for `{0:?}` is configured more than once")]
49 DuplicateEdgeWeight(EdgeKind),
50 #[error("node identifier `{0}` occurs more than once")]
52 DuplicateNodeId(String),
53 #[error("service scope stable key `{0}` does not identify a service node")]
55 UnknownService(String),
56}
57
58#[derive(Debug, Clone)]
59struct AcceptedEdge {
60 source: usize,
61 target: usize,
62 weight: f64,
63}
64
65#[derive(Debug)]
66struct WeightedGraph {
67 nodes: Vec<Node>,
68 adjacency: Vec<BTreeMap<usize, f64>>,
69 accepted_edges: Vec<AcceptedEdge>,
70 weighted_degree: Vec<f64>,
71 neighbor_count: Vec<usize>,
72 total_undirected_weight: f64,
73}
74
75pub fn analyze_communities(
88 snapshot_id: impl Into<String>,
89 nodes: &[Node],
90 edges: &[Edge],
91 config: CommunityConfig,
92) -> Result<CommunitySnapshot, CommunityError> {
93 analyze_communities_with_progress(snapshot_id, nodes, edges, config, |_| {})
94}
95
96pub fn analyze_communities_with_progress<F>(
102 snapshot_id: impl Into<String>,
103 nodes: &[Node],
104 edges: &[Edge],
105 config: CommunityConfig,
106 mut progress: F,
107) -> Result<CommunitySnapshot, CommunityError>
108where
109 F: FnMut(u64),
110{
111 let weights = validate_inputs(nodes, edges, &config)?;
112 let selected = scoped_node_ids(nodes, edges, &config, &weights)?;
113 let graph = build_graph(nodes, edges, &config, &weights, &selected);
114 let assignments = match config.algorithm {
115 CommunityAlgorithm::ConnectedComponents => connected_components(&graph, &mut progress),
116 CommunityAlgorithm::WeightedClustering => {
117 weighted_label_propagation(&graph, config.seed, config.max_iterations, &mut progress)
118 }
119 CommunityAlgorithm::Louvain => louvain(
120 &graph,
121 config.seed,
122 config.resolution,
123 config.max_iterations,
124 &mut progress,
125 ),
126 };
127 let communities = describe_communities(&graph, &assignments);
128
129 Ok(CommunitySnapshot {
130 snapshot_id: snapshot_id.into(),
131 engine_version: ENGINE_VERSION.to_owned(),
132 config,
133 communities,
134 })
135}
136
137#[must_use]
144pub fn compare_community_snapshots(
145 before: &CommunitySnapshot,
146 after: &CommunitySnapshot,
147) -> CommunityDelta {
148 let overlaps = overlap_matrix(&before.communities, &after.communities);
149 let before_related =
150 related_after(&overlaps, before.communities.len(), after.communities.len());
151 let after_related =
152 related_before(&overlaps, before.communities.len(), after.communities.len());
153 let (mut changes, mut matched_before, mut matched_after) =
154 classify_structural_changes(before, after, &overlaps, &before_related, &after_related);
155 classify_pairwise_changes(
156 before,
157 after,
158 &overlaps,
159 &mut matched_before,
160 &mut matched_after,
161 &mut changes,
162 );
163 classify_unmatched(before, after, &matched_before, &matched_after, &mut changes);
164 changes.sort_by(compare_changes);
165 CommunityDelta {
166 before_snapshot_id: before.snapshot_id.clone(),
167 after_snapshot_id: after.snapshot_id.clone(),
168 changes,
169 }
170}
171
172fn classify_structural_changes(
173 before: &CommunitySnapshot,
174 after: &CommunitySnapshot,
175 overlaps: &BTreeMap<(usize, usize), f64>,
176 before_related: &[Vec<usize>],
177 after_related: &[Vec<usize>],
178) -> (Vec<CommunityChange>, BTreeSet<usize>, BTreeSet<usize>) {
179 let mut changes = Vec::new();
180 let mut matched_before = BTreeSet::new();
181 let mut matched_after = BTreeSet::new();
182 for (before_index, related) in before_related.iter().enumerate() {
183 if related.len() >= 2 {
184 matched_before.insert(before_index);
185 matched_after.extend(related.iter().copied());
186 changes.push(CommunityChange {
187 kind: CommunityChangeKind::Split,
188 before: vec![before.communities[before_index].id.clone()],
189 after: related
190 .iter()
191 .map(|index| after.communities[*index].id.clone())
192 .collect(),
193 overlap: maximum_overlap(overlaps, related, |index| (before_index, index)),
194 explanation: format!(
195 "One prior community overlaps {} successor communities at or above {:.2}.",
196 related.len(),
197 RELATED_OVERLAP
198 ),
199 });
200 }
201 }
202 for (after_index, related) in after_related.iter().enumerate() {
203 if related.len() >= 2 {
204 matched_after.insert(after_index);
205 matched_before.extend(related.iter().copied());
206 changes.push(CommunityChange {
207 kind: CommunityChangeKind::Merged,
208 before: related
209 .iter()
210 .map(|index| before.communities[*index].id.clone())
211 .collect(),
212 after: vec![after.communities[after_index].id.clone()],
213 overlap: maximum_overlap(overlaps, related, |index| (index, after_index)),
214 explanation: format!(
215 "{} prior communities overlap one successor at or above {:.2}.",
216 related.len(),
217 RELATED_OVERLAP
218 ),
219 });
220 }
221 }
222 (changes, matched_before, matched_after)
223}
224
225fn maximum_overlap(
226 overlaps: &BTreeMap<(usize, usize), f64>,
227 related: &[usize],
228 key: impl Fn(usize) -> (usize, usize),
229) -> f64 {
230 related
231 .iter()
232 .filter_map(|&index| overlaps.get(&key(index)).copied())
233 .fold(0.0, f64::max)
234}
235
236fn classify_pairwise_changes(
237 before: &CommunitySnapshot,
238 after: &CommunitySnapshot,
239 overlaps: &BTreeMap<(usize, usize), f64>,
240 matched_before: &mut BTreeSet<usize>,
241 matched_after: &mut BTreeSet<usize>,
242 changes: &mut Vec<CommunityChange>,
243) {
244 let mut candidates: Vec<(usize, usize, f64)> = overlaps
245 .iter()
246 .filter(|(_, overlap)| **overlap >= RELATED_OVERLAP)
247 .map(|(&(left, right), &overlap)| (left, right, overlap))
248 .collect();
249 candidates.sort_by(|left, right| {
250 right
251 .2
252 .total_cmp(&left.2)
253 .then_with(|| {
254 before.communities[left.0]
255 .id
256 .cmp(&before.communities[right.0].id)
257 })
258 .then_with(|| {
259 after.communities[left.1]
260 .id
261 .cmp(&after.communities[right.1].id)
262 })
263 });
264 for (before_index, after_index, overlap) in candidates {
265 if matched_before.contains(&before_index) || matched_after.contains(&after_index) {
266 continue;
267 }
268 matched_before.insert(before_index);
269 matched_after.insert(after_index);
270 if overlap + EPSILON < STABLE_OVERLAP {
271 changes.push(CommunityChange {
272 kind: CommunityChangeKind::MateriallyChanged,
273 before: vec![before.communities[before_index].id.clone()],
274 after: vec![after.communities[after_index].id.clone()],
275 overlap,
276 explanation: format!("Best one-to-one member overlap is {overlap:.3}, below the stable threshold {STABLE_OVERLAP:.2}."),
277 });
278 }
279 }
280}
281
282fn classify_unmatched(
283 before: &CommunitySnapshot,
284 after: &CommunitySnapshot,
285 matched_before: &BTreeSet<usize>,
286 matched_after: &BTreeSet<usize>,
287 changes: &mut Vec<CommunityChange>,
288) {
289 for (index, community) in before.communities.iter().enumerate() {
290 if !matched_before.contains(&index) {
291 changes.push(CommunityChange {
292 kind: CommunityChangeKind::Removed,
293 before: vec![community.id.clone()],
294 after: Vec::new(),
295 overlap: 0.0,
296 explanation: format!("No successor community reaches the related-overlap threshold {RELATED_OVERLAP:.2}."),
297 });
298 }
299 }
300 for (index, community) in after.communities.iter().enumerate() {
301 if !matched_after.contains(&index) {
302 changes.push(CommunityChange {
303 kind: CommunityChangeKind::Created,
304 before: Vec::new(),
305 after: vec![community.id.clone()],
306 overlap: 0.0,
307 explanation: format!(
308 "No prior community reaches the related-overlap threshold {RELATED_OVERLAP:.2}."
309 ),
310 });
311 }
312 }
313}
314
315fn validate_inputs(
316 nodes: &[Node],
317 edges: &[Edge],
318 config: &CommunityConfig,
319) -> Result<[f64; EDGE_KIND_COUNT], CommunityError> {
320 if !config.resolution.is_finite() || config.resolution <= 0.0 {
321 return Err(CommunityError::InvalidResolution(config.resolution));
322 }
323 if !(1..=10_000).contains(&config.max_iterations) {
324 return Err(CommunityError::InvalidMaxIterations(config.max_iterations));
325 }
326 if !config.minimum_confidence.is_finite() || !(0.0..=1.0).contains(&config.minimum_confidence) {
327 return Err(CommunityError::InvalidMinimumConfidence(
328 config.minimum_confidence,
329 ));
330 }
331 let mut node_ids = BTreeSet::new();
332 for node in nodes {
333 if !node_ids.insert(node.id.as_str()) {
334 return Err(CommunityError::DuplicateNodeId(node.id.as_str().to_owned()));
335 }
336 }
337 for edge in edges {
338 if !edge.confidence.is_finite() || !(0.0..=1.0).contains(&edge.confidence) {
339 return Err(CommunityError::InvalidEdgeConfidence {
340 edge_id: edge.id.as_str().to_owned(),
341 confidence: edge.confidence,
342 });
343 }
344 }
345
346 let mut weights = [1.0; EDGE_KIND_COUNT];
347 let mut configured = [false; EDGE_KIND_COUNT];
348 for CommunityEdgeWeight { kind, weight } in &config.edge_weights {
349 if !weight.is_finite() || *weight < 0.0 {
350 return Err(CommunityError::InvalidEdgeWeight {
351 kind: *kind,
352 weight: *weight,
353 });
354 }
355 let index = edge_kind_index(*kind);
356 if configured[index] {
357 return Err(CommunityError::DuplicateEdgeWeight(*kind));
358 }
359 configured[index] = true;
360 weights[index] = *weight;
361 }
362 Ok(weights)
363}
364
365fn scoped_node_ids(
366 nodes: &[Node],
367 edges: &[Edge],
368 config: &CommunityConfig,
369 weights: &[f64; EDGE_KIND_COUNT],
370) -> Result<BTreeSet<NodeId>, CommunityError> {
371 match &config.scope {
372 CommunityScope::Federated | CommunityScope::Workspace => {
373 Ok(nodes.iter().map(|node| node.id.clone()).collect())
374 }
375 CommunityScope::Repository(repo_id) => Ok(nodes
376 .iter()
377 .filter(|node| node.repo_id.as_ref() == Some(repo_id))
378 .map(|node| node.id.clone())
379 .collect()),
380 CommunityScope::Service(stable_key) => {
381 let services: BTreeSet<NodeId> = nodes
382 .iter()
383 .filter(|node| {
384 node.kind == NodeKind::Service && node.stable_key.as_str() == stable_key
385 })
386 .map(|node| node.id.clone())
387 .collect();
388 if services.is_empty() {
389 return Err(CommunityError::UnknownService(stable_key.clone()));
390 }
391 let known: BTreeSet<&str> = nodes.iter().map(|node| node.id.as_str()).collect();
392 let mut selected = services.clone();
393 for edge in edges {
394 if edge.status != EpistemicStatus::Confirmed
395 || edge.confidence < config.minimum_confidence
396 || weights[edge_kind_index(edge.kind)] <= 0.0
397 || !known.contains(edge.source.as_str())
398 || !known.contains(edge.target.as_str())
399 {
400 continue;
401 }
402 if services.contains(&edge.source) {
403 selected.insert(edge.target.clone());
404 }
405 if services.contains(&edge.target) {
406 selected.insert(edge.source.clone());
407 }
408 }
409 Ok(selected)
410 }
411 }
412}
413
414fn build_graph(
415 nodes: &[Node],
416 edges: &[Edge],
417 config: &CommunityConfig,
418 weights: &[f64; EDGE_KIND_COUNT],
419 selected: &BTreeSet<NodeId>,
420) -> WeightedGraph {
421 let mut graph_nodes: Vec<Node> = nodes
422 .iter()
423 .filter(|node| selected.contains(&node.id))
424 .cloned()
425 .collect();
426 graph_nodes.sort_by(|left, right| left.id.cmp(&right.id));
427 let index: BTreeMap<&str, usize> = graph_nodes
428 .iter()
429 .enumerate()
430 .map(|(position, node)| (node.id.as_str(), position))
431 .collect();
432 let mut ordered_edges: Vec<&Edge> = edges.iter().collect();
433 ordered_edges.sort_by(|left, right| {
434 left.source
435 .cmp(&right.source)
436 .then_with(|| left.target.cmp(&right.target))
437 .then_with(|| edge_kind_index(left.kind).cmp(&edge_kind_index(right.kind)))
438 .then_with(|| left.id.cmp(&right.id))
439 .then_with(|| left.confidence.total_cmp(&right.confidence))
440 });
441
442 let mut accepted_edges = Vec::new();
443 let mut undirected = BTreeMap::<(usize, usize), f64>::new();
444 for edge in ordered_edges {
445 if edge.status != EpistemicStatus::Confirmed || edge.confidence < config.minimum_confidence
446 {
447 continue;
448 }
449 let Some(&source) = index.get(edge.source.as_str()) else {
450 continue;
451 };
452 let Some(&target) = index.get(edge.target.as_str()) else {
453 continue;
454 };
455 let weight = weights[edge_kind_index(edge.kind)] * f64::from(edge.confidence);
456 if weight <= 0.0 {
457 continue;
458 }
459 accepted_edges.push(AcceptedEdge {
460 source,
461 target,
462 weight,
463 });
464 let pair = if source <= target {
465 (source, target)
466 } else {
467 (target, source)
468 };
469 *undirected.entry(pair).or_default() += weight;
470 }
471
472 let undirected_edges: Vec<(usize, usize, f64)> = undirected
473 .into_iter()
474 .map(|((source, target), weight)| (source, target, weight))
475 .collect();
476 let mut adjacency = vec![BTreeMap::new(); graph_nodes.len()];
477 let mut weighted_degree = vec![0.0; graph_nodes.len()];
478 let mut neighbors = vec![BTreeSet::new(); graph_nodes.len()];
479 let mut total_undirected_weight = 0.0;
480 for &(source, target, weight) in &undirected_edges {
481 total_undirected_weight += weight;
482 if source == target {
483 adjacency[source].insert(target, weight);
484 weighted_degree[source] += 2.0 * weight;
485 } else {
486 adjacency[source].insert(target, weight);
487 adjacency[target].insert(source, weight);
488 weighted_degree[source] += weight;
489 weighted_degree[target] += weight;
490 neighbors[source].insert(target);
491 neighbors[target].insert(source);
492 }
493 }
494 let neighbor_count = neighbors.into_iter().map(|items| items.len()).collect();
495 WeightedGraph {
496 nodes: graph_nodes,
497 adjacency,
498 accepted_edges,
499 weighted_degree,
500 neighbor_count,
501 total_undirected_weight,
502 }
503}
504
505fn connected_components<F>(graph: &WeightedGraph, progress: &mut F) -> Vec<usize>
506where
507 F: FnMut(u64),
508{
509 let mut assignments = vec![usize::MAX; graph.nodes.len()];
510 let mut component = 0;
511 for start in 0..graph.nodes.len() {
512 if assignments[start] != usize::MAX {
513 continue;
514 }
515 assignments[start] = component;
516 let mut pending = vec![start];
517 while let Some(node) = pending.pop() {
518 for (&neighbor, &weight) in &graph.adjacency[node] {
519 if weight > 0.0 && assignments[neighbor] == usize::MAX {
520 assignments[neighbor] = component;
521 pending.push(neighbor);
522 }
523 }
524 }
525 component += 1;
526 progress(1);
527 }
528 assignments
529}
530
531fn weighted_label_propagation<F>(
532 graph: &WeightedGraph,
533 seed: u64,
534 max_iterations: u32,
535 progress: &mut F,
536) -> Vec<usize>
537where
538 F: FnMut(u64),
539{
540 let mut assignments: Vec<usize> = (0..graph.nodes.len()).collect();
541 let order = seeded_node_order(graph, seed);
542 for _ in 0..max_iterations {
543 let mut changed = false;
544 for &node in &order {
545 let mut scores = BTreeMap::<usize, f64>::new();
546 for (&neighbor, &weight) in &graph.adjacency[node] {
547 if neighbor != node {
548 *scores.entry(assignments[neighbor]).or_default() += weight;
549 }
550 }
551 let current = assignments[node];
552 let current_score = scores.get(¤t).copied().unwrap_or_default();
553 let mut best = current;
554 let mut best_score = current_score;
555 for (candidate, score) in scores {
556 if score > best_score + EPSILON
557 || ((score - best_score).abs() <= EPSILON
558 && score > current_score + EPSILON
559 && seeded_label_key(graph, seed, candidate)
560 < seeded_label_key(graph, seed, best))
561 {
562 best = candidate;
563 best_score = score;
564 }
565 }
566 if best != current {
567 assignments[node] = best;
568 changed = true;
569 }
570 }
571 progress(1);
572 if !changed {
573 break;
574 }
575 }
576 assignments
577}
578
579fn louvain<F>(
584 graph: &WeightedGraph,
585 seed: u64,
586 resolution: f64,
587 max_iterations: u32,
588 progress: &mut F,
589) -> Vec<usize>
590where
591 F: FnMut(u64),
592{
593 let count = graph.nodes.len();
594 let mut assignments: Vec<usize> = (0..count).collect();
595 let total = graph.total_undirected_weight;
596 if total <= EPSILON {
597 return assignments;
598 }
599 let label_keys = (0..count)
600 .map(|label| seeded_label_key(graph, seed, label))
601 .collect::<Vec<_>>();
602 let mut community_degree = graph.weighted_degree.clone();
603 let mut members = vec![1_usize; count];
604 let mut empty = BTreeSet::new();
605 let order = seeded_node_order(graph, seed);
606 for _ in 0..max_iterations {
607 let mut changed = false;
608 for &node in &order {
609 let current = assignments[node];
610 let degree = graph.weighted_degree[node];
611 let mut links = BTreeMap::from([(current, 0.0)]);
612 for (&neighbor, &weight) in &graph.adjacency[node] {
613 if neighbor != node {
614 *links.entry(assignments[neighbor]).or_insert(0.0) += weight;
615 }
616 }
617 if let Some(&label) = empty.first() {
618 links.entry(label).or_insert(0.0);
619 }
620 let current_links = links[¤t];
621 let source_degree = community_degree[current] - degree;
622 let mut best = current;
623 let mut best_gain = 0.0;
624 for (&candidate, &candidate_links) in &links {
625 if candidate == current {
626 continue;
627 }
628 let gain = (candidate_links - current_links) / total
629 - resolution * degree * (community_degree[candidate] - source_degree)
630 / (2.0 * total * total);
631 if gain > best_gain + EPSILON
632 || ((gain - best_gain).abs() <= EPSILON
633 && gain > EPSILON
634 && label_keys[candidate] < label_keys[best])
635 {
636 best = candidate;
637 best_gain = gain;
638 }
639 }
640 if best != current && best_gain > EPSILON {
641 community_degree[current] -= degree;
642 community_degree[best] += degree;
643 members[current] -= 1;
644 members[best] += 1;
645 if members[current] == 0 {
646 empty.insert(current);
647 }
648 empty.remove(&best);
649 assignments[node] = best;
650 changed = true;
651 }
652 }
653 progress(1);
654 if !changed {
655 break;
656 }
657 }
658 assignments
659}
660
661fn seeded_node_order(graph: &WeightedGraph, seed: u64) -> Vec<usize> {
662 let mut order: Vec<usize> = (0..graph.nodes.len()).collect();
663 order.sort_by(|&left, &right| {
664 seeded_key(seed, graph.nodes[left].id.as_str())
665 .cmp(&seeded_key(seed, graph.nodes[right].id.as_str()))
666 .then_with(|| graph.nodes[left].id.cmp(&graph.nodes[right].id))
667 });
668 order
669}
670
671fn seeded_label_key(graph: &WeightedGraph, seed: u64, label: usize) -> String {
672 graph.nodes.get(label).map_or_else(
673 || stable_id("community-order", &format!("{seed}:empty:{label}")),
674 |node| seeded_key(seed, node.id.as_str()),
675 )
676}
677
678fn seeded_key(seed: u64, value: &str) -> String {
679 stable_id("community-order", &format!("{seed}:{value}"))
680}
681
682fn describe_communities(graph: &WeightedGraph, assignments: &[usize]) -> Vec<Community> {
683 let mut grouped = BTreeMap::<usize, Vec<usize>>::new();
684 for (node, &community) in assignments.iter().enumerate() {
685 grouped.entry(community).or_default().push(node);
686 }
687 let mut groups: Vec<Vec<usize>> = grouped.into_values().collect();
688 for members in &mut groups {
689 members.sort_by(|&left, &right| graph.nodes[left].id.cmp(&graph.nodes[right].id));
690 }
691 groups.sort_by(|left, right| compare_member_groups(graph, left, right));
692 let page_rank = weighted_page_rank(graph);
693 let god_nodes = detect_god_nodes(graph);
694
695 groups
696 .iter()
697 .map(|members| describe_community(graph, members, &page_rank, &god_nodes))
698 .collect()
699}
700
701fn describe_community(
702 graph: &WeightedGraph,
703 members: &[usize],
704 page_rank: &[f64],
705 god_nodes: &BTreeSet<usize>,
706) -> Community {
707 let member_set: BTreeSet<usize> = members.iter().copied().collect();
708 let central = central_nodes(graph, members, page_rank, god_nodes);
709 let (label, label_evidence) = structural_label(graph, members, ¢ral);
710 let mut repositories = BTreeSet::<RepoId>::new();
711 let mut services = BTreeSet::<NodeId>::new();
712 for &member in members {
713 if let Some(repo_id) = &graph.nodes[member].repo_id {
714 repositories.insert(repo_id.clone());
715 }
716 if graph.nodes[member].kind == NodeKind::Service {
717 services.insert(graph.nodes[member].id.clone());
718 }
719 }
720 let mut inbound_contracts = BTreeSet::new();
721 let mut outbound_contracts = BTreeSet::new();
722 let mut cohesion = 0.0;
723 let mut coupling = 0.0;
724 let mut cross_community_edges = 0;
725 let mut internal_pairs = BTreeSet::new();
726 for edge in &graph.accepted_edges {
727 let source_inside = member_set.contains(&edge.source);
728 let target_inside = member_set.contains(&edge.target);
729 if source_inside && target_inside {
730 cohesion += edge.weight;
731 if edge.source != edge.target {
732 internal_pairs.insert((edge.source, edge.target));
733 }
734 } else if source_inside || target_inside {
735 coupling += edge.weight;
736 cross_community_edges += 1;
737 if target_inside && is_contract_kind(graph.nodes[edge.target].kind) {
738 inbound_contracts.insert(graph.nodes[edge.target].id.clone());
739 }
740 if source_inside && is_contract_kind(graph.nodes[edge.source].kind) {
741 outbound_contracts.insert(graph.nodes[edge.source].id.clone());
742 }
743 }
744 }
745 let possible = members
746 .len()
747 .saturating_mul(members.len().saturating_sub(1));
748 let density = if possible == 0 {
749 0.0
750 } else {
751 usize_to_f64(internal_pairs.len()) / usize_to_f64(possible)
752 };
753 let mut limitations = Vec::new();
754 if members.len() == 1 {
755 limitations
756 .push("Community contains a single node; structural metrics are limited.".to_owned());
757 }
758 for &node in members {
759 if god_nodes.contains(&node) {
760 limitations.push(format!(
761 "High-degree god node `{}` may dominate community structure.",
762 graph.nodes[node].id.as_str()
763 ));
764 }
765 }
766 if cohesion <= EPSILON {
767 limitations.push("Community has no positive internal accepted edge weight.".to_owned());
768 }
769 limitations.sort();
770 let member_ids: Vec<NodeId> = members
771 .iter()
772 .map(|&member| graph.nodes[member].id.clone())
773 .collect();
774 let canonical_members = member_ids
775 .iter()
776 .map(|id| format!("{}:{}", id.as_str().len(), id.as_str()))
777 .collect::<Vec<_>>()
778 .join("|");
779
780 Community {
781 id: CommunityId::new(stable_id("community", &canonical_members)),
782 label,
783 members: member_ids,
784 central_nodes: central
785 .into_iter()
786 .map(|node| graph.nodes[node].id.clone())
787 .collect(),
788 repositories: repositories.into_iter().collect(),
789 services: services.into_iter().collect(),
790 inbound_contracts: inbound_contracts.into_iter().collect(),
791 outbound_contracts: outbound_contracts.into_iter().collect(),
792 metrics: CommunityMetrics {
793 size: members.len(),
794 density,
795 cohesion,
796 coupling,
797 cross_community_edges,
798 },
799 label_evidence,
800 limitations,
801 }
802}
803
804fn weighted_page_rank(graph: &WeightedGraph) -> Vec<f64> {
805 let count = graph.nodes.len();
806 if count == 0 {
807 return Vec::new();
808 }
809 let count_f64 = usize_to_f64(count);
810 let mut ranks = vec![1.0 / count_f64; count];
811 let mut outgoing = vec![0.0; count];
812 for edge in &graph.accepted_edges {
813 outgoing[edge.source] += edge.weight;
814 }
815 for _ in 0..PAGE_RANK_ITERATIONS {
816 let dangling: f64 = ranks
817 .iter()
818 .enumerate()
819 .filter(|(node, _)| outgoing[*node] <= EPSILON)
820 .map(|(_, rank)| *rank)
821 .sum();
822 let base = (1.0 - PAGE_RANK_DAMPING) / count_f64 + PAGE_RANK_DAMPING * dangling / count_f64;
823 let mut next = vec![base; count];
824 for edge in &graph.accepted_edges {
825 if outgoing[edge.source] > EPSILON {
826 next[edge.target] +=
827 PAGE_RANK_DAMPING * ranks[edge.source] * edge.weight / outgoing[edge.source];
828 }
829 }
830 ranks = next;
831 }
832 ranks
833}
834
835fn detect_god_nodes(graph: &WeightedGraph) -> BTreeSet<usize> {
836 if graph.nodes.len() < 4 {
837 return BTreeSet::new();
838 }
839 let mut degrees = graph.neighbor_count.clone();
840 degrees.sort_unstable();
841 let median = degrees[degrees.len() / 2];
842 let majority = graph.nodes.len().div_ceil(2);
843 graph
844 .neighbor_count
845 .iter()
846 .enumerate()
847 .filter(|(_, degree)| **degree >= majority && **degree >= median.saturating_mul(2).max(3))
848 .map(|(node, _)| node)
849 .collect()
850}
851
852fn central_nodes(
853 graph: &WeightedGraph,
854 members: &[usize],
855 page_rank: &[f64],
856 god_nodes: &BTreeSet<usize>,
857) -> Vec<usize> {
858 let maximum_degree = members
859 .iter()
860 .map(|&node| graph.weighted_degree[node])
861 .fold(0.0, f64::max);
862 let mut central = members.to_vec();
863 central.sort_by(|&left, &right| {
864 god_nodes
865 .contains(&right)
866 .cmp(&god_nodes.contains(&left))
867 .then_with(|| {
868 let left_score =
869 centrality_score(page_rank[left], graph.weighted_degree[left], maximum_degree);
870 let right_score = centrality_score(
871 page_rank[right],
872 graph.weighted_degree[right],
873 maximum_degree,
874 );
875 right_score.total_cmp(&left_score)
876 })
877 .then_with(|| graph.nodes[left].id.cmp(&graph.nodes[right].id))
878 });
879 central.truncate(3);
880 central
881}
882
883fn centrality_score(page_rank: f64, weighted_degree: f64, maximum_degree: f64) -> f64 {
884 let normalized_degree = if maximum_degree <= EPSILON {
885 0.0
886 } else {
887 weighted_degree / maximum_degree
888 };
889 0.65 * page_rank + 0.35 * normalized_degree
890}
891
892fn structural_label(
893 graph: &WeightedGraph,
894 members: &[usize],
895 central: &[usize],
896) -> (String, Vec<CommunityLabelEvidence>) {
897 let central_set: BTreeSet<usize> = central.iter().copied().collect();
898 let mut terms = BTreeMap::<String, (u32, NodeId, u32)>::new();
899 for &member in members {
900 let node = &graph.nodes[member];
901 let category_score = match node.kind {
902 NodeKind::Service => 400,
903 NodeKind::Repository => 300,
904 kind if is_contract_kind(kind) => 200,
905 _ => 0,
906 };
907 let central_score = if central_set.contains(&member) {
908 100
909 } else {
910 0
911 };
912 let score = category_score + central_score;
913 if score == 0 {
914 continue;
915 }
916 let mut node_terms = normalized_terms(&node.label);
917 node_terms.extend(normalized_terms(&node.stable_key));
918 for term in node_terms {
919 let entry = terms.entry(term).or_insert_with(|| (0, node.id.clone(), 0));
920 entry.0 = entry.0.saturating_add(score);
921 if score > entry.2 || (score == entry.2 && node.id < entry.1) {
922 entry.1 = node.id.clone();
923 entry.2 = score;
924 }
925 }
926 }
927 let mut ranked: Vec<(String, u32, NodeId)> = terms
928 .into_iter()
929 .map(|(term, (score, node_id, _))| (term, score, node_id))
930 .collect();
931 ranked.sort_by(|left, right| {
932 right
933 .1
934 .cmp(&left.1)
935 .then_with(|| left.0.cmp(&right.0))
936 .then_with(|| left.2.cmp(&right.2))
937 });
938 ranked.truncate(3);
939 if ranked.is_empty() {
940 let fallback = members
941 .first()
942 .map_or("community", |&member| graph.nodes[member].label.as_str());
943 return (format!("Community: {fallback}"), Vec::new());
944 }
945 let label = ranked
946 .iter()
947 .map(|(term, _, _)| title_case(term))
948 .collect::<Vec<_>>()
949 .join(" / ");
950 let evidence = ranked
951 .into_iter()
952 .map(|(term, _, node_id)| CommunityLabelEvidence { node_id, term })
953 .collect();
954 (label, evidence)
955}
956
957fn normalized_terms(value: &str) -> BTreeSet<String> {
958 value
959 .split(|character: char| !character.is_alphanumeric())
960 .map(str::to_lowercase)
961 .filter(|term| {
962 (3..=32).contains(&term.len())
963 && term.chars().any(char::is_alphabetic)
964 && !is_stop_term(term)
965 })
966 .collect()
967}
968
969fn is_stop_term(term: &str) -> bool {
970 matches!(
971 term,
972 "api"
973 | "app"
974 | "application"
975 | "artifact"
976 | "community"
977 | "default"
978 | "http"
979 | "https"
980 | "operation"
981 | "repo"
982 | "repository"
983 | "rpc"
984 | "service"
985 | "src"
986 | "test"
987 | "tests"
988 | "version"
989 )
990}
991
992fn title_case(term: &str) -> String {
993 let mut characters = term.chars();
994 characters.next().map_or_else(String::new, |first| {
995 first.to_uppercase().collect::<String>() + characters.as_str()
996 })
997}
998
999fn is_contract_kind(kind: NodeKind) -> bool {
1000 matches!(
1001 kind,
1002 NodeKind::HttpOperation
1003 | NodeKind::GraphqlOperation
1004 | NodeKind::RpcMethod
1005 | NodeKind::EventChannel
1006 | NodeKind::EventSchema
1007 | NodeKind::Database
1008 | NodeKind::DatabaseTable
1009 )
1010}
1011
1012fn compare_member_groups(graph: &WeightedGraph, left: &[usize], right: &[usize]) -> Ordering {
1013 left.iter()
1014 .map(|&node| graph.nodes[node].id.as_str())
1015 .cmp(right.iter().map(|&node| graph.nodes[node].id.as_str()))
1016}
1017
1018fn overlap_matrix(before: &[Community], after: &[Community]) -> BTreeMap<(usize, usize), f64> {
1019 let mut overlaps = BTreeMap::new();
1020 for (before_index, old) in before.iter().enumerate() {
1021 let old_members: BTreeSet<&str> = old.members.iter().map(NodeId::as_str).collect();
1022 for (after_index, new) in after.iter().enumerate() {
1023 let new_members: BTreeSet<&str> = new.members.iter().map(NodeId::as_str).collect();
1024 let intersection = old_members.intersection(&new_members).count();
1025 let union = old_members.union(&new_members).count();
1026 let overlap = if union == 0 {
1027 1.0
1028 } else {
1029 usize_to_f64(intersection) / usize_to_f64(union)
1030 };
1031 overlaps.insert((before_index, after_index), overlap);
1032 }
1033 }
1034 overlaps
1035}
1036
1037fn related_after(
1038 overlaps: &BTreeMap<(usize, usize), f64>,
1039 before_count: usize,
1040 after_count: usize,
1041) -> Vec<Vec<usize>> {
1042 (0..before_count)
1043 .map(|before| {
1044 (0..after_count)
1045 .filter(|after| {
1046 overlaps
1047 .get(&(before, *after))
1048 .is_some_and(|overlap| *overlap >= RELATED_OVERLAP)
1049 })
1050 .collect()
1051 })
1052 .collect()
1053}
1054
1055fn related_before(
1056 overlaps: &BTreeMap<(usize, usize), f64>,
1057 before_count: usize,
1058 after_count: usize,
1059) -> Vec<Vec<usize>> {
1060 (0..after_count)
1061 .map(|after| {
1062 (0..before_count)
1063 .filter(|before| {
1064 overlaps
1065 .get(&(*before, after))
1066 .is_some_and(|overlap| *overlap >= RELATED_OVERLAP)
1067 })
1068 .collect()
1069 })
1070 .collect()
1071}
1072
1073fn compare_changes(left: &CommunityChange, right: &CommunityChange) -> Ordering {
1074 change_kind_index(left.kind)
1075 .cmp(&change_kind_index(right.kind))
1076 .then_with(|| left.before.cmp(&right.before))
1077 .then_with(|| left.after.cmp(&right.after))
1078 .then_with(|| left.overlap.total_cmp(&right.overlap))
1079 .then_with(|| left.explanation.cmp(&right.explanation))
1080}
1081
1082const fn change_kind_index(kind: CommunityChangeKind) -> usize {
1083 match kind {
1084 CommunityChangeKind::Created => 0,
1085 CommunityChangeKind::Removed => 1,
1086 CommunityChangeKind::Split => 2,
1087 CommunityChangeKind::Merged => 3,
1088 CommunityChangeKind::MateriallyChanged => 4,
1089 }
1090}
1091
1092const fn edge_kind_index(kind: EdgeKind) -> usize {
1093 match kind {
1094 EdgeKind::Contains => 0,
1095 EdgeKind::Provides => 1,
1096 EdgeKind::Consumes => 2,
1097 EdgeKind::CallsRemote => 3,
1098 EdgeKind::Publishes => 4,
1099 EdgeKind::Subscribes => 5,
1100 EdgeKind::DeliversTo => 6,
1101 EdgeKind::DependsOnPackage => 7,
1102 EdgeKind::DependsOnRepository => 8,
1103 EdgeKind::ReadsTable => 9,
1104 EdgeKind::WritesTable => 10,
1105 EdgeKind::Deploys => 11,
1106 EdgeKind::Configures => 12,
1107 EdgeKind::Documents => 13,
1108 EdgeKind::OwnedBy => 14,
1109 EdgeKind::ImplementedBy => 15,
1110 EdgeKind::Validates => 16,
1111 EdgeKind::ChangedIn => 17,
1112 EdgeKind::Affects => 18,
1113 EdgeKind::Precedes => 19,
1114 EdgeKind::Reverts => 20,
1115 EdgeKind::CompatibleWith => 21,
1116 EdgeKind::IncompatibleWith => 22,
1117 EdgeKind::MemberOf => 23,
1118 EdgeKind::ManualLink => 24,
1119 }
1120}
1121
1122#[expect(
1123 clippy::cast_precision_loss,
1124 reason = "graph cardinalities are bounded by addressable memory and only form normalized metrics"
1125)]
1126fn usize_to_f64(value: usize) -> f64 {
1127 value as f64
1128}
1129
1130#[cfg(test)]
1131mod tests {
1132 use code_system_graph_model::{EdgeId, NodeId};
1133
1134 use super::*;
1135
1136 fn node(id: &str, kind: NodeKind, repo: &str, label: &str) -> Node {
1137 Node {
1138 id: NodeId::new(id),
1139 kind,
1140 repo_id: Some(RepoId::new(repo)),
1141 stable_key: format!("stable:{label}"),
1142 label: label.to_owned(),
1143 }
1144 }
1145
1146 fn edge(id: &str, source: &str, target: &str, kind: EdgeKind, confidence: f32) -> Edge {
1147 Edge {
1148 id: EdgeId::new(id),
1149 source: NodeId::new(source),
1150 target: NodeId::new(target),
1151 kind,
1152 confidence,
1153 status: EpistemicStatus::Confirmed,
1154 evidence: Vec::new(),
1155 }
1156 }
1157
1158 fn config(algorithm: CommunityAlgorithm) -> CommunityConfig {
1159 CommunityConfig {
1160 algorithm,
1161 scope: CommunityScope::Federated,
1162 seed: 17,
1163 resolution: 1.0,
1164 minimum_confidence: 0.0,
1165 edge_weights: Vec::new(),
1166 max_iterations: 100,
1167 }
1168 }
1169
1170 fn two_cluster_graph() -> (Vec<Node>, Vec<Edge>) {
1171 let nodes = ["a", "b", "c", "d", "e", "f"]
1172 .into_iter()
1173 .map(|id| node(id, NodeKind::Service, "repo:one", id))
1174 .collect();
1175 let mut edges = Vec::new();
1176 let mut number = 0;
1177 for cluster in [["a", "b", "c"], ["d", "e", "f"]] {
1178 for source in cluster {
1179 for target in cluster {
1180 if source != target {
1181 edges.push(edge(
1182 &format!("e{number}"),
1183 source,
1184 target,
1185 EdgeKind::CallsRemote,
1186 1.0,
1187 ));
1188 number += 1;
1189 }
1190 }
1191 }
1192 }
1193 edges.push(edge("bridge", "c", "d", EdgeKind::ManualLink, 1.0));
1194 (nodes, edges)
1195 }
1196
1197 #[test]
1198 fn connected_components_should_return_maximal_regions() {
1199 let nodes = vec![
1200 node("a", NodeKind::Service, "repo:one", "alpha"),
1201 node("b", NodeKind::HttpOperation, "repo:one", "alpha endpoint"),
1202 node("c", NodeKind::Service, "repo:two", "beta"),
1203 ];
1204 let edges = vec![edge("ab", "a", "b", EdgeKind::Provides, 1.0)];
1205
1206 let result = analyze_communities(
1207 "snapshot",
1208 &nodes,
1209 &edges,
1210 config(CommunityAlgorithm::ConnectedComponents),
1211 )
1212 .expect("analysis should succeed");
1213
1214 assert_eq!(
1215 result
1216 .communities
1217 .iter()
1218 .map(|community| community.metrics.size)
1219 .collect::<Vec<_>>(),
1220 vec![2, 1]
1221 );
1222 }
1223
1224 #[test]
1225 fn weighted_clustering_should_respect_relationship_weights() {
1226 let (nodes, edges) = two_cluster_graph();
1227 let mut analysis_config = config(CommunityAlgorithm::WeightedClustering);
1228 analysis_config.edge_weights.push(CommunityEdgeWeight {
1229 kind: EdgeKind::ManualLink,
1230 weight: 0.01,
1231 });
1232
1233 let result = analyze_communities("snapshot", &nodes, &edges, analysis_config)
1234 .expect("analysis should succeed");
1235
1236 assert_eq!(result.communities.len(), 2);
1237 }
1238
1239 #[test]
1240 fn louvain_should_optimize_modularity_into_weighted_clusters() {
1241 let (nodes, edges) = two_cluster_graph();
1242 let mut analysis_config = config(CommunityAlgorithm::Louvain);
1243 analysis_config.edge_weights.push(CommunityEdgeWeight {
1244 kind: EdgeKind::ManualLink,
1245 weight: 0.05,
1246 });
1247
1248 let result = analyze_communities("snapshot", &nodes, &edges, analysis_config)
1249 .expect("analysis should succeed");
1250
1251 assert_eq!(result.communities.len(), 2);
1252 }
1253
1254 #[test]
1255 fn seeded_analysis_should_be_byte_reproducible() {
1256 let (mut nodes, mut edges) = two_cluster_graph();
1257 let analysis_config = config(CommunityAlgorithm::Louvain);
1258 let first = analyze_communities("snapshot", &nodes, &edges, analysis_config.clone())
1259 .expect("first analysis should succeed");
1260 nodes.reverse();
1261 edges.reverse();
1262 let second = analyze_communities("snapshot", &nodes, &edges, analysis_config)
1263 .expect("second analysis should succeed");
1264
1265 assert_eq!(
1266 serde_json::to_vec(&first).expect("snapshot should serialize"),
1267 serde_json::to_vec(&second).expect("snapshot should serialize")
1268 );
1269 }
1270
1271 #[test]
1272 fn repository_scope_should_exclude_other_repositories() {
1273 let nodes = vec![
1274 node("a", NodeKind::Service, "repo:one", "alpha"),
1275 node("b", NodeKind::Artifact, "repo:one", "alpha manifest"),
1276 node("c", NodeKind::Service, "repo:two", "beta"),
1277 ];
1278 let edges = vec![
1279 edge("ab", "a", "b", EdgeKind::Contains, 1.0),
1280 edge("ac", "a", "c", EdgeKind::CallsRemote, 1.0),
1281 ];
1282 let mut analysis_config = config(CommunityAlgorithm::ConnectedComponents);
1283 analysis_config.scope = CommunityScope::Repository(RepoId::new("repo:one"));
1284
1285 let result = analyze_communities("snapshot", &nodes, &edges, analysis_config)
1286 .expect("analysis should succeed");
1287
1288 assert_eq!(result.communities[0].members.len(), 2);
1289 }
1290
1291 #[test]
1292 fn service_scope_should_include_only_directly_attached_nodes() {
1293 let mut service = node("service", NodeKind::Service, "repo:one", "billing");
1294 service.stable_key = "service:billing".to_owned();
1295 let nodes = vec![
1296 service,
1297 node("contract", NodeKind::HttpOperation, "repo:one", "charge"),
1298 node("indirect", NodeKind::Artifact, "repo:one", "schema"),
1299 ];
1300 let edges = vec![
1301 edge("first", "service", "contract", EdgeKind::Provides, 1.0),
1302 edge("second", "contract", "indirect", EdgeKind::Contains, 1.0),
1303 ];
1304 let mut analysis_config = config(CommunityAlgorithm::ConnectedComponents);
1305 analysis_config.scope = CommunityScope::Service("service:billing".to_owned());
1306
1307 let result = analyze_communities("snapshot", &nodes, &edges, analysis_config)
1308 .expect("analysis should succeed");
1309
1310 assert_eq!(
1311 result.communities[0].members,
1312 vec![NodeId::new("contract"), NodeId::new("service")]
1313 );
1314 }
1315
1316 #[test]
1317 fn metrics_should_report_cohesion_density_and_cross_coupling() {
1318 let (nodes, edges) = two_cluster_graph();
1319 let mut analysis_config = config(CommunityAlgorithm::Louvain);
1320 analysis_config.edge_weights.push(CommunityEdgeWeight {
1321 kind: EdgeKind::ManualLink,
1322 weight: 0.05,
1323 });
1324
1325 let result = analyze_communities("snapshot", &nodes, &edges, analysis_config)
1326 .expect("analysis should succeed");
1327 let first = &result.communities[0];
1328
1329 assert!(
1330 (first.metrics.density - 1.0).abs() <= EPSILON
1331 && first.metrics.cohesion > first.metrics.coupling
1332 && first.metrics.cross_community_edges == 1
1333 );
1334 }
1335
1336 #[test]
1337 fn labels_should_prefer_service_and_contract_terms_with_evidence() {
1338 let nodes = vec![
1339 node("service", NodeKind::Service, "repo:one", "Billing Gateway"),
1340 node(
1341 "contract",
1342 NodeKind::HttpOperation,
1343 "repo:one",
1344 "Create Invoice",
1345 ),
1346 ];
1347 let edges = vec![edge(
1348 "provides",
1349 "service",
1350 "contract",
1351 EdgeKind::Provides,
1352 1.0,
1353 )];
1354
1355 let result = analyze_communities(
1356 "snapshot",
1357 &nodes,
1358 &edges,
1359 config(CommunityAlgorithm::ConnectedComponents),
1360 )
1361 .expect("analysis should succeed");
1362
1363 assert!(
1364 result.communities[0].label.contains("Billing")
1365 && !result.communities[0].label_evidence.is_empty()
1366 );
1367 }
1368
1369 #[test]
1370 fn god_nodes_should_be_central_and_disclosed() {
1371 let mut nodes = vec![node("hub", NodeKind::Service, "repo:one", "gateway")];
1372 let mut edges = Vec::new();
1373 for index in 0..5 {
1374 let leaf = format!("leaf-{index}");
1375 nodes.push(node(&leaf, NodeKind::Artifact, "repo:one", &leaf));
1376 edges.push(edge(
1377 &format!("edge-{index}"),
1378 "hub",
1379 &leaf,
1380 EdgeKind::Contains,
1381 1.0,
1382 ));
1383 }
1384
1385 let result = analyze_communities(
1386 "snapshot",
1387 &nodes,
1388 &edges,
1389 config(CommunityAlgorithm::ConnectedComponents),
1390 )
1391 .expect("analysis should succeed");
1392
1393 assert!(
1394 result.communities[0].central_nodes[0] == NodeId::new("hub")
1395 && result.communities[0]
1396 .limitations
1397 .iter()
1398 .any(|limitation| limitation.contains("god node"))
1399 );
1400 }
1401
1402 fn community(id: &str, members: &[&str]) -> Community {
1403 Community {
1404 id: CommunityId::new(id),
1405 label: id.to_owned(),
1406 members: members.iter().map(|member| NodeId::new(*member)).collect(),
1407 central_nodes: Vec::new(),
1408 repositories: Vec::new(),
1409 services: Vec::new(),
1410 inbound_contracts: Vec::new(),
1411 outbound_contracts: Vec::new(),
1412 metrics: CommunityMetrics {
1413 size: members.len(),
1414 density: 0.0,
1415 cohesion: 0.0,
1416 coupling: 0.0,
1417 cross_community_edges: 0,
1418 },
1419 label_evidence: Vec::new(),
1420 limitations: Vec::new(),
1421 }
1422 }
1423
1424 fn snapshot(id: &str, communities: Vec<Community>) -> CommunitySnapshot {
1425 CommunitySnapshot {
1426 snapshot_id: id.to_owned(),
1427 engine_version: ENGINE_VERSION.to_owned(),
1428 config: config(CommunityAlgorithm::ConnectedComponents),
1429 communities,
1430 }
1431 }
1432
1433 #[test]
1434 fn comparison_should_classify_created_community() {
1435 let before = snapshot("before", Vec::new());
1436 let after = snapshot("after", vec![community("new", &["a"])]);
1437
1438 let delta = compare_community_snapshots(&before, &after);
1439
1440 assert_eq!(delta.changes[0].kind, CommunityChangeKind::Created);
1441 }
1442
1443 #[test]
1444 fn comparison_should_classify_removed_community() {
1445 let before = snapshot("before", vec![community("old", &["a"])]);
1446 let after = snapshot("after", Vec::new());
1447
1448 let delta = compare_community_snapshots(&before, &after);
1449
1450 assert_eq!(delta.changes[0].kind, CommunityChangeKind::Removed);
1451 }
1452
1453 #[test]
1454 fn comparison_should_classify_split_community() {
1455 let before = snapshot("before", vec![community("old", &["a", "b", "c", "d"])]);
1456 let after = snapshot(
1457 "after",
1458 vec![
1459 community("left", &["a", "b"]),
1460 community("right", &["c", "d"]),
1461 ],
1462 );
1463
1464 let delta = compare_community_snapshots(&before, &after);
1465
1466 assert_eq!(delta.changes[0].kind, CommunityChangeKind::Split);
1467 }
1468
1469 #[test]
1470 fn comparison_should_classify_merged_community() {
1471 let before = snapshot(
1472 "before",
1473 vec![
1474 community("left", &["a", "b"]),
1475 community("right", &["c", "d"]),
1476 ],
1477 );
1478 let after = snapshot("after", vec![community("new", &["a", "b", "c", "d"])]);
1479
1480 let delta = compare_community_snapshots(&before, &after);
1481
1482 assert_eq!(delta.changes[0].kind, CommunityChangeKind::Merged);
1483 }
1484
1485 #[test]
1486 fn comparison_should_classify_materially_changed_community() {
1487 let before = snapshot("before", vec![community("old", &["a", "b", "c", "d"])]);
1488 let after = snapshot("after", vec![community("new", &["a", "b", "c", "e"])]);
1489
1490 let delta = compare_community_snapshots(&before, &after);
1491
1492 assert_eq!(
1493 delta.changes[0].kind,
1494 CommunityChangeKind::MateriallyChanged
1495 );
1496 }
1497
1498 #[test]
1499 fn validation_should_reject_non_finite_confidence() {
1500 let nodes = vec![
1501 node("a", NodeKind::Service, "repo:one", "alpha"),
1502 node("b", NodeKind::Service, "repo:one", "beta"),
1503 ];
1504 let edges = vec![edge("invalid", "a", "b", EdgeKind::CallsRemote, f32::NAN)];
1505
1506 let error = analyze_communities(
1507 "snapshot",
1508 &nodes,
1509 &edges,
1510 config(CommunityAlgorithm::ConnectedComponents),
1511 )
1512 .expect_err("invalid confidence should fail");
1513
1514 assert!(matches!(
1515 error,
1516 CommunityError::InvalidEdgeConfidence { .. }
1517 ));
1518 }
1519
1520 fn modularity(graph: &WeightedGraph, assignments: &[usize], resolution: f64) -> f64 {
1523 let total = graph.total_undirected_weight;
1524 if total <= EPSILON {
1525 return 0.0;
1526 }
1527 let mut internal = BTreeMap::<usize, f64>::new();
1528 let mut degree = BTreeMap::<usize, f64>::new();
1529 for (node, &community) in assignments.iter().enumerate() {
1530 *degree.entry(community).or_default() += graph.weighted_degree[node];
1531 }
1532 for (source, neighbors) in graph.adjacency.iter().enumerate() {
1533 for (&target, &weight) in neighbors.range(source..) {
1534 if assignments[source] == assignments[target] {
1535 *internal.entry(assignments[source]).or_default() += weight;
1536 }
1537 }
1538 }
1539 degree
1540 .into_iter()
1541 .map(|(community, community_degree)| {
1542 let inside = internal.get(&community).copied().unwrap_or_default();
1543 inside / total - resolution * (community_degree / (2.0 * total)).powi(2)
1544 })
1545 .sum()
1546 }
1547
1548 fn first_empty_label(assignments: &[usize]) -> Option<usize> {
1549 let mut used = vec![false; assignments.len()];
1550 for &assignment in assignments {
1551 if let Some(slot) = used.get_mut(assignment) {
1552 *slot = true;
1553 }
1554 }
1555 used.iter().position(|value| !value)
1556 }
1557
1558 fn reference_louvain(
1560 graph: &WeightedGraph,
1561 seed: u64,
1562 resolution: f64,
1563 max_iterations: u32,
1564 ) -> Vec<usize> {
1565 let mut assignments: Vec<usize> = (0..graph.nodes.len()).collect();
1566 if graph.total_undirected_weight <= EPSILON {
1567 return assignments;
1568 }
1569 let order = seeded_node_order(graph, seed);
1570 for _ in 0..max_iterations {
1571 let mut changed = false;
1572 for &node in &order {
1573 let current = assignments[node];
1574 let baseline = modularity(graph, &assignments, resolution);
1575 let mut candidates = BTreeSet::from([current]);
1576 for &neighbor in graph.adjacency[node].keys() {
1577 candidates.insert(assignments[neighbor]);
1578 }
1579 if let Some(empty) = first_empty_label(&assignments) {
1580 candidates.insert(empty);
1581 }
1582 let mut best = current;
1583 let mut best_modularity = baseline;
1584 for candidate in candidates {
1585 if candidate == current {
1586 continue;
1587 }
1588 assignments[node] = candidate;
1589 let candidate_modularity = modularity(graph, &assignments, resolution);
1590 assignments[node] = current;
1591 if candidate_modularity > best_modularity + EPSILON
1592 || ((candidate_modularity - best_modularity).abs() <= EPSILON
1593 && candidate_modularity > baseline + EPSILON
1594 && seeded_label_key(graph, seed, candidate)
1595 < seeded_label_key(graph, seed, best))
1596 {
1597 best = candidate;
1598 best_modularity = candidate_modularity;
1599 }
1600 }
1601 if best != current && best_modularity > baseline + EPSILON {
1602 assignments[node] = best;
1603 changed = true;
1604 }
1605 }
1606 if !changed {
1607 break;
1608 }
1609 }
1610 assignments
1611 }
1612
1613 fn pseudo_random_graph(seed: u64) -> (Vec<Node>, Vec<Edge>) {
1614 let mut state = seed;
1615 let mut next = move |bound: u64| {
1616 state = state
1617 .wrapping_mul(6_364_136_223_846_793_005)
1618 .wrapping_add(1_442_695_040_888_963_407);
1619 (state >> 33) % bound
1620 };
1621 let nodes = (0..60)
1622 .map(|index| {
1623 let id = format!("n{index:02}");
1624 node(&id, NodeKind::Service, "repo:one", &id)
1625 })
1626 .collect::<Vec<_>>();
1627 let kinds = [
1628 EdgeKind::CallsRemote,
1629 EdgeKind::ManualLink,
1630 EdgeKind::Consumes,
1631 EdgeKind::Validates,
1632 ];
1633 let edges = (0..180)
1634 .map(|number| {
1635 let source = format!("n{:02}", next(60));
1636 let target = format!("n{:02}", next(60));
1637 let kind = kinds[usize::try_from(next(4)).expect("small index")];
1638 let confidence = 0.5 + f32::from(u8::try_from(next(50)).expect("small")) / 100.0;
1639 edge(&format!("e{number}"), &source, &target, kind, confidence)
1640 })
1641 .collect();
1642 (nodes, edges)
1643 }
1644
1645 #[test]
1646 fn incremental_louvain_should_match_full_modularity_recomputation() {
1647 for graph_seed in [1, 2, 3, 4] {
1648 let (nodes, edges) = pseudo_random_graph(graph_seed);
1649 let config = config(CommunityAlgorithm::Louvain);
1650 let weights = validate_inputs(&nodes, &edges, &config).expect("weights");
1651 let selected = scoped_node_ids(&nodes, &edges, &config, &weights).expect("scope");
1652 let graph = build_graph(&nodes, &edges, &config, &weights, &selected);
1653 for (seed, resolution) in [(17, 1.0), (3, 0.5), (99, 2.0)] {
1654 assert_eq!(
1655 louvain(&graph, seed, resolution, 100, &mut |_| {}),
1656 reference_louvain(&graph, seed, resolution, 100),
1657 "graph {graph_seed}, seed {seed}, resolution {resolution}"
1658 );
1659 }
1660 }
1661 }
1662
1663 #[test]
1664 fn completed_community_units_should_report_progress() {
1665 let (nodes, edges) = two_cluster_graph();
1666 let mut completed = 0_u64;
1667
1668 analyze_communities_with_progress(
1669 "snapshot",
1670 &nodes,
1671 &edges,
1672 config(CommunityAlgorithm::Louvain),
1673 |units| completed = completed.checked_add(units).expect("bounded progress"),
1674 )
1675 .expect("analysis");
1676
1677 assert!(completed > 0);
1678 }
1679}