reddb_server/storage/engine/algorithms/
components.rs

1//! Connected Components Algorithms
2//!
3//! Find connected components in graphs using Union-Find with path compression.
4//! Useful for identifying isolated network segments.
5
6use std::collections::HashMap;
7
8use super::super::graph_store::GraphStore;
9
10// ============================================================================
11// Union-Find Data Structure
12// ============================================================================
13
14/// Union-Find data structure with path compression
15pub(crate) struct UnionFind {
16    parent: HashMap<String, String>,
17    rank: HashMap<String, usize>,
18}
19
20impl UnionFind {
21    pub fn new() -> Self {
22        Self {
23            parent: HashMap::new(),
24            rank: HashMap::new(),
25        }
26    }
27
28    pub fn make_set(&mut self, x: &str) {
29        // Single hash lookup on `parent`: initialise the set only when absent.
30        if let std::collections::hash_map::Entry::Vacant(slot) = self.parent.entry(x.to_string()) {
31            slot.insert(x.to_string());
32            self.rank.insert(x.to_string(), 0);
33        }
34    }
35
36    pub fn find(&mut self, x: &str) -> String {
37        let parent = self.parent.get(x).cloned().unwrap_or_else(|| x.to_string());
38        if parent != x {
39            // Path compression
40            let root = self.find(&parent);
41            self.parent.insert(x.to_string(), root.clone());
42            root
43        } else {
44            x.to_string()
45        }
46    }
47
48    pub fn union(&mut self, x: &str, y: &str) {
49        let root_x = self.find(x);
50        let root_y = self.find(y);
51
52        if root_x == root_y {
53            return;
54        }
55
56        let rank_x = *self.rank.get(&root_x).unwrap_or(&0);
57        let rank_y = *self.rank.get(&root_y).unwrap_or(&0);
58
59        // Union by rank
60        if rank_x < rank_y {
61            self.parent.insert(root_x, root_y);
62        } else if rank_x > rank_y {
63            self.parent.insert(root_y, root_x);
64        } else {
65            self.parent.insert(root_y, root_x.clone());
66            self.rank.insert(root_x, rank_x + 1);
67        }
68    }
69}
70
71// ============================================================================
72// Connected Components
73// ============================================================================
74
75/// Connected components finder
76pub struct ConnectedComponents;
77
78/// A connected component in the graph
79#[derive(Debug, Clone)]
80pub struct Component {
81    /// Component ID (representative node)
82    pub id: String,
83    /// Nodes in this component
84    pub nodes: Vec<String>,
85    /// Size of the component
86    pub size: usize,
87}
88
89/// Result of connected components computation
90#[derive(Debug, Clone)]
91pub struct ComponentsResult {
92    /// List of components, sorted by size descending
93    pub components: Vec<Component>,
94    /// Total number of components
95    pub count: usize,
96}
97
98impl ComponentsResult {
99    /// Get the largest component
100    pub fn largest(&self) -> Option<&Component> {
101        self.components.first()
102    }
103
104    /// Get components with at least min_size nodes
105    pub fn filter_by_size(&self, min_size: usize) -> Vec<&Component> {
106        self.components
107            .iter()
108            .filter(|c| c.size >= min_size)
109            .collect()
110    }
111
112    /// Find which component a node belongs to
113    pub fn component_of(&self, node_id: &str) -> Option<&Component> {
114        self.components
115            .iter()
116            .find(|c| c.nodes.contains(&node_id.to_string()))
117    }
118}
119
120impl ConnectedComponents {
121    /// Find all connected components in the graph (treating edges as undirected)
122    pub fn find(graph: &GraphStore) -> ComponentsResult {
123        let mut uf = UnionFind::new();
124
125        // Add all nodes
126        for node in graph.iter_nodes() {
127            uf.make_set(&node.id);
128        }
129
130        // Union nodes connected by edges (both directions)
131        for node in graph.iter_nodes() {
132            for (_, target, _) in graph.outgoing_edges(&node.id) {
133                uf.union(&node.id, &target);
134            }
135        }
136
137        // Group nodes by their root
138        let mut groups: HashMap<String, Vec<String>> = HashMap::new();
139        for node in graph.iter_nodes() {
140            let root = uf.find(&node.id);
141            groups.entry(root).or_default().push(node.id.clone());
142        }
143
144        // Build components
145        let mut components: Vec<Component> = groups
146            .into_iter()
147            .map(|(id, nodes)| {
148                let size = nodes.len();
149                Component { id, nodes, size }
150            })
151            .collect();
152
153        // Sort by size descending
154        components.sort_by_key(|b| std::cmp::Reverse(b.size));
155
156        let count = components.len();
157        ComponentsResult { components, count }
158    }
159}
reddb_server/storage/engine/algorithms/components.rs

reddb_server/storage/engine/algorithms/
components.rs
