problemreductions/models/graph/
minimum_cut_into_bounded_sets.rs

1//! MinimumCutIntoBoundedSets problem implementation.
2//!
3//! A graph partitioning problem that finds a partition of vertices into two
4//! bounded-size sets (containing designated source and sink vertices) that
5//! minimizes total cut weight. From Garey & Johnson, A2 ND17.
6
7use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
8use crate::topology::{Graph, SimpleGraph};
9use crate::traits::Problem;
10use crate::types::{Min, WeightElement};
11use num_traits::Zero;
12use serde::{Deserialize, Serialize};
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "MinimumCutIntoBoundedSets",
17        display_name: "Minimum Cut Into Bounded Sets",
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 a minimum-weight cut partitioning vertices into two bounded-size sets",
26        fields: MinimumCutIntoBoundedSetsCreateSpec::FIELDS,
27    }
28}
29
30/// Minimum Cut Into Bounded Sets (Garey & Johnson ND17).
31///
32/// Given a weighted graph G = (V, E), source vertex s, sink vertex t,
33/// and size bound B, find a partition of V into disjoint sets V1 and V2
34/// such that:
35/// - s is in V1, t is in V2
36/// - |V1| <= B, |V2| <= B
37/// - The total weight of edges crossing the partition is minimized
38///
39/// # Type Parameters
40///
41/// * `G` - The graph type (e.g., `SimpleGraph`)
42/// * `W` - The weight type for edges (e.g., `i64`)
43///
44/// # Example
45///
46/// ```
47/// use problemreductions::models::graph::MinimumCutIntoBoundedSets;
48/// use problemreductions::topology::SimpleGraph;
49/// use problemreductions::{Problem, BruteForce};
50///
51/// // Simple 4-vertex path graph with unit weights, s=0, t=3
52/// let graph = SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]);
53/// let problem = MinimumCutIntoBoundedSets::new(graph, vec![1, 1, 1], 0, 3, 3);
54///
55/// // Partition {0,1} vs {2,3}: cut edge (1,2) with weight 1
56/// let val = problem.evaluate(&vec![false, false, true, true]).unwrap();
57/// assert_eq!(val, problemreductions::types::Min(Some(1)));
58/// ```
59#[derive(Debug, Clone, Serialize, Deserialize)]
60#[serde(try_from = "MinimumCutIntoBoundedSetsData<G, W>")]
61#[serde(bound(deserialize = "G: Graph + Deserialize<'de>, W: WeightElement + Deserialize<'de>"))]
62pub struct MinimumCutIntoBoundedSets<G, W: WeightElement> {
63    /// The underlying graph structure.
64    graph: G,
65    /// Weights for each edge (in the same order as graph.edges()).
66    edge_weights: Vec<W>,
67    /// Source vertex s that must be in V1.
68    source: usize,
69    /// Sink vertex t that must be in V2.
70    sink: usize,
71    /// Maximum size B for each partition set.
72    size_bound: usize,
73}
74
75#[derive(Deserialize)]
76#[serde(bound(deserialize = "G: Graph + Deserialize<'de>, W: WeightElement + Deserialize<'de>"))]
77struct MinimumCutIntoBoundedSetsData<G, W: WeightElement> {
78    graph: G,
79    edge_weights: Vec<W>,
80    source: usize,
81    sink: usize,
82    size_bound: usize,
83}
84
85impl<G, W> TryFrom<MinimumCutIntoBoundedSetsData<G, W>> for MinimumCutIntoBoundedSets<G, W>
86where
87    G: Graph,
88    W: WeightElement,
89{
90    type Error = crate::registry::ConstructionError;
91
92    fn try_from(data: MinimumCutIntoBoundedSetsData<G, W>) -> Result<Self, Self::Error> {
93        Self::try_new(
94            data.graph,
95            data.edge_weights,
96            data.source,
97            data.sink,
98            data.size_bound,
99        )
100    }
101}
102
103#[derive(Debug, Deserialize, crate::CreateSpec)]
104struct MinimumCutIntoBoundedSetsCreateSpec {
105    /// The undirected graph.
106    graph: SimpleGraph,
107    /// Edge weights; defaults to one per edge.
108    edge_weights: Option<Vec<i64>>,
109    /// Source vertex.
110    source: usize,
111    /// Sink vertex.
112    sink: usize,
113    /// Maximum size for each partition set.
114    size_bound: usize,
115}
116impl TryFrom<MinimumCutIntoBoundedSetsCreateSpec> for MinimumCutIntoBoundedSets<SimpleGraph, i64> {
117    type Error = crate::registry::ConstructionError;
118    fn try_from(spec: MinimumCutIntoBoundedSetsCreateSpec) -> Result<Self, Self::Error> {
119        let count = spec.graph.num_edges();
120        let edge_weights = spec.edge_weights.unwrap_or_else(|| vec![1; count]);
121        Self::try_new(
122            spec.graph,
123            edge_weights,
124            spec.source,
125            spec.sink,
126            spec.size_bound,
127        )
128    }
129}
130
131impl<G: Graph, W: WeightElement> MinimumCutIntoBoundedSets<G, W> {
132    /// Create a new MinimumCutIntoBoundedSets problem.
133    ///
134    /// # Arguments
135    /// * `graph` - The undirected graph
136    /// * `edge_weights` - Weights for each edge (must match graph.num_edges())
137    /// * `source` - Source vertex s (must be in V1)
138    /// * `sink` - Sink vertex t (must be in V2)
139    /// * `size_bound` - Maximum size B for each partition set
140    ///
141    /// # Panics
142    /// Panics if edge_weights length doesn't match num_edges, if source == sink,
143    /// or if source/sink are out of bounds.
144    pub fn new(
145        graph: G,
146        edge_weights: Vec<W>,
147        source: usize,
148        sink: usize,
149        size_bound: usize,
150    ) -> Self {
151        Self::try_new(graph, edge_weights, source, sink, size_bound)
152            .unwrap_or_else(|error| panic!("{error}"))
153    }
154
155    fn try_new(
156        graph: G,
157        edge_weights: Vec<W>,
158        source: usize,
159        sink: usize,
160        size_bound: usize,
161    ) -> Result<Self, crate::registry::ConstructionError> {
162        if edge_weights.len() != graph.num_edges() {
163            return Err(crate::registry::ConstructionError::length_mismatch(
164                "edge_weights",
165                edge_weights.len(),
166                graph.num_edges(),
167            ));
168        }
169        if source >= graph.num_vertices() {
170            return Err("source vertex out of bounds".into());
171        }
172        if sink >= graph.num_vertices() {
173            return Err("sink vertex out of bounds".into());
174        }
175        if source == sink {
176            return Err("source and sink must be different vertices".into());
177        }
178        Ok(Self {
179            graph,
180            edge_weights,
181            source,
182            sink,
183            size_bound,
184        })
185    }
186
187    /// Get a reference to the underlying graph.
188    pub fn graph(&self) -> &G {
189        &self.graph
190    }
191
192    /// Get the edge weights.
193    pub fn edge_weights(&self) -> &[W] {
194        &self.edge_weights
195    }
196
197    /// Get the source vertex.
198    pub fn source(&self) -> usize {
199        self.source
200    }
201
202    /// Get the sink vertex.
203    pub fn sink(&self) -> usize {
204        self.sink
205    }
206
207    /// Get the size bound B.
208    pub fn size_bound(&self) -> usize {
209        self.size_bound
210    }
211
212    /// Get the number of vertices in the underlying graph.
213    pub fn num_vertices(&self) -> usize {
214        self.graph.num_vertices()
215    }
216
217    /// Get the number of edges in the underlying graph.
218    pub fn num_edges(&self) -> usize {
219        self.graph.num_edges()
220    }
221}
222
223impl<G, W> Problem for MinimumCutIntoBoundedSets<G, W>
224where
225    G: Graph + crate::variant::VariantParam,
226    W: WeightElement + crate::variant::VariantParam,
227{
228    const NAME: &'static str = "MinimumCutIntoBoundedSets";
229    type Solution = Vec<bool>;
230    type Value = Min<W::Sum>;
231
232    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
233
234    fn variant() -> Vec<(&'static str, &'static str)> {
235        crate::variant_params![G, W]
236    }
237
238    fn evaluate(
239        &self,
240        config: &Self::Solution,
241    ) -> Result<Min<W::Sum>, crate::traits::EvaluationError> {
242        Ok({
243            let n = self.graph.num_vertices();
244            if config.len() != n {
245                return Err(crate::traits::EvaluationError::InvalidConfiguration(
246                    "partition assignment length does not match the graph vertices".into(),
247                ));
248            }
249
250            // Check source is in V1 (config=0) and sink is in V2 (config=1)
251            if config[self.source] || !config[self.sink] {
252                return Ok(Min(None));
253            }
254
255            // Check size bounds
256            let count_v1 = config.iter().filter(|&&x| !x).count();
257            let count_v2 = config.iter().filter(|&&x| x).count();
258            if count_v1 > self.size_bound || count_v2 > self.size_bound {
259                return Ok(Min(None));
260            }
261
262            // Compute cut weight
263            let mut cut_weight = W::Sum::zero();
264            for ((u, v), weight) in self.graph.edges().iter().zip(self.edge_weights.iter()) {
265                if config[*u] != config[*v] {
266                    cut_weight = W::checked_add_to_sum(
267                        cut_weight,
268                        weight.to_sum(),
269                        "summing bounded-set cut weights",
270                    )?;
271                }
272            }
273
274            Min(Some(cut_weight))
275        })
276    }
277}
278
279impl<G, W> crate::solvers::BruteForceProblem for MinimumCutIntoBoundedSets<G, W>
280where
281    G: Graph + crate::variant::VariantParam,
282    W: WeightElement + crate::variant::VariantParam,
283{
284    fn dimensions(&self) -> Vec<usize> {
285        vec![2; self.graph.num_vertices()]
286    }
287}
288
289#[cfg(feature = "example-db")]
290pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
291    vec![crate::example_db::specs::ModelExampleSpec {
292        id: "minimum_cut_into_bounded_sets",
293        instance: Box::new(MinimumCutIntoBoundedSets::new(
294            SimpleGraph::new(
295                8,
296                vec![
297                    (0, 1),
298                    (0, 2),
299                    (1, 2),
300                    (1, 3),
301                    (2, 4),
302                    (3, 5),
303                    (3, 6),
304                    (4, 5),
305                    (4, 6),
306                    (5, 7),
307                    (6, 7),
308                    (5, 6),
309                ],
310            ),
311            vec![2, 3, 1, 4, 2, 1, 3, 2, 1, 2, 3, 1],
312            0,
313            7,
314            5,
315        )),
316        // V1={0,1,2,3}, V2={4,5,6,7}: cut edges (2,4)=2,(3,5)=1,(3,6)=3 => 6
317        optimal_config: serde_json::json!(vec![false, false, false, false, true, true, true, true]),
318        optimal_value: serde_json::json!(6),
319    }]
320}
321
322crate::impl_random_generate!(MinimumCutIntoBoundedSets<SimpleGraph, i64>, crate::random::EndpointRandomSpec, |spec| {
323    let (source, sink) = spec.endpoints()?;
324    let graph = spec.graph()?;
325    let edge_weights = vec![1; graph.num_edges()];
326    Ok(MinimumCutIntoBoundedSets::new(graph, edge_weights, source, sink, spec.num_vertices))
327});
328
329crate::declare_variants! {
330    default MinimumCutIntoBoundedSets<SimpleGraph, i64> => "2^num_vertices" create MinimumCutIntoBoundedSetsCreateSpec random,
331}
332
333crate::register_brute_force! {
334    MinimumCutIntoBoundedSets<SimpleGraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
335}
336
337#[cfg(test)]
338#[path = "../../unit_tests/models/graph/minimum_cut_into_bounded_sets.rs"]
339mod tests;
problemreductions/models/graph/minimum_cut_into_bounded_sets.rs

problemreductions/models/graph/
minimum_cut_into_bounded_sets.rs
