weavatrix_graph/algo/cuts/stoer_wagner/
mod.rs

1mod candidate;
2mod queue;
3
4use self::candidate::{Candidate, better, canonical_candidate, map_nodes, nodes, validate_weight};
5use self::queue::MaxQueue;
6use crate::{GraphError, IndexUndirectedGraphView, Measure, Result, Vec};
7use alloc::collections::BTreeMap;
8use core::cmp::Ordering;
9
10/// A deterministic global minimum cut and both sides of its partition.
11#[derive(Debug, Clone, PartialEq)]
12pub struct StoerWagnerCut<Node, Weight> {
13    weight: Weight,
14    partition: Vec<Node>,
15    complement: Vec<Node>,
16}
17
18impl<Node, Weight: Copy> StoerWagnerCut<Node, Weight> {
19    #[must_use]
20    pub const fn weight(&self) -> Weight {
21        self.weight
22    }
23
24    #[must_use]
25    pub fn partition(&self) -> &[Node] {
26        &self.partition
27    }
28
29    #[must_use]
30    pub fn complement(&self) -> &[Node] {
31        &self.complement
32    }
33
34    #[must_use]
35    pub fn into_parts(self) -> (Weight, Vec<Node>, Vec<Node>) {
36        (self.weight, self.partition, self.complement)
37    }
38}
39
40struct WorkingCut<M> {
41    adjacency: Vec<BTreeMap<usize, M>>,
42    active: Vec<bool>,
43    groups: Vec<Vec<usize>>,
44    active_count: usize,
45}
46
47/// Finds the global minimum cut of an undirected weighted multigraph.
48///
49/// Parallel edge weights are added with overflow checking; self-loops do not
50/// affect the cut. Empty and singleton graphs return `Ok(None)`.
51///
52/// # Errors
53///
54/// Returns an error for a negative/non-finite weight or checked-add overflow.
55pub fn stoer_wagner_min_cut<G, F, M>(
56    graph: &G,
57    edge_weight: F,
58) -> Result<Option<StoerWagnerCut<G::Node, M>>>
59where
60    G: IndexUndirectedGraphView,
61    F: FnMut(G::Edge) -> M,
62    M: Measure,
63{
64    stoer_wagner_min_cut_filtered(graph, |_| true, edge_weight)
65}
66
67/// Filtered Stoer-Wagner min-cut. Each predicate and accepted weight callback
68/// is evaluated exactly once per edge.
69///
70/// # Errors
71///
72/// Returns an error for invalid weights or arithmetic overflow.
73pub fn stoer_wagner_min_cut_filtered<G, P, F, M>(
74    graph: &G,
75    mut allows_edge: P,
76    mut edge_weight: F,
77) -> Result<Option<StoerWagnerCut<G::Node, M>>>
78where
79    G: IndexUndirectedGraphView,
80    P: FnMut(G::Edge) -> bool,
81    F: FnMut(G::Edge) -> M,
82    M: Measure,
83{
84    if graph.node_count() < 2 {
85        return Ok(None);
86    }
87    let (nodes_by_slot, nodes) = nodes(graph);
88    let mut working = WorkingCut::new(graph.node_bound(), &nodes);
89    for edge in graph.edge_indices() {
90        if !allows_edge(edge) {
91            continue;
92        }
93        let weight = edge_weight(edge);
94        validate_weight(weight)?;
95        let Some(endpoints) = graph.edge_endpoints(edge) else {
96            continue;
97        };
98        let source = G::node_slot(endpoints.source());
99        let target = G::node_slot(endpoints.target());
100        if source != target {
101            working.add_edge(source, target, weight)?;
102        }
103    }
104    let candidate = working.solve(&nodes)?;
105    candidate
106        .map(|cut| {
107            Ok(StoerWagnerCut {
108                weight: cut.weight,
109                partition: map_nodes(&cut.partition, &nodes_by_slot)?,
110                complement: map_nodes(&cut.complement, &nodes_by_slot)?,
111            })
112        })
113        .transpose()
114}
115
116impl<M: Measure> WorkingCut<M> {
117    fn new(node_bound: usize, nodes: &[usize]) -> Self {
118        let mut active = vec![false; node_bound];
119        for &node in nodes {
120            active[node] = true;
121        }
122        let groups = (0..node_bound).map(|node| vec![node]).collect();
123        Self {
124            adjacency: vec![BTreeMap::new(); node_bound],
125            active,
126            groups,
127            active_count: nodes.len(),
128        }
129    }
130
131    fn add_edge(&mut self, source: usize, target: usize, weight: M) -> Result<()> {
132        let sum = self.adjacency[source]
133            .get(&target)
134            .copied()
135            .unwrap_or_else(M::zero)
136            .checked_add(weight)
137            .ok_or(GraphError::ArithmeticOverflow {
138                operation: "Stoer-Wagner edge aggregation",
139            })?;
140        self.adjacency[source].insert(target, sum);
141        self.adjacency[target].insert(source, sum);
142        Ok(())
143    }
144
145    fn solve(&mut self, nodes: &[usize]) -> Result<Option<Candidate<M>>> {
146        let mut best = None;
147        let mut queue = MaxQueue::with_capacity(nodes.len() * 2);
148        let mut weights = vec![M::zero(); self.active.len()];
149        let mut added = vec![false; self.active.len()];
150        while self.active_count > 1 {
151            let (source, target, weight) =
152                self.phase(nodes, &mut queue, &mut weights, &mut added)?;
153            let candidate = canonical_candidate(weight, &self.groups[target], nodes);
154            if better(&candidate, best.as_ref()) {
155                best = Some(candidate);
156            }
157            self.merge(source, target)?;
158        }
159        Ok(best)
160    }
161
162    fn phase(
163        &self,
164        nodes: &[usize],
165        queue: &mut MaxQueue<M>,
166        weights: &mut [M],
167        added: &mut [bool],
168    ) -> Result<(usize, usize, M)> {
169        weights.fill(M::zero());
170        added.fill(false);
171        queue.clear();
172        for &node in nodes {
173            if self.active[node] {
174                queue.push(node, M::zero());
175            }
176        }
177        let mut previous = None;
178        for index in 0..self.active_count {
179            let (node, weight) = pop_current(queue, &self.active, added, weights)
180                .ok_or_else(|| invalid_phase_state("no queued active node remains"))?;
181            if index + 1 == self.active_count {
182                let source = previous
183                    .ok_or_else(|| invalid_phase_state("phase has fewer than two nodes"))?;
184                return Ok((source, node, weight));
185            }
186            added[node] = true;
187            previous = Some(node);
188            for (&neighbor, &edge_weight) in &self.adjacency[node] {
189                if self.active[neighbor] && !added[neighbor] {
190                    weights[neighbor] = weights[neighbor].checked_add(edge_weight).ok_or(
191                        GraphError::ArithmeticOverflow {
192                            operation: "Stoer-Wagner phase",
193                        },
194                    )?;
195                    queue.push(neighbor, weights[neighbor]);
196                }
197            }
198        }
199        Err(invalid_phase_state("phase selected no target"))
200    }
201
202    fn merge(&mut self, source: usize, target: usize) -> Result<()> {
203        let removed = core::mem::take(&mut self.adjacency[target]);
204        self.adjacency[source].remove(&target);
205        for (neighbor, weight) in removed {
206            self.adjacency[neighbor].remove(&target);
207            if neighbor == source || !self.active[neighbor] {
208                continue;
209            }
210            let sum = self.adjacency[source]
211                .get(&neighbor)
212                .copied()
213                .unwrap_or_else(M::zero)
214                .checked_add(weight)
215                .ok_or(GraphError::ArithmeticOverflow {
216                    operation: "Stoer-Wagner contraction",
217                })?;
218            self.adjacency[source].insert(neighbor, sum);
219            self.adjacency[neighbor].insert(source, sum);
220        }
221        self.active[target] = false;
222        self.active_count -= 1;
223        let mut target_group = core::mem::take(&mut self.groups[target]);
224        self.groups[source].append(&mut target_group);
225        self.groups[source].sort_unstable();
226        Ok(())
227    }
228}
229
230fn pop_current<M: Measure>(
231    queue: &mut MaxQueue<M>,
232    active: &[bool],
233    added: &[bool],
234    weights: &[M],
235) -> Option<(usize, M)> {
236    while let Some((node, weight)) = queue.pop() {
237        let Some((&is_active, &is_added, &current_weight)) = active
238            .get(node)
239            .zip(added.get(node))
240            .zip(weights.get(node))
241            .map(|((active, added), weight)| (active, added, weight))
242        else {
243            continue;
244        };
245        if is_active && !is_added && weight.compare(current_weight) == Some(Ordering::Equal) {
246            return Some((node, weight));
247        }
248    }
249    None
250}
251
252fn invalid_phase_state(value: &'static str) -> GraphError {
253    GraphError::InvalidAlgorithmParameter {
254        algorithm: "Stoer-Wagner",
255        parameter: "active cut state",
256        value: value.into(),
257    }
258}
weavatrix_graph/algo/cuts/stoer_wagner/mod.rs

weavatrix_graph/algo/cuts/stoer_wagner/
mod.rs
