1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
use ahash::AHashSet;
use crate::{
HyperedgeTrait,
Hypergraph,
VertexIndex,
VertexTrait,
errors::HypergraphError,
};
impl<V, HE> Hypergraph<V, HE>
where
V: VertexTrait,
HE: HyperedgeTrait,
{
/// Returns the strongly connected components (SCCs) of the hypergraph using
/// Kosaraju's algorithm.
///
/// Each SCC is a sorted `Vec<VertexIndex>` of vertices that are mutually
/// reachable following directed hyperedges. A vertex with no edges forms its
/// own single-element SCC. The order of the outer `Vec` follows reverse
/// finish order from the first DFS pass (topological order for DAGs).
///
/// Returns an empty `Vec` for an empty hypergraph.
pub fn strongly_connected_components(
&self,
) -> Result<Vec<Vec<VertexIndex>>, HypergraphError<V, HE>> {
let mut all_vertices: Vec<VertexIndex> =
self.vertices_mapping.left.values().copied().collect();
all_vertices.sort();
// Phase 1 — iterative DFS on the original graph; record finish order.
let mut visited: AHashSet<VertexIndex> = AHashSet::new();
let mut finish_order: Vec<VertexIndex> = Vec::new();
for &start in &all_vertices {
if visited.contains(&start) {
continue;
}
// Each stack entry: (vertex, exiting).
// Push (v, false) to enter v, then (v, true) to record finish.
let mut stack: Vec<(VertexIndex, bool)> = vec![(start, false)];
while let Some((v, exiting)) = stack.pop() {
if exiting {
finish_order.push(v);
continue;
}
if !visited.insert(v) {
continue;
}
stack.push((v, true));
for neighbor in self.get_adjacent_vertices_from(v)? {
if !visited.contains(&neighbor) {
stack.push((neighbor, false));
}
}
}
}
// Phase 2 — iterative DFS on the transposed graph in reverse finish order.
// The transposed graph is traversed by following incoming edges via
// `get_adjacent_vertices_to`.
let mut visited2: AHashSet<VertexIndex> = AHashSet::new();
let mut sccs: Vec<Vec<VertexIndex>> = Vec::new();
for &start in finish_order.iter().rev() {
if visited2.contains(&start) {
continue;
}
let mut scc: Vec<VertexIndex> = Vec::new();
let mut stack: Vec<VertexIndex> = vec![start];
visited2.insert(start);
while let Some(v) = stack.pop() {
scc.push(v);
for predecessor in self.get_adjacent_vertices_to(v)? {
if visited2.insert(predecessor) {
stack.push(predecessor);
}
}
}
scc.sort();
sccs.push(scc);
}
Ok(sccs)
}
}