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::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: &["GraphPartitioning", "MaximumBipartiteSubgraph"],
18        dimensions: &[
19            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
20            VariantDimension::new("weight", "i32", &["i32", "One"]),
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::Max;
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_witnesses(&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, Max(Some(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 Value = Max<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]) -> Max<W::Sum> {
185        // All cuts are valid, so always return Valid
186        let partition: Vec<bool> = config.iter().map(|&c| c != 0).collect();
187        Max(Some(cut_size(&self.graph, &self.edge_weights, &partition)))
188    }
189}
190
191/// Compute the total weight of edges crossing the cut.
192///
193/// # Arguments
194/// * `graph` - The graph structure
195/// * `edge_weights` - Weights for each edge (same order as `graph.edges()`)
196/// * `partition` - Boolean slice indicating which set each vertex belongs to
197pub(crate) fn cut_size<G, W>(graph: &G, edge_weights: &[W], partition: &[bool]) -> W::Sum
198where
199    G: Graph,
200    W: WeightElement,
201{
202    let mut total = W::Sum::zero();
203    for ((u, v), weight) in graph.edges().iter().zip(edge_weights.iter()) {
204        if *u < partition.len() && *v < partition.len() && partition[*u] != partition[*v] {
205            total += weight.to_sum();
206        }
207    }
208    total
209}
210
211crate::declare_variants! {
212    default MaxCut<SimpleGraph, i32> => "2^(2.372 * num_vertices / 3)",
213    MaxCut<SimpleGraph, One> => "2^(0.7907 * num_vertices)",
214}
215
216#[cfg(feature = "example-db")]
217pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
218    vec![
219        crate::example_db::specs::ModelExampleSpec {
220            id: "max_cut_simplegraph_i32",
221            instance: Box::new(MaxCut::<_, i32>::unweighted(SimpleGraph::new(
222                5,
223                vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)],
224            ))),
225            optimal_config: vec![1, 0, 0, 1, 0],
226            optimal_value: serde_json::json!(5),
227        },
228        crate::example_db::specs::ModelExampleSpec {
229            id: "max_cut_simplegraph_one",
230            instance: Box::new(MaxCut::new(
231                SimpleGraph::new(
232                    5,
233                    vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 4), (2, 3), (3, 4)],
234                ),
235                vec![One; 7],
236            )),
237            optimal_config: vec![0, 1, 0, 1, 0],
238            optimal_value: serde_json::json!(6),
239        },
240    ]
241}
242
243#[cfg(test)]
244#[path = "../../unit_tests/models/graph/max_cut.rs"]
245mod tests;
problemreductions/models/graph/max_cut.rs

problemreductions/models/graph/
max_cut.rs
