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)]
60pub struct MinimumCutIntoBoundedSets<G, W: WeightElement> {
61    /// The underlying graph structure.
62    graph: G,
63    /// Weights for each edge (in the same order as graph.edges()).
64    edge_weights: Vec<W>,
65    /// Source vertex s that must be in V1.
66    source: usize,
67    /// Sink vertex t that must be in V2.
68    sink: usize,
69    /// Maximum size B for each partition set.
70    size_bound: usize,
71}
72
73#[derive(Debug, Deserialize, crate::CreateSpec)]
74struct MinimumCutIntoBoundedSetsCreateSpec {
75    /// The undirected graph.
76    graph: SimpleGraph,
77    /// Edge weights; defaults to one per edge.
78    edge_weights: Option<Vec<i64>>,
79    /// Source vertex.
80    source: usize,
81    /// Sink vertex.
82    sink: usize,
83    /// Maximum size for each partition set.
84    size_bound: usize,
85}
86impl TryFrom<MinimumCutIntoBoundedSetsCreateSpec> for MinimumCutIntoBoundedSets<SimpleGraph, i64> {
87    type Error = crate::registry::ConstructionError;
88    fn try_from(spec: MinimumCutIntoBoundedSetsCreateSpec) -> Result<Self, Self::Error> {
89        let count = spec.graph.num_edges();
90        let edge_weights = spec.edge_weights.unwrap_or_else(|| vec![1; count]);
91        if edge_weights.len() != count {
92            return Err(format!(
93                "edge_weights has {} entries, expected {count}",
94                edge_weights.len()
95            )
96            .into());
97        }
98        let vertices = spec.graph.num_vertices();
99        if spec.source >= vertices || spec.sink >= vertices || spec.source == spec.sink {
100            return Err("source and sink must be distinct valid graph vertices"
101                .to_string()
102                .into());
103        }
104        Ok(Self::new(
105            spec.graph,
106            edge_weights,
107            spec.source,
108            spec.sink,
109            spec.size_bound,
110        ))
111    }
112}
113
114impl<G: Graph, W: WeightElement> MinimumCutIntoBoundedSets<G, W> {
115    /// Create a new MinimumCutIntoBoundedSets problem.
116    ///
117    /// # Arguments
118    /// * `graph` - The undirected graph
119    /// * `edge_weights` - Weights for each edge (must match graph.num_edges())
120    /// * `source` - Source vertex s (must be in V1)
121    /// * `sink` - Sink vertex t (must be in V2)
122    /// * `size_bound` - Maximum size B for each partition set
123    ///
124    /// # Panics
125    /// Panics if edge_weights length doesn't match num_edges, if source == sink,
126    /// or if source/sink are out of bounds.
127    pub fn new(
128        graph: G,
129        edge_weights: Vec<W>,
130        source: usize,
131        sink: usize,
132        size_bound: usize,
133    ) -> Self {
134        assert_eq!(
135            edge_weights.len(),
136            graph.num_edges(),
137            "edge_weights length must match num_edges"
138        );
139        assert!(source < graph.num_vertices(), "source vertex out of bounds");
140        assert!(sink < graph.num_vertices(), "sink vertex out of bounds");
141        assert_ne!(source, sink, "source and sink must be different vertices");
142        Self {
143            graph,
144            edge_weights,
145            source,
146            sink,
147            size_bound,
148        }
149    }
150
151    /// Get a reference to the underlying graph.
152    pub fn graph(&self) -> &G {
153        &self.graph
154    }
155
156    /// Get the edge weights.
157    pub fn edge_weights(&self) -> &[W] {
158        &self.edge_weights
159    }
160
161    /// Get the source vertex.
162    pub fn source(&self) -> usize {
163        self.source
164    }
165
166    /// Get the sink vertex.
167    pub fn sink(&self) -> usize {
168        self.sink
169    }
170
171    /// Get the size bound B.
172    pub fn size_bound(&self) -> usize {
173        self.size_bound
174    }
175
176    /// Get the number of vertices in the underlying graph.
177    pub fn num_vertices(&self) -> usize {
178        self.graph.num_vertices()
179    }
180
181    /// Get the number of edges in the underlying graph.
182    pub fn num_edges(&self) -> usize {
183        self.graph.num_edges()
184    }
185}
186
187impl<G, W> Problem for MinimumCutIntoBoundedSets<G, W>
188where
189    G: Graph + crate::variant::VariantParam,
190    W: WeightElement + crate::variant::VariantParam,
191{
192    const NAME: &'static str = "MinimumCutIntoBoundedSets";
193    type Solution = Vec<bool>;
194    type Value = Min<W::Sum>;
195
196    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
197
198    fn variant() -> Vec<(&'static str, &'static str)> {
199        crate::variant_params![G, W]
200    }
201
202    fn evaluate(
203        &self,
204        config: &Self::Solution,
205    ) -> Result<Min<W::Sum>, crate::traits::EvaluationError> {
206        Ok({
207            let n = self.graph.num_vertices();
208            if config.len() != n {
209                return Err(crate::traits::EvaluationError::InvalidConfiguration(
210                    "partition assignment length does not match the graph vertices".into(),
211                ));
212            }
213
214            // Check source is in V1 (config=0) and sink is in V2 (config=1)
215            if config[self.source] || !config[self.sink] {
216                return Ok(Min(None));
217            }
218
219            // Check size bounds
220            let count_v1 = config.iter().filter(|&&x| !x).count();
221            let count_v2 = config.iter().filter(|&&x| x).count();
222            if count_v1 > self.size_bound || count_v2 > self.size_bound {
223                return Ok(Min(None));
224            }
225
226            // Compute cut weight
227            let mut cut_weight = W::Sum::zero();
228            for ((u, v), weight) in self.graph.edges().iter().zip(self.edge_weights.iter()) {
229                if config[*u] != config[*v] {
230                    cut_weight = W::checked_add_to_sum(
231                        cut_weight,
232                        weight.to_sum(),
233                        "summing bounded-set cut weights",
234                    )?;
235                }
236            }
237
238            Min(Some(cut_weight))
239        })
240    }
241}
242
243impl<G, W> crate::solvers::BruteForceProblem for MinimumCutIntoBoundedSets<G, W>
244where
245    G: Graph + crate::variant::VariantParam,
246    W: WeightElement + crate::variant::VariantParam,
247{
248    fn dimensions(&self) -> Vec<usize> {
249        vec![2; self.graph.num_vertices()]
250    }
251}
252
253#[cfg(feature = "example-db")]
254pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
255    vec![crate::example_db::specs::ModelExampleSpec {
256        id: "minimum_cut_into_bounded_sets",
257        instance: Box::new(MinimumCutIntoBoundedSets::new(
258            SimpleGraph::new(
259                8,
260                vec![
261                    (0, 1),
262                    (0, 2),
263                    (1, 2),
264                    (1, 3),
265                    (2, 4),
266                    (3, 5),
267                    (3, 6),
268                    (4, 5),
269                    (4, 6),
270                    (5, 7),
271                    (6, 7),
272                    (5, 6),
273                ],
274            ),
275            vec![2, 3, 1, 4, 2, 1, 3, 2, 1, 2, 3, 1],
276            0,
277            7,
278            5,
279        )),
280        // V1={0,1,2,3}, V2={4,5,6,7}: cut edges (2,4)=2,(3,5)=1,(3,6)=3 => 6
281        optimal_config: serde_json::json!(vec![false, false, false, false, true, true, true, true]),
282        optimal_value: serde_json::json!(6),
283    }]
284}
285
286crate::impl_random_generate!(MinimumCutIntoBoundedSets<SimpleGraph, i64>, crate::random::EndpointRandomSpec, |spec| {
287    let (source, sink) = spec.endpoints()?;
288    let graph = spec.graph()?;
289    let edge_weights = vec![1; graph.num_edges()];
290    Ok(MinimumCutIntoBoundedSets::new(graph, edge_weights, source, sink, spec.num_vertices))
291});
292
293crate::declare_variants! {
294    default MinimumCutIntoBoundedSets<SimpleGraph, i64> => "2^num_vertices" create MinimumCutIntoBoundedSetsCreateSpec random,
295}
296
297crate::register_brute_force! {
298    MinimumCutIntoBoundedSets<SimpleGraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
299}
300
301#[cfg(test)]
302#[path = "../../unit_tests/models/graph/minimum_cut_into_bounded_sets.rs"]
303mod tests;
problemreductions/models/graph/minimum_cut_into_bounded_sets.rs

problemreductions/models/graph/
minimum_cut_into_bounded_sets.rs
