cocycle 0.1.1

Topological data analysis in pure Rust
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
//! Exact matching distances between complete persistence diagrams.
//!
//! Each operation compares one explicitly computed homology dimension and keeps
//! interval multiplicity. Finite points may match other finite points or the
//! diagonal. Essential points `(birth, +infinity)` match only essential points;
//! unequal essential counts give positive infinity. Truncated coverage is an
//! error even when no interval in the requested dimension is right-censored.
//!
//! "Exact" means no algorithmic approximation, not exact real arithmetic. The
//! solvers use binary64 arithmetic. Numerical failure is an error, never a NaN or
//! a substitute infinite distance. The existing diagram types require finite
//! births and positive finite lifetimes; diagonal points and other infinite
//! endpoint categories are outside this API's input domain.
//!
//! Raw diagrams do not establish field or source compatibility. The `_results`
//! functions additionally require equal fields and declared edge-length parameter
//! conventions. Both APIs leave units and normalization to the caller; matching
//! conventions do not establish those facts. Distances between sparse
//! approximations describe the two supplied diagrams, not the unknown original
//! diagrams and not an approximation error certificate.
//!
//! # Execution controls
//!
//! Each raw and context-aware function has a `_with` variant accepting
//! [`Execution`]. Existing functions use `Execution::default()`. One fresh private
//! budget spans context/coverage validation, interval extraction, preparation,
//! candidates, all matching routes and accumulation. Counted work includes
//! intervals, candidate or graph rows, search visits and batches; repeated scans
//! count again. Counts are algorithm-dependent, not timings, bytes or a stable
//! performance score. A zero budget rejects even an empty distance operation.
//!
//! A pre-set cancellation flag is checked before validation or extraction;
//! otherwise validation and resource errors occur in execution order. Long loops
//! poll at row, visit or batch boundaries. Sorting, selection, allocations and
//! user `AsRef` callbacks cannot be interrupted internally; cancellation is
//! cooperative, without a hard latency guarantee. A resource error returns no
//! partial distance and changes neither input nor the caller's flag. Each retry
//! starts fresh. Workspace quotas and internal parallelism controls are outside
//! this API; matching routes and scratch remain private.
//!
//! ```
//! use cocycle::diagram::{Coverage, IntervalEnd, PersistenceDiagram, PersistenceInterval};
//! use cocycle::diagram_distances::{bottleneck_distance, wasserstein_2_euclidean};
//! let first = PersistenceDiagram::new(0, Coverage::Complete, vec![
//!     PersistenceInterval::new(0, 0.0, IntervalEnd::Finite(2.0))?,
//! ])?;
//! let empty = PersistenceDiagram::new(0, Coverage::Complete, vec![])?;
//! assert_eq!(bottleneck_distance(&first, &empty, 0)?, 1.0);
//! assert!((wasserstein_2_euclidean(&first, &empty, 0)? - 2.0_f64.sqrt()).abs() < 1e-14);
//! # Ok::<(), cocycle::Error>(())
//! ```

use crate::diagram::{Coverage, IntervalEnd, PersistenceData, PersistenceDiagram};
use crate::execution::{Execution, WorkBudget};
use crate::{Error, Result};

// The standalone worker opts in with --cfg cocycle_distance_bench. Neither
// counter updates nor their argument evaluation exist in ordinary crate builds.
macro_rules! record {
    ($($body:tt)*) => {
        #[cfg(any(test, cocycle_distance_bench))]
        { $($body)* }
    };
}

// Keep ablation controls out of the normal build; the second expression is the
// selected production policy. This is compile-time selection, including debug.
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;

/// Exact bottleneck distance, with pointwise L-infinity cost.
///
/// A finite point `(b, d)` has diagonal cost `(d-b)/2`. Empty finite diagrams
/// have distance zero. Essential counts must agree; otherwise returns infinity.
///
/// # Errors
/// Returns an error for uncomputed dimensions, incomplete coverage, allocation
/// failure or unrepresentable numerical work. See the module's input contract.
pub fn bottleneck_distance(
    first: &PersistenceDiagram,
    second: &PersistenceDiagram,
    dimension: usize,
) -> Result<f64> {
    bottleneck_distance_with(first, second, dimension, &Execution::default())
}

/// Bottleneck distance with cooperative work and cancellation controls.
///
/// One budget covers validation, point preparation, matching and accumulation.
/// See the module's execution contract for counted work and cancellation limits.
/// # Errors
/// Includes [`bottleneck_distance`] errors, [`Error::Cancelled`] and
/// [`Error::WorkLimitExceeded`]. No partial distance is returned.
pub fn bottleneck_distance_with(
    first: &PersistenceDiagram,
    second: &PersistenceDiagram,
    dimension: usize,
    execution: &Execution<'_>,
) -> Result<f64> {
    distance_with(first, second, dimension, Kind::Bottleneck, execution)
}

/// Exact order-one Wasserstein distance, with pointwise L-infinity cost.
///
/// Sums costs, including diagonal cost `(d-b)/2`. Empty finite diagrams have
/// distance zero. This is distinct from Wasserstein with Euclidean ground cost.
///
/// # Errors
/// Returns an error for uncomputed dimensions, incomplete coverage, allocation
/// failure or numerical overflow/underflow. Essential count mismatch is infinity.
pub fn wasserstein_1_infinity(
    first: &PersistenceDiagram,
    second: &PersistenceDiagram,
    dimension: usize,
) -> Result<f64> {
    wasserstein_1_infinity_with(first, second, dimension, &Execution::default())
}

/// W1-L-infinity distance with the execution contract of [`bottleneck_distance_with`].
/// # Errors
/// Includes [`wasserstein_1_infinity`] errors, [`Error::Cancelled`] and
/// [`Error::WorkLimitExceeded`]. No partial distance is returned.
pub fn wasserstein_1_infinity_with(
    first: &PersistenceDiagram,
    second: &PersistenceDiagram,
    dimension: usize,
    execution: &Execution<'_>,
) -> Result<f64> {
    distance_with(first, second, dimension, Kind::W1, execution)
}

/// Exact order-two Wasserstein distance, with pointwise Euclidean cost.
///
/// Minimizes the sum of squared costs and returns its square root. The diagonal
/// cost is `(d-b)/sqrt(2)`. Empty finite diagrams have distance zero.
///
/// # Errors
/// Returns an error for uncomputed dimensions, incomplete coverage, allocation
/// failure or numerical overflow/underflow. Essential count mismatch is infinity.
pub fn wasserstein_2_euclidean(
    first: &PersistenceDiagram,
    second: &PersistenceDiagram,
    dimension: usize,
) -> Result<f64> {
    wasserstein_2_euclidean_with(first, second, dimension, &Execution::default())
}

/// W2-Euclidean distance with the execution contract of [`bottleneck_distance_with`].
/// # Errors
/// Includes [`wasserstein_2_euclidean`] errors, [`Error::Cancelled`] and
/// [`Error::WorkLimitExceeded`]. No partial distance is returned.
pub fn wasserstein_2_euclidean_with(
    first: &PersistenceDiagram,
    second: &PersistenceDiagram,
    dimension: usize,
    execution: &Execution<'_>,
) -> Result<f64> {
    distance_with(first, second, dimension, Kind::W2, execution)
}

/// Bottleneck distance with additional computation-context validation.
///
/// Accepts common data and compatible wrappers through a borrow of already stored
/// [`PersistenceData`]. This adapter performs no copying or context reconstruction.
///
/// Requires equal coefficient characteristics and declared edge-length scales.
/// Unspecified scales are rejected, including two unspecified scales: equality
/// does not establish comparable units. Call the raw-diagram function after
/// establishing a common scale yourself for supplied filtrations. Even declared
/// edge lengths do not certify physical units or normalization across datasets;
/// the caller must establish them before interpreting the returned distance.
/// Original and modified sparse edge values use the same parameter convention,
/// but describe different filtrations. Their distance compares the resulting
/// diagrams and is not a distance between the original pairwise metrics.
/// Vertex counts, construction kinds and cutoff requests
/// need not agree when both diagrams have complete coverage. Approximation
/// provenance remains in the borrowed results; no original-data guarantee is
/// inferred from this scalar distance.
///
/// # Errors
/// Returns [`Error::IncompatibleDiagramContext`] for unequal fields or unsupported
/// scale conventions, in addition to errors from [`bottleneck_distance`].
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())
}

/// Context-checked bottleneck distance with one cooperative operation budget.
///
/// Borrows stored common data just like [`bottleneck_distance_results`].
/// # Errors
/// Includes [`bottleneck_distance_results`] errors, [`Error::Cancelled`] and
/// [`Error::WorkLimitExceeded`]. No partial distance is returned.
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)
}

/// W1-L-infinity distance with the context checks of [`bottleneck_distance_results`].
///
/// # Errors
/// Returns an error for incompatible fields/scales or any [`wasserstein_1_infinity`]
/// input, allocation or numerical failure.
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())
}

/// Context-checked W1 with the controls of [`bottleneck_distance_results_with`].
/// # Errors
/// Includes [`wasserstein_1_infinity_results`] errors, [`Error::Cancelled`] and
/// [`Error::WorkLimitExceeded`]. No partial distance is returned.
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)
}

/// W2-Euclidean distance with the context checks of [`bottleneck_distance_results`].
///
/// # Errors
/// Returns an error for incompatible fields/scales or any [`wasserstein_2_euclidean`]
/// input, allocation or numerical failure.
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())
}

/// Context-checked W2 with the controls of [`bottleneck_distance_results_with`].
/// # Errors
/// Includes [`wasserstein_2_euclidean_results`] errors, [`Error::Cancelled`] and
/// [`Error::WorkLimitExceeded`]. No partial distance is returned.
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 {
        // Check cancellation before invoking caller-provided conversion code.
        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 });
            }
        }
    }
    // The owning diagram sorts by dimension and then birth, so this subsequence
    // already has the monotone order required by one-dimensional matching.
    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;
    // An unspecified scale is not a shared unit, even for the same source kind.
    // Match the supported convention explicitly so future conventions require
    // a deliberate compatibility policy here.
    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};

    // Exercise an actual kernel/stage rather than stopping at the public facade.
    // Discover work dynamically; no algorithm's incidental count is frozen.
    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 })
            );
        }
    }
}