problemreductions/models/graph/
max_cut.rs

1//! MaxCut problem implementation.
2//!
3//! The Maximum Cut problem asks for a partition of vertices into two sets
4//! that maximizes the total weight of edges crossing the partition.
5
6use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::types::{Max, One, WeightElement};
10use num_traits::Zero;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "MaxCut",
16        display_name: "Max Cut",
17        aliases: &["MaximumBipartiteSubgraph"],
18        dimensions: &[
19            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
20            VariantDimension::new("weight", "i64", &["i64", "One"]),
21        ],
22        category: crate::registry::ProblemCategory::Graph,
23        module_path: module_path!(),
24        description: "Find maximum weight cut in a graph",
25        fields: MaxCutI64CreateSpec::FIELDS,
26    }
27}
28
29/// The Maximum Cut problem.
30///
31/// Given a weighted graph G = (V, E) with edge weights w_e,
32/// find a partition of V into sets S and V\S such that
33/// the total weight of edges crossing the cut is maximized.
34///
35/// # Representation
36///
37/// Each vertex is assigned a binary value:
38/// - 0: vertex is in set S
39/// - 1: vertex is in set V\S
40///
41/// An edge contributes to the cut if its endpoints are in different sets.
42///
43/// # Type Parameters
44///
45/// * `G` - The graph type (e.g., `SimpleGraph`, `KingsSubgraph`, `UnitDiskGraph`)
46/// * `W` - The weight type for edges (e.g., `i64`, `f64`)
47///
48/// # Example
49///
50/// ```
51/// use problemreductions::models::graph::MaxCut;
52/// use problemreductions::topology::SimpleGraph;
53/// use problemreductions::types::Max;
54/// use problemreductions::{Problem, BruteForce};
55///
56/// // Create a triangle with unit weights
57/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]);
58/// let problem = MaxCut::new(graph, vec![1, 1, 1]);
59///
60/// // Solve with brute force
61/// let solver = BruteForce::new();
62/// let solutions = solver.find_all_witnesses(&problem).unwrap();
63///
64/// // Maximum cut in triangle is 2 (any partition cuts 2 edges)
65/// for sol in solutions {
66///     let size = problem.evaluate(&sol).unwrap();
67///     assert_eq!(size, Max(Some(2)));
68/// }
69/// ```
70#[derive(Debug, Clone, Serialize, Deserialize)]
71#[serde(try_from = "MaxCutData<G, W>")]
72#[serde(bound(deserialize = "G: Graph + Deserialize<'de>, W: Clone + Default + Deserialize<'de>"))]
73pub struct MaxCut<G, W> {
74    /// The underlying graph structure.
75    graph: G,
76    /// Weights for each edge (in the same order as graph.edges()).
77    edge_weights: Vec<W>,
78}
79
80#[derive(Deserialize)]
81struct MaxCutData<G, W> {
82    graph: G,
83    edge_weights: Vec<W>,
84}
85
86impl<G, W> TryFrom<MaxCutData<G, W>> for MaxCut<G, W>
87where
88    G: Graph,
89    W: Clone + Default,
90{
91    type Error = crate::registry::ConstructionError;
92
93    fn try_from(data: MaxCutData<G, W>) -> Result<Self, Self::Error> {
94        Self::try_new(data.graph, data.edge_weights)
95    }
96}
97
98macro_rules! max_cut_create_spec {
99    ($name:ident, $weight:ty, $one:expr $(, $edge_weights:ident)?) => {
100        #[derive(Debug, Deserialize, crate::CreateSpec)]
101        struct $name {
102            #[create(codec = "edge-list")]
103            graph: Vec<(usize, usize)>,
104            num_vertices: Option<usize>,
105            $(
106            #[create(codec = "comma-separated")]
107            $edge_weights: Option<Vec<$weight>>,
108            )?
109        }
110
111        impl TryFrom<$name> for MaxCut<SimpleGraph, $weight> {
112            type Error = crate::registry::ConstructionError;
113
114            fn try_from(spec: $name) -> Result<Self, Self::Error> {
115                let graph = simple_graph_from_create(spec.graph, spec.num_vertices)?;
116                let edge_weights = { $(if let Some(value) = spec.$edge_weights { value } else)? { vec![$one; graph.num_edges()] } };
117                Self::try_new(graph, edge_weights)
118            }
119        }
120    };
121}
122
123max_cut_create_spec!(MaxCutI64CreateSpec, i64, 1, edge_weights);
124max_cut_create_spec!(MaxCutOneCreateSpec, One, One);
125
126fn simple_graph_from_create(
127    edges: Vec<(usize, usize)>,
128    num_vertices: Option<usize>,
129) -> Result<SimpleGraph, crate::registry::ConstructionError> {
130    if edges.is_empty() && num_vertices.is_none() {
131        return Err("num_vertices is required for an empty graph"
132            .to_string()
133            .into());
134    }
135    for (index, &(u, v)) in edges.iter().enumerate() {
136        if u == v {
137            return Err(format!("graph edge {index} is a self-loop at vertex {u}").into());
138        }
139    }
140    let inferred = edges
141        .iter()
142        .flat_map(|&(u, v)| [u, v])
143        .max()
144        .map(|vertex| vertex.checked_add(1).ok_or("vertex count overflows usize"))
145        .transpose()?
146        .unwrap_or(0);
147    let num_vertices = num_vertices.unwrap_or(inferred);
148    if num_vertices < inferred {
149        return Err(format!("num_vertices {num_vertices} is too small for graph endpoints; need at least {inferred}").into());
150    }
151    Ok(SimpleGraph::new(num_vertices, edges))
152}
153
154impl<G: Graph, W: Clone + Default> MaxCut<G, W> {
155    /// Create a MaxCut problem from a graph with specified edge weights.
156    ///
157    /// # Arguments
158    /// * `graph` - The underlying graph
159    /// * `edge_weights` - Weights for each edge (must match graph.num_edges())
160    pub fn new(graph: G, edge_weights: Vec<W>) -> Self {
161        Self::try_new(graph, edge_weights).unwrap_or_else(|error| panic!("{error}"))
162    }
163
164    fn try_new(graph: G, edge_weights: Vec<W>) -> Result<Self, crate::registry::ConstructionError> {
165        if edge_weights.len() != graph.num_edges() {
166            return Err(crate::registry::ConstructionError::length_mismatch(
167                "edge_weights",
168                edge_weights.len(),
169                graph.num_edges(),
170            ));
171        }
172        Ok(Self {
173            graph,
174            edge_weights,
175        })
176    }
177
178    /// Create a MaxCut problem with unit weights.
179    pub fn unweighted(graph: G) -> Self
180    where
181        W: WeightElement,
182    {
183        let edge_weights = vec![W::unit(); graph.num_edges()];
184        Self {
185            graph,
186            edge_weights,
187        }
188    }
189
190    /// Get a reference to the underlying graph.
191    pub fn graph(&self) -> &G {
192        &self.graph
193    }
194
195    /// Get the edges with weights.
196    pub fn edges(&self) -> Vec<(usize, usize, W)> {
197        self.graph
198            .edges()
199            .into_iter()
200            .zip(self.edge_weights.iter())
201            .map(|((u, v), w)| (u, v, w.clone()))
202            .collect()
203    }
204
205    /// Get the weight of an edge by its index.
206    pub fn edge_weight_by_index(&self, idx: usize) -> Option<&W> {
207        self.edge_weights.get(idx)
208    }
209
210    /// Get the weight of an edge between vertices u and v.
211    pub fn edge_weight(&self, u: usize, v: usize) -> Option<&W> {
212        // Find the edge index
213        for (idx, (eu, ev)) in self.graph.edges().iter().enumerate() {
214            if (*eu == u && *ev == v) || (*eu == v && *ev == u) {
215                return self.edge_weights.get(idx);
216            }
217        }
218        None
219    }
220
221    /// Get edge weights only.
222    pub fn edge_weights(&self) -> Vec<W> {
223        self.edge_weights.clone()
224    }
225
226    /// Compute the cut size for a given partition configuration.
227    pub fn cut_size(&self, config: &[bool]) -> Result<W::Sum, crate::traits::EvaluationError>
228    where
229        W: WeightElement,
230    {
231        cut_size(&self.graph, &self.edge_weights, config)
232    }
233}
234
235impl<G: Graph, W: WeightElement> MaxCut<G, W> {
236    /// Get the number of vertices in the underlying graph.
237    pub fn num_vertices(&self) -> usize {
238        self.graph().num_vertices()
239    }
240
241    /// Get the number of edges in the underlying graph.
242    pub fn num_edges(&self) -> usize {
243        self.graph().num_edges()
244    }
245}
246
247impl<G, W> Problem for MaxCut<G, W>
248where
249    G: Graph + crate::variant::VariantParam,
250    W: WeightElement + crate::variant::VariantParam,
251{
252    const NAME: &'static str = "MaxCut";
253    type Solution = Vec<bool>;
254    type Value = Max<W::Sum>;
255
256    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
257
258    fn variant() -> Vec<(&'static str, &'static str)> {
259        crate::variant_params![G, W]
260    }
261
262    fn evaluate(
263        &self,
264        config: &Self::Solution,
265    ) -> Result<Max<W::Sum>, crate::traits::EvaluationError> {
266        if config.len() != self.graph.num_vertices() {
267            return Err(crate::traits::EvaluationError::InvalidConfiguration(
268                "cut assignment length does not match the graph vertices".into(),
269            ));
270        }
271        Ok({
272            // All cuts are valid, so always return Valid
273            Max(Some(cut_size(&self.graph, &self.edge_weights, config)?))
274        })
275    }
276}
277
278impl<G, W> crate::solvers::BruteForceProblem for MaxCut<G, W>
279where
280    G: Graph + crate::variant::VariantParam,
281    W: WeightElement + crate::variant::VariantParam,
282{
283    fn dimensions(&self) -> Vec<usize> {
284        vec![2; self.graph.num_vertices()]
285    }
286}
287
288/// Compute the total weight of edges crossing the cut.
289///
290/// # Arguments
291/// * `graph` - The graph structure
292/// * `edge_weights` - Weights for each edge (same order as `graph.edges()`)
293/// * `partition` - Boolean slice indicating which set each vertex belongs to
294pub(crate) fn cut_size<G, W>(
295    graph: &G,
296    edge_weights: &[W],
297    partition: &[bool],
298) -> Result<W::Sum, crate::traits::EvaluationError>
299where
300    G: Graph,
301    W: WeightElement,
302{
303    let mut total = W::Sum::zero();
304    for ((u, v), weight) in graph.edges().iter().zip(edge_weights.iter()) {
305        if *u < partition.len() && *v < partition.len() && partition[*u] != partition[*v] {
306            total = W::checked_add_to_sum(total, weight.to_sum(), "summing cut-edge weights")?;
307        }
308    }
309    Ok(total)
310}
311
312crate::impl_random_generate!(MaxCut<SimpleGraph, i64>, crate::random::SimpleGraphRandomSpec, |spec| {
313    let graph = spec.graph()?;
314    let weights = vec![1; graph.num_edges()];
315    Ok(MaxCut::new(graph, weights))
316});
317
318crate::declare_variants! {
319    default MaxCut<SimpleGraph, i64> => "2^(2.372 * num_vertices / 3)" create MaxCutI64CreateSpec random,
320    MaxCut<SimpleGraph, One> => "2^(0.7907 * num_vertices)" create MaxCutOneCreateSpec,
321}
322
323crate::register_brute_force! {
324    MaxCut<SimpleGraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
325    MaxCut<SimpleGraph, One> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
326}
327
328#[cfg(feature = "example-db")]
329pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
330    vec![
331        crate::example_db::specs::ModelExampleSpec {
332            id: "max_cut_simplegraph",
333            instance: Box::new(MaxCut::<_, i64>::unweighted(SimpleGraph::new(
334                5,
335                vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)],
336            ))),
337            optimal_config: serde_json::json!(vec![true, false, false, true, false]),
338            optimal_value: serde_json::json!(5),
339        },
340        crate::example_db::specs::ModelExampleSpec {
341            id: "max_cut_seven_edge_graph",
342            instance: Box::new(MaxCut::new(
343                SimpleGraph::new(
344                    5,
345                    vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 4), (2, 3), (3, 4)],
346                ),
347                vec![One; 7],
348            )),
349            optimal_config: serde_json::json!(vec![false, true, false, true, false]),
350            optimal_value: serde_json::json!(6),
351        },
352    ]
353}
354
355#[cfg(test)]
356#[path = "../../unit_tests/models/graph/max_cut.rs"]
357mod tests;
358
359crate::decision_problem_meta!(MaxCut<SimpleGraph, i64>, "DecisionMaxCut");
360crate::register_decision_variant!(
361    MaxCut<SimpleGraph, i64>, "DecisionMaxCut", "2^(2.372 * num_vertices / 3)", &[],
362    "Does a feasible solution have objective value >= the bound?",
363    category: crate::registry::ProblemCategory::Graph,
364    dims: [
365            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
366            VariantDimension::new("weight", "i64", &["i64"]),
367        ],
368    fields: [
369        crate::registry::FieldInfo { name: "graph", type_name: "Vec<(usize,usize)>", description: "Graph edges as comma-separated vertex pairs." },
370        crate::registry::FieldInfo { name: "num_vertices", type_name: "usize", description: "Number of vertices, including isolated vertices." },
371        crate::registry::FieldInfo { name: "edge_weights", type_name: "Vec<i64>", description: "Weights for each edge in graph order." },
372        crate::registry::FieldInfo { name: "bound", type_name: "i64", description: "Accept objective values >= this bound" },
373    ],
374    decode: |_, indices: Vec<usize>| crate::config::config_to_bits(&indices)
375);
376
377#[cfg(feature = "example-db")]
378pub(crate) fn decision_canonical_rule_example_specs(
379) -> Vec<crate::example_db::specs::RuleExampleSpec> {
380    vec![crate::example_db::specs::RuleExampleSpec {
381        id: "decision_max_cut_to_max_cut",
382        build: || {
383            let source = crate::models::decision::Decision::new(
384                MaxCut::<_, i64>::unweighted(SimpleGraph::new(
385                    5,
386                    vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)],
387                )),
388                5,
389            );
390            let witness = serde_json::json!(vec![true, false, false, true, false]);
391            crate::example_db::specs::rule_example_with_witness::<_, MaxCut<SimpleGraph, i64>>(
392                source,
393                crate::export::SolutionPair {
394                    source_config: witness.clone(),
395                    target_config: witness,
396                },
397            )
398        },
399    }]
400}
problemreductions/models/graph/max_cut.rs

problemreductions/models/graph/
max_cut.rs
