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

problemreductions/rules/
maximumcommonedgesubgraph_ilp.rs
