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

problemreductions/models/graph/
max_cut.rs
