uni_algo/algo/algorithms/
wcc.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! Weakly Connected Components (WCC) Algorithm.
5
6use crate::algo::GraphProjection;
7use crate::algo::algorithms::Algorithm;
8use std::collections::HashMap;
9use uni_common::core::id::Vid;
10
11pub struct Wcc;
12
13#[derive(Debug, Clone, Default)]
14pub struct WccConfig {
15    pub min_component_size: Option<usize>,
16}
17
18pub struct WccResult {
19    pub components: Vec<(Vid, u64)>, // (node, component_id)
20    pub component_count: usize,
21}
22
23impl Algorithm for Wcc {
24    type Config = WccConfig;
25    type Result = WccResult;
26
27    fn name() -> &'static str {
28        "wcc"
29    }
30
31    fn run(graph: &GraphProjection, config: Self::Config) -> Self::Result {
32        let n = graph.vertex_count();
33        if n == 0 {
34            return WccResult {
35                components: Vec::new(),
36                component_count: 0,
37            };
38        }
39
40        // Union-Find with path compression
41        let mut parent: Vec<u32> = (0..n as u32).collect();
42        let mut rank: Vec<u8> = vec![0; n];
43
44        fn find(parent: &mut [u32], mut x: u32) -> u32 {
45            while parent[x as usize] != x {
46                parent[x as usize] = parent[parent[x as usize] as usize]; // path compression
47                x = parent[x as usize];
48            }
49            x
50        }
51
52        fn union(parent: &mut [u32], rank: &mut [u8], x: u32, y: u32) {
53            let px = find(parent, x);
54            let py = find(parent, y);
55            if px == py {
56                return;
57            }
58            // Union by rank
59            match rank[px as usize].cmp(&rank[py as usize]) {
60                std::cmp::Ordering::Less => parent[px as usize] = py,
61                std::cmp::Ordering::Greater => parent[py as usize] = px,
62                std::cmp::Ordering::Equal => {
63                    parent[py as usize] = px;
64                    rank[px as usize] += 1;
65                }
66            }
67        }
68
69        // Process all edges
70        for v in 0..n as u32 {
71            for &u in graph.out_neighbors(v) {
72                union(&mut parent, &mut rank, v, u);
73            }
74        }
75
76        // Assign contiguous component IDs
77        let mut comp_map: HashMap<u32, u64> = HashMap::default();
78        let mut next_id = 0u64;
79
80        let mut results = Vec::with_capacity(n);
81        for slot in 0..n as u32 {
82            let root = find(&mut parent, slot);
83            let cid = *comp_map.entry(root).or_insert_with(|| {
84                let id = next_id;
85                next_id += 1;
86                id
87            });
88            results.push((graph.to_vid(slot), cid));
89        }
90
91        // Filter by min size if specified
92        if let Some(min_size) = config.min_component_size {
93            let mut sizes = HashMap::new();
94            for (_, cid) in &results {
95                *sizes.entry(*cid).or_insert(0) += 1;
96            }
97            results.retain(|(_, cid)| *sizes.get(cid).unwrap() >= min_size);
98        }
99
100        WccResult {
101            component_count: comp_map.len(),
102            components: results,
103        }
104    }
105}
uni_algo/algo/algorithms/wcc.rs

uni_algo/algo/algorithms/
wcc.rs
