problemreductions/models/graph/
minimum_multiway_cut.rs

1//! Minimum Multiway Cut problem implementation.
2//!
3//! The Minimum Multiway Cut problem asks for a minimum weight set of edges
4//! whose removal disconnects all terminal pairs.
5
6use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::types::{Min, WeightElement};
10use num_traits::Zero;
11use serde::{Deserialize, Serialize};
12use std::collections::VecDeque;
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "MinimumMultiwayCut",
17        display_name: "Minimum Multiway Cut",
18        aliases: &[],
19        dimensions: &[
20            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
21            VariantDimension::new("weight", "i64", &["i64"]),
22        ],
23        category: crate::registry::ProblemCategory::Graph,
24        module_path: module_path!(),
25        description: "Find minimum weight set of edges whose removal disconnects all terminal pairs",
26        fields: MinimumMultiwayCutCreateSpec::FIELDS,
27    }
28}
29
30/// The Minimum Multiway Cut problem.
31///
32/// Given an undirected weighted graph G = (V, E, w) and a set of k terminal
33/// vertices T = {t_1, ..., t_k}, find a minimum-weight set of edges C ⊆ E
34/// such that no two terminals remain in the same connected component of
35/// G' = (V, E \ C).
36///
37/// # Representation
38///
39/// Each edge is assigned a binary variable:
40/// - 0: edge is kept
41/// - 1: edge is removed (in the cut)
42///
43/// A configuration is feasible if removing the cut edges disconnects all
44/// terminal pairs.
45#[derive(Debug, Clone, Serialize, Deserialize)]
46#[serde(try_from = "MinimumMultiwayCutData<G, W>")]
47#[serde(bound(deserialize = "G: Graph + Deserialize<'de>, W: Clone + Default + Deserialize<'de>"))]
48pub struct MinimumMultiwayCut<G, W> {
49    graph: G,
50    terminals: Vec<usize>,
51    edge_weights: Vec<W>,
52}
53
54#[derive(Deserialize)]
55struct MinimumMultiwayCutData<G, W> {
56    graph: G,
57    terminals: Vec<usize>,
58    edge_weights: Vec<W>,
59}
60
61impl<G, W> TryFrom<MinimumMultiwayCutData<G, W>> for MinimumMultiwayCut<G, W>
62where
63    G: Graph,
64    W: Clone + Default,
65{
66    type Error = crate::registry::ConstructionError;
67
68    fn try_from(data: MinimumMultiwayCutData<G, W>) -> Result<Self, Self::Error> {
69        Self::try_new(data.graph, data.terminals, data.edge_weights)
70    }
71}
72
73#[derive(Debug, Deserialize, crate::CreateSpec)]
74struct MinimumMultiwayCutCreateSpec {
75    /// The undirected graph G=(V,E).
76    graph: SimpleGraph,
77    /// Terminal vertices that must be separated.
78    terminals: Vec<usize>,
79    /// Edge weights w: E -> R in graph edge order.
80    edge_weights: Vec<i64>,
81}
82
83impl TryFrom<MinimumMultiwayCutCreateSpec> for MinimumMultiwayCut<SimpleGraph, i64> {
84    type Error = crate::registry::ConstructionError;
85    fn try_from(spec: MinimumMultiwayCutCreateSpec) -> Result<Self, Self::Error> {
86        Self::try_new(spec.graph, spec.terminals, spec.edge_weights)
87    }
88}
89
90impl<G: Graph, W: Clone + Default> MinimumMultiwayCut<G, W> {
91    /// Create a MinimumMultiwayCut problem.
92    ///
93    /// `edge_weights` must have one entry per edge, in the same order as
94    /// [`Graph::edges()`](crate::topology::Graph::edges). Each binary
95    /// variable corresponds to an edge: 0 = keep, 1 = cut.
96    ///
97    /// # Panics
98    /// - If `edge_weights.len() != graph.num_edges()`
99    /// - If `terminals.len() < 2`
100    /// - If any terminal index is out of bounds
101    /// - If there are duplicate terminal indices
102    pub fn new(graph: G, terminals: Vec<usize>, edge_weights: Vec<W>) -> Self {
103        Self::try_new(graph, terminals, edge_weights).unwrap_or_else(|error| panic!("{error}"))
104    }
105
106    fn try_new(
107        graph: G,
108        terminals: Vec<usize>,
109        edge_weights: Vec<W>,
110    ) -> Result<Self, crate::registry::ConstructionError> {
111        if edge_weights.len() != graph.num_edges() {
112            return Err(crate::registry::ConstructionError::length_mismatch(
113                "edge_weights",
114                edge_weights.len(),
115                graph.num_edges(),
116            ));
117        }
118        if terminals.len() < 2 {
119            return Err("need at least 2 terminals".into());
120        }
121        let mut sorted = terminals.clone();
122        sorted.sort();
123        sorted.dedup();
124        if sorted.len() != terminals.len() {
125            return Err("duplicate terminal indices".into());
126        }
127        for &t in &terminals {
128            if t >= graph.num_vertices() {
129                return Err("terminal index out of bounds".into());
130            }
131        }
132        Ok(Self {
133            graph,
134            terminals,
135            edge_weights,
136        })
137    }
138
139    /// Get a reference to the underlying graph.
140    pub fn graph(&self) -> &G {
141        &self.graph
142    }
143
144    /// Get the terminal vertices.
145    pub fn terminals(&self) -> &[usize] {
146        &self.terminals
147    }
148
149    /// Get the edge weights.
150    pub fn edge_weights(&self) -> &[W] {
151        &self.edge_weights
152    }
153}
154
155impl<G: Graph, W: WeightElement> MinimumMultiwayCut<G, W> {
156    /// Number of vertices in the graph.
157    pub fn num_vertices(&self) -> usize {
158        self.graph.num_vertices()
159    }
160
161    /// Number of edges in the graph.
162    pub fn num_edges(&self) -> usize {
163        self.graph.num_edges()
164    }
165
166    /// Number of terminal vertices.
167    pub fn num_terminals(&self) -> usize {
168        self.terminals.len()
169    }
170}
171
172/// Check if all terminals are in distinct connected components
173/// when edges marked as cut (config[e]) are removed.
174fn terminals_separated<G: Graph>(graph: &G, terminals: &[usize], config: &[bool]) -> bool {
175    let n = graph.num_vertices();
176    let edges = graph.edges();
177
178    // Build adjacency list from non-cut edges
179    let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
180    for (idx, (u, v)) in edges.iter().enumerate() {
181        if !config[idx] {
182            adj[*u].push(*v);
183            adj[*v].push(*u);
184        }
185    }
186
187    // BFS from each terminal; if a terminal is already visited by a previous
188    // terminal's BFS, they share a component => infeasible.
189    let mut component = vec![usize::MAX; n];
190    for (comp_id, &t) in terminals.iter().enumerate() {
191        if component[t] != usize::MAX {
192            return false;
193        }
194        let mut queue = VecDeque::new();
195        queue.push_back(t);
196        component[t] = comp_id;
197        while let Some(u) = queue.pop_front() {
198            for &v in &adj[u] {
199                if component[v] == usize::MAX {
200                    component[v] = comp_id;
201                    queue.push_back(v);
202                }
203            }
204        }
205    }
206    true
207}
208
209impl<G, W> Problem for MinimumMultiwayCut<G, W>
210where
211    G: Graph + crate::variant::VariantParam,
212    W: WeightElement + crate::variant::VariantParam,
213{
214    const NAME: &'static str = "MinimumMultiwayCut";
215    type Solution = Vec<bool>;
216    type Value = Min<W::Sum>;
217
218    crate::problem_parameters![
219        ("num_edges", num_edges),
220        ("num_terminals", num_terminals),
221        ("num_vertices", num_vertices),
222    ];
223
224    fn variant() -> Vec<(&'static str, &'static str)> {
225        crate::variant_params![G, W]
226    }
227
228    fn evaluate(
229        &self,
230        config: &Self::Solution,
231    ) -> Result<Min<W::Sum>, crate::traits::EvaluationError> {
232        if config.len() != self.graph.num_edges() {
233            return Err(crate::traits::EvaluationError::InvalidConfiguration(
234                "edge-selection length does not match the graph".into(),
235            ));
236        }
237        Ok({
238            if !terminals_separated(&self.graph, &self.terminals, config) {
239                return Ok(Min(None));
240            }
241            let mut total = W::Sum::zero();
242            for (idx, &selected) in config.iter().enumerate() {
243                if selected {
244                    total = W::checked_add_to_sum(
245                        total,
246                        self.edge_weights[idx].to_sum(),
247                        "summing multiway cut edge weights",
248                    )?;
249                }
250            }
251            Min(Some(total))
252        })
253    }
254}
255
256impl<G, W> crate::solvers::BruteForceProblem for MinimumMultiwayCut<G, W>
257where
258    G: Graph + crate::variant::VariantParam,
259    W: WeightElement + crate::variant::VariantParam,
260{
261    fn dimensions(&self) -> Vec<usize> {
262        vec![2; self.graph.num_edges()]
263    }
264}
265
266crate::declare_variants! {
267    default MinimumMultiwayCut<SimpleGraph, i64> => "1.84^num_terminals * num_vertices^3" create MinimumMultiwayCutCreateSpec,
268}
269
270crate::register_brute_force! {
271    MinimumMultiwayCut<SimpleGraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
272}
273
274#[cfg(feature = "example-db")]
275pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
276    vec![crate::example_db::specs::ModelExampleSpec {
277        id: "minimum_multiway_cut_simplegraph",
278        instance: Box::new(MinimumMultiwayCut::new(
279            SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4), (0, 4), (1, 3)]),
280            vec![0, 2, 4],
281            vec![2, 3, 1, 2, 4, 5],
282        )),
283        optimal_config: serde_json::json!(vec![true, false, false, true, true, false]),
284        optimal_value: serde_json::json!(8),
285    }]
286}
287
288#[cfg(test)]
289#[path = "../../unit_tests/models/graph/minimum_multiway_cut.rs"]
290mod tests;
problemreductions/models/graph/minimum_multiway_cut.rs

problemreductions/models/graph/
minimum_multiway_cut.rs
