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::{FieldInfo, 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", "i32", &["i32"]),
22        ],
23        module_path: module_path!(),
24        description: "Find minimum weight set of edges whose removal disconnects all terminal pairs",
25        fields: &[
26            FieldInfo { name: "graph", type_name: "G", description: "The undirected graph G=(V,E)" },
27            FieldInfo { name: "terminals", type_name: "Vec<usize>", description: "Terminal vertices that must be separated" },
28            FieldInfo { name: "edge_weights", type_name: "Vec<W>", description: "Edge weights w: E -> R (same order as graph.edges())" },
29        ],
30    }
31}
32
33/// The Minimum Multiway Cut problem.
34///
35/// Given an undirected weighted graph G = (V, E, w) and a set of k terminal
36/// vertices T = {t_1, ..., t_k}, find a minimum-weight set of edges C ⊆ E
37/// such that no two terminals remain in the same connected component of
38/// G' = (V, E \ C).
39///
40/// # Representation
41///
42/// Each edge is assigned a binary variable:
43/// - 0: edge is kept
44/// - 1: edge is removed (in the cut)
45///
46/// A configuration is feasible if removing the cut edges disconnects all
47/// terminal pairs.
48#[derive(Debug, Clone, Serialize, Deserialize)]
49pub struct MinimumMultiwayCut<G, W> {
50    graph: G,
51    terminals: Vec<usize>,
52    edge_weights: Vec<W>,
53}
54
55impl<G: Graph, W: Clone + Default> MinimumMultiwayCut<G, W> {
56    /// Create a MinimumMultiwayCut problem.
57    ///
58    /// `edge_weights` must have one entry per edge, in the same order as
59    /// [`Graph::edges()`](crate::topology::Graph::edges). Each binary
60    /// variable corresponds to an edge: 0 = keep, 1 = cut.
61    ///
62    /// # Panics
63    /// - If `edge_weights.len() != graph.num_edges()`
64    /// - If `terminals.len() < 2`
65    /// - If any terminal index is out of bounds
66    /// - If there are duplicate terminal indices
67    pub fn new(graph: G, terminals: Vec<usize>, edge_weights: Vec<W>) -> Self {
68        assert_eq!(
69            edge_weights.len(),
70            graph.num_edges(),
71            "edge_weights length must match num_edges"
72        );
73        assert!(terminals.len() >= 2, "need at least 2 terminals");
74        let mut sorted = terminals.clone();
75        sorted.sort();
76        sorted.dedup();
77        assert_eq!(sorted.len(), terminals.len(), "duplicate terminal indices");
78        for &t in &terminals {
79            assert!(t < graph.num_vertices(), "terminal index out of bounds");
80        }
81        Self {
82            graph,
83            terminals,
84            edge_weights,
85        }
86    }
87
88    /// Get a reference to the underlying graph.
89    pub fn graph(&self) -> &G {
90        &self.graph
91    }
92
93    /// Get the terminal vertices.
94    pub fn terminals(&self) -> &[usize] {
95        &self.terminals
96    }
97
98    /// Get the edge weights.
99    pub fn edge_weights(&self) -> &[W] {
100        &self.edge_weights
101    }
102}
103
104impl<G: Graph, W: WeightElement> MinimumMultiwayCut<G, W> {
105    /// Number of vertices in the graph.
106    pub fn num_vertices(&self) -> usize {
107        self.graph.num_vertices()
108    }
109
110    /// Number of edges in the graph.
111    pub fn num_edges(&self) -> usize {
112        self.graph.num_edges()
113    }
114
115    /// Number of terminal vertices.
116    pub fn num_terminals(&self) -> usize {
117        self.terminals.len()
118    }
119}
120
121/// Check if all terminals are in distinct connected components
122/// when edges marked as cut (config[e] == 1) are removed.
123fn terminals_separated<G: Graph>(graph: &G, terminals: &[usize], config: &[usize]) -> bool {
124    let n = graph.num_vertices();
125    let edges = graph.edges();
126
127    // Build adjacency list from non-cut edges
128    let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
129    for (idx, (u, v)) in edges.iter().enumerate() {
130        if config.get(idx).copied().unwrap_or(0) == 0 {
131            adj[*u].push(*v);
132            adj[*v].push(*u);
133        }
134    }
135
136    // BFS from each terminal; if a terminal is already visited by a previous
137    // terminal's BFS, they share a component => infeasible.
138    let mut component = vec![usize::MAX; n];
139    for (comp_id, &t) in terminals.iter().enumerate() {
140        if component[t] != usize::MAX {
141            return false;
142        }
143        let mut queue = VecDeque::new();
144        queue.push_back(t);
145        component[t] = comp_id;
146        while let Some(u) = queue.pop_front() {
147            for &v in &adj[u] {
148                if component[v] == usize::MAX {
149                    component[v] = comp_id;
150                    queue.push_back(v);
151                }
152            }
153        }
154    }
155    true
156}
157
158impl<G, W> Problem for MinimumMultiwayCut<G, W>
159where
160    G: Graph + crate::variant::VariantParam,
161    W: WeightElement + crate::variant::VariantParam,
162{
163    const NAME: &'static str = "MinimumMultiwayCut";
164    type Value = Min<W::Sum>;
165
166    fn variant() -> Vec<(&'static str, &'static str)> {
167        crate::variant_params![G, W]
168    }
169
170    fn dims(&self) -> Vec<usize> {
171        vec![2; self.graph.num_edges()]
172    }
173
174    fn evaluate(&self, config: &[usize]) -> Min<W::Sum> {
175        if !terminals_separated(&self.graph, &self.terminals, config) {
176            return Min(None);
177        }
178        let mut total = W::Sum::zero();
179        for (idx, &selected) in config.iter().enumerate() {
180            if selected == 1 {
181                if let Some(w) = self.edge_weights.get(idx) {
182                    total += w.to_sum();
183                }
184            }
185        }
186        Min(Some(total))
187    }
188}
189
190crate::declare_variants! {
191    default MinimumMultiwayCut<SimpleGraph, i32> => "1.84^num_terminals * num_vertices^3",
192}
193
194#[cfg(feature = "example-db")]
195pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
196    vec![crate::example_db::specs::ModelExampleSpec {
197        id: "minimum_multiway_cut_simplegraph_i32",
198        instance: Box::new(MinimumMultiwayCut::new(
199            SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4), (0, 4), (1, 3)]),
200            vec![0, 2, 4],
201            vec![2, 3, 1, 2, 4, 5],
202        )),
203        optimal_config: vec![1, 0, 0, 1, 1, 0],
204        optimal_value: serde_json::json!(8),
205    }]
206}
207
208#[cfg(test)]
209#[path = "../../unit_tests/models/graph/minimum_multiway_cut.rs"]
210mod tests;
problemreductions/models/graph/minimum_multiway_cut.rs

problemreductions/models/graph/
minimum_multiway_cut.rs
