holos_tda/certificate/
model.rs

1//! Public certificate data types and shared private models.
2
3use std::fmt;
4
5use crate::{Bar, CriticalPair, Diagram, Error};
6
7/// Failure while producing or checking an algebraic certificate.
8#[derive(Debug, Clone, PartialEq, Eq)]
9pub struct CertificateError {
10    message: String,
11}
12
13impl CertificateError {
14    pub(crate) fn new(message: impl Into<String>) -> Self {
15        Self {
16            message: message.into(),
17        }
18    }
19
20    /// Description of the violated certificate rule.
21    pub fn message(&self) -> &str {
22        &self.message
23    }
24}
25
26impl fmt::Display for CertificateError {
27    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
28        write!(f, "reduction certificate: {}", self.message)
29    }
30}
31
32impl std::error::Error for CertificateError {}
33
34/// Resource limits for certificate production and verification.
35#[derive(Debug, Clone, Copy, PartialEq, Eq)]
36#[non_exhaustive]
37pub struct CertificateLimits {
38    /// Largest accepted certificate envelope in bytes.
39    pub max_bytes: usize,
40    /// Largest accepted vertex count.
41    pub max_vertices: usize,
42    /// Largest accepted filtered edge count.
43    pub max_edges: usize,
44    /// Largest accepted filtered triangle count.
45    pub max_triangles: usize,
46    /// Largest accepted simplex count in any dimension above two.
47    pub max_higher_simplices: usize,
48    /// Largest homology dimension accepted by a graded certificate.
49    pub max_dimension: usize,
50    /// Largest accepted total change-of-basis term count.
51    pub max_terms: usize,
52    /// Largest accepted diagram bar count.
53    pub max_bars: usize,
54}
55
56impl Default for CertificateLimits {
57    fn default() -> Self {
58        Self {
59            max_bytes: 1 << 30,
60            max_vertices: 1_000_000,
61            max_edges: 20_000_000,
62            max_triangles: 100_000_000,
63            max_higher_simplices: 100_000_000,
64            max_dimension: 8,
65            max_terms: 200_000_000,
66            max_bars: 100_000_000,
67        }
68    }
69}
70
71/// One nonzero coefficient in a sparse change-of-basis column.
72#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
73pub struct CertificateTerm {
74    /// Earlier or current source-column position.
75    pub index: usize,
76    /// Coefficient in `1..modulus`.
77    pub coefficient: u32,
78}
79
80/// One filtration-compatible change-of-basis column.
81#[derive(Debug, Clone, PartialEq, Eq)]
82pub struct ChangeColumn {
83    /// Nonzero terms in ascending source-column order.
84    pub terms: Vec<CertificateTerm>,
85}
86
87/// How an existing checked reduction was adapted to a changed filtration.
88#[derive(Debug, Clone, Copy, PartialEq, Eq)]
89pub enum ReductionRepairMode {
90    /// Every reduction column remained valid in the same position.
91    Reused,
92    /// A stable prefix was reused and the remaining columns were reduced.
93    SuffixRepaired,
94    /// No reduction column could be reused.
95    Rebuilt,
96}
97
98/// Exact algebraic work charged to one reduction repair.
99#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
100pub struct ReductionRepairWork {
101    /// Edge-boundary columns retained without reduction.
102    pub edge_columns_reused: usize,
103    /// Edge-boundary columns reduced after the retained prefix.
104    pub edge_columns_reduced: usize,
105    /// Triangle-boundary columns retained without reduction.
106    pub triangle_columns_reused: usize,
107    /// Triangle-boundary columns reduced after the retained prefix.
108    pub triangle_columns_reduced: usize,
109    /// Sparse column additions performed by the repair.
110    pub column_additions: usize,
111}
112
113impl ReductionRepairWork {
114    /// Total boundary columns in the repaired reduction.
115    pub fn columns(&self) -> usize {
116        self.edge_columns_reused
117            + self.edge_columns_reduced
118            + self.triangle_columns_reused
119            + self.triangle_columns_reduced
120    }
121
122    /// Columns retained without another reduction pass.
123    pub fn columns_reused(&self) -> usize {
124        self.edge_columns_reused + self.triangle_columns_reused
125    }
126
127    /// Columns processed by the repair reduction.
128    pub fn columns_reduced(&self) -> usize {
129        self.edge_columns_reduced + self.triangle_columns_reduced
130    }
131}
132
133/// A checked reduction adapted to a changed filtration.
134#[derive(Debug, Clone)]
135pub struct ReductionRepair {
136    pub(super) certificate: ReductionCertificate,
137    pub(super) mode: ReductionRepairMode,
138    pub(super) work: ReductionRepairWork,
139}
140
141impl ReductionRepair {
142    /// Repaired certificate bound to the updated graph.
143    pub fn certificate(&self) -> &ReductionCertificate {
144        &self.certificate
145    }
146
147    /// How the reduction was adapted.
148    pub fn mode(&self) -> ReductionRepairMode {
149        self.mode
150    }
151
152    /// Exact reduction work charged by the operation.
153    pub fn work(&self) -> ReductionRepairWork {
154        self.work
155    }
156
157    pub(crate) fn into_certificate(self) -> ReductionCertificate {
158        self.certificate
159    }
160}
161
162/// One simplex named by its ascending vertex labels.
163#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
164pub struct FiltrationSimplex {
165    pub(super) vertices: Vec<usize>,
166}
167
168impl FiltrationSimplex {
169    pub(super) fn new(vertices: impl Into<Vec<usize>>) -> Self {
170        Self {
171            vertices: vertices.into(),
172        }
173    }
174
175    /// Simplex dimension.
176    pub fn dimension(&self) -> usize {
177        self.vertices.len().saturating_sub(1)
178    }
179
180    /// Ascending vertex labels.
181    pub fn vertices(&self) -> &[usize] {
182        &self.vertices
183    }
184}
185
186/// Algebraic reason that one filtration comparison must remain true.
187#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
188#[non_exhaustive]
189pub enum ReductionGuardKind {
190    /// A source term in `V` must not follow its target column.
191    ChangeOfBasis,
192    /// A reduced-column term must not follow the declared pivot.
193    Pivot,
194}
195
196/// One comparison sufficient to preserve a checked reduction.
197#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
198pub struct ReductionGuard {
199    pub(super) kind: ReductionGuardKind,
200    pub(super) earlier: FiltrationSimplex,
201    pub(super) later: FiltrationSimplex,
202}
203
204impl ReductionGuard {
205    /// Why the comparison is required.
206    pub fn kind(&self) -> ReductionGuardKind {
207        self.kind
208    }
209
210    /// Simplex that must not follow [`Self::later`].
211    pub fn earlier(&self) -> &FiltrationSimplex {
212        &self.earlier
213    }
214
215    /// Simplex that must not precede [`Self::earlier`].
216    pub fn later(&self) -> &FiltrationSimplex {
217        &self.later
218    }
219}
220
221/// Kind of failed condition in a certified reduction region.
222#[derive(Debug, Clone, Copy, PartialEq, Eq)]
223#[non_exhaustive]
224pub enum RegionViolationKind {
225    /// The labeled vertex set changed.
226    VertexSetChanged,
227    /// The complete listed edge set changed.
228    EdgeSetChanged,
229    /// An edge crossed the fixed threshold.
230    ThresholdCrossing,
231    /// A required filtration comparison reversed.
232    GuardFailed,
233}
234
235/// One condition that prevents reuse of a certified reduction.
236#[derive(Debug, Clone, PartialEq, Eq)]
237pub struct RegionViolation {
238    pub(super) kind: RegionViolationKind,
239    pub(super) guard_index: Option<usize>,
240    pub(super) first: Option<FiltrationSimplex>,
241    pub(super) second: Option<FiltrationSimplex>,
242}
243
244impl RegionViolation {
245    /// Kind of failed condition.
246    pub fn kind(&self) -> RegionViolationKind {
247        self.kind
248    }
249
250    /// Index in [`CertifiedReductionRegion::guards`], when a guard failed.
251    pub fn guard_index(&self) -> Option<usize> {
252        self.guard_index
253    }
254
255    /// First affected simplex, when one is available.
256    pub fn first(&self) -> Option<&FiltrationSimplex> {
257        self.first.as_ref()
258    }
259
260    /// Second affected simplex, when one is available.
261    pub fn second(&self) -> Option<&FiltrationSimplex> {
262        self.second.as_ref()
263    }
264}
265
266/// Exact result obtained by reusing one checked algebraic reduction.
267#[derive(Debug, Clone)]
268pub struct CertifiedRegionEvaluation {
269    pub(super) diagram: Diagram,
270    pub(super) h1_pairs: Vec<(Bar, CriticalPair)>,
271    pub(super) guards_checked: usize,
272}
273
274impl CertifiedRegionEvaluation {
275    /// Exact H0 and H1 diagram at the updated weights.
276    pub fn diagram(&self) -> &Diagram {
277        &self.diagram
278    }
279
280    /// Positive H1 intervals and their unchanged critical simplices.
281    pub fn h1_critical_pairs(&self) -> &[(Bar, CriticalPair)] {
282        &self.h1_pairs
283    }
284
285    /// Number of algebraic comparisons checked for this evaluation.
286    pub fn guards_checked(&self) -> usize {
287        self.guards_checked
288    }
289}
290#[derive(Debug, Clone)]
291pub(super) struct RegionH1Pair {
292    pub(super) birth: [usize; 2],
293    pub(super) death: Option<[usize; 3]>,
294}
295
296#[derive(Debug, Clone, Copy)]
297pub(super) enum RegionValueFormula {
298    Vertex,
299    Edge(usize),
300    Triangle([usize; 3]),
301}
302
303impl RegionValueFormula {
304    pub(super) fn value(self, edge_value: impl Fn(usize) -> f64) -> f64 {
305        match self {
306            Self::Vertex => 0.0,
307            Self::Edge(edge) => edge_value(edge),
308            Self::Triangle([first, second, third]) => edge_value(first)
309                .max(edge_value(second))
310                .max(edge_value(third)),
311        }
312    }
313}
314
315/// Reusable exact H0 and H1 reduction under result-sensitive guards.
316///
317/// The region fixes the labeled graph and threshold membership. It does not
318/// fix the complete weak edge order. Reuse is valid while every declared
319/// change-of-basis and pivot guard remains true.
320#[derive(Debug, Clone)]
321pub struct CertifiedReductionRegion {
322    pub(super) vertex_count: usize,
323    pub(super) threshold: Option<f64>,
324    pub(super) topology: Vec<[usize; 2]>,
325    pub(super) active: Vec<bool>,
326    pub(super) complete_guards: Vec<ReductionGuard>,
327    pub(super) guards: Vec<ReductionGuard>,
328    pub(super) guard_indices: Vec<(usize, usize)>,
329    pub(super) guard_ranks: Vec<u128>,
330    pub(super) guard_formulas: Vec<RegionValueFormula>,
331    pub(super) h0_deaths: Vec<[usize; 2]>,
332    pub(super) h0_essential: usize,
333    pub(super) h1_pairs: Vec<RegionH1Pair>,
334    pub(super) h1_formulas: Vec<(usize, Option<[usize; 3]>)>,
335}
336
337/// Proof that a filtered boundary matrix has the declared reduced pivots.
338#[derive(Debug, Clone)]
339pub struct ReductionCertificate {
340    pub(super) vertex_count: usize,
341    pub(super) threshold: Option<f64>,
342    pub(super) modulus: u32,
343    pub(super) graph_digest: [u8; 32],
344    pub(super) edge_columns: Vec<ChangeColumn>,
345    pub(super) triangle_columns: Vec<ChangeColumn>,
346    pub(super) diagram: Diagram,
347}
348
349pub(super) type CertificateResult<T> = std::result::Result<T, CertificateError>;
350impl From<CertificateError> for Error {
351    fn from(error: CertificateError) -> Self {
352        Self::InvalidInput(error.to_string())
353    }
354}
holos_tda/certificate/model.rs

holos_tda/certificate/
model.rs
