srcgraph_metrics/
scc.rs

1//! Strongly-connected components — Tarjan via `petgraph::algo::tarjan_scc`,
2//! plus condensation DAG and per-SCC status rating.
3//!
4//! See `DESIGN.md` (Phase 1) at the workspace root.
5//!
6//! @yah:ticket(R152-T2, "metrics::scc — Tarjan SCC + condensation DAG + rate_scc classifier (ready/partial/entangled)")
7//! @yah:assignee(agent:claude)
8//! @yah:at(2026-05-12T22:14:25Z)
9//! @yah:status(review)
10//! @yah:parent(R152)
11//! @yah:verify("cargo test -p srcgraph-metrics scc")
12//! @yah:handoff("Implemented SccStatus enum (Ready/Partial/Entangled), SccInfo, SccResult, rate_scc classifier, and compute_scc generic over N:ClassNode+E:EdgeKind. Builds condensation DAG alongside SCC list. 5 tests all pass.")
13
14use petgraph::algo::tarjan_scc;
15use petgraph::graph::{DiGraph, Graph, NodeIndex};
16use petgraph::visit::EdgeRef;
17use serde::{Deserialize, Serialize};
18use std::collections::{HashMap, HashSet};
19
20use srcgraph_core::{ClassNode, EdgeKind};
21
22/// Per-SCC severity classification.
23///
24/// Thresholds: 1 node → Ready; 2–3 → Partial; ≥4 → Entangled.
25#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
26#[serde(rename_all = "snake_case")]
27pub enum SccStatus {
28    /// Singleton SCC — class has no circular dependency.
29    Ready,
30    /// 2–3 class cycle — tractable to break with moderate refactoring.
31    Partial,
32    /// ≥4 class cycle — deeply tangled, needs architectural redesign.
33    Entangled,
34}
35
36/// Information about one strongly-connected component.
37#[derive(Debug, Clone)]
38pub struct SccInfo {
39    /// Ordinal within `SccResult::components` (also the weight of its DAG node).
40    pub id: usize,
41    /// Node indices in the original graph belonging to this SCC.
42    pub members: Vec<NodeIndex>,
43    pub status: SccStatus,
44}
45
46/// Output of [`compute_scc`].
47pub struct SccResult {
48    /// SCCs in reverse topological order (sinks first — matches `tarjan_scc` output).
49    pub components: Vec<SccInfo>,
50    /// Condensation DAG: each node holds the SCC index into `components`.
51    /// An edge `u → v` means the SCC `u` has a dependency on SCC `v`.
52    pub dag: DiGraph<usize, ()>,
53}
54
55/// Classify an SCC by its member count.
56pub fn rate_scc(size: usize) -> SccStatus {
57    match size {
58        1 => SccStatus::Ready,
59        2..=3 => SccStatus::Partial,
60        _ => SccStatus::Entangled,
61    }
62}
63
64/// Compute SCCs and the condensation DAG for `graph`.
65///
66/// Generic over `N: ClassNode` and `E: EdgeKind` so this works on both
67/// [`OwnedGraph`](srcgraph_core::OwnedGraph) (from GraphML) and `kg-store` graph types
68/// that implement those traits.
69pub fn compute_scc<N, E>(graph: &Graph<N, E>) -> SccResult
70where
71    N: ClassNode,
72    E: EdgeKind,
73{
74    let raw: Vec<Vec<NodeIndex>> = tarjan_scc(graph);
75
76    // Map every graph node to its SCC index so we can build the condensation.
77    let mut node_to_scc: HashMap<NodeIndex, usize> = HashMap::with_capacity(graph.node_count());
78    let components: Vec<SccInfo> = raw
79        .into_iter()
80        .enumerate()
81        .map(|(i, members)| {
82            for &n in &members {
83                node_to_scc.insert(n, i);
84            }
85            SccInfo {
86                id: i,
87                status: rate_scc(members.len()),
88                members,
89            }
90        })
91        .collect();
92
93    // Build condensation: one DAG node per SCC, one DAG edge per distinct inter-SCC edge.
94    let mut dag: DiGraph<usize, ()> = DiGraph::with_capacity(components.len(), 0);
95    let dag_nodes: Vec<_> = (0..components.len()).map(|i| dag.add_node(i)).collect();
96
97    let mut seen: HashSet<(usize, usize)> = HashSet::new();
98    for e in graph.edge_references() {
99        let s = node_to_scc[&e.source()];
100        let t = node_to_scc[&e.target()];
101        if s != t && seen.insert((s, t)) {
102            dag.add_edge(dag_nodes[s], dag_nodes[t], ());
103        }
104    }
105
106    SccResult { components, dag }
107}
108
109#[cfg(test)]
110mod tests {
111    use super::*;
112    use srcgraph_core::{EdgeType, OwnedClassNode, OwnedGraph};
113    use petgraph::Graph;
114
115    fn node(id: &str) -> OwnedClassNode {
116        OwnedClassNode {
117            id: id.to_owned(),
118            name: id.split('.').last().unwrap_or(id).to_owned(),
119            namespace: "test".to_owned(),
120            line_count: 10,
121            method_count: 2,
122            halstead_eta1: 0,
123            halstead_eta2: 0,
124            halstead_n1: 0,
125            halstead_n2: 0,
126            method_connectivity: None,
127            method_fingerprints: None,
128            method_tokens: None,
129            call_sequences: None,
130            cyclomatic_complexity: None,
131            path_conditions: None,
132            invariants: None,
133            error_messages: None,
134            magic_numbers: None,
135            dead_code: None,
136            tenant_branches: None,
137            state_transitions: None,
138        }
139    }
140
141    #[test]
142    fn scc_linear_dag_all_ready() {
143        // A → B → C — linear DAG, no cycles; each class is its own singleton SCC.
144        let mut g: OwnedGraph = Graph::new();
145        let a = g.add_node(node("A"));
146        let b = g.add_node(node("B"));
147        let c = g.add_node(node("C"));
148        g.add_edge(a, b, EdgeType::MethodCall);
149        g.add_edge(b, c, EdgeType::MethodCall);
150
151        let r = compute_scc(&g);
152
153        assert_eq!(r.components.len(), 3);
154        assert!(r.components.iter().all(|s| s.status == SccStatus::Ready));
155        assert!(r.components.iter().all(|s| s.members.len() == 1));
156        // Condensation DAG mirrors the original edges (one per singleton SCC pair).
157        assert_eq!(r.dag.node_count(), 3);
158        assert_eq!(r.dag.edge_count(), 2);
159    }
160
161    #[test]
162    fn scc_three_cycle_partial() {
163        // A → B → C → A — one 3-node SCC rated Partial.
164        let mut g: OwnedGraph = Graph::new();
165        let a = g.add_node(node("A"));
166        let b = g.add_node(node("B"));
167        let c = g.add_node(node("C"));
168        g.add_edge(a, b, EdgeType::MethodCall);
169        g.add_edge(b, c, EdgeType::MethodCall);
170        g.add_edge(c, a, EdgeType::MethodCall);
171
172        let r = compute_scc(&g);
173
174        assert_eq!(r.components.len(), 1, "entire graph is one SCC");
175        assert_eq!(r.components[0].status, SccStatus::Partial);
176        assert_eq!(r.components[0].members.len(), 3);
177        // Condensation is a single node, no edges.
178        assert_eq!(r.dag.edge_count(), 0);
179    }
180
181    #[test]
182    fn scc_large_cycle_entangled() {
183        // 5-node cycle — rated Entangled.
184        let mut g: OwnedGraph = Graph::new();
185        let nodes: Vec<_> = (0..5).map(|i| g.add_node(node(&format!("N{i}")))).collect();
186        for i in 0..5 {
187            g.add_edge(nodes[i], nodes[(i + 1) % 5], EdgeType::MethodCall);
188        }
189
190        let r = compute_scc(&g);
191
192        assert_eq!(r.components.len(), 1);
193        assert_eq!(r.components[0].status, SccStatus::Entangled);
194        assert_eq!(r.components[0].members.len(), 5);
195    }
196
197    #[test]
198    fn scc_condensation_dag_shape() {
199        // A ↔ B (2-cycle), C → A, D → C.
200        // SCCs: {A,B} (Partial), {C} (Ready), {D} (Ready).
201        // Condensation edges: D→C, C→{AB} — two edges.
202        let mut g: OwnedGraph = Graph::new();
203        let a = g.add_node(node("A"));
204        let b = g.add_node(node("B"));
205        let c = g.add_node(node("C"));
206        let d = g.add_node(node("D"));
207        g.add_edge(a, b, EdgeType::MethodCall);
208        g.add_edge(b, a, EdgeType::MethodCall); // A ↔ B cycle
209        g.add_edge(c, a, EdgeType::MethodCall); // C depends on cycle
210        g.add_edge(d, c, EdgeType::MethodCall); // D → C
211
212        let r = compute_scc(&g);
213
214        assert_eq!(r.components.len(), 3, "3 SCCs: {{A,B}}, {{C}}, {{D}}");
215
216        let pair = r.components.iter().find(|s| s.members.len() == 2).expect("2-node SCC");
217        assert_eq!(pair.status, SccStatus::Partial);
218
219        assert_eq!(r.dag.node_count(), 3);
220        assert_eq!(r.dag.edge_count(), 2, "two inter-SCC edges");
221    }
222
223    #[test]
224    fn rate_scc_thresholds() {
225        assert_eq!(rate_scc(1), SccStatus::Ready);
226        assert_eq!(rate_scc(2), SccStatus::Partial);
227        assert_eq!(rate_scc(3), SccStatus::Partial);
228        assert_eq!(rate_scc(4), SccStatus::Entangled);
229        assert_eq!(rate_scc(100), SccStatus::Entangled);
230    }
231}
srcgraph_metrics/scc.rs

srcgraph_metrics/
scc.rs
