holos_tda/intervention/
search.rs

1use std::collections::{BTreeMap, BTreeSet};
2
3use super::Result;
4use super::model::{
5    EdgeWeightEdit, H1Intervention, InterventionArtifact, InterventionBudget, InterventionStatus,
6};
7use super::primitives::maximum_edit;
8use crate::{
9    EdgeKey, Error, IntervalGroupId, PersistenceProgram, ProgramTraceArtifact, ProgramUpdateMode,
10    SparseDistanceMatrix, VerifiedProgramTrace,
11};
12
13impl PersistenceProgram {
14    /// Find an independent-weight edit that shortens one finite H1 class
15    /// space.
16    ///
17    /// The target must satisfy `birth < target_scale < death`. The candidate
18    /// lowers every edge above `target_scale` in every declared destroyer
19    /// triangle. `Optimal` is relative to the same reduction and critical-pair
20    /// certificate. It is not a global inverse persistence claim across
21    /// unrelated pairings.
22    pub fn kill_h1_before(
23        &self,
24        target: IntervalGroupId,
25        target_scale: f64,
26        budget: InterventionBudget,
27    ) -> Result<H1Intervention> {
28        let space = validate_intervention_request(self, target, target_scale)?;
29        if budget.max_candidates == 0 {
30            return Ok(budget_limited_intervention(target, target_scale));
31        }
32        search_intervention(self, space, target, target_scale)
33    }
34}
35
36fn validate_intervention_request(
37    program: &PersistenceProgram,
38    target: IntervalGroupId,
39    target_scale: f64,
40) -> Result<&crate::PersistentClassSpace> {
41    if !target_scale.is_finite() || target_scale < 0.0 {
42        return Err(Error::InvalidInput(format!(
43            "intervention target scale must be non-negative and finite, got {target_scale}"
44        )));
45    }
46    let space = program
47        .result()
48        .spaces
49        .iter()
50        .find(|space| space.id == target)
51        .ok_or_else(|| Error::InvalidInput(format!("unknown class space {target}")))?;
52    check_intervention_interval(space, target_scale)?;
53    Ok(space)
54}
55
56fn check_intervention_interval(
57    space: &crate::PersistentClassSpace,
58    target_scale: f64,
59) -> Result<()> {
60    if space.interval.is_essential() {
61        return Err(Error::InvalidInput(
62            "the finite-death intervention does not support an essential class space".into(),
63        ));
64    }
65    if target_scale <= space.interval.birth || target_scale >= space.interval.death {
66        return Err(Error::InvalidInput(format!(
67            "target scale must lie strictly inside ({}, {})",
68            space.interval.birth, space.interval.death
69        )));
70    }
71    Ok(())
72}
73
74fn budget_limited_intervention(target: IntervalGroupId, target_scale: f64) -> H1Intervention {
75    H1Intervention {
76        target,
77        target_scale,
78        status: InterventionStatus::BudgetLimited,
79        lower_bound: 0.0,
80        upper_bound: None,
81        edits: Vec::new(),
82        result: None,
83        artifact: None,
84    }
85}
86
87fn search_intervention(
88    program: &PersistenceProgram,
89    space: &crate::PersistentClassSpace,
90    target: IntervalGroupId,
91    target_scale: f64,
92) -> Result<H1Intervention> {
93    let edits = destroyer_edits(program.current_graph(), space, target_scale)?;
94    if edits.is_empty() {
95        return Err(Error::InvalidInput(
96            "declared destroyer triangles need no edge edit".into(),
97        ));
98    }
99    let updated = apply_edits(program.current_graph(), &edits)?;
100    let trace = ProgramTraceArtifact::build(
101        program.current_graph(),
102        std::slice::from_ref(&updated),
103        program.params(),
104        program.limits(),
105    )?;
106    let verified = trace.verify(program.limits())?;
107    if !continued_space_dies_by(&verified, target, target_scale) {
108        return Ok(budget_limited_intervention(target, target_scale));
109    }
110    finish_intervention(program, space, target, target_scale, edits, trace, verified)
111}
112
113fn finish_intervention(
114    program: &PersistenceProgram,
115    space: &crate::PersistentClassSpace,
116    target: IntervalGroupId,
117    target_scale: f64,
118    edits: Vec<EdgeWeightEdit>,
119    trace: ProgramTraceArtifact,
120    verified: VerifiedProgramTrace,
121) -> Result<H1Intervention> {
122    let upper_bound = maximum_edit(&edits);
123    let reused = verified.steps[0].mode == ProgramUpdateMode::Reused;
124    let lower_bound = if reused {
125        space.interval.death - target_scale
126    } else {
127        0.0
128    };
129    let status = if reused && lower_bound.to_bits() == upper_bound.to_bits() {
130        InterventionStatus::Optimal
131    } else {
132        InterventionStatus::BoundedGap
133    };
134    let artifact = InterventionArtifact {
135        target,
136        target_scale,
137        status,
138        lower_bound,
139        upper_bound,
140        edits: edits.clone(),
141        trace,
142    };
143    artifact.verify(program.limits())?;
144    Ok(H1Intervention {
145        target,
146        target_scale,
147        status,
148        lower_bound,
149        upper_bound: Some(upper_bound),
150        edits,
151        result: Some(verified.final_program.result().clone()),
152        artifact: Some(artifact),
153    })
154}
155pub(super) fn destroyer_edits(
156    graph: &SparseDistanceMatrix,
157    space: &crate::PersistentClassSpace,
158    target_scale: f64,
159) -> Result<Vec<EdgeWeightEdit>> {
160    let mut edges = BTreeSet::new();
161    for pair in &space.critical_pairs {
162        let death = pair.death.as_ref().ok_or_else(|| {
163            Error::InvalidInput("finite class space has no destroyer triangle".into())
164        })?;
165        let [u, v, w]: [usize; 3] = death
166            .vertices
167            .as_slice()
168            .try_into()
169            .map_err(|_| Error::InvalidInput("destroyer is not a triangle".into()))?;
170        for edge in [EdgeKey::new(u, v), EdgeKey::new(u, w), EdgeKey::new(v, w)] {
171            if graph.get(edge.u, edge.v) > target_scale {
172                edges.insert(edge);
173            }
174        }
175    }
176    Ok(edges
177        .into_iter()
178        .map(|edge| EdgeWeightEdit {
179            edge,
180            before: graph.get(edge.u, edge.v),
181            after: target_scale,
182        })
183        .collect())
184}
185
186pub(super) fn apply_edits(
187    graph: &SparseDistanceMatrix,
188    edits: &[EdgeWeightEdit],
189) -> Result<SparseDistanceMatrix> {
190    let by_edge: BTreeMap<_, _> = edits.iter().map(|edit| (edit.edge, edit)).collect();
191    let triplets: Vec<_> = graph
192        .edges()
193        .map(|(u, v, value)| {
194            let edge = EdgeKey::new(u, v);
195            let value = by_edge.get(&edge).map_or(value, |edit| edit.after);
196            (u, v, value)
197        })
198        .collect();
199    if by_edge
200        .keys()
201        .any(|edge| graph.get(edge.u, edge.v).is_infinite())
202    {
203        return Err(Error::InvalidInput(
204            "intervention edit names an absent edge".into(),
205        ));
206    }
207    SparseDistanceMatrix::from_triplets(graph.len(), &triplets)
208}
209
210pub(super) fn continued_space_dies_by(
211    verified: &VerifiedProgramTrace,
212    target: IntervalGroupId,
213    target_scale: f64,
214) -> bool {
215    let Some(initial) = verified
216        .initial_result
217        .spaces
218        .iter()
219        .find(|space| space.id == target)
220    else {
221        return false;
222    };
223    let Some(step) = verified.steps.first() else {
224        return false;
225    };
226    let final_by_basis: BTreeMap<_, _> = verified
227        .final_program
228        .result()
229        .spaces
230        .iter()
231        .flat_map(|space| space.basis.iter().map(move |class| (class.id, space)))
232        .collect();
233    let mapped: BTreeMap<_, _> = step
234        .continuation
235        .iter()
236        .filter(|record| record.old_spaces.contains(&target))
237        .flat_map(|record| record.transport.iter().map(|term| (term.old, term.new)))
238        .collect();
239    initial.basis.iter().all(|class| {
240        mapped
241            .get(&class.id)
242            .and_then(|new| final_by_basis.get(new))
243            .is_some_and(|space| space.interval.death <= target_scale)
244    })
245}
holos_tda/intervention/search.rs

holos_tda/intervention/
search.rs
