problemreductions/rules/
subgraphisomorphism_ilp.rs

1//! Reduction from SubgraphIsomorphism to ILP (Integer Linear Programming).
2//!
3//! Injective assignment with non-edge constraints:
4//! - Binary x_{v,u}: pattern vertex v maps to host vertex u
5//! - Assignment: each pattern vertex to exactly one host vertex
6//! - Injectivity: each host vertex receives at most one pattern vertex
7//! - Non-edge forbiddance: for each pattern edge {v,w} and each host non-edge {u,u'},
8//!   x_{v,u} + x_{w,u'} <= 1 AND x_{v,u'} + x_{w,u} <= 1
9
10use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
11use crate::models::graph::SubgraphIsomorphism;
12use crate::reduction;
13use crate::rules::ilp_helpers::{one_hot_assignment_constraints, one_hot_decode_rows};
14use crate::rules::traits::{ReduceTo, ReductionResult};
15use crate::topology::Graph;
16
17/// Result of reducing SubgraphIsomorphism to ILP.
18///
19/// Variable layout (all binary):
20/// - `x_{v,u}` at index `v * n_host + u` for pattern vertex v, host vertex u
21#[derive(Debug, Clone)]
22pub struct ReductionSubIsoToILP {
23    target: ILP<bool>,
24    num_pattern_vertices: usize,
25    num_host_vertices: usize,
26}
27
28impl ReductionResult for ReductionSubIsoToILP {
29    type Source = SubgraphIsomorphism;
30    type Target = ILP<bool>;
31
32    fn target_problem(&self) -> &ILP<bool> {
33        &self.target
34    }
35
36    /// Extract: for each pattern vertex v, output the unique host vertex u with x_{v,u} = 1.
37    fn extract_solution(
38        &self,
39        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
40    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
41        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
42
43        one_hot_decode_rows(
44            target_solution,
45            self.num_pattern_vertices,
46            self.num_host_vertices,
47            0,
48        )
49    }
50}
51
52#[reduction(
53    transform = upper_bound {
54        num_vars = "num_pattern_vertices * num_host_vertices",
55        num_constraints = "num_pattern_vertices + num_host_vertices + num_pattern_edges * num_host_vertices^2",
56    },
57    unavailable = {
58        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
59    }
60)]
61impl ReduceTo<ILP<bool>> for SubgraphIsomorphism {
62    type Result = ReductionSubIsoToILP;
63
64    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
65        let n_pat = self.num_pattern_vertices();
66        let n_host = self.num_host_vertices();
67        let host = self.host_graph();
68        let pattern = self.pattern_graph();
69        let pat_edges = pattern.edges();
70
71        let num_vars = n_pat * n_host;
72
73        let mut constraints = Vec::new();
74
75        // Assignment constraints
76        constraints.extend(one_hot_assignment_constraints(n_pat, n_host, 0));
77
78        // Non-edge forbiddance: for each pattern edge {v,w} and each host non-edge {u,u'}
79        for &(v, w) in &pat_edges {
80            for u in 0..n_host {
81                for u_prime in 0..n_host {
82                    if u == u_prime {
83                        continue;
84                    }
85                    if host.has_edge(u, u_prime) {
86                        continue;
87                    }
88                    // x_{v,u} + x_{w,u'} <= 1
89                    constraints.push(LinearConstraint::le(
90                        vec![(v * n_host + u, 1), (w * n_host + u_prime, 1)],
91                        1,
92                    ));
93                }
94            }
95        }
96
97        // Feasibility: no objective
98        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
99            .map_err(Self::target_construction)?;
100
101        Ok(ReductionSubIsoToILP {
102            target,
103            num_pattern_vertices: n_pat,
104            num_host_vertices: n_host,
105        })
106    }
107}
108
109#[cfg(feature = "example-db")]
110pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
111    use crate::topology::SimpleGraph;
112    vec![crate::example_db::specs::RuleExampleSpec {
113        id: "subgraphisomorphism_to_ilp",
114        build: || {
115            // Host: C4, Pattern: P3 (path on 3 vertices embeddable in cycle)
116            let host = SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3), (3, 0)]);
117            let pattern = SimpleGraph::new(3, vec![(0, 1), (1, 2)]);
118            let source = SubgraphIsomorphism::new(host, pattern);
119            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
120        },
121    }]
122}
123
124#[cfg(test)]
125#[path = "../unit_tests/rules/subgraphisomorphism_ilp.rs"]
126mod tests;
problemreductions/rules/subgraphisomorphism_ilp.rs

problemreductions/rules/
subgraphisomorphism_ilp.rs
