mod access;
mod metadata;
pub use metadata::{ApproximationTarget, RipsApproximation, RipsApproximationBound};
mod blocker;
mod edges;
mod expansion;
mod greedy;
mod options;
use super::RipsInputKind;
use crate::complex::{WeightedEdge, WeightedGraph};
use crate::filtration::Coverage;
use crate::geometry::{
DissimilarityMatrixView, MatrixLayout, PointCloudView, distance::nonnegative,
euclidean_distance, validate_metric_with_checkpoints,
};
use crate::{Error, Result};
pub(crate) use access::SparseRipsAccess;
pub use expansion::SparseRipsExpansion;
pub use options::SparseRipsOptions;
#[derive(Clone, Debug)]
pub struct SparseRips {
pub(crate) graph: WeightedGraph,
pub(crate) metadata: RipsApproximation,
pub(crate) coverage: Coverage,
pub(crate) kind: RipsInputKind,
radii: Vec<Option<f64>>,
factor: f64,
}
impl SparseRips {
pub fn graph(&self) -> &WeightedGraph {
&self.graph
}
pub fn approximation(&self) -> &RipsApproximation {
&self.metadata
}
pub fn coverage(&self) -> Coverage {
self.coverage
}
pub fn input_kind(&self) -> RipsInputKind {
self.kind
}
}
pub fn sparse_rips_from_distances(
input: DissimilarityMatrixView<'_>,
options: &SparseRipsOptions,
) -> Result<SparseRips> {
build(
input.len(),
options,
RipsInputKind::Dissimilarities,
|a, b| Ok(input.get(a, b).unwrap()),
)
}
pub fn sparse_rips_from_points(
input: PointCloudView<'_>,
options: &SparseRipsOptions,
) -> Result<SparseRips> {
build(input.len(), options, RipsInputKind::Euclidean, |a, b| {
euclidean_distance(input, a, b)
})
}
pub fn sparse_rips_with_distance<P>(
points: &[P],
options: &SparseRipsOptions,
mut distance: impl FnMut(&P, &P) -> Result<f64>,
) -> Result<SparseRips> {
let n = points.len();
let count = crate::geometry::pair_count(n).ok_or(Error::SizeOverflow {
operation: "sparse callback pair count",
})?;
let mut values = Vec::new();
values.try_reserve_exact(count).map_err(|_| allocation())?;
for b in 0..n {
for a in 0..b {
values.push(distance(&points[a], &points[b])?);
}
}
let matrix = DissimilarityMatrixView::new(&values, n, MatrixLayout::LowerTriangle)?;
build(n, options, RipsInputKind::Custom, |a, b| {
Ok(matrix.get(a, b).unwrap())
})
}
fn build(
n: usize,
options: &SparseRipsOptions,
kind: RipsInputKind,
mut distance: impl FnMut(usize, usize) -> Result<f64>,
) -> Result<SparseRips> {
build_with(n, options, kind, &mut distance, &mut || Ok(()))
}
pub(super) fn build_with(
n: usize,
options: &SparseRipsOptions,
kind: RipsInputKind,
mut distance: impl FnMut(usize, usize) -> Result<f64>,
checkpoint: &mut impl FnMut() -> Result<()>,
) -> Result<SparseRips> {
if options.start.is_some_and(|v| v >= n) {
return Err(Error::InvalidParameter {
parameter: "start_vertex",
reason: "outside input vertices",
});
}
checkpoint()?;
for b in 0..n {
for a in 0..b {
checkpoint()?;
nonnegative(distance(a, b)?, "sparse distance", None)?;
}
}
let metric = validate_metric_with_checkpoints(n, options.policy, &mut distance, checkpoint)?;
let greedy = greedy::permutation(n, options.start, &mut distance, checkpoint)?;
let kept = greedy
.radii
.iter()
.take_while(|r| r.is_none_or(|r| r > 0.0 && r >= options.min_radius))
.count();
let covering_radius = greedy.radii.get(kept).copied().flatten().unwrap_or(0.0);
let mut retained_vertices = Vec::new();
retained_vertices
.try_reserve_exact(kept)
.map_err(|_| allocation())?;
retained_vertices.extend_from_slice(&greedy.order[..kept]);
retained_vertices.sort_unstable();
let mut radii = Vec::new();
radii.try_reserve_exact(kept).map_err(|_| allocation())?;
radii.resize(kept, None);
for (&v, &r) in greedy.order[..kept].iter().zip(&greedy.radii) {
radii[retained_vertices.binary_search(&v).unwrap()] = r;
}
let mut graph_edges = Vec::new();
let mut omitted_by_scale = false;
for j in 1..kept {
for i in 0..j {
checkpoint()?;
let a = greedy.order[i];
let b = greedy.order[j];
if let Some(value) = edges::value(
distance(a, b)?,
greedy.radii[i],
greedy.radii[j].unwrap(),
options.epsilon,
)? {
if options.max_scale.is_some_and(|t| value > t) {
omitted_by_scale = true;
continue;
}
graph_edges.try_reserve(1).map_err(|_| allocation())?;
graph_edges.push(WeightedEdge {
vertices: [
retained_vertices.binary_search(&a).unwrap(),
retained_vertices.binary_search(&b).unwrap(),
],
value,
});
}
}
}
let coverage = if omitted_by_scale {
Coverage::Through(options.max_scale.unwrap())
} else {
Coverage::Complete
};
checkpoint()?;
let graph = WeightedGraph::new(kept, graph_edges)?;
checkpoint()?;
Ok(SparseRips {
graph,
coverage,
kind,
radii,
factor: blocker::factor(options.epsilon),
metadata: RipsApproximation {
epsilon: options.epsilon,
permutation: greedy.order,
insertion_radii: greedy.radii,
retained_vertices,
min_insertion_radius: options.min_radius,
max_scale: options.max_scale,
metric,
covering_radius,
},
})
}
fn allocation() -> Error {
Error::AllocationFailed {
context: "sparse Rips construction",
}
}
mod builder;
pub use builder::{ApproximateRipsBuilder, ApproximateRipsCallbackBuilder};