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

problemreductions/rules/
isomorphicspanningtree_ilp.rs
