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
use std::collections::VecDeque;
use ahash::AHashSet;
use crate::{
HyperedgeTrait,
Hypergraph,
VertexIndex,
VertexTrait,
errors::HypergraphError,
};
impl<V, HE> Hypergraph<V, HE>
where
V: VertexTrait,
HE: HyperedgeTrait,
{
/// Returns the weakly connected components of the hypergraph.
///
/// Each component is a sorted `Vec<VertexIndex>` of vertices that are
/// mutually reachable when edge direction is ignored. Isolated vertices
/// form their own single-element component. The outer `Vec` is sorted by
/// the smallest index in each component, giving a deterministic result.
///
/// Returns an empty `Vec` for an empty hypergraph.
pub fn 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();
let mut visited: AHashSet<VertexIndex> = AHashSet::new();
let mut components: Vec<Vec<VertexIndex>> = Vec::new();
for start in all_vertices {
if visited.contains(&start) {
continue;
}
let mut component: Vec<VertexIndex> = Vec::new();
let mut queue: VecDeque<VertexIndex> = VecDeque::new();
visited.insert(start);
queue.push_back(start);
while let Some(current) = queue.pop_front() {
component.push(current);
// Treat edges as undirected: follow both outgoing and incoming.
for neighbor in self.get_adjacent_vertices_from(current)? {
if visited.insert(neighbor) {
queue.push_back(neighbor);
}
}
for neighbor in self.get_adjacent_vertices_to(current)? {
if visited.insert(neighbor) {
queue.push_back(neighbor);
}
}
}
component.sort();
components.push(component);
}
Ok(components)
}
}