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::{FieldInfo, ProblemSchemaEntry};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::{OptimizationProblem, Problem};
9use crate::types::{Direction, SolutionSize, WeightElement};
10use num_traits::Zero;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "MaxCut",
16        module_path: module_path!(),
17        description: "Find maximum weight cut in a graph",
18        fields: &[
19            FieldInfo { name: "graph", type_name: "G", description: "The graph with edge weights" },
20            FieldInfo { name: "edge_weights", type_name: "Vec<W>", description: "Edge weights w: E -> R" },
21        ],
22    }
23}
24
25/// The Maximum Cut problem.
26///
27/// Given a weighted graph G = (V, E) with edge weights w_e,
28/// find a partition of V into sets S and V\S such that
29/// the total weight of edges crossing the cut is maximized.
30///
31/// # Representation
32///
33/// Each vertex is assigned a binary value:
34/// - 0: vertex is in set S
35/// - 1: vertex is in set V\S
36///
37/// An edge contributes to the cut if its endpoints are in different sets.
38///
39/// # Type Parameters
40///
41/// * `G` - The graph type (e.g., `SimpleGraph`, `KingsSubgraph`, `UnitDiskGraph`)
42/// * `W` - The weight type for edges (e.g., `i32`, `f64`)
43///
44/// # Example
45///
46/// ```
47/// use problemreductions::models::graph::MaxCut;
48/// use problemreductions::topology::SimpleGraph;
49/// use problemreductions::types::SolutionSize;
50/// use problemreductions::{Problem, Solver, BruteForce};
51///
52/// // Create a triangle with unit weights
53/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]);
54/// let problem = MaxCut::new(graph, vec![1, 1, 1]);
55///
56/// // Solve with brute force
57/// let solver = BruteForce::new();
58/// let solutions = solver.find_all_best(&problem);
59///
60/// // Maximum cut in triangle is 2 (any partition cuts 2 edges)
61/// for sol in solutions {
62///     let size = problem.evaluate(&sol);
63///     assert_eq!(size, SolutionSize::Valid(2));
64/// }
65/// ```
66#[derive(Debug, Clone, Serialize, Deserialize)]
67pub struct MaxCut<G, W> {
68    /// The underlying graph structure.
69    graph: G,
70    /// Weights for each edge (in the same order as graph.edges()).
71    edge_weights: Vec<W>,
72}
73
74impl<G: Graph, W: Clone + Default> MaxCut<G, W> {
75    /// Create a MaxCut problem from a graph with specified edge weights.
76    ///
77    /// # Arguments
78    /// * `graph` - The underlying graph
79    /// * `edge_weights` - Weights for each edge (must match graph.num_edges())
80    pub fn new(graph: G, edge_weights: Vec<W>) -> Self {
81        assert_eq!(
82            edge_weights.len(),
83            graph.num_edges(),
84            "edge_weights length must match num_edges"
85        );
86        Self {
87            graph,
88            edge_weights,
89        }
90    }
91
92    /// Create a MaxCut problem with unit weights.
93    pub fn unweighted(graph: G) -> Self
94    where
95        W: From<i32>,
96    {
97        let edge_weights = vec![W::from(1); graph.num_edges()];
98        Self {
99            graph,
100            edge_weights,
101        }
102    }
103
104    /// Get a reference to the underlying graph.
105    pub fn graph(&self) -> &G {
106        &self.graph
107    }
108
109    /// Get the edges with weights.
110    pub fn edges(&self) -> Vec<(usize, usize, W)> {
111        self.graph
112            .edges()
113            .into_iter()
114            .zip(self.edge_weights.iter())
115            .map(|((u, v), w)| (u, v, w.clone()))
116            .collect()
117    }
118
119    /// Get the weight of an edge by its index.
120    pub fn edge_weight_by_index(&self, idx: usize) -> Option<&W> {
121        self.edge_weights.get(idx)
122    }
123
124    /// Get the weight of an edge between vertices u and v.
125    pub fn edge_weight(&self, u: usize, v: usize) -> Option<&W> {
126        // Find the edge index
127        for (idx, (eu, ev)) in self.graph.edges().iter().enumerate() {
128            if (*eu == u && *ev == v) || (*eu == v && *ev == u) {
129                return self.edge_weights.get(idx);
130            }
131        }
132        None
133    }
134
135    /// Get edge weights only.
136    pub fn edge_weights(&self) -> Vec<W> {
137        self.edge_weights.clone()
138    }
139
140    /// Compute the cut size for a given partition configuration.
141    pub fn cut_size(&self, config: &[usize]) -> W::Sum
142    where
143        W: WeightElement,
144    {
145        let partition: Vec<bool> = config.iter().map(|&c| c != 0).collect();
146        cut_size(&self.graph, &self.edge_weights, &partition)
147    }
148}
149
150impl<G: Graph, W: WeightElement> MaxCut<G, W> {
151    /// Get the number of vertices in the underlying graph.
152    pub fn num_vertices(&self) -> usize {
153        self.graph().num_vertices()
154    }
155
156    /// Get the number of edges in the underlying graph.
157    pub fn num_edges(&self) -> usize {
158        self.graph().num_edges()
159    }
160}
161
162impl<G, W> Problem for MaxCut<G, W>
163where
164    G: Graph + crate::variant::VariantParam,
165    W: WeightElement + crate::variant::VariantParam,
166{
167    const NAME: &'static str = "MaxCut";
168    type Metric = SolutionSize<W::Sum>;
169
170    fn variant() -> Vec<(&'static str, &'static str)> {
171        crate::variant_params![G, W]
172    }
173
174    fn dims(&self) -> Vec<usize> {
175        vec![2; self.graph.num_vertices()]
176    }
177
178    fn evaluate(&self, config: &[usize]) -> SolutionSize<W::Sum> {
179        // All cuts are valid, so always return Valid
180        let partition: Vec<bool> = config.iter().map(|&c| c != 0).collect();
181        SolutionSize::Valid(cut_size(&self.graph, &self.edge_weights, &partition))
182    }
183}
184
185impl<G, W> OptimizationProblem for MaxCut<G, W>
186where
187    G: Graph + crate::variant::VariantParam,
188    W: WeightElement + crate::variant::VariantParam,
189{
190    type Value = W::Sum;
191
192    fn direction(&self) -> Direction {
193        Direction::Maximize
194    }
195}
196
197/// Compute the total weight of edges crossing the cut.
198///
199/// # Arguments
200/// * `graph` - The graph structure
201/// * `edge_weights` - Weights for each edge (same order as `graph.edges()`)
202/// * `partition` - Boolean slice indicating which set each vertex belongs to
203pub(crate) fn cut_size<G, W>(graph: &G, edge_weights: &[W], partition: &[bool]) -> W::Sum
204where
205    G: Graph,
206    W: WeightElement,
207{
208    let mut total = W::Sum::zero();
209    for ((u, v), weight) in graph.edges().iter().zip(edge_weights.iter()) {
210        if *u < partition.len() && *v < partition.len() && partition[*u] != partition[*v] {
211            total += weight.to_sum();
212        }
213    }
214    total
215}
216
217crate::declare_variants! {
218    MaxCut<SimpleGraph, i32> => "2^(2.372 * num_vertices / 3)",
219}
220
221#[cfg(test)]
222#[path = "../../unit_tests/models/graph/max_cut.rs"]
223mod tests;
problemreductions/models/graph/max_cut.rs

problemreductions/models/graph/
max_cut.rs
