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_solution(self.target_problem(), target_solution)?;
32
33        crate::rules::ilp_helpers::one_hot_decode_rows(target_solution, self.n, self.n, 0)
34    }
35}
36
37#[reduction(
38    transform = upper_bound {
39        num_vars = "num_vertices * num_vertices",
40        num_constraints = "2 * num_vertices + 2 * (num_vertices - 1) * num_vertices * num_vertices",
41    },
42    unavailable = {
43        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
44    }
45)]
46impl ReduceTo<ILP<bool>> for IsomorphicSpanningTree<SimpleGraph> {
47    type Result = ReductionISTToILP;
48
49    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
50        let n = self.num_vertices();
51        let num_vars = n * n;
52
53        let mut constraints = Vec::new();
54
55        // Each tree vertex u maps to exactly one graph vertex:
56        // Σ_v x_{u,v} = 1  ∀ u
57        for u in 0..n {
58            let terms: Vec<(usize, i64)> = (0..n).map(|v| (u * n + v, 1)).collect();
59            constraints.push(LinearConstraint::eq(terms, 1));
60        }
61
62        // Each graph vertex v is mapped to by exactly one tree vertex:
63        // Σ_u x_{u,v} = 1  ∀ v
64        for v in 0..n {
65            let terms: Vec<(usize, i64)> = (0..n).map(|u| (u * n + v, 1)).collect();
66            constraints.push(LinearConstraint::eq(terms, 1));
67        }
68
69        // For each tree edge {u, w} and each pair (v, z) that is NOT a graph edge:
70        // x_{u,v} + x_{w,z} <= 1
71        // x_{u,z} + x_{w,v} <= 1
72        for (u, w) in self.tree().edges() {
73            for v in 0..n {
74                for z in 0..n {
75                    if v != z && !self.graph().has_edge(v, z) {
76                        constraints.push(LinearConstraint::le(
77                            vec![(u * n + v, 1), (w * n + z, 1)],
78                            1,
79                        ));
80                    }
81                }
82            }
83        }
84
85        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
86            .map_err(Self::target_construction)?;
87        Ok(ReductionISTToILP { target, n })
88    }
89}
90
91#[cfg(feature = "example-db")]
92pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
93    use crate::export::SolutionPair;
94    use crate::topology::SimpleGraph;
95    vec![crate::example_db::specs::RuleExampleSpec {
96        id: "isomorphicspanningtree_to_ilp",
97        build: || {
98            // K4 graph, star tree
99            let source = IsomorphicSpanningTree::new(
100                SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]),
101                SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3)]),
102            );
103            // Identity bijection works
104            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
105                source,
106                SolutionPair {
107                    source_config: serde_json::json!(vec![0, 1, 2, 3]),
108                    // x_{0,0}=1, x_{1,1}=1, x_{2,2}=1, x_{3,3}=1
109                    target_config: serde_json::json!(vec![
110                        1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1
111                    ]),
112                },
113            )
114        },
115    }]
116}
117
118#[cfg(test)]
119#[path = "../unit_tests/rules/isomorphicspanningtree_ilp.rs"]
120mod tests;
problemreductions/rules/isomorphicspanningtree_ilp.rs

problemreductions/rules/
isomorphicspanningtree_ilp.rs
