problemreductions/rules/
maximumcommonedgesubgraph_ilp.rs

1//! Reduction from MaximumCommonEdgeSubgraph to ILP (Integer Linear Programming).
2//!
3//! Binary mapping variables `x_(u,p)` indicate that source vertex `u in V1`
4//! is mapped to target vertex `p in V2`. Row and column inequalities encode a
5//! partial injective map. For every label-compatible source/target arc pair
6//! `((u, lambda, v), (p, lambda, q))` we introduce a binary `y_(a,b)` that is
7//! forced to `1` exactly when both `x_(u,p)` and `x_(v,q)` are selected, via
8//! the McCormick linearization. The ILP objective is `max sum y_(a,b)`, which
9//! equals the count of preserved labelled arcs.
10//!
11//! This is a direct ILP rendering of the polyhedral formulation studied by
12//! Bahiense, Manic, Piva, and de Souza (DAM 2012) adapted to the directed
13//! edge-labelled graph model used in the library.
14
15use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
16use crate::models::graph::MaximumCommonEdgeSubgraph;
17use crate::reduction;
18use crate::rules::ilp_helpers::mccormick_product;
19use crate::rules::traits::{ReduceTo, ReductionResult};
20
21/// Result of reducing MaximumCommonEdgeSubgraph to ILP.
22///
23/// Variable layout (all binary):
24/// - `x_(u,p)` at index `u * n2 + p` for `u in V1`, `p in V2`
25/// - `y_(a,b)` for each label-compatible source/target arc pair, indexed
26///   sequentially after the `x` block in the order they are enumerated by
27///   the constructor.
28#[derive(Debug, Clone)]
29pub struct ReductionMCESToILP {
30    target: ILP<bool>,
31    num_vertices_1: usize,
32    num_vertices_2: usize,
33}
34
35impl ReductionResult for ReductionMCESToILP {
36    type Source = MaximumCommonEdgeSubgraph;
37    type Target = ILP<bool>;
38
39    fn target_problem(&self) -> &ILP<bool> {
40        &self.target
41    }
42
43    /// Extract: for each source vertex `u`, output the unique target vertex
44    /// `p` with `x_(u,p) = 1`, or the sentinel `n2` ("bottom") when no
45    /// mapping variable is selected.
46    fn extract_solution(
47        &self,
48        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
49    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
50        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
51
52        let n2 = self.num_vertices_2;
53        (0..self.num_vertices_1)
54            .map(|vertex| {
55                let mut selected =
56                    (0..n2).filter(|&mapped| target_solution[vertex * n2 + mapped] == 1);
57                match (selected.next(), selected.next()) {
58                    (Some(mapped), None) => Ok(mapped),
59                    (None, _) => Ok(n2),
60                    (Some(_), Some(_)) => Err(crate::rules::ExtractionError::invalid(format!(
61                        "source vertex {vertex} maps to multiple target vertices"
62                    ))),
63                }
64            })
65            .collect()
66    }
67}
68
69// Row/column injection inequalities contain 2*n1*n2 terms. Each compatible
70// arc pair contributes at most seven McCormick terms; self-loops merge them.
71#[reduction(transform = upper_bound {
72    max_constraint_magnitude_bits = "2",
73    num_vars = "num_vertices_1 * num_vertices_2 + num_arcs_1 * num_arcs_2",
74    num_constraints = "num_vertices_1 + num_vertices_2 + 3 * num_arcs_1 * num_arcs_2",
75    num_nonzeros = "2 * num_vertices_1 * num_vertices_2 + 7 * num_arcs_1 * num_arcs_2",
76})]
77impl ReduceTo<ILP<bool>> for MaximumCommonEdgeSubgraph {
78    type Result = ReductionMCESToILP;
79
80    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
81        let n1 = self.num_vertices_1();
82        let n2 = self.num_vertices_2();
83        let arcs_1 = self.graph_1().arcs();
84        let arcs_2 = self.graph_2().arcs();
85
86        let num_x = n1 * n2;
87        let x_idx = |u: usize, p: usize| -> usize { u * n2 + p };
88
89        // Enumerate label-compatible source/target arc pairs in a fixed order
90        // so the y-variable indexing is deterministic.
91        let mut y_pairs: Vec<(usize, usize)> = Vec::new();
92        for (a_idx, a) in arcs_1.iter().enumerate() {
93            for (b_idx, b) in arcs_2.iter().enumerate() {
94                if a.label == b.label {
95                    y_pairs.push((a_idx, b_idx));
96                }
97            }
98        }
99
100        let num_y = y_pairs.len();
101        let num_vars = num_x + num_y;
102        let y_idx = |seq: usize| -> usize { num_x + seq };
103
104        let mut constraints: Vec<LinearConstraint> = Vec::new();
105
106        // Row constraints: each source vertex maps to at most one target.
107        for u in 0..n1 {
108            let terms: Vec<(usize, i64)> = (0..n2).map(|p| (x_idx(u, p), 1)).collect();
109            constraints.push(LinearConstraint::le(terms, 1));
110        }
111
112        // Column constraints: each target vertex receives at most one source.
113        for p in 0..n2 {
114            let terms: Vec<(usize, i64)> = (0..n1).map(|u| (x_idx(u, p), 1)).collect();
115            constraints.push(LinearConstraint::le(terms, 1));
116        }
117
118        // Linking constraints: y_(a,b) = x_(u,p) AND x_(v,q) via McCormick.
119        for (seq, &(a_idx, b_idx)) in y_pairs.iter().enumerate() {
120            let a = arcs_1[a_idx];
121            let b = arcs_2[b_idx];
122            constraints.extend(mccormick_product(
123                y_idx(seq),
124                x_idx(a.src, b.src),
125                x_idx(a.dst, b.dst),
126            ));
127        }
128
129        // Objective: maximize the number of preserved labelled arcs.
130        let objective: Vec<(usize, i64)> = (0..num_y).map(|seq| (y_idx(seq), 1)).collect();
131
132        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize)
133            .map_err(Self::target_construction)?;
134
135        Ok(ReductionMCESToILP {
136            target,
137            num_vertices_1: n1,
138            num_vertices_2: n2,
139        })
140    }
141}
142
143#[cfg(feature = "example-db")]
144pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
145    use crate::models::graph::{LabelledArc, LabelledDigraph};
146    vec![crate::example_db::specs::RuleExampleSpec {
147        id: "maximumcommonedgesubgraph_to_ilp",
148        build: || {
149            // Small triangle/path instance: optimal MCES preserves 2 arcs.
150            let source = MaximumCommonEdgeSubgraph::new(
151                LabelledDigraph::new(
152                    3,
153                    vec![LabelledArc::new(0, 0, 1), LabelledArc::new(1, 1, 2)],
154                ),
155                LabelledDigraph::new(
156                    3,
157                    vec![LabelledArc::new(0, 0, 1), LabelledArc::new(1, 1, 2)],
158                ),
159            );
160            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
161        },
162    }]
163}
164
165#[cfg(test)]
166#[path = "../unit_tests/rules/maximumcommonedgesubgraph_ilp.rs"]
167mod tests;
problemreductions/rules/maximumcommonedgesubgraph_ilp.rs

problemreductions/rules/
maximumcommonedgesubgraph_ilp.rs
