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#[reduction(
70    transform = upper_bound {
71        num_vars = "num_vertices_1 * num_vertices_2 + num_arcs_1 * num_arcs_2",
72        num_constraints = "num_vertices_1 + num_vertices_2 + 3 * num_arcs_1 * num_arcs_2",
73    },
74    unavailable = {
75        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
76    }
77)]
78impl ReduceTo<ILP<bool>> for MaximumCommonEdgeSubgraph {
79    type Result = ReductionMCESToILP;
80
81    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
82        let n1 = self.num_vertices_1();
83        let n2 = self.num_vertices_2();
84        let arcs_1 = self.graph_1().arcs();
85        let arcs_2 = self.graph_2().arcs();
86
87        let num_x = n1 * n2;
88        let x_idx = |u: usize, p: usize| -> usize { u * n2 + p };
89
90        // Enumerate label-compatible source/target arc pairs in a fixed order
91        // so the y-variable indexing is deterministic.
92        let mut y_pairs: Vec<(usize, usize)> = Vec::new();
93        for (a_idx, a) in arcs_1.iter().enumerate() {
94            for (b_idx, b) in arcs_2.iter().enumerate() {
95                if a.label == b.label {
96                    y_pairs.push((a_idx, b_idx));
97                }
98            }
99        }
100
101        let num_y = y_pairs.len();
102        let num_vars = num_x + num_y;
103        let y_idx = |seq: usize| -> usize { num_x + seq };
104
105        let mut constraints: Vec<LinearConstraint> = Vec::new();
106
107        // Row constraints: each source vertex maps to at most one target.
108        for u in 0..n1 {
109            let terms: Vec<(usize, i64)> = (0..n2).map(|p| (x_idx(u, p), 1)).collect();
110            constraints.push(LinearConstraint::le(terms, 1));
111        }
112
113        // Column constraints: each target vertex receives at most one source.
114        for p in 0..n2 {
115            let terms: Vec<(usize, i64)> = (0..n1).map(|u| (x_idx(u, p), 1)).collect();
116            constraints.push(LinearConstraint::le(terms, 1));
117        }
118
119        // Linking constraints: y_(a,b) = x_(u,p) AND x_(v,q) via McCormick.
120        for (seq, &(a_idx, b_idx)) in y_pairs.iter().enumerate() {
121            let a = arcs_1[a_idx];
122            let b = arcs_2[b_idx];
123            constraints.extend(mccormick_product(
124                y_idx(seq),
125                x_idx(a.src, b.src),
126                x_idx(a.dst, b.dst),
127            ));
128        }
129
130        // Objective: maximize the number of preserved labelled arcs.
131        let objective: Vec<(usize, i64)> = (0..num_y).map(|seq| (y_idx(seq), 1)).collect();
132
133        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize)
134            .map_err(Self::target_construction)?;
135
136        Ok(ReductionMCESToILP {
137            target,
138            num_vertices_1: n1,
139            num_vertices_2: n2,
140        })
141    }
142}
143
144#[cfg(feature = "example-db")]
145pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
146    use crate::models::graph::{LabelledArc, LabelledDigraph};
147    vec![crate::example_db::specs::RuleExampleSpec {
148        id: "maximumcommonedgesubgraph_to_ilp",
149        build: || {
150            // Small triangle/path instance: optimal MCES preserves 2 arcs.
151            let source = MaximumCommonEdgeSubgraph::new(
152                LabelledDigraph::new(
153                    3,
154                    vec![LabelledArc::new(0, 0, 1), LabelledArc::new(1, 1, 2)],
155                ),
156                LabelledDigraph::new(
157                    3,
158                    vec![LabelledArc::new(0, 0, 1), LabelledArc::new(1, 1, 2)],
159                ),
160            );
161            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
162        },
163    }]
164}
165
166#[cfg(test)]
167#[path = "../unit_tests/rules/maximumcommonedgesubgraph_ilp.rs"]
168mod tests;
problemreductions/rules/maximumcommonedgesubgraph_ilp.rs

problemreductions/rules/
maximumcommonedgesubgraph_ilp.rs
