holos_tda/filtration/
simplex.rs

1use std::collections::{BTreeMap, BTreeSet};
2
3use super::grade::{FiltrationError, FiltrationGrade, ScalarGrade, ScalarProjection};
4
5/// One simplex with a stable vertex key and a filtration grade.
6#[derive(Debug, Clone, PartialEq, Eq)]
7pub struct FilteredSimplex<G> {
8    vertices: Vec<usize>,
9    grade: G,
10}
11
12impl<G> FilteredSimplex<G> {
13    /// Construct a simplex. The enclosing complex checks its vertex key.
14    pub fn new(vertices: Vec<usize>, grade: G) -> Self {
15        Self { vertices, grade }
16    }
17
18    /// Stable vertex labels in ascending order.
19    pub fn vertices(&self) -> &[usize] {
20        &self.vertices
21    }
22
23    /// Dimension of this simplex.
24    pub fn dimension(&self) -> usize {
25        self.vertices.len().saturating_sub(1)
26    }
27
28    /// Filtration grade of this simplex.
29    pub fn grade(&self) -> &G {
30        &self.grade
31    }
32}
33
34/// A finite explicit filtered simplicial complex.
35///
36/// Vertex labels are stable keys. Every nonempty face must occur exactly once,
37/// and each face grade must precede the grade of its cofaces.
38#[derive(Debug, Clone, PartialEq, Eq)]
39pub struct FilteredSimplicialComplex<G> {
40    vertex_labels: Vec<usize>,
41    simplices: Vec<Vec<FilteredSimplex<G>>>,
42}
43
44impl<G: FiltrationGrade> FilteredSimplicialComplex<G> {
45    /// Construct a checked explicit complex grouped by simplex dimension.
46    pub fn new(
47        vertex_labels: Vec<usize>,
48        mut simplices: Vec<Vec<FilteredSimplex<G>>>,
49    ) -> Result<Self, FiltrationError> {
50        if vertex_labels.windows(2).any(|pair| pair[0] >= pair[1]) {
51            return Err(FiltrationError::new(
52                "vertex labels must be strictly increasing",
53            ));
54        }
55        if simplices.is_empty() {
56            simplices.push(Vec::new());
57        }
58        for dimension in &mut simplices {
59            dimension.sort_by(|left, right| left.vertices.cmp(&right.vertices));
60        }
61        let complex = Self {
62            vertex_labels,
63            simplices,
64        };
65        complex.validate()?;
66        Ok(complex)
67    }
68
69    /// Stable labels of all vertices in this complex.
70    pub fn vertex_labels(&self) -> &[usize] {
71        &self.vertex_labels
72    }
73
74    /// Highest stored simplex dimension, including a trailing empty group.
75    pub fn max_dimension(&self) -> usize {
76        self.simplices.len().saturating_sub(1)
77    }
78
79    /// Simplices grouped by dimension and ordered by vertex key.
80    pub fn simplices(&self) -> &[Vec<FilteredSimplex<G>>] {
81        &self.simplices
82    }
83
84    /// Number of stored simplices in all dimensions.
85    pub fn simplex_count(&self) -> usize {
86        self.simplices.iter().map(Vec::len).sum()
87    }
88
89    /// Apply a scalar projection and check the resulting filtration.
90    pub fn project<P: ScalarProjection<G>>(
91        &self,
92        projection: &P,
93    ) -> Result<FilteredSimplicialComplex<ScalarGrade>, FiltrationError> {
94        let mut simplices = Vec::with_capacity(self.simplices.len());
95        for dimension in &self.simplices {
96            let mut projected = Vec::with_capacity(dimension.len());
97            for simplex in dimension {
98                projected.push(FilteredSimplex::new(
99                    simplex.vertices.clone(),
100                    projection.project(&simplex.grade)?,
101                ));
102            }
103            simplices.push(projected);
104        }
105        FilteredSimplicialComplex::new(self.vertex_labels.clone(), simplices)
106    }
107
108    fn validate(&self) -> Result<(), FiltrationError> {
109        let labels: BTreeSet<_> = self.vertex_labels.iter().copied().collect();
110        let mut grades = BTreeMap::<Vec<usize>, &G>::new();
111        for (dimension, simplices) in self.simplices.iter().enumerate() {
112            for simplex in simplices {
113                validate_simplex_key(simplex, dimension, &labels)?;
114                insert_simplex_grade(simplex, &mut grades)?;
115            }
116        }
117        validate_declared_vertices(&self.simplices[0], &self.vertex_labels)?;
118        validate_faces(&grades)
119    }
120}
121
122fn validate_simplex_key<G>(
123    simplex: &FilteredSimplex<G>,
124    dimension: usize,
125    labels: &BTreeSet<usize>,
126) -> Result<(), FiltrationError> {
127    if simplex.vertices.len() != dimension + 1 {
128        return Err(FiltrationError::new(format!(
129            "simplex {:?} is stored in dimension {dimension}",
130            simplex.vertices
131        )));
132    }
133    if simplex.vertices.windows(2).any(|pair| pair[0] >= pair[1]) {
134        return Err(FiltrationError::new(format!(
135            "simplex {:?} does not have a canonical vertex key",
136            simplex.vertices
137        )));
138    }
139    if simplex
140        .vertices
141        .iter()
142        .any(|vertex| !labels.contains(vertex))
143    {
144        return Err(FiltrationError::new(format!(
145            "simplex {:?} uses an unknown vertex label",
146            simplex.vertices
147        )));
148    }
149    Ok(())
150}
151
152fn insert_simplex_grade<'a, G>(
153    simplex: &'a FilteredSimplex<G>,
154    grades: &mut BTreeMap<Vec<usize>, &'a G>,
155) -> Result<(), FiltrationError> {
156    if grades
157        .insert(simplex.vertices.clone(), &simplex.grade)
158        .is_some()
159    {
160        return Err(FiltrationError::new(format!(
161            "simplex {:?} occurs more than once",
162            simplex.vertices
163        )));
164    }
165    Ok(())
166}
167
168fn validate_declared_vertices<G>(
169    vertices: &[FilteredSimplex<G>],
170    labels: &[usize],
171) -> Result<(), FiltrationError> {
172    let declared: Vec<_> = vertices.iter().map(|simplex| simplex.vertices[0]).collect();
173    if declared != labels {
174        return Err(FiltrationError::new(
175            "zero-dimensional simplices must match the vertex labels",
176        ));
177    }
178    Ok(())
179}
180
181fn validate_faces<G: FiltrationGrade>(
182    grades: &BTreeMap<Vec<usize>, &G>,
183) -> Result<(), FiltrationError> {
184    for (key, grade) in grades {
185        if key.len() > 1 {
186            validate_simplex_faces(key, *grade, grades)?;
187        }
188    }
189    Ok(())
190}
191
192fn validate_simplex_faces<G: FiltrationGrade>(
193    key: &[usize],
194    grade: &G,
195    grades: &BTreeMap<Vec<usize>, &G>,
196) -> Result<(), FiltrationError> {
197    for removed in 0..key.len() {
198        let mut face = key.to_vec();
199        face.remove(removed);
200        let face_grade = grades.get(&face).ok_or_else(|| {
201            FiltrationError::new(format!("simplex {key:?} is missing the face {face:?}"))
202        })?;
203        if !face_grade.precedes(grade) {
204            return Err(FiltrationError::new(format!(
205                "face {face:?} appears after its coface {key:?}"
206            )));
207        }
208    }
209    Ok(())
210}
holos_tda/filtration/simplex.rs

holos_tda/filtration/
simplex.rs
