qualia_core_db/solvers/ontology_align/
align.rs

1//! Ontology alignment as optimization (CI-SKM ch 4) — given a similarity matrix
2//! between two ontologies' entities, find the injective correspondence set that
3//! maximizes total alignment quality. Greedy initialization refined by
4//! hill-climbing (reusing `optimization::metaheuristics`, no new optimizer).
5//!
6//! The output is a set of graded **`closeMatch` proposals → `RequiresHumanReview`**
7//! ([`super::correspondence`]); it never asserts `exactMatch`. Kernel-class
8//! `Divergent`.
9
10use crate::solvers::ontology_align::correspondence::{Alignment, Correspondence};
11use crate::solvers::optimization::metaheuristics::hill_climbing;
12
13/// Total matched similarity of an injective assignment `map[source] = target`
14/// (`-1` = unmatched). Row-major `sim` is `n_source × n_target`.
15fn quality(sim: &[f64], n_target: usize, map: &[i64]) -> f64 {
16    let mut q = 0.0;
17    for (i, &t) in map.iter().enumerate() {
18        if t >= 0 {
19            q += sim[i * n_target + t as usize];
20        }
21    }
22    q
23}
24
25/// Align two ontologies from their `n_source × n_target` similarity matrix. Only
26/// correspondences with degree ≥ `threshold` are proposed. Returns the alignment as
27/// review-required `closeMatch` proposals.
28pub fn align(sim: &[f64], n_source: usize, n_target: usize, threshold: f64) -> Option<Alignment> {
29    if n_source == 0 || n_target == 0 || sim.len() != n_source * n_target {
30        return None;
31    }
32
33    // Greedy initialization: take the strongest available pairs first.
34    let mut pairs: Vec<(usize, usize, f64)> = Vec::with_capacity(n_source * n_target);
35    for i in 0..n_source {
36        for j in 0..n_target {
37            pairs.push((i, j, sim[i * n_target + j]));
38        }
39    }
40    pairs.sort_by(|a, b| b.2.partial_cmp(&a.2).unwrap_or(core::cmp::Ordering::Equal));
41    let mut map = vec![-1i64; n_source];
42    let mut target_used = vec![false; n_target];
43    for (i, j, s) in pairs {
44        if s >= threshold && map[i] < 0 && !target_used[j] {
45            map[i] = j as i64;
46            target_used[j] = true;
47        }
48    }
49
50    // Hill-climb: for each source, try reassigning to a free target (or unmatch),
51    // keeping the assignment injective.
52    let neighbors = |m: &Vec<i64>| {
53        let mut used = vec![false; n_target];
54        for &t in m {
55            if t >= 0 {
56                used[t as usize] = true;
57            }
58        }
59        let mut out = Vec::new();
60        for i in 0..n_source {
61            // Unmatch.
62            if m[i] >= 0 {
63                let mut c = m.clone();
64                c[i] = -1;
65                out.push(c);
66            }
67            for j in 0..n_target {
68                let free = !used[j] || m[i] == j as i64;
69                if free && sim[i * n_target + j] >= threshold && m[i] != j as i64 {
70                    let mut c = m.clone();
71                    c[i] = j as i64;
72                    out.push(c);
73                }
74            }
75        }
76        out
77    };
78    let objective = |m: &Vec<i64>| -quality(sim, n_target, m);
79    let (best, neg_q) = hill_climbing(map, &neighbors, &objective, 200);
80
81    let correspondences: Vec<Correspondence> = best
82        .iter()
83        .enumerate()
84        .filter_map(|(i, &t)| {
85            if t >= 0 {
86                let j = t as usize;
87                Some(Correspondence::propose(i, j, sim[i * n_target + j]))
88            } else {
89                None
90            }
91        })
92        .collect();
93
94    Some(Alignment {
95        correspondences,
96        quality: -neg_q,
97    })
98}
99
100#[cfg(test)]
101mod tests {
102    use super::*;
103
104    #[test]
105    fn recovers_the_diagonal_correspondence() {
106        // 3×3 similarity, strong on the diagonal → align i↔i.
107        let sim = [0.9, 0.1, 0.2, 0.1, 0.8, 0.3, 0.2, 0.2, 0.95];
108        let a = align(&sim, 3, 3, 0.5).unwrap();
109        assert_eq!(a.correspondences.len(), 3);
110        for c in &a.correspondences {
111            assert_eq!(c.source, c.target, "expected diagonal match");
112        }
113        assert!(a.quality > 2.5);
114        // The guardrail: every correspondence is a review-required close-match.
115        assert!(a.all_require_review());
116    }
117
118    #[test]
119    fn weak_pairs_below_threshold_are_not_proposed() {
120        // Only one strong pair; the rest are below threshold.
121        let sim = [0.9, 0.1, 0.1, 0.1];
122        let a = align(&sim, 2, 2, 0.5).unwrap();
123        assert_eq!(a.correspondences.len(), 1);
124        assert_eq!(
125            (a.correspondences[0].source, a.correspondences[0].target),
126            (0, 0)
127        );
128    }
129
130    #[test]
131    fn never_asserts_exact_match() {
132        // No matter the input, the engine only emits review-required proposals.
133        let sim = [1.0, 1.0, 1.0, 1.0];
134        let a = align(&sim, 2, 2, 0.0).unwrap();
135        assert!(a.all_require_review());
136        assert!(a.correspondences.iter().all(|c| c.degree <= 1.0));
137    }
138
139    #[test]
140    fn guards() {
141        assert!(align(&[], 0, 0, 0.5).is_none());
142        assert!(align(&[1.0, 2.0], 2, 2, 0.5).is_none()); // wrong length
143    }
144}
qualia_core_db/solvers/ontology_align/align.rs

qualia_core_db/solvers/ontology_align/
align.rs
