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)]
73pub struct MaximumContactMapOverlap {
74    num_vertices_1: usize,
75    contacts_1: Vec<(usize, usize)>,
76    num_vertices_2: usize,
77    contacts_2: Vec<(usize, usize)>,
78}
79
80/// Canonicalize a contact set: each pair is normalized to `(min, max)`, no
81/// self-loops are allowed, all endpoints must be in range, and duplicates
82/// (after normalization) cause a panic.
83fn canonicalize_contacts(
84    raw: Vec<(usize, usize)>,
85    num_vertices: usize,
86    side: &str,
87) -> Vec<(usize, usize)> {
88    let mut seen: HashSet<(usize, usize)> = HashSet::new();
89    let mut out = Vec::with_capacity(raw.len());
90    for (u, v) in raw {
91        assert!(
92            u < num_vertices && v < num_vertices,
93            "{side} contact endpoint out of range for num_vertices = {num_vertices}: ({u}, {v})"
94        );
95        assert!(u != v, "{side} contact has self-loop: ({u}, {v})");
96        let (a, b) = if u < v { (u, v) } else { (v, u) };
97        assert!(
98            seen.insert((a, b)),
99            "{side} has duplicate contact after normalization: ({a}, {b})"
100        );
101        out.push((a, b));
102    }
103    out
104}
105
106impl MaximumContactMapOverlap {
107    /// Construct a new instance from two ordered contact maps.
108    ///
109    /// Contacts are canonicalized to `(min, max)` pairs. Self-loops, duplicate
110    /// contacts (after normalization), and out-of-range endpoints panic.
111    pub fn new(
112        num_vertices_1: usize,
113        contacts_1: Vec<(usize, usize)>,
114        num_vertices_2: usize,
115        contacts_2: Vec<(usize, usize)>,
116    ) -> Self {
117        let contacts_1 = canonicalize_contacts(contacts_1, num_vertices_1, "G_1");
118        let contacts_2 = canonicalize_contacts(contacts_2, num_vertices_2, "G_2");
119        Self {
120            num_vertices_1,
121            contacts_1,
122            num_vertices_2,
123            contacts_2,
124        }
125    }
126
127    /// Number of ordered residues/vertices in `G_1`.
128    pub fn num_vertices_1(&self) -> usize {
129        self.num_vertices_1
130    }
131
132    /// Number of ordered residues/vertices in `G_2`.
133    pub fn num_vertices_2(&self) -> usize {
134        self.num_vertices_2
135    }
136
137    /// Number of contacts in `G_1`.
138    pub fn num_contacts_1(&self) -> usize {
139        self.contacts_1.len()
140    }
141
142    /// Number of contacts in `G_2`.
143    pub fn num_contacts_2(&self) -> usize {
144        self.contacts_2.len()
145    }
146
147    /// Contacts of `G_1` as canonicalized `(u, v)` pairs with `u < v`.
148    pub fn contacts_1(&self) -> &[(usize, usize)] {
149        &self.contacts_1
150    }
151
152    /// Contacts of `G_2` as canonicalized `(u, v)` pairs with `u < v`.
153    pub fn contacts_2(&self) -> &[(usize, usize)] {
154        &self.contacts_2
155    }
156
157    /// Check that `config` describes an order-preserving partial injective
158    /// alignment.
159    ///
160    /// Validity requires: `config.len() == |V_1|`, every entry lies in
161    /// `0..=|V_2|` (with `0` denoting `bot`), all nonzero entries are
162    /// pairwise distinct (injectivity), and the nonzero entries are strictly
163    /// increasing in source order.
164    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
165        if config.len() != self.num_vertices_1 {
166            return false;
167        }
168        let max_value = self.num_vertices_2; // valid range is 0..=num_vertices_2
169        let mut previous_nonzero: Option<usize> = None;
170        let mut used: HashSet<usize> = HashSet::new();
171        for &value in config {
172            if value > max_value {
173                return false;
174            }
175            if value == 0 {
176                continue;
177            }
178            if !used.insert(value) {
179                return false;
180            }
181            if let Some(prev) = previous_nonzero {
182                if value <= prev {
183                    return false;
184                }
185            }
186            previous_nonzero = Some(value);
187        }
188        true
189    }
190
191    /// Count contacts of `G_1` preserved by the alignment `config`. Returns
192    /// `None` if `config` is infeasible.
193    pub fn preserved_contact_count(
194        &self,
195        config: &[usize],
196    ) -> Result<Option<i64>, crate::traits::EvaluationError> {
197        if !self.is_valid_solution(config) {
198            return Ok(None);
199        }
200        let contacts_2_set: HashSet<(usize, usize)> = self.contacts_2.iter().copied().collect();
201        let mut count = 0usize;
202        for &(i, k) in &self.contacts_1 {
203            let fi = config[i];
204            let fk = config[k];
205            if fi == 0 || fk == 0 {
206                continue;
207            }
208            // Encoding: nonzero value v means vertex v - 1 of G_2.
209            let a = fi - 1;
210            let b = fk - 1;
211            let pair = if a < b { (a, b) } else { (b, a) };
212            if contacts_2_set.contains(&pair) {
213                count += 1;
214            }
215        }
216        Ok(Some(i64::try_from(count).map_err(|_| {
217            crate::traits::EvaluationError::IntegerOverflow(
218                "converting preserved-contact count to i64".into(),
219            )
220        })?))
221    }
222}
223
224impl Problem for MaximumContactMapOverlap {
225    const NAME: &'static str = "MaximumContactMapOverlap";
226    type Solution = Vec<usize>;
227    type Value = Max<i64>;
228
229    crate::problem_parameters![
230        ("num_contacts_1", num_contacts_1),
231        ("num_contacts_2", num_contacts_2),
232        ("num_vertices_1", num_vertices_1),
233        ("num_vertices_2", num_vertices_2),
234    ];
235
236    fn variant() -> Vec<(&'static str, &'static str)> {
237        crate::variant_params![]
238    }
239
240    fn evaluate(
241        &self,
242        config: &Self::Solution,
243    ) -> Result<Max<i64>, crate::traits::EvaluationError> {
244        if config.len() != self.num_vertices_1 {
245            return Err(crate::traits::EvaluationError::InvalidConfiguration(
246                "contact-map alignment length does not match the first map".into(),
247            ));
248        }
249        if config.iter().any(|&vertex| vertex > self.num_vertices_2) {
250            return Err(crate::traits::EvaluationError::InvalidConfiguration(
251                "contact-map alignment contains an out-of-range target vertex".into(),
252            ));
253        }
254        Ok({
255            match self.preserved_contact_count(config)? {
256                Some(count) => Max(Some(count)),
257                None => Max(None),
258            }
259        })
260    }
261}
262
263impl crate::solvers::BruteForceProblem for MaximumContactMapOverlap {
264    fn dimensions(&self) -> Vec<usize> {
265        vec![self.num_vertices_2 + 1; self.num_vertices_1]
266    }
267}
268
269crate::declare_variants! {
270    default MaximumContactMapOverlap => "(num_vertices_2 + 1)^num_vertices_1",
271}
272
273crate::register_brute_force! {
274    MaximumContactMapOverlap,
275}
276
277#[cfg(feature = "example-db")]
278pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
279    // Canonical example from the issue:
280    //   G_1: n_1 = 4, E_1 = {{0,2}, {1,3}}
281    //   G_2: n_2 = 5, E_2 = {{0,3}, {1,4}, {0,2}}
282    // Optimal alignment: 0->0, 1->1, 2->3, 3->4 (encoded as [1, 2, 4, 5]).
283    //   - order-preserving: 1 < 2 < 4 < 5
284    //   - injectivity: all values distinct
285    //   - contact {0,2}: mapped (0, 3); sorted (0, 3) in E_2
286    //   - contact {1,3}: mapped (1, 4); sorted (1, 4) in E_2
287    //   - value = 2 contacts preserved.
288    vec![crate::example_db::specs::ModelExampleSpec {
289        id: "maximum_contact_map_overlap",
290        instance: Box::new(MaximumContactMapOverlap::new(
291            4,
292            vec![(0, 2), (1, 3)],
293            5,
294            vec![(0, 3), (1, 4), (0, 2)],
295        )),
296        optimal_config: serde_json::json!(vec![1, 2, 4, 5]),
297        optimal_value: serde_json::json!(2),
298    }]
299}
300
301#[cfg(test)]
302#[path = "../../unit_tests/models/graph/maximum_contact_map_overlap.rs"]
303mod tests;
problemreductions/models/graph/maximum_contact_map_overlap.rs

problemreductions/models/graph/
maximum_contact_map_overlap.rs
