ruvector_mincut/algorithm/
replacement.rs

1//! Replacement edge data structure for O(log n) reconnection
2//!
3//! Provides fast lookup of replacement edges when a tree edge is deleted.
4//! Based on the level-based approach from dynamic connectivity literature.
5
6use crate::graph::VertexId;
7use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
8
9/// Edge identifier as (smaller, larger) vertex pair
10pub type EdgeKey = (VertexId, VertexId);
11
12/// Normalize an edge to (min, max) ordering
13#[inline]
14fn normalize_edge(u: VertexId, v: VertexId) -> EdgeKey {
15    if u < v { (u, v) } else { (v, u) }
16}
17
18/// Level-based replacement edge index for O(log n) lookup
19///
20/// Organizes non-tree edges by level, enabling efficient replacement
21/// edge discovery when tree edges are deleted.
22///
23/// # Complexity
24/// - Lookup: O(log n) amortized
25/// - Insert: O(log n)
26/// - Delete: O(log n)
27#[derive(Debug, Clone)]
28pub struct ReplacementEdgeIndex {
29    /// Maximum level (log₂ n)
30    max_level: usize,
31    /// Non-tree edges organized by level
32    /// Level 0 contains all non-tree edges initially
33    level_edges: Vec<BTreeSet<EdgeKey>>,
34    /// Reverse lookup: edge -> level
35    edge_level: HashMap<EdgeKey, usize>,
36    /// Tree edges (for quick membership check)
37    tree_edges: HashSet<EdgeKey>,
38    /// Adjacency for each vertex at each level
39    level_adjacency: Vec<HashMap<VertexId, BTreeSet<VertexId>>>,
40    /// Component sizes (for smaller-to-larger promotion)
41    component_size: HashMap<VertexId, usize>,
42}
43
44impl ReplacementEdgeIndex {
45    /// Create a new replacement edge index
46    pub fn new(n: usize) -> Self {
47        // log₂(n) levels
48        let max_level = (n as f64).log2().ceil() as usize + 1;
49        let max_level = max_level.max(1);
50
51        Self {
52            max_level,
53            level_edges: vec![BTreeSet::new(); max_level],
54            edge_level: HashMap::new(),
55            tree_edges: HashSet::new(),
56            level_adjacency: vec![HashMap::new(); max_level],
57            component_size: HashMap::new(),
58        }
59    }
60
61    /// Add a tree edge
62    pub fn add_tree_edge(&mut self, u: VertexId, v: VertexId) {
63        let key = normalize_edge(u, v);
64        self.tree_edges.insert(key);
65    }
66
67    /// Remove a tree edge (returns if it was present)
68    pub fn remove_tree_edge(&mut self, u: VertexId, v: VertexId) -> bool {
69        let key = normalize_edge(u, v);
70        self.tree_edges.remove(&key)
71    }
72
73    /// Add a non-tree edge at level 0
74    pub fn add_non_tree_edge(&mut self, u: VertexId, v: VertexId) {
75        let key = normalize_edge(u, v);
76
77        // Don't add if it's a tree edge
78        if self.tree_edges.contains(&key) {
79            return;
80        }
81
82        // Add at level 0
83        if self.level_edges[0].insert(key) {
84            self.edge_level.insert(key, 0);
85
86            // Update adjacency
87            self.level_adjacency[0]
88                .entry(u)
89                .or_default()
90                .insert(v);
91            self.level_adjacency[0]
92                .entry(v)
93                .or_default()
94                .insert(u);
95        }
96    }
97
98    /// Remove a non-tree edge
99    pub fn remove_non_tree_edge(&mut self, u: VertexId, v: VertexId) {
100        let key = normalize_edge(u, v);
101
102        if let Some(level) = self.edge_level.remove(&key) {
103            self.level_edges[level].remove(&key);
104
105            // Update adjacency
106            if let Some(adj) = self.level_adjacency[level].get_mut(&u) {
107                adj.remove(&v);
108            }
109            if let Some(adj) = self.level_adjacency[level].get_mut(&v) {
110                adj.remove(&u);
111            }
112        }
113    }
114
115    /// Find a replacement edge for deleted tree edge (u, v)
116    ///
117    /// Returns Some((x, y)) if a replacement exists, None if components disconnect.
118    ///
119    /// # Complexity
120    /// O(log n) amortized through level-based search
121    pub fn find_replacement(&mut self, u: VertexId, v: VertexId,
122                            tree_adjacency: &HashMap<VertexId, HashSet<VertexId>>)
123        -> Option<EdgeKey>
124    {
125        let key = normalize_edge(u, v);
126
127        // The edge should be a tree edge
128        if !self.tree_edges.contains(&key) {
129            return None;
130        }
131
132        // Find smaller component using BFS on tree edges only
133        let (smaller_vertices, _larger_vertices) =
134            self.find_components_after_cut(u, v, tree_adjacency);
135
136        // Search for replacement edge across levels (from highest to 0)
137        for level in (0..self.max_level).rev() {
138            if let Some(replacement) = self.find_replacement_at_level(level, &smaller_vertices) {
139                return Some(replacement);
140            }
141        }
142
143        // No replacement found - promote edges from smaller component to next level
144        self.promote_edges(&smaller_vertices);
145
146        None
147    }
148
149    /// Fast replacement lookup when components are already known
150    ///
151    /// # Complexity
152    /// O(log n) - binary search through levels
153    pub fn find_replacement_fast(&self, smaller_component: &HashSet<VertexId>) -> Option<EdgeKey> {
154        // Search levels from 0 (most edges) upward
155        for level in 0..self.max_level {
156            if let Some(replacement) = self.find_replacement_at_level(level, smaller_component) {
157                return Some(replacement);
158            }
159        }
160        None
161    }
162
163    /// Find replacement at a specific level
164    fn find_replacement_at_level(&self, level: usize, component: &HashSet<VertexId>) -> Option<EdgeKey> {
165        // Look through adjacency at this level for edges crossing component boundary
166        for &vertex in component {
167            if let Some(neighbors) = self.level_adjacency[level].get(&vertex) {
168                for &neighbor in neighbors {
169                    if !component.contains(&neighbor) {
170                        // Found a crossing edge!
171                        return Some(normalize_edge(vertex, neighbor));
172                    }
173                }
174            }
175        }
176        None
177    }
178
179    /// Find the two components after cutting tree edge (u, v)
180    fn find_components_after_cut(&self, u: VertexId, v: VertexId,
181                                  tree_adj: &HashMap<VertexId, HashSet<VertexId>>)
182        -> (HashSet<VertexId>, HashSet<VertexId>)
183    {
184        let mut comp_u = HashSet::new();
185        let mut stack = vec![u];
186        comp_u.insert(u);
187
188        while let Some(x) = stack.pop() {
189            if let Some(neighbors) = tree_adj.get(&x) {
190                for &y in neighbors {
191                    // Skip the cut edge
192                    if (x == u && y == v) || (x == v && y == u) {
193                        continue;
194                    }
195                    if comp_u.insert(y) {
196                        stack.push(y);
197                    }
198                }
199            }
200        }
201
202        let mut comp_v = HashSet::new();
203        stack.push(v);
204        comp_v.insert(v);
205
206        while let Some(x) = stack.pop() {
207            if let Some(neighbors) = tree_adj.get(&x) {
208                for &y in neighbors {
209                    if (x == u && y == v) || (x == v && y == u) {
210                        continue;
211                    }
212                    if comp_v.insert(y) {
213                        stack.push(y);
214                    }
215                }
216            }
217        }
218
219        // Return smaller component first
220        if comp_u.len() <= comp_v.len() {
221            (comp_u, comp_v)
222        } else {
223            (comp_v, comp_u)
224        }
225    }
226
227    /// Promote non-tree edges from smaller component to next level
228    fn promote_edges(&mut self, component: &HashSet<VertexId>) {
229        let mut to_promote = Vec::new();
230
231        // Find edges at each level that have both endpoints in the component
232        for level in 0..self.max_level.saturating_sub(1) {
233            for &vertex in component {
234                if let Some(neighbors) = self.level_adjacency[level].get(&vertex).cloned() {
235                    for neighbor in neighbors {
236                        if component.contains(&neighbor) {
237                            let key = normalize_edge(vertex, neighbor);
238                            to_promote.push((key, level));
239                        }
240                    }
241                }
242            }
243        }
244
245        // Perform promotions
246        for (key, old_level) in to_promote {
247            let new_level = (old_level + 1).min(self.max_level - 1);
248            if new_level != old_level {
249                let (u, v) = key;
250
251                // Remove from old level
252                self.level_edges[old_level].remove(&key);
253                if let Some(adj) = self.level_adjacency[old_level].get_mut(&u) {
254                    adj.remove(&v);
255                }
256                if let Some(adj) = self.level_adjacency[old_level].get_mut(&v) {
257                    adj.remove(&u);
258                }
259
260                // Add to new level
261                self.level_edges[new_level].insert(key);
262                self.edge_level.insert(key, new_level);
263                self.level_adjacency[new_level]
264                    .entry(u)
265                    .or_default()
266                    .insert(v);
267                self.level_adjacency[new_level]
268                    .entry(v)
269                    .or_default()
270                    .insert(u);
271            }
272        }
273    }
274
275    /// Get statistics about the index
276    pub fn stats(&self) -> ReplacementIndexStats {
277        let edges_per_level: Vec<usize> = self.level_edges.iter()
278            .map(|s| s.len())
279            .collect();
280
281        ReplacementIndexStats {
282            max_level: self.max_level,
283            tree_edges: self.tree_edges.len(),
284            non_tree_edges: self.edge_level.len(),
285            edges_per_level,
286        }
287    }
288}
289
290/// Statistics about the replacement edge index
291#[derive(Debug, Clone)]
292pub struct ReplacementIndexStats {
293    /// Maximum level (log₂ n)
294    pub max_level: usize,
295    /// Number of tree edges tracked
296    pub tree_edges: usize,
297    /// Number of non-tree edges across all levels
298    pub non_tree_edges: usize,
299    /// Count of edges at each level
300    pub edges_per_level: Vec<usize>,
301}
302
303#[cfg(test)]
304mod tests {
305    use super::*;
306
307    #[test]
308    fn test_new_index() {
309        let idx = ReplacementEdgeIndex::new(100);
310        assert!(idx.max_level >= 7); // log2(100) ≈ 6.6
311        assert_eq!(idx.tree_edges.len(), 0);
312    }
313
314    #[test]
315    fn test_add_tree_edge() {
316        let mut idx = ReplacementEdgeIndex::new(10);
317        idx.add_tree_edge(1, 2);
318        idx.add_tree_edge(2, 3);
319
320        assert!(idx.tree_edges.contains(&(1, 2)));
321        assert!(idx.tree_edges.contains(&(2, 3)));
322    }
323
324    #[test]
325    fn test_add_non_tree_edge() {
326        let mut idx = ReplacementEdgeIndex::new(10);
327        idx.add_tree_edge(1, 2);
328        idx.add_non_tree_edge(1, 3);
329        idx.add_non_tree_edge(2, 4);
330
331        // Non-tree edge should be at level 0
332        assert!(idx.level_edges[0].contains(&(1, 3)));
333        assert!(idx.level_edges[0].contains(&(2, 4)));
334        assert_eq!(idx.edge_level.get(&(1, 3)), Some(&0));
335    }
336
337    #[test]
338    fn test_find_replacement_simple() {
339        let mut idx = ReplacementEdgeIndex::new(10);
340
341        // Tree: 1 - 2 - 3
342        idx.add_tree_edge(1, 2);
343        idx.add_tree_edge(2, 3);
344
345        // Non-tree edge: 1 - 3 (bypasses 2)
346        idx.add_non_tree_edge(1, 3);
347
348        // Build tree adjacency
349        let mut tree_adj: HashMap<VertexId, HashSet<VertexId>> = HashMap::new();
350        tree_adj.entry(1).or_default().insert(2);
351        tree_adj.entry(2).or_default().insert(1);
352        tree_adj.entry(2).or_default().insert(3);
353        tree_adj.entry(3).or_default().insert(2);
354
355        // Delete tree edge (1, 2) - should find (1, 3) as replacement
356        let replacement = idx.find_replacement(1, 2, &tree_adj);
357        assert_eq!(replacement, Some((1, 3)));
358    }
359
360    #[test]
361    fn test_find_replacement_none() {
362        let mut idx = ReplacementEdgeIndex::new(10);
363
364        // Tree: 1 - 2 - 3 (no non-tree edges)
365        idx.add_tree_edge(1, 2);
366        idx.add_tree_edge(2, 3);
367
368        let mut tree_adj: HashMap<VertexId, HashSet<VertexId>> = HashMap::new();
369        tree_adj.entry(1).or_default().insert(2);
370        tree_adj.entry(2).or_default().insert(1);
371        tree_adj.entry(2).or_default().insert(3);
372        tree_adj.entry(3).or_default().insert(2);
373
374        // No replacement for (1, 2)
375        let replacement = idx.find_replacement(1, 2, &tree_adj);
376        assert!(replacement.is_none());
377    }
378
379    #[test]
380    fn test_find_replacement_fast() {
381        let mut idx = ReplacementEdgeIndex::new(10);
382
383        // Non-tree edges at level 0
384        idx.add_non_tree_edge(1, 4);
385        idx.add_non_tree_edge(2, 5);
386
387        // Component {1, 2, 3}
388        let component: HashSet<VertexId> = [1, 2, 3].into_iter().collect();
389
390        // Should find (1, 4) or (2, 5) as crossing edge
391        let replacement = idx.find_replacement_fast(&component);
392        assert!(replacement.is_some());
393        let (u, v) = replacement.unwrap();
394        assert!(component.contains(&u) != component.contains(&v));
395    }
396
397    #[test]
398    fn test_stats() {
399        let mut idx = ReplacementEdgeIndex::new(100);
400        idx.add_tree_edge(1, 2);
401        idx.add_tree_edge(2, 3);
402        idx.add_non_tree_edge(1, 3);
403        idx.add_non_tree_edge(3, 4);
404
405        let stats = idx.stats();
406        assert_eq!(stats.tree_edges, 2);
407        assert_eq!(stats.non_tree_edges, 2);
408        assert_eq!(stats.edges_per_level[0], 2);
409    }
410
411    #[test]
412    fn test_remove_edges() {
413        let mut idx = ReplacementEdgeIndex::new(10);
414
415        idx.add_tree_edge(1, 2);
416        idx.add_non_tree_edge(1, 3);
417
418        assert!(idx.remove_tree_edge(1, 2));
419        assert!(!idx.tree_edges.contains(&(1, 2)));
420
421        idx.remove_non_tree_edge(1, 3);
422        assert!(!idx.level_edges[0].contains(&(1, 3)));
423    }
424}
ruvector_mincut/algorithm/replacement.rs

ruvector_mincut/algorithm/
replacement.rs
