Skip to main content

code_system_graph_core/
communities.rs

1//! Deterministic community detection and comparison for federated graphs.
2
3use 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/// Failure returned when community-analysis inputs violate their documented invariants.
20#[derive(Debug, Error, PartialEq)]
21pub enum CommunityError {
22    /// The Louvain resolution is not finite and strictly positive.
23    #[error("community resolution must be finite and positive, found {0}")]
24    InvalidResolution(f64),
25    /// The iteration limit is outside the supported inclusive range.
26    #[error("community max_iterations must be in 1..=10_000, found {0}")]
27    InvalidMaxIterations(u32),
28    /// The configured confidence threshold is not finite or outside zero through one.
29    #[error("community minimum_confidence must be finite and in 0..=1, found {0}")]
30    InvalidMinimumConfidence(f32),
31    /// An input edge has a non-finite or out-of-range confidence.
32    #[error("edge `{edge_id}` confidence must be finite and in 0..=1, found {confidence}")]
33    InvalidEdgeConfidence {
34        /// Stable identity of the invalid edge.
35        edge_id: String,
36        /// Invalid confidence value.
37        confidence: f32,
38    },
39    /// A configured relationship weight is negative or non-finite.
40    #[error("community edge weight for `{kind:?}` must be finite and non-negative, found {weight}")]
41    InvalidEdgeWeight {
42        /// Relationship kind carrying the invalid weight.
43        kind: EdgeKind,
44        /// Invalid relationship weight.
45        weight: f64,
46    },
47    /// More than one explicit weight was supplied for the same relationship kind.
48    #[error("community edge weight for `{0:?}` is configured more than once")]
49    DuplicateEdgeWeight(EdgeKind),
50    /// More than one node uses the same stable identifier.
51    #[error("node identifier `{0}` occurs more than once")]
52    DuplicateNodeId(String),
53    /// Service scope did not resolve to an exact service stable key.
54    #[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
75/// Detects deterministic communities in one immutable graph snapshot.
76///
77/// Only confirmed edges meeting `minimum_confidence` participate. Relationship
78/// weights are multiplied by edge confidence, parallel directions are summed,
79/// and the resulting weighted graph is symmetrized before clustering. Central
80/// nodes combine weighted `PageRank` (65%) and normalized weighted degree (35%),
81/// with detected high-degree god nodes disclosed and ranked first.
82///
83/// # Errors
84///
85/// Returns [`CommunityError`] when configuration values, edge confidences, node
86/// identities, or an exact service scope are invalid.
87pub 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
96/// Analyzes communities while reporting each completed finite optimization unit.
97///
98/// # Errors
99///
100/// Returns [`CommunityError`] under the same conditions as [`analyze_communities`].
101pub 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/// Compares two community snapshots using deterministic member-set overlap.
138///
139/// Jaccard overlap of at least 0.25 establishes a material relationship. One
140/// old community related to multiple new communities is a split, while the
141/// inverse is a merge. Remaining one-to-one relationships below 0.80 are
142/// materially changed; unrelated communities are created or removed.
143#[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(&current).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
579/// Local-moving Louvain phase. Each move is scored by its exact modularity gain: for node `i` with
580/// weighted degree `k`, links `k_c` to community `c`, and community degree totals `d_c`, moving from
581/// `a` to `b` changes modularity by
582/// `(k_b - k_a) / m - resolution * k * (d_b - (d_a - k)) / (2 * m^2)`.
583fn 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[&current];
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, &central);
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    /// Computes generalized undirected modularity:
1521    /// `sum_c(internal_weight_c / m - resolution * (degree_c / (2m))^2)`.
1522    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    /// Louvain local moving that recomputes full modularity for every candidate move.
1559    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}