problemreductions/models/graph/
maximum_contact_map_overlap.rs

1//! Maximum Contact Map Overlap problem implementation.
2//!
3//! Given two finite ordered contact maps `G_1 = (V_1, E_1)` and
4//! `G_2 = (V_2, E_2)` where each `V_r` is the ordered vertex set
5//! `{0, 1, ..., n_r - 1}` and each `E_r` is a simple undirected contact set,
6//! find an order-preserving partial injective alignment
7//! `f: V_1 -> V_2 union {bot}` that maximizes the number of preserved contacts
8//!
9//! `|{{i, k} in E_1 : i, k both matched and {f(i), f(k)} in E_2}|`.
10//!
11//! The configuration vector has length `|V_1|`. For each source vertex `i`, the
12//! value `config[i] in {0, 1, ..., |V_2|}` records the alignment: `0` denotes
13//! `bot` (unmatched), and `j + 1` denotes "matched to vertex `j` of `G_2`".
14//! Feasibility requires that the non-zero entries are pairwise distinct
15//! (injectivity) and strictly increasing in source order (order-preserving).
16
17use crate::registry::{FieldInfo, ProblemSchemaEntry};
18use crate::traits::Problem;
19use crate::types::Max;
20use serde::{Deserialize, Serialize};
21use std::collections::HashSet;
22
23inventory::submit! {
24    ProblemSchemaEntry {
25        name: "MaximumContactMapOverlap",
26        display_name: "Maximum Contact Map Overlap",
27        aliases: &["CMO", "MaxCMO"],
28        dimensions: &[],
29        category: crate::registry::ProblemCategory::Graph,
30        module_path: module_path!(),
31        description: "Maximize the number of preserved contacts under an order-preserving partial injective alignment from G_1 into G_2",
32        fields: &[
33            FieldInfo {
34                name: "num_vertices_1",
35                type_name: "usize",
36                description: "Number of ordered residues/vertices in the first contact map G_1",
37            },
38            FieldInfo {
39                name: "contacts_1",
40                type_name: "Vec<(usize,usize)>",
41                description: "Simple undirected contacts of G_1 as canonicalized (u,v) pairs with u < v",
42            },
43            FieldInfo {
44                name: "num_vertices_2",
45                type_name: "usize",
46                description: "Number of ordered residues/vertices in the second contact map G_2",
47            },
48            FieldInfo {
49                name: "contacts_2",
50                type_name: "Vec<(usize,usize)>",
51                description: "Simple undirected contacts of G_2 as canonicalized (u,v) pairs with u < v",
52            },
53        ],
54    }
55}
56
57/// The Maximum Contact Map Overlap problem.
58///
59/// Given two finite ordered contact maps `G_1 = (V_1, E_1)` and
60/// `G_2 = (V_2, E_2)`, find an order-preserving partial injective alignment
61/// `f: V_1 -> V_2 union {bot}` that maximizes the number of preserved contacts
62///
63/// `|{{i, k} in E_1 : i, k both matched and {f(i), f(k)} in E_2}|`.
64///
65/// # Configuration encoding
66///
67/// `dims()` returns `vec![|V_2| + 1; |V_1|]`. For each source vertex `i`,
68/// `config[i] = 0` denotes `bot` (unmatched) and `config[i] = j + 1` denotes
69/// "matched to vertex `j in V_2`". Feasibility requires that the nonzero
70/// entries are pairwise distinct (injectivity) and strictly increasing along
71/// the index order of `V_1` (order-preserving).
72#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
73#[serde(try_from = "MaximumContactMapOverlapData")]
74pub struct MaximumContactMapOverlap {
75    num_vertices_1: usize,
76    contacts_1: Vec<(usize, usize)>,
77    num_vertices_2: usize,
78    contacts_2: Vec<(usize, usize)>,
79}
80
81#[derive(Deserialize)]
82struct MaximumContactMapOverlapData {
83    num_vertices_1: usize,
84    contacts_1: Vec<(usize, usize)>,
85    num_vertices_2: usize,
86    contacts_2: Vec<(usize, usize)>,
87}
88
89impl TryFrom<MaximumContactMapOverlapData> for MaximumContactMapOverlap {
90    type Error = crate::registry::ConstructionError;
91    fn try_from(data: MaximumContactMapOverlapData) -> Result<Self, Self::Error> {
92        Self::try_new(
93            data.num_vertices_1,
94            data.contacts_1,
95            data.num_vertices_2,
96            data.contacts_2,
97        )
98    }
99}
100
101/// Canonicalize a contact set: each pair is normalized to `(min, max)`.
102/// Self-loops, out-of-range endpoints, and duplicates (after normalization)
103/// are rejected.
104fn canonicalize_contacts(
105    raw: Vec<(usize, usize)>,
106    num_vertices: usize,
107    side: &str,
108) -> Result<Vec<(usize, usize)>, crate::registry::ConstructionError> {
109    let mut seen: HashSet<(usize, usize)> = HashSet::new();
110    let mut out = Vec::with_capacity(raw.len());
111    for (u, v) in raw {
112        if u >= num_vertices || v >= num_vertices {
113            return Err(format!(
114                "{side} contact endpoint out of range for num_vertices = {num_vertices}: ({u}, {v})"
115            )
116            .into());
117        }
118        if u == v {
119            return Err(format!("{side} contact has self-loop: ({u}, {v})").into());
120        }
121        let (a, b) = if u < v { (u, v) } else { (v, u) };
122        if !seen.insert((a, b)) {
123            return Err(
124                format!("{side} has duplicate contact after normalization: ({a}, {b})").into(),
125            );
126        }
127        out.push((a, b));
128    }
129    Ok(out)
130}
131
132impl MaximumContactMapOverlap {
133    /// Construct a new instance from two ordered contact maps.
134    ///
135    /// Contacts are canonicalized to `(min, max)` pairs.
136    ///
137    /// # Panics
138    ///
139    /// Panics on self-loops, duplicate contacts (after normalization), and
140    /// out-of-range endpoints.
141    pub fn new(
142        num_vertices_1: usize,
143        contacts_1: Vec<(usize, usize)>,
144        num_vertices_2: usize,
145        contacts_2: Vec<(usize, usize)>,
146    ) -> Self {
147        Self::try_new(num_vertices_1, contacts_1, num_vertices_2, contacts_2)
148            .unwrap_or_else(|error| panic!("{error}"))
149    }
150
151    /// Create an instance, returning validation errors instead of panicking.
152    fn try_new(
153        num_vertices_1: usize,
154        contacts_1: Vec<(usize, usize)>,
155        num_vertices_2: usize,
156        contacts_2: Vec<(usize, usize)>,
157    ) -> Result<Self, crate::registry::ConstructionError> {
158        let contacts_1 = canonicalize_contacts(contacts_1, num_vertices_1, "G_1")?;
159        let contacts_2 = canonicalize_contacts(contacts_2, num_vertices_2, "G_2")?;
160        Ok(Self {
161            num_vertices_1,
162            contacts_1,
163            num_vertices_2,
164            contacts_2,
165        })
166    }
167
168    /// Number of ordered residues/vertices in `G_1`.
169    pub fn num_vertices_1(&self) -> usize {
170        self.num_vertices_1
171    }
172
173    /// Number of ordered residues/vertices in `G_2`.
174    pub fn num_vertices_2(&self) -> usize {
175        self.num_vertices_2
176    }
177
178    /// Number of contacts in `G_1`.
179    pub fn num_contacts_1(&self) -> usize {
180        self.contacts_1.len()
181    }
182
183    /// Number of contacts in `G_2`.
184    pub fn num_contacts_2(&self) -> usize {
185        self.contacts_2.len()
186    }
187
188    /// Contacts of `G_1` as canonicalized `(u, v)` pairs with `u < v`.
189    pub fn contacts_1(&self) -> &[(usize, usize)] {
190        &self.contacts_1
191    }
192
193    /// Contacts of `G_2` as canonicalized `(u, v)` pairs with `u < v`.
194    pub fn contacts_2(&self) -> &[(usize, usize)] {
195        &self.contacts_2
196    }
197
198    /// Check that `config` describes an order-preserving partial injective
199    /// alignment.
200    ///
201    /// Validity requires: `config.len() == |V_1|`, every entry lies in
202    /// `0..=|V_2|` (with `0` denoting `bot`), all nonzero entries are
203    /// pairwise distinct (injectivity), and the nonzero entries are strictly
204    /// increasing in source order.
205    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
206        if config.len() != self.num_vertices_1 {
207            return false;
208        }
209        let max_value = self.num_vertices_2; // valid range is 0..=num_vertices_2
210        let mut previous_nonzero: Option<usize> = None;
211        let mut used: HashSet<usize> = HashSet::new();
212        for &value in config {
213            if value > max_value {
214                return false;
215            }
216            if value == 0 {
217                continue;
218            }
219            if !used.insert(value) {
220                return false;
221            }
222            if let Some(prev) = previous_nonzero {
223                if value <= prev {
224                    return false;
225                }
226            }
227            previous_nonzero = Some(value);
228        }
229        true
230    }
231
232    /// Count contacts of `G_1` preserved by the alignment `config`. Returns
233    /// `None` if `config` is infeasible.
234    pub fn preserved_contact_count(
235        &self,
236        config: &[usize],
237    ) -> Result<Option<i64>, crate::traits::EvaluationError> {
238        if !self.is_valid_solution(config) {
239            return Ok(None);
240        }
241        let contacts_2_set: HashSet<(usize, usize)> = self.contacts_2.iter().copied().collect();
242        let mut count = 0usize;
243        for &(i, k) in &self.contacts_1 {
244            let fi = config[i];
245            let fk = config[k];
246            if fi == 0 || fk == 0 {
247                continue;
248            }
249            // Encoding: nonzero value v means vertex v - 1 of G_2.
250            let a = fi - 1;
251            let b = fk - 1;
252            let pair = if a < b { (a, b) } else { (b, a) };
253            if contacts_2_set.contains(&pair) {
254                count += 1;
255            }
256        }
257        Ok(Some(i64::try_from(count).map_err(|_| {
258            crate::traits::EvaluationError::IntegerOverflow(
259                "converting preserved-contact count to i64".into(),
260            )
261        })?))
262    }
263}
264
265impl Problem for MaximumContactMapOverlap {
266    const NAME: &'static str = "MaximumContactMapOverlap";
267    type Solution = Vec<usize>;
268    type Value = Max<i64>;
269
270    crate::problem_parameters![
271        ("num_contacts_1", num_contacts_1),
272        ("num_contacts_2", num_contacts_2),
273        ("num_vertices_1", num_vertices_1),
274        ("num_vertices_2", num_vertices_2),
275    ];
276
277    fn variant() -> Vec<(&'static str, &'static str)> {
278        crate::variant_params![]
279    }
280
281    fn evaluate(
282        &self,
283        config: &Self::Solution,
284    ) -> Result<Max<i64>, crate::traits::EvaluationError> {
285        if config.len() != self.num_vertices_1 {
286            return Err(crate::traits::EvaluationError::InvalidConfiguration(
287                "contact-map alignment length does not match the first map".into(),
288            ));
289        }
290        if config.iter().any(|&vertex| vertex > self.num_vertices_2) {
291            return Err(crate::traits::EvaluationError::InvalidConfiguration(
292                "contact-map alignment contains an out-of-range target vertex".into(),
293            ));
294        }
295        Ok({
296            match self.preserved_contact_count(config)? {
297                Some(count) => Max(Some(count)),
298                None => Max(None),
299            }
300        })
301    }
302}
303
304impl crate::solvers::BruteForceProblem for MaximumContactMapOverlap {
305    fn dimensions(&self) -> Vec<usize> {
306        vec![self.num_vertices_2 + 1; self.num_vertices_1]
307    }
308}
309
310crate::declare_variants! {
311    default MaximumContactMapOverlap => "(num_vertices_2 + 1)^num_vertices_1",
312}
313
314crate::register_brute_force! {
315    MaximumContactMapOverlap,
316}
317
318#[cfg(feature = "example-db")]
319pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
320    // Canonical example from the issue:
321    //   G_1: n_1 = 4, E_1 = {{0,2}, {1,3}}
322    //   G_2: n_2 = 5, E_2 = {{0,3}, {1,4}, {0,2}}
323    // Optimal alignment: 0->0, 1->1, 2->3, 3->4 (encoded as [1, 2, 4, 5]).
324    //   - order-preserving: 1 < 2 < 4 < 5
325    //   - injectivity: all values distinct
326    //   - contact {0,2}: mapped (0, 3); sorted (0, 3) in E_2
327    //   - contact {1,3}: mapped (1, 4); sorted (1, 4) in E_2
328    //   - value = 2 contacts preserved.
329    vec![crate::example_db::specs::ModelExampleSpec {
330        id: "maximum_contact_map_overlap",
331        instance: Box::new(MaximumContactMapOverlap::new(
332            4,
333            vec![(0, 2), (1, 3)],
334            5,
335            vec![(0, 3), (1, 4), (0, 2)],
336        )),
337        optimal_config: serde_json::json!(vec![1, 2, 4, 5]),
338        optimal_value: serde_json::json!(2),
339    }]
340}
341
342#[cfg(test)]
343#[path = "../../unit_tests/models/graph/maximum_contact_map_overlap.rs"]
344mod tests;
problemreductions/models/graph/maximum_contact_map_overlap.rs

problemreductions/models/graph/
maximum_contact_map_overlap.rs
