1use crate::graph_builder::build_node_index;
2use serde::{Deserialize, Serialize};
3
4#[derive(Debug, Clone, Serialize, Deserialize)]
5pub struct SccComponent {
6 pub nodes: Vec<String>,
7 pub size: usize,
8 pub is_trivial: bool,
9}
10
11#[derive(Debug, Clone, Serialize, Deserialize)]
12pub struct SccResult {
13 pub components: Vec<SccComponent>,
14 pub total_components: usize,
15 pub non_trivial_count: usize,
16 pub largest_component_size: usize,
17 pub node_count: usize,
18 pub edge_count: usize,
19}
20
21pub fn tarjan_scc(edges: &[(String, String)]) -> SccResult {
22 if edges.is_empty() {
23 return SccResult {
24 components: Vec::new(),
25 total_components: 0,
26 non_trivial_count: 0,
27 largest_component_size: 0,
28 node_count: 0,
29 edge_count: 0,
30 };
31 }
32
33 let (node_vec, node_idx) = build_node_index(edges);
34 let n = node_vec.len();
35
36 let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
37 for (a, b) in edges {
38 let ai = node_idx[a];
39 let bi = node_idx[b];
40 adj[ai].push(bi);
41 }
42
43 let mut index_counter = 0usize;
44 let mut indices = vec![None::<usize>; n];
45 let mut lowlinks = vec![0usize; n];
46 let mut on_stack = vec![false; n];
47 let mut stack: Vec<usize> = Vec::new();
48 let mut components: Vec<Vec<usize>> = Vec::new();
49
50 #[allow(clippy::too_many_arguments)]
51 fn strongconnect(
52 v: usize,
53 adj: &[Vec<usize>],
54 index_counter: &mut usize,
55 indices: &mut Vec<Option<usize>>,
56 lowlinks: &mut Vec<usize>,
57 on_stack: &mut Vec<bool>,
58 stack: &mut Vec<usize>,
59 components: &mut Vec<Vec<usize>>,
60 ) {
61 indices[v] = Some(*index_counter);
62 lowlinks[v] = *index_counter;
63 *index_counter += 1;
64 stack.push(v);
65 on_stack[v] = true;
66
67 for &w in &adj[v] {
68 match indices[w] {
69 None => {
70 strongconnect(
71 w,
72 adj,
73 index_counter,
74 indices,
75 lowlinks,
76 on_stack,
77 stack,
78 components,
79 );
80 lowlinks[v] = lowlinks[v].min(lowlinks[w]);
81 }
82 Some(_) if on_stack[w] => {
83 lowlinks[v] = lowlinks[v].min(indices[w].unwrap());
84 }
85 _ => {}
86 }
87 }
88
89 if indices[v] == Some(lowlinks[v]) {
90 let mut component = Vec::new();
91 loop {
92 let w = stack.pop().unwrap();
93 on_stack[w] = false;
94 component.push(w);
95 if w == v {
96 break;
97 }
98 }
99 components.push(component);
100 }
101 }
102
103 for v in 0..n {
104 if indices[v].is_none() {
105 strongconnect(
106 v,
107 &adj,
108 &mut index_counter,
109 &mut indices,
110 &mut lowlinks,
111 &mut on_stack,
112 &mut stack,
113 &mut components,
114 );
115 }
116 }
117
118 let mut scc_components: Vec<SccComponent> = components
119 .into_iter()
120 .map(|indices| {
121 let mut nodes: Vec<String> = indices.iter().map(|&i| node_vec[i].clone()).collect();
122 nodes.sort();
123 let size = nodes.len();
124 let is_trivial = size == 1 && {
125 let node_idx_val = node_idx[&nodes[0]];
126 !adj[node_idx_val].contains(&node_idx_val)
127 };
128 SccComponent {
129 is_trivial,
130 nodes,
131 size,
132 }
133 })
134 .collect();
135
136 let non_trivial_count = scc_components.iter().filter(|c| !c.is_trivial).count();
137 let largest_component_size = scc_components.iter().map(|c| c.size).max().unwrap_or(0);
138
139 scc_components.sort_by(|a, b| b.size.cmp(&a.size).then(a.nodes.cmp(&b.nodes)));
140
141 SccResult {
142 total_components: scc_components.len(),
143 non_trivial_count,
144 largest_component_size,
145 components: scc_components,
146 node_count: n,
147 edge_count: edges.len(),
148 }
149}
150
151#[cfg(test)]
152mod tests {
153 use super::*;
154
155 fn e(a: &str, b: &str) -> (String, String) {
156 (a.to_string(), b.to_string())
157 }
158
159 #[test]
160 fn empty_graph() {
161 let result = tarjan_scc(&[]);
162 assert_eq!(result.total_components, 0);
163 assert_eq!(result.node_count, 0);
164 }
165
166 #[test]
167 fn single_node_no_edges() {
168 let result = tarjan_scc(&[]);
169 assert_eq!(result.total_components, 0);
170 }
171
172 #[test]
173 fn single_edge_two_components() {
174 let edges = vec![e("a", "b")];
175 let result = tarjan_scc(&edges);
176 assert_eq!(result.total_components, 2);
177 assert!(result.components.iter().all(|c| c.is_trivial));
178 }
179
180 #[test]
181 fn simple_cycle() {
182 let edges = vec![e("a", "b"), e("b", "c"), e("c", "a")];
183 let result = tarjan_scc(&edges);
184 assert_eq!(result.non_trivial_count, 1);
185 assert_eq!(result.largest_component_size, 3);
186 let scc = &result.components[0];
187 assert_eq!(scc.nodes, vec!["a", "b", "c"]);
188 }
189
190 #[test]
191 fn two_cycles_connected() {
192 let edges = vec![
193 e("a", "b"),
194 e("b", "a"),
195 e("c", "d"),
196 e("d", "c"),
197 e("a", "c"),
198 ];
199 let result = tarjan_scc(&edges);
200 assert_eq!(result.non_trivial_count, 2);
201 assert_eq!(result.total_components, 2);
202 }
203
204 #[test]
205 fn self_loop_is_nontrivial() {
206 let edges = vec![e("a", "a")];
207 let result = tarjan_scc(&edges);
208 assert_eq!(result.non_trivial_count, 1);
209 assert_eq!(result.components[0].nodes, vec!["a"]);
210 assert!(!result.components[0].is_trivial);
211 }
212
213 #[test]
214 fn dag_all_trivial() {
215 let edges = vec![e("a", "b"), e("b", "c"), e("a", "c")];
216 let result = tarjan_scc(&edges);
217 assert_eq!(result.non_trivial_count, 0);
218 assert_eq!(result.total_components, 3);
219 }
220
221 #[test]
222 fn nested_cycles() {
223 let edges = vec![
224 e("a", "b"),
225 e("b", "c"),
226 e("c", "a"),
227 e("b", "d"),
228 e("d", "b"),
229 ];
230 let result = tarjan_scc(&edges);
231 assert_eq!(result.non_trivial_count, 1);
232 assert_eq!(result.largest_component_size, 4);
233 }
234}