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)]
46pub struct MinimumMultiwayCut<G, W> {
47    graph: G,
48    terminals: Vec<usize>,
49    edge_weights: Vec<W>,
50}
51
52#[derive(Debug, Deserialize, crate::CreateSpec)]
53struct MinimumMultiwayCutCreateSpec {
54    /// The undirected graph G=(V,E).
55    graph: SimpleGraph,
56    /// Terminal vertices that must be separated.
57    terminals: Vec<usize>,
58    /// Edge weights w: E -> R in graph edge order.
59    edge_weights: Vec<i64>,
60}
61
62impl TryFrom<MinimumMultiwayCutCreateSpec> for MinimumMultiwayCut<SimpleGraph, i64> {
63    type Error = crate::registry::ConstructionError;
64    fn try_from(spec: MinimumMultiwayCutCreateSpec) -> Result<Self, Self::Error> {
65        if spec.edge_weights.len() != spec.graph.num_edges() {
66            return Err(format!(
67                "edge_weights has {} entries, expected {}",
68                spec.edge_weights.len(),
69                spec.graph.num_edges()
70            )
71            .into());
72        }
73        if spec.terminals.len() < 2 {
74            return Err("at least two terminals are required".to_string().into());
75        }
76        let mut distinct = spec.terminals.clone();
77        distinct.sort_unstable();
78        distinct.dedup();
79        if distinct.len() != spec.terminals.len() {
80            return Err("terminals must be distinct".to_string().into());
81        }
82        if let Some(&terminal) = spec
83            .terminals
84            .iter()
85            .find(|&&t| t >= spec.graph.num_vertices())
86        {
87            return Err(format!(
88                "terminal {terminal} is outside graph with {} vertices",
89                spec.graph.num_vertices()
90            )
91            .into());
92        }
93        Ok(Self::new(spec.graph, spec.terminals, spec.edge_weights))
94    }
95}
96
97impl<G: Graph, W: Clone + Default> MinimumMultiwayCut<G, W> {
98    /// Create a MinimumMultiwayCut problem.
99    ///
100    /// `edge_weights` must have one entry per edge, in the same order as
101    /// [`Graph::edges()`](crate::topology::Graph::edges). Each binary
102    /// variable corresponds to an edge: 0 = keep, 1 = cut.
103    ///
104    /// # Panics
105    /// - If `edge_weights.len() != graph.num_edges()`
106    /// - If `terminals.len() < 2`
107    /// - If any terminal index is out of bounds
108    /// - If there are duplicate terminal indices
109    pub fn new(graph: G, terminals: Vec<usize>, edge_weights: Vec<W>) -> Self {
110        assert_eq!(
111            edge_weights.len(),
112            graph.num_edges(),
113            "edge_weights length must match num_edges"
114        );
115        assert!(terminals.len() >= 2, "need at least 2 terminals");
116        let mut sorted = terminals.clone();
117        sorted.sort();
118        sorted.dedup();
119        assert_eq!(sorted.len(), terminals.len(), "duplicate terminal indices");
120        for &t in &terminals {
121            assert!(t < graph.num_vertices(), "terminal index out of bounds");
122        }
123        Self {
124            graph,
125            terminals,
126            edge_weights,
127        }
128    }
129
130    /// Get a reference to the underlying graph.
131    pub fn graph(&self) -> &G {
132        &self.graph
133    }
134
135    /// Get the terminal vertices.
136    pub fn terminals(&self) -> &[usize] {
137        &self.terminals
138    }
139
140    /// Get the edge weights.
141    pub fn edge_weights(&self) -> &[W] {
142        &self.edge_weights
143    }
144}
145
146impl<G: Graph, W: WeightElement> MinimumMultiwayCut<G, W> {
147    /// Number of vertices in the graph.
148    pub fn num_vertices(&self) -> usize {
149        self.graph.num_vertices()
150    }
151
152    /// Number of edges in the graph.
153    pub fn num_edges(&self) -> usize {
154        self.graph.num_edges()
155    }
156
157    /// Number of terminal vertices.
158    pub fn num_terminals(&self) -> usize {
159        self.terminals.len()
160    }
161}
162
163/// Check if all terminals are in distinct connected components
164/// when edges marked as cut (config[e]) are removed.
165fn terminals_separated<G: Graph>(graph: &G, terminals: &[usize], config: &[bool]) -> bool {
166    let n = graph.num_vertices();
167    let edges = graph.edges();
168
169    // Build adjacency list from non-cut edges
170    let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
171    for (idx, (u, v)) in edges.iter().enumerate() {
172        if !config.get(idx).copied().unwrap_or(false) {
173            adj[*u].push(*v);
174            adj[*v].push(*u);
175        }
176    }
177
178    // BFS from each terminal; if a terminal is already visited by a previous
179    // terminal's BFS, they share a component => infeasible.
180    let mut component = vec![usize::MAX; n];
181    for (comp_id, &t) in terminals.iter().enumerate() {
182        if component[t] != usize::MAX {
183            return false;
184        }
185        let mut queue = VecDeque::new();
186        queue.push_back(t);
187        component[t] = comp_id;
188        while let Some(u) = queue.pop_front() {
189            for &v in &adj[u] {
190                if component[v] == usize::MAX {
191                    component[v] = comp_id;
192                    queue.push_back(v);
193                }
194            }
195        }
196    }
197    true
198}
199
200impl<G, W> Problem for MinimumMultiwayCut<G, W>
201where
202    G: Graph + crate::variant::VariantParam,
203    W: WeightElement + crate::variant::VariantParam,
204{
205    const NAME: &'static str = "MinimumMultiwayCut";
206    type Solution = Vec<bool>;
207    type Value = Min<W::Sum>;
208
209    crate::problem_parameters![
210        ("num_edges", num_edges),
211        ("num_terminals", num_terminals),
212        ("num_vertices", num_vertices),
213    ];
214
215    fn variant() -> Vec<(&'static str, &'static str)> {
216        crate::variant_params![G, W]
217    }
218
219    fn evaluate(
220        &self,
221        config: &Self::Solution,
222    ) -> Result<Min<W::Sum>, crate::traits::EvaluationError> {
223        if config.len() != self.graph.num_edges() {
224            return Err(crate::traits::EvaluationError::InvalidConfiguration(
225                "edge-selection length does not match the graph".into(),
226            ));
227        }
228        Ok({
229            if !terminals_separated(&self.graph, &self.terminals, config) {
230                return Ok(Min(None));
231            }
232            let mut total = W::Sum::zero();
233            for (idx, &selected) in config.iter().enumerate() {
234                if selected {
235                    if let Some(w) = self.edge_weights.get(idx) {
236                        total = W::checked_add_to_sum(
237                            total,
238                            w.to_sum(),
239                            "summing multiway cut edge weights",
240                        )?;
241                    }
242                }
243            }
244            Min(Some(total))
245        })
246    }
247}
248
249impl<G, W> crate::solvers::BruteForceProblem for MinimumMultiwayCut<G, W>
250where
251    G: Graph + crate::variant::VariantParam,
252    W: WeightElement + crate::variant::VariantParam,
253{
254    fn dimensions(&self) -> Vec<usize> {
255        vec![2; self.graph.num_edges()]
256    }
257}
258
259crate::declare_variants! {
260    default MinimumMultiwayCut<SimpleGraph, i64> => "1.84^num_terminals * num_vertices^3" create MinimumMultiwayCutCreateSpec,
261}
262
263crate::register_brute_force! {
264    MinimumMultiwayCut<SimpleGraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
265}
266
267#[cfg(feature = "example-db")]
268pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
269    vec![crate::example_db::specs::ModelExampleSpec {
270        id: "minimum_multiway_cut_simplegraph",
271        instance: Box::new(MinimumMultiwayCut::new(
272            SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4), (0, 4), (1, 3)]),
273            vec![0, 2, 4],
274            vec![2, 3, 1, 2, 4, 5],
275        )),
276        optimal_config: serde_json::json!(vec![true, false, false, true, true, false]),
277        optimal_value: serde_json::json!(8),
278    }]
279}
280
281#[cfg(test)]
282#[path = "../../unit_tests/models/graph/minimum_multiway_cut.rs"]
283mod tests;
problemreductions/models/graph/minimum_multiway_cut.rs

problemreductions/models/graph/
minimum_multiway_cut.rs
