Initialize WCC state for a local CSR partition.
(
vertex_count: usize,
shard_id: u32,
node_names: Vec<String>,
local_edges: &dyn Fn(u32) -> Vec<u32>,
ghost_edges: &dyn Fn(u32) -> Vec<(String, u32)>,
)
| 48 | impl ShardWccState { |
| 49 | /// Initialize WCC state for a local CSR partition. |
| 50 | pub fn init( |
| 51 | vertex_count: usize, |
| 52 | shard_id: u32, |
| 53 | node_names: Vec<String>, |
| 54 | local_edges: &dyn Fn(u32) -> Vec<u32>, |
| 55 | ghost_edges: &dyn Fn(u32) -> Vec<(String, u32)>, |
| 56 | ) -> Self { |
| 57 | let parent: Vec<usize> = (0..vertex_count).collect(); |
| 58 | let rank = vec![0u8; vertex_count]; |
| 59 | |
| 60 | let mut state = Self { |
| 61 | vertex_count, |
| 62 | parent, |
| 63 | rank, |
| 64 | global_labels: Vec::new(), |
| 65 | shard_id, |
| 66 | boundary_edges: HashMap::new(), |
| 67 | node_names, |
| 68 | }; |
| 69 | |
| 70 | // Local union-find pass. |
| 71 | for u in 0..vertex_count { |
| 72 | for v in local_edges(u as u32) { |
| 73 | state.union(u, v as usize); |
| 74 | } |
| 75 | } |
| 76 | |
| 77 | // Build boundary edge map. |
| 78 | for u in 0..vertex_count { |
| 79 | let ghosts = ghost_edges(u as u32); |
| 80 | if !ghosts.is_empty() { |
| 81 | state.boundary_edges.insert(u as u32, ghosts); |
| 82 | } |
| 83 | } |
| 84 | |
| 85 | // Initialize global labels from local roots. |
| 86 | state.global_labels = (0..vertex_count) |
| 87 | .map(|i| { |
| 88 | let root = state.find(i); |
| 89 | format!("{}:{}", shard_id, state.node_names[root]) |
| 90 | }) |
| 91 | .collect(); |
| 92 | |
| 93 | state |
| 94 | } |
| 95 | |
| 96 | fn find(&mut self, mut x: usize) -> usize { |
| 97 | while self.parent[x] != x { |