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;
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(&self, target_solution: &[usize]) -> Vec<usize> {
38        let n_host = self.num_host_vertices;
39        (0..self.num_pattern_vertices)
40            .map(|v| {
41                (0..n_host)
42                    .find(|&u| target_solution[v * n_host + u] == 1)
43                    .unwrap_or(0)
44            })
45            .collect()
46    }
47}
48
49#[reduction(
50    overhead = {
51        num_vars = "num_pattern_vertices * num_host_vertices",
52        num_constraints = "num_pattern_vertices + num_host_vertices + num_pattern_edges * num_host_vertices^2",
53    }
54)]
55impl ReduceTo<ILP<bool>> for SubgraphIsomorphism {
56    type Result = ReductionSubIsoToILP;
57
58    fn reduce_to(&self) -> Self::Result {
59        let n_pat = self.num_pattern_vertices();
60        let n_host = self.num_host_vertices();
61        let host = self.host_graph();
62        let pattern = self.pattern_graph();
63        let pat_edges = pattern.edges();
64
65        let num_vars = n_pat * n_host;
66
67        let mut constraints = Vec::new();
68
69        // Assignment constraints
70        constraints.extend(one_hot_assignment_constraints(n_pat, n_host, 0));
71
72        // Non-edge forbiddance: for each pattern edge {v,w} and each host non-edge {u,u'}
73        for &(v, w) in &pat_edges {
74            for u in 0..n_host {
75                for u_prime in 0..n_host {
76                    if u == u_prime {
77                        continue;
78                    }
79                    if host.has_edge(u, u_prime) {
80                        continue;
81                    }
82                    // x_{v,u} + x_{w,u'} <= 1
83                    constraints.push(LinearConstraint::le(
84                        vec![(v * n_host + u, 1.0), (w * n_host + u_prime, 1.0)],
85                        1.0,
86                    ));
87                }
88            }
89        }
90
91        // Feasibility: no objective
92        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize);
93
94        ReductionSubIsoToILP {
95            target,
96            num_pattern_vertices: n_pat,
97            num_host_vertices: n_host,
98        }
99    }
100}
101
102#[cfg(feature = "example-db")]
103pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
104    use crate::topology::SimpleGraph;
105    vec![crate::example_db::specs::RuleExampleSpec {
106        id: "subgraphisomorphism_to_ilp",
107        build: || {
108            // Host: C4, Pattern: P3 (path on 3 vertices embeddable in cycle)
109            let host = SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3), (3, 0)]);
110            let pattern = SimpleGraph::new(3, vec![(0, 1), (1, 2)]);
111            let source = SubgraphIsomorphism::new(host, pattern);
112            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
113        },
114    }]
115}
116
117#[cfg(test)]
118#[path = "../unit_tests/rules/subgraphisomorphism_ilp.rs"]
119mod tests;
problemreductions/rules/subgraphisomorphism_ilp.rs

problemreductions/rules/
subgraphisomorphism_ilp.rs
