mod incidence;
mod simplex;
use crate::{Error, Result};
pub use incidence::BoundaryTerm;
pub(crate) use simplex::compare_filtration;
pub use simplex::{Simplex, SimplexId};
use std::collections::HashMap;
#[derive(Clone, Debug)]
pub struct SimplicialComplex {
simplices: Vec<Simplex>,
lookup: HashMap<Vec<usize>, SimplexId>,
boundaries: Vec<Vec<BoundaryTerm>>,
cofacets: Vec<Vec<SimplexId>>,
vertex_count: usize,
dimension: Option<usize>,
zero_born: bool,
}
impl SimplicialComplex {
pub fn new(simplices: Vec<Simplex>) -> Result<Self> {
Self::new_with(simplices, &crate::execution::Execution::default())
}
pub fn new_with(
simplices: Vec<Simplex>,
execution: &crate::execution::Execution<'_>,
) -> Result<Self> {
let mut budget = crate::execution::WorkBudget::new(execution)?;
Self::from_simplices(simplices, &mut || budget.step())
}
pub fn max_filtration_value(&self) -> Option<f64> {
self.simplices.last().map(Simplex::value)
}
pub fn vertex_count(&self) -> usize {
self.vertex_count
}
pub(crate) fn has_zero_born_vertices(&self) -> bool {
self.zero_born
}
pub(crate) fn from_simplices(
mut simplices: Vec<Simplex>,
checkpoint: &mut impl FnMut() -> Result<()>,
) -> Result<Self> {
checkpoint()?;
simplices.sort_unstable();
let mut lookup = HashMap::new();
lookup
.try_reserve(simplices.len())
.map_err(|_| allocation())?;
let mut boundaries = Vec::new();
let mut cofacets: Vec<Vec<SimplexId>> = Vec::new();
boundaries
.try_reserve_exact(simplices.len())
.map_err(|_| allocation())?;
cofacets
.try_reserve_exact(simplices.len())
.map_err(|_| allocation())?;
let mut vertex_count = 0;
let mut dimension = None;
let mut zero_born = true;
for (position, simplex) in simplices.iter().enumerate() {
checkpoint()?;
dimension = dimension.max(Some(simplex.dimension()));
if simplex.dimension() == 0 {
vertex_count += 1;
zero_born &= simplex.value() == 0.;
}
let id = SimplexId(position);
let mut boundary = Vec::new();
if simplex.dimension() > 0 {
boundary
.try_reserve_exact(simplex.vertices.len())
.map_err(|_| allocation())?;
for omitted in 0..simplex.vertices.len() {
checkpoint()?;
let mut vertices = simplex.vertices.clone();
vertices.remove(omitted);
let &face = lookup.get(&vertices).ok_or(Error::InvalidComplex {
cell: Some(position),
reason: "simplex face missing or later in filtration",
})?;
boundary.push(BoundaryTerm {
face,
coefficient: if omitted % 2 == 0 { 1 } else { -1 },
});
cofacets[face.0].try_reserve(1).map_err(|_| allocation())?;
cofacets[face.0].push(id);
}
}
if lookup.insert(simplex.vertices.clone(), id).is_some() {
return Err(Error::InvalidComplex {
cell: Some(position),
reason: "duplicate simplex",
});
}
boundaries.push(boundary);
cofacets.push(Vec::new());
}
Ok(Self {
simplices,
lookup,
boundaries,
cofacets,
vertex_count,
dimension,
zero_born,
})
}
pub fn simplices(&self) -> &[Simplex] {
&self.simplices
}
pub fn len(&self) -> usize {
self.simplices.len()
}
pub fn is_empty(&self) -> bool {
self.simplices.is_empty()
}
pub fn dimension(&self) -> Option<usize> {
self.dimension
}
pub fn find(&self, vertices: &[usize]) -> Option<SimplexId> {
self.lookup.get(vertices).copied()
}
pub fn simplex(&self, id: SimplexId) -> Option<&Simplex> {
self.simplices.get(id.0)
}
pub fn boundary(&self, id: SimplexId) -> Option<&[BoundaryTerm]> {
self.boundaries.get(id.0).map(Vec::as_slice)
}
pub fn cofacets(&self, id: SimplexId) -> Option<&[SimplexId]> {
self.cofacets.get(id.0).map(Vec::as_slice)
}
}
fn allocation() -> Error {
Error::AllocationFailed {
context: "simplicial incidence",
}
}