problemreductions/rules/
graphpartitioning_maxcut.rs

1//! Reduction from GraphPartitioning to MaxCut on a weighted complete graph.
2
3use crate::models::graph::{GraphPartitioning, MaxCut};
4use crate::reduction;
5use crate::rules::traits::{ReduceTo, ReductionResult};
6use crate::topology::{Graph, SimpleGraph};
7
8/// Result of reducing GraphPartitioning to MaxCut.
9#[derive(Debug, Clone)]
10pub struct ReductionGPToMaxCut {
11    target: MaxCut<SimpleGraph, i32>,
12}
13
14#[cfg(any(test, feature = "example-db"))]
15const ISSUE_EXAMPLE_WITNESS: [usize; 6] = [0, 0, 0, 1, 1, 1];
16
17impl ReductionResult for ReductionGPToMaxCut {
18    type Source = GraphPartitioning<SimpleGraph>;
19    type Target = MaxCut<SimpleGraph, i32>;
20
21    fn target_problem(&self) -> &Self::Target {
22        &self.target
23    }
24
25    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
26        target_solution.to_vec()
27    }
28}
29
30#[cfg(any(test, feature = "example-db"))]
31fn issue_example() -> GraphPartitioning<SimpleGraph> {
32    GraphPartitioning::new(SimpleGraph::new(
33        6,
34        vec![
35            (0, 1),
36            (0, 2),
37            (1, 2),
38            (1, 3),
39            (2, 3),
40            (2, 4),
41            (3, 4),
42            (3, 5),
43            (4, 5),
44        ],
45    ))
46}
47
48fn complete_graph_edges_and_weights(graph: &SimpleGraph) -> (Vec<(usize, usize)>, Vec<i32>) {
49    let num_vertices = graph.num_vertices();
50    let p = penalty_weight(graph.num_edges());
51    let mut edges = Vec::new();
52    let mut weights = Vec::new();
53
54    for u in 0..num_vertices {
55        for v in (u + 1)..num_vertices {
56            edges.push((u, v));
57            weights.push(if graph.has_edge(u, v) { p - 1 } else { p });
58        }
59    }
60
61    (edges, weights)
62}
63
64fn penalty_weight(num_edges: usize) -> i32 {
65    i32::try_from(num_edges)
66        .ok()
67        .and_then(|num_edges| num_edges.checked_add(1))
68        .expect("GraphPartitioning -> MaxCut penalty exceeds i32 range")
69}
70
71#[reduction(
72    overhead = {
73        num_vertices = "num_vertices",
74        num_edges = "num_vertices * (num_vertices - 1) / 2",
75    }
76)]
77impl ReduceTo<MaxCut<SimpleGraph, i32>> for GraphPartitioning<SimpleGraph> {
78    type Result = ReductionGPToMaxCut;
79
80    fn reduce_to(&self) -> Self::Result {
81        let (edges, weights) = complete_graph_edges_and_weights(self.graph());
82        let target = MaxCut::new(SimpleGraph::new(self.num_vertices(), edges), weights);
83
84        ReductionGPToMaxCut { target }
85    }
86}
87
88#[cfg(feature = "example-db")]
89pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
90    use crate::export::SolutionPair;
91
92    vec![crate::example_db::specs::RuleExampleSpec {
93        id: "graphpartitioning_to_maxcut",
94        build: || {
95            crate::example_db::specs::rule_example_with_witness::<_, MaxCut<SimpleGraph, i32>>(
96                issue_example(),
97                SolutionPair {
98                    source_config: ISSUE_EXAMPLE_WITNESS.to_vec(),
99                    target_config: ISSUE_EXAMPLE_WITNESS.to_vec(),
100                },
101            )
102        },
103    }]
104}
105
106#[cfg(test)]
107#[path = "../unit_tests/rules/graphpartitioning_maxcut.rs"]
108mod tests;
problemreductions/rules/graphpartitioning_maxcut.rs

problemreductions/rules/
graphpartitioning_maxcut.rs
