use crate::diagram::{Coverage, IntervalEnd, PersistenceData, PersistenceDiagram};
use crate::execution::{Execution, WorkBudget};
use crate::{Error, Result};
macro_rules! record {
($($body:tt)*) => {
#[cfg(any(test, cocycle_distance_bench))]
{ $($body)* }
};
}
macro_rules! experiment {
($value:expr, $production:expr) => {{
#[cfg(any(test, cocycle_distance_bench))]
{
$value
}
#[cfg(not(any(test, cocycle_distance_bench)))]
{
$production
}
}};
}
pub(crate) mod bottleneck;
pub(crate) mod wasserstein;
pub fn bottleneck_distance(
first: &PersistenceDiagram,
second: &PersistenceDiagram,
dimension: usize,
) -> Result<f64> {
bottleneck_distance_with(first, second, dimension, &Execution::default())
}
pub fn bottleneck_distance_with(
first: &PersistenceDiagram,
second: &PersistenceDiagram,
dimension: usize,
execution: &Execution<'_>,
) -> Result<f64> {
distance_with(first, second, dimension, Kind::Bottleneck, execution)
}
pub fn wasserstein_1_infinity(
first: &PersistenceDiagram,
second: &PersistenceDiagram,
dimension: usize,
) -> Result<f64> {
wasserstein_1_infinity_with(first, second, dimension, &Execution::default())
}
pub fn wasserstein_1_infinity_with(
first: &PersistenceDiagram,
second: &PersistenceDiagram,
dimension: usize,
execution: &Execution<'_>,
) -> Result<f64> {
distance_with(first, second, dimension, Kind::W1, execution)
}
pub fn wasserstein_2_euclidean(
first: &PersistenceDiagram,
second: &PersistenceDiagram,
dimension: usize,
) -> Result<f64> {
wasserstein_2_euclidean_with(first, second, dimension, &Execution::default())
}
pub fn wasserstein_2_euclidean_with(
first: &PersistenceDiagram,
second: &PersistenceDiagram,
dimension: usize,
execution: &Execution<'_>,
) -> Result<f64> {
distance_with(first, second, dimension, Kind::W2, execution)
}
pub fn bottleneck_distance_results<L, R>(first: &L, second: &R, dimension: usize) -> Result<f64>
where
L: AsRef<PersistenceData> + ?Sized,
R: AsRef<PersistenceData> + ?Sized,
{
bottleneck_distance_results_with(first, second, dimension, &Execution::default())
}
pub fn bottleneck_distance_results_with<L, R>(
first: &L,
second: &R,
dimension: usize,
execution: &Execution<'_>,
) -> Result<f64>
where
L: AsRef<PersistenceData> + ?Sized,
R: AsRef<PersistenceData> + ?Sized,
{
distance_results_with(first, second, dimension, Kind::Bottleneck, execution)
}
pub fn wasserstein_1_infinity_results<L, R>(first: &L, second: &R, dimension: usize) -> Result<f64>
where
L: AsRef<PersistenceData> + ?Sized,
R: AsRef<PersistenceData> + ?Sized,
{
wasserstein_1_infinity_results_with(first, second, dimension, &Execution::default())
}
pub fn wasserstein_1_infinity_results_with<L, R>(
first: &L,
second: &R,
dimension: usize,
execution: &Execution<'_>,
) -> Result<f64>
where
L: AsRef<PersistenceData> + ?Sized,
R: AsRef<PersistenceData> + ?Sized,
{
distance_results_with(first, second, dimension, Kind::W1, execution)
}
pub fn wasserstein_2_euclidean_results<L, R>(first: &L, second: &R, dimension: usize) -> Result<f64>
where
L: AsRef<PersistenceData> + ?Sized,
R: AsRef<PersistenceData> + ?Sized,
{
wasserstein_2_euclidean_results_with(first, second, dimension, &Execution::default())
}
pub fn wasserstein_2_euclidean_results_with<L, R>(
first: &L,
second: &R,
dimension: usize,
execution: &Execution<'_>,
) -> Result<f64>
where
L: AsRef<PersistenceData> + ?Sized,
R: AsRef<PersistenceData> + ?Sized,
{
distance_results_with(first, second, dimension, Kind::W2, execution)
}
#[derive(Clone, Copy)]
enum Kind {
Bottleneck,
W1,
W2,
}
fn distance_with(
first: &PersistenceDiagram,
second: &PersistenceDiagram,
dimension: usize,
kind: Kind,
execution: &Execution<'_>,
) -> Result<f64> {
if execution.is_unlimited() {
distance(first, second, dimension, kind, &mut WorkBudget::unlimited())
} else {
distance(
first,
second,
dimension,
kind,
&mut WorkBudget::new(execution)?,
)
}
}
fn distance_results_with<L, R>(
first: &L,
second: &R,
dimension: usize,
kind: Kind,
execution: &Execution<'_>,
) -> Result<f64>
where
L: AsRef<PersistenceData> + ?Sized,
R: AsRef<PersistenceData> + ?Sized,
{
if execution.is_unlimited() {
distance_results(
first.as_ref(),
second.as_ref(),
dimension,
kind,
&mut WorkBudget::unlimited(),
)
} else {
let mut budget = WorkBudget::new(execution)?;
distance_results(
first.as_ref(),
second.as_ref(),
dimension,
kind,
&mut budget,
)
}
}
struct Points {
finite: Vec<[f64; 2]>,
essential: Vec<f64>,
}
fn points<const CONTROLLED: bool>(
diagram: &PersistenceDiagram,
dimension: usize,
budget: &mut WorkBudget<'_, CONTROLLED>,
) -> Result<Points> {
budget.step()?;
let view = diagram.dimension(dimension)?;
if let Coverage::Through(through) = diagram.coverage() {
return Err(Error::IncompleteDiagram { through });
}
let mut finite = Vec::new();
let mut essential = Vec::new();
for interval in view.iter() {
budget.step()?;
match interval.end() {
IntervalEnd::Finite(death) => {
finite.try_reserve(1).map_err(|_| Error::AllocationFailed {
context: "finite distance points",
})?;
finite.push([interval.birth(), death]);
}
IntervalEnd::Essential => {
essential
.try_reserve(1)
.map_err(|_| Error::AllocationFailed {
context: "essential distance points",
})?;
essential.push(interval.birth());
}
IntervalEnd::RightCensored { through } => {
return Err(Error::IncompleteDiagram { through });
}
}
}
Ok(Points { finite, essential })
}
fn distance<const CONTROLLED: bool>(
first: &PersistenceDiagram,
second: &PersistenceDiagram,
dimension: usize,
kind: Kind,
budget: &mut WorkBudget<'_, CONTROLLED>,
) -> Result<f64> {
let first = points(first, dimension, budget)?;
let second = points(second, dimension, budget)?;
budget.check()?;
if first.essential.len() != second.essential.len() {
return Ok(f64::INFINITY);
}
let finite = match kind {
Kind::Bottleneck => bottleneck::distance(&first.finite, &second.finite, budget)?,
Kind::W1 => wasserstein::distance(
&first.finite,
&second.finite,
wasserstein::Metric::W1,
budget,
)?,
Kind::W2 => wasserstein::distance(
&first.finite,
&second.finite,
wasserstein::Metric::W2,
budget,
)?,
};
let mut value = finite;
let mut compensation = 0.0;
for (left, right) in first
.essential
.chunks(256)
.zip(second.essential.chunks(256))
{
budget.step_by(left.len())?;
for (&left, &right) in left.iter().zip(right) {
let cost = (left - right).abs();
if !cost.is_finite() {
return Err(Error::NumericalFailure {
context: "essential point distance",
});
}
value = match kind {
Kind::Bottleneck => value.max(cost),
Kind::W1 => {
let corrected = cost - compensation;
let sum = value + corrected;
compensation = (sum - value) - corrected;
sum
}
Kind::W2 => value.hypot(cost),
};
}
}
budget.check()?;
if !value.is_finite() {
return Err(Error::NumericalFailure {
context: "diagram distance accumulation",
});
}
Ok(if value == 0.0 { 0.0 } else { value })
}
fn distance_results<const CONTROLLED: bool>(
first: &PersistenceData,
second: &PersistenceData,
dimension: usize,
kind: Kind,
budget: &mut WorkBudget<'_, CONTROLLED>,
) -> Result<f64> {
budget.step()?;
check_context(first, second)?;
distance(first.diagram(), second.diagram(), dimension, kind, budget)
}
fn check_context(first: &PersistenceData, second: &PersistenceData) -> Result<()> {
if first.context().characteristic() != second.context().characteristic() {
return Err(Error::IncompatibleDiagramContext {
reason: "coefficient field characteristics differ",
});
}
use crate::filtration::FiltrationScale;
if !matches!(
(
first.context().filtration().scale(),
second.context().filtration().scale(),
),
(FiltrationScale::EdgeLength, FiltrationScale::EdgeLength)
) {
return Err(Error::IncompatibleDiagramContext {
reason: "diagram distance requires declared edge-length parameter conventions",
});
}
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
use std::fmt::Debug;
use std::sync::atomic::{AtomicBool, Ordering};
pub(super) fn check_control<T: PartialEq + Debug>(
mut run: impl FnMut(&mut WorkBudget<'_>) -> Result<T>,
) {
let mut counted = WorkBudget::new(&Execution::default().max_work(u64::MAX)).unwrap();
let expected = run(&mut counted).unwrap();
let work = counted.used();
assert!(work > 1);
for limit in [0, work / 4, work / 2, work - 1, work, work + 1] {
let mut budget = WorkBudget::new(&Execution::default().max_work(limit)).unwrap();
let result = run(&mut budget);
if limit < work {
assert_eq!(result, Err(Error::WorkLimitExceeded { limit }));
} else {
assert_eq!(result.unwrap(), expected);
}
assert_eq!(
run(&mut WorkBudget::new(&Execution::default()).unwrap()).unwrap(),
expected
);
}
for at in [work / 4, work / 2] {
let flag = AtomicBool::new(false);
let execution = Execution::new(Some(u64::MAX), Some(&flag));
let mut budget = WorkBudget::new(&execution).unwrap();
budget.cancel_at_work(at);
assert_eq!(run(&mut budget), Err(Error::Cancelled));
assert!(budget.used() >= at);
assert!(flag.load(Ordering::Relaxed));
assert_eq!(
run(&mut WorkBudget::new(&Execution::default()).unwrap()).unwrap(),
expected
);
}
}
#[test]
fn extraction_and_matching_share_the_operation_budget() {
let make = |offset| {
PersistenceDiagram::new(
0,
Coverage::Complete,
vec![
crate::diagram::PersistenceInterval::new(
0,
offset,
IntervalEnd::Finite(offset + 3.),
)
.unwrap(),
crate::diagram::PersistenceInterval::new(
0,
offset + 1.,
IntervalEnd::Finite(offset + 4.),
)
.unwrap(),
],
)
.unwrap()
};
let a = make(0.);
let b = make(0.25);
for kind in [Kind::Bottleneck, Kind::W1, Kind::W2] {
let mut preparation =
WorkBudget::new(&Execution::default().max_work(u64::MAX)).unwrap();
let left = points(&a, 0, &mut preparation).unwrap();
let right = points(&b, 0, &mut preparation).unwrap();
let mut kernel = WorkBudget::new(&Execution::default().max_work(u64::MAX)).unwrap();
match kind {
Kind::Bottleneck => bottleneck::distance(&left.finite, &right.finite, &mut kernel),
Kind::W1 => wasserstein::distance(
&left.finite,
&right.finite,
wasserstein::Metric::W1,
&mut kernel,
),
Kind::W2 => wasserstein::distance(
&left.finite,
&right.finite,
wasserstein::Metric::W2,
&mut kernel,
),
}
.unwrap();
let mut whole = WorkBudget::new(&Execution::default().max_work(u64::MAX)).unwrap();
distance(&a, &b, 0, kind, &mut whole).unwrap();
assert_eq!(whole.used(), preparation.used() + kernel.used());
let limit = preparation.used().max(kernel.used());
let mut limited = WorkBudget::new(&Execution::default().max_work(limit)).unwrap();
assert_eq!(
distance(&a, &b, 0, kind, &mut limited),
Err(Error::WorkLimitExceeded { limit })
);
}
}
}