sim_lib_discrete_graph/alignment/
verify.rs

1use super::{
2    Alignment, AlignmentCertificate, AlignmentMemory, DtwPolicy, full_table, peak_memory,
3    reconstruct, rolling_row, select_endpoint, select_rolling_endpoint, validate_policy,
4};
5use crate::{FiniteCost, GraphError};
6
7/// Verifies an alignment certificate, deterministic ties, path, and receipt.
8pub fn verify_alignment<T, C: FiniteCost>(
9    left: &[T],
10    right: &[T],
11    local_cost: impl Fn(&T, &T) -> C,
12    policy: &DtwPolicy<C>,
13    alignment: &Alignment<C>,
14) -> Result<(), GraphError> {
15    validate_policy(policy)?;
16    alignment.receipt.validate()?;
17    let (score, steps, certificate, stats) = match policy.memory {
18        AlignmentMemory::Full => {
19            let (cells, stats) = full_table(left, right, &local_cost, policy, None)?;
20            let endpoint = select_endpoint(&cells, policy.boundary)?;
21            let score = cells[left.len()][endpoint]
22                .as_ref()
23                .expect("selected endpoint is reachable")
24                .total_cost
25                .clone();
26            let steps = reconstruct(&cells, left.len(), endpoint, policy.boundary)?;
27            (
28                score,
29                Some(steps),
30                AlignmentCertificate::Full { cells },
31                stats,
32            )
33        }
34        AlignmentMemory::RollingScoreOnly => {
35            let (final_row, stats) = rolling_row(left, right, &local_cost, policy, None)?;
36            let endpoint = select_rolling_endpoint(&final_row, policy.boundary, right.len())?;
37            let score = final_row[endpoint]
38                .as_ref()
39                .expect("selected endpoint is reachable")
40                .clone();
41            (
42                score,
43                None,
44                AlignmentCertificate::Rolling {
45                    final_row,
46                    endpoint,
47                },
48                stats,
49            )
50        }
51    };
52    if alignment.score != score || alignment.steps != steps || alignment.certificate != certificate
53    {
54        return Err(GraphError::CertificateInvalid(
55            "alignment result violates its Bellman recurrence or stable ties".to_owned(),
56        ));
57    }
58    let memory = peak_memory(left.len(), right.len(), policy.memory)?;
59    if alignment.receipt.cells != stats.cells
60        || alignment.receipt.edges != stats.edges
61        || alignment.receipt.peak_memory_cells != memory
62    {
63        return Err(GraphError::CertificateInvalid(
64            "alignment receipt does not match evaluated cells and edges".to_owned(),
65        ));
66    }
67    Ok(())
68}
sim_lib_discrete_graph/alignment/verify.rs

sim_lib_discrete_graph/alignment/
verify.rs
