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

problemreductions/rules/
subgraphisomorphism_ilp.rs
