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

problemreductions/rules/
graphpartitioning_maxcut.rs
