problemreductions/rules/
isomorphicspanningtree_ilp.rs

1//! Reduction from IsomorphicSpanningTree to ILP (Integer Linear Programming).
2//!
3//! Binary variable x_{u,v} with x_{u,v} = 1 iff tree vertex u maps to graph
4//! vertex v. Bijection constraints plus non-edge exclusion for every tree edge.
5
6use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
7use crate::models::graph::IsomorphicSpanningTree;
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::{Graph, SimpleGraph};
11
12#[derive(Debug, Clone)]
13pub struct ReductionISTToILP {
14    target: ILP<bool>,
15    n: usize,
16}
17
18impl ReductionResult for ReductionISTToILP {
19    type Source = IsomorphicSpanningTree<SimpleGraph>;
20    type Target = ILP<bool>;
21
22    fn target_problem(&self) -> &ILP<bool> {
23        &self.target
24    }
25
26    /// For each tree vertex u, output the unique graph vertex v with x_{u,v} = 1.
27    fn extract_solution(
28        &self,
29        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
30    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
31        crate::rules::traits::validate_target_witness(
32            self.target_problem(),
33            target_solution,
34            |value| value.value.is_some(),
35            "target ILP assignment is infeasible",
36        )?;
37
38        crate::rules::ilp_helpers::one_hot_decode_rows(target_solution, self.n, self.n, 0)
39    }
40}
41
42#[crate::aggregate_reduction(ilp_feasibility)]
43impl crate::rules::AggregateReductionResult for ReductionISTToILP {}
44
45// Two assignment families contribute 2n rows and 2n^2 terms. Each of the
46// n-1 tree edges emits one two-term row per ordered non-edge, at most n(n-1).
47// At n=0 both products vanish, including the otherwise negative n-1 factor.
48#[reduction(transform = upper_bound {
49    max_constraint_magnitude_bits = "2",
50    num_vars = "num_vertices * num_vertices",
51    num_constraints = "2 * num_vertices + num_vertices * (num_vertices - 1)^2",
52    num_nonzeros = "2 * num_vertices^2 + 2 * num_vertices * (num_vertices - 1)^2",
53})]
54impl ReduceTo<ILP<bool>> for IsomorphicSpanningTree<SimpleGraph> {
55    type Result = ReductionISTToILP;
56
57    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
58        let n = self.num_vertices();
59        let num_vars = n * n;
60
61        let mut constraints = Vec::new();
62
63        // Each tree vertex u maps to exactly one graph vertex:
64        // Σ_v x_{u,v} = 1  ∀ u
65        for u in 0..n {
66            let terms: Vec<(usize, i64)> = (0..n).map(|v| (u * n + v, 1)).collect();
67            constraints.push(LinearConstraint::eq(terms, 1));
68        }
69
70        // Each graph vertex v is mapped to by exactly one tree vertex:
71        // Σ_u x_{u,v} = 1  ∀ v
72        for v in 0..n {
73            let terms: Vec<(usize, i64)> = (0..n).map(|u| (u * n + v, 1)).collect();
74            constraints.push(LinearConstraint::eq(terms, 1));
75        }
76
77        // For each tree edge {u, w} and each pair (v, z) that is NOT a graph edge:
78        // x_{u,v} + x_{w,z} <= 1
79        // x_{u,z} + x_{w,v} <= 1
80        for (u, w) in self.tree().edges() {
81            for v in 0..n {
82                for z in 0..n {
83                    if v != z && !self.graph().has_edge(v, z) {
84                        constraints.push(LinearConstraint::le(
85                            vec![(u * n + v, 1), (w * n + z, 1)],
86                            1,
87                        ));
88                    }
89                }
90            }
91        }
92
93        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
94            .map_err(Self::target_construction)?;
95        Ok(ReductionISTToILP { target, n })
96    }
97}
98
99#[cfg(feature = "example-db")]
100pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
101    use crate::export::SolutionPair;
102    use crate::topology::SimpleGraph;
103    vec![crate::example_db::specs::RuleExampleSpec {
104        id: "isomorphicspanningtree_to_ilp",
105        build: || {
106            // K4 graph, star tree
107            let source = IsomorphicSpanningTree::new(
108                SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]),
109                SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3)]),
110            );
111            // Identity bijection works
112            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
113                source,
114                SolutionPair {
115                    source_config: serde_json::json!(vec![0, 1, 2, 3]),
116                    // x_{0,0}=1, x_{1,1}=1, x_{2,2}=1, x_{3,3}=1
117                    target_config: serde_json::json!(vec![
118                        1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1
119                    ]),
120                },
121            )
122        },
123    }]
124}
125
126#[cfg(test)]
127#[path = "../unit_tests/rules/isomorphicspanningtree_ilp.rs"]
128mod tests;
problemreductions/rules/isomorphicspanningtree_ilp.rs

problemreductions/rules/
isomorphicspanningtree_ilp.rs
