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

reddb_server/storage/engine/algorithms/
components.rs
