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