ruvector_dag/mincut/
local_kcut.rs

1//! Local K-Cut: Sublinear min-cut approximation
2
3use super::engine::{FlowEdge, MinCutResult};
4use std::collections::{HashMap, HashSet, VecDeque};
5
6/// Local K-Cut oracle for approximate min-cut
7pub struct LocalKCut {
8    visited: HashSet<usize>,
9    distance: HashMap<usize, usize>,
10}
11
12impl LocalKCut {
13    pub fn new() -> Self {
14        Self {
15            visited: HashSet::new(),
16            distance: HashMap::new(),
17        }
18    }
19
20    /// Compute approximate min-cut using local search
21    /// Time complexity: O(k * local_depth) where k << n
22    pub fn compute(
23        &mut self,
24        graph: &HashMap<usize, Vec<FlowEdge>>,
25        source: usize,
26        sink: usize,
27        depth: usize,
28    ) -> MinCutResult {
29        self.visited.clear();
30        self.distance.clear();
31
32        // BFS from source with limited depth
33        let source_reachable = self.limited_bfs(graph, source, depth);
34
35        // BFS from sink with limited depth
36        let sink_reachable = self.limited_bfs(graph, sink, depth);
37
38        // Find cut edges
39        let mut cut_edges = Vec::new();
40        let mut cut_value = 0.0;
41
42        for &node in &source_reachable {
43            if let Some(edges) = graph.get(&node) {
44                for edge in edges {
45                    if !source_reachable.contains(&edge.to) && edge.capacity > 0.0 {
46                        cut_edges.push((edge.from, edge.to));
47                        cut_value += edge.capacity;
48                    }
49                }
50            }
51        }
52
53        MinCutResult {
54            cut_value,
55            source_side: source_reachable,
56            sink_side: sink_reachable,
57            cut_edges,
58        }
59    }
60
61    fn limited_bfs(
62        &mut self,
63        graph: &HashMap<usize, Vec<FlowEdge>>,
64        start: usize,
65        max_depth: usize,
66    ) -> HashSet<usize> {
67        let mut reachable = HashSet::new();
68        let mut queue = VecDeque::new();
69
70        queue.push_back((start, 0));
71        reachable.insert(start);
72
73        while let Some((node, depth)) = queue.pop_front() {
74            if depth >= max_depth {
75                continue;
76            }
77
78            if let Some(edges) = graph.get(&node) {
79                for edge in edges {
80                    if edge.capacity > edge.flow && !reachable.contains(&edge.to) {
81                        reachable.insert(edge.to);
82                        queue.push_back((edge.to, depth + 1));
83                    }
84                }
85            }
86        }
87
88        reachable
89    }
90}
ruvector_dag/mincut/local_kcut.rs

ruvector_dag/mincut/
local_kcut.rs
