pub struct Node<'a, T> {
pub key: &'a str,
pub value: T,
pub deps: Vec<&'a str>,
}
pub enum Scc<T> {
Acyclic(T),
Cyclic(Vec<T>),
}
pub fn strongly_connected_components<T>(nodes: Vec<Node<'_, T>>) -> Vec<Scc<T>> {
let n = nodes.len();
let mut sorted: Vec<usize> = (0..n).collect();
sorted.sort_by_key(|&i| nodes[i].key);
let key_vertex =
|key: &str| -> Option<usize> { sorted.binary_search_by(|&i| nodes[i].key.cmp(key)).ok() };
let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
for v in 0..n {
for dep in &nodes[sorted[v]].deps {
if let Some(w) = key_vertex(dep) {
adj[v].push(w);
}
}
}
let mut transposed: Vec<Vec<usize>> = vec![Vec::new(); n];
for (v, targets) in adj.iter().enumerate() {
for &w in targets {
transposed[w].push(v);
}
}
for list in &mut transposed {
list.reverse();
}
let mut post_order: Vec<usize> = Vec::with_capacity(n);
let mut visited = vec![false; n];
let mut stack: Vec<(usize, usize)> = Vec::new();
for root in 0..n {
if visited[root] {
continue;
}
visited[root] = true;
stack.push((root, 0));
while let Some(&mut (v, ref mut next)) = stack.last_mut() {
if let Some(&w) = transposed[v].get(*next) {
*next += 1;
if !visited[w] {
visited[w] = true;
stack.push((w, 0));
}
} else {
post_order.push(v);
stack.pop();
}
}
}
let mut components: Vec<Vec<usize>> = Vec::new();
let mut visited = vec![false; n];
for &root in post_order.iter().rev() {
if visited[root] {
continue;
}
let mut component = Vec::new();
visited[root] = true;
stack.push((root, 0));
component.push(root);
while let Some(&mut (v, ref mut next)) = stack.last_mut() {
if let Some(&w) = adj[v].get(*next) {
*next += 1;
if !visited[w] {
visited[w] = true;
component.push(w);
stack.push((w, 0));
}
} else {
stack.pop();
}
}
components.push(component);
}
let has_self_edge: Vec<bool> = (0..n).map(|v| adj[v].contains(&v)).collect();
let mut values: Vec<Option<T>> = nodes.into_iter().map(|node| Some(node.value)).collect();
let mut take = |v: usize| {
values[sorted[v]]
.take()
.expect("each vertex appears in exactly one SCC")
};
components
.into_iter()
.map(|component| {
if component.len() == 1 && !has_self_edge[component[0]] {
Scc::Acyclic(take(component[0]))
} else {
Scc::Cyclic(component.into_iter().map(&mut take).collect())
}
})
.collect()
}