problemreductions/rules/
graphpartitioning_qubo.rs

1//! Reduction from GraphPartitioning to QUBO.
2//!
3//! Uses the penalty-method QUBO
4//! H = sum_(u,v in E) (x_u + x_v - 2 x_u x_v) + P (sum_i x_i - n/2)^2
5//! with P = |E| + 1 so any imbalanced partition is dominated by a balanced one.
6
7use crate::models::algebraic::QUBO;
8use crate::models::graph::GraphPartitioning;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11use crate::topology::{Graph, SimpleGraph};
12
13/// Result of reducing GraphPartitioning to QUBO.
14#[derive(Debug, Clone)]
15pub struct ReductionGraphPartitioningToQUBO {
16    target: QUBO<f64>,
17}
18
19impl ReductionResult for ReductionGraphPartitioningToQUBO {
20    type Source = GraphPartitioning<SimpleGraph>;
21    type Target = QUBO<f64>;
22
23    fn target_problem(&self) -> &Self::Target {
24        &self.target
25    }
26
27    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
28        target_solution.to_vec()
29    }
30}
31
32#[reduction(overhead = { num_vars = "num_vertices" })]
33impl ReduceTo<QUBO<f64>> for GraphPartitioning<SimpleGraph> {
34    type Result = ReductionGraphPartitioningToQUBO;
35
36    fn reduce_to(&self) -> Self::Result {
37        let n = self.num_vertices();
38        let penalty = self.num_edges() as f64 + 1.0;
39        let mut matrix = vec![vec![0.0f64; n]; n];
40        let mut degrees = vec![0usize; n];
41        let edges = self.graph().edges();
42
43        for &(u, v) in &edges {
44            degrees[u] += 1;
45            degrees[v] += 1;
46        }
47
48        for (i, row) in matrix.iter_mut().enumerate() {
49            row[i] = degrees[i] as f64 + penalty * (1.0 - n as f64);
50            for value in row.iter_mut().skip(i + 1) {
51                *value = 2.0 * penalty;
52            }
53        }
54
55        for (u, v) in edges {
56            let (lo, hi) = if u < v { (u, v) } else { (v, u) };
57            matrix[lo][hi] -= 2.0;
58        }
59
60        ReductionGraphPartitioningToQUBO {
61            target: QUBO::from_matrix(matrix),
62        }
63    }
64}
65
66#[cfg(feature = "example-db")]
67pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
68    use crate::export::SolutionPair;
69
70    vec![crate::example_db::specs::RuleExampleSpec {
71        id: "graphpartitioning_to_qubo",
72        build: || {
73            crate::example_db::specs::rule_example_with_witness::<_, QUBO<f64>>(
74                GraphPartitioning::new(SimpleGraph::new(
75                    6,
76                    vec![
77                        (0, 1),
78                        (0, 2),
79                        (1, 2),
80                        (1, 3),
81                        (2, 3),
82                        (2, 4),
83                        (3, 4),
84                        (3, 5),
85                        (4, 5),
86                    ],
87                )),
88                SolutionPair {
89                    source_config: vec![0, 0, 0, 1, 1, 1],
90                    target_config: vec![0, 0, 0, 1, 1, 1],
91                },
92            )
93        },
94    }]
95}
96
97#[cfg(test)]
98#[path = "../unit_tests/rules/graphpartitioning_qubo.rs"]
99mod tests;
problemreductions/rules/graphpartitioning_qubo.rs

problemreductions/rules/
graphpartitioning_qubo.rs
