weavatrix_graph/algo/components/
weak.rs

1use crate::IndexGraphView;
2
3#[must_use]
4pub fn weakly_connected_components<G>(graph: &G) -> Vec<Vec<G::Node>>
5where
6    G: IndexGraphView,
7{
8    with_filter(graph, &|_| true)
9}
10
11#[must_use]
12pub fn weakly_connected_components_filtered<G, F>(graph: &G, allows_edge: F) -> Vec<Vec<G::Node>>
13where
14    G: IndexGraphView,
15    F: Fn(G::Edge) -> bool,
16{
17    with_filter(graph, &allows_edge)
18}
19
20fn with_filter<G, F>(graph: &G, allows_edge: &F) -> Vec<Vec<G::Node>>
21where
22    G: IndexGraphView,
23    F: Fn(G::Edge) -> bool,
24{
25    let node_bound = graph.node_bound();
26    let mut sets = DisjointSet::new(node_bound);
27    for (edge, endpoints) in graph.edge_references() {
28        if !allows_edge(edge) {
29            continue;
30        }
31        let source = G::node_slot(endpoints.source());
32        let target = G::node_slot(endpoints.target());
33        if source < node_bound && target < node_bound {
34            sets.union(source, target);
35        }
36    }
37
38    let mut grouped = vec![Vec::new(); node_bound];
39    for node in graph.node_indices() {
40        let slot = G::node_slot(node);
41        if slot < node_bound {
42            grouped[sets.root(slot)].push(node);
43        }
44    }
45    let mut components = grouped
46        .into_iter()
47        .filter(|component| !component.is_empty())
48        .collect::<Vec<_>>();
49    components.sort_unstable_by_key(|component| G::node_slot(component[0]));
50    components
51}
52
53struct DisjointSet {
54    parent: Vec<usize>,
55    rank: Vec<u8>,
56}
57
58impl DisjointSet {
59    fn new(len: usize) -> Self {
60        Self {
61            parent: (0..len).collect(),
62            rank: vec![0; len],
63        }
64    }
65
66    fn find(&mut self, mut node: usize) -> usize {
67        loop {
68            let parent = self.parent[node];
69            if parent == node {
70                return node;
71            }
72            self.parent[node] = self.parent[parent];
73            node = parent;
74        }
75    }
76
77    fn root(&self, mut node: usize) -> usize {
78        loop {
79            let parent = self.parent[node];
80            if parent == node {
81                return node;
82            }
83            node = parent;
84        }
85    }
86
87    fn union(&mut self, left: usize, right: usize) {
88        let mut left = self.find(left);
89        let mut right = self.find(right);
90        if left == right {
91            return;
92        }
93        if self.rank[left] < self.rank[right] {
94            std::mem::swap(&mut left, &mut right);
95        }
96        self.parent[right] = left;
97        if self.rank[left] == self.rank[right] {
98            self.rank[left] += 1;
99        }
100    }
101}
weavatrix_graph/algo/components/weak.rs

weavatrix_graph/algo/components/
weak.rs
