Metadata-Version: 2.4
Name: vineyards
Version: 1.0.2
Summary: Vineyards over changing triangulations: exact vine tracking for moving 2D and 3D point sets through Delaunay flips (frame-bound and event-driven).
Author-email: Shawn Ray <shawnray5699@gmail.com>
License-Expression: MIT
Project-URL: Homepage, https://github.com/codingwithshawnyt/vineyards
Project-URL: Repository, https://github.com/codingwithshawnyt/vineyards
Project-URL: Issues, https://github.com/codingwithshawnyt/vineyards/issues
Project-URL: Changelog, https://github.com/codingwithshawnyt/vineyards/blob/main/CHANGELOG.md
Keywords: topological-data-analysis,persistent-homology,vineyards,Delaunay,kinetic-data-structures,computational-topology
Classifier: Development Status :: 5 - Production/Stable
Classifier: Intended Audience :: Science/Research
Classifier: Operating System :: MacOS
Classifier: Operating System :: Microsoft :: Windows
Classifier: Operating System :: POSIX :: Linux
Classifier: Typing :: Typed
Classifier: Programming Language :: C++
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Topic :: Scientific/Engineering :: Visualization
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.24
Requires-Dist: gudhi>=3.6
Provides-Extra: test
Requires-Dist: pytest>=7.0; extra == "test"
Requires-Dist: matplotlib>=3.7; extra == "test"
Requires-Dist: pillow>=9.0; extra == "test"
Requires-Dist: pybind11>=2.10; extra == "test"
Requires-Dist: setuptools>=61.0; extra == "test"
Provides-Extra: dionysus
Requires-Dist: dionysus>=2.2; extra == "dionysus"
Provides-Extra: plot
Requires-Dist: matplotlib>=3.7; extra == "plot"
Requires-Dist: pillow>=9.0; extra == "plot"
Provides-Extra: viz
Requires-Dist: matplotlib>=3.7; extra == "viz"
Requires-Dist: pillow>=9.0; extra == "viz"
Requires-Dist: pyvista>=0.44; extra == "viz"
Provides-Extra: docs
Requires-Dist: sphinx>=7.0; extra == "docs"
Requires-Dist: sphinx-rtd-theme>=2.0; extra == "docs"
Dynamic: license-file

# Vineyards over changing triangulations

A vineyard (Cohen-Steiner, Edelsbrunner, Morozov, SoCG 2006) is the 1-parameter
family of persistence diagrams of a changing filtration: each diagram point
traces a vine through time. CEM06 updates the decomposition `D = R·U` in linear
time per transposition when the complex is fixed and only filtration values
move. This library closes the remaining case: moving 2D/3D point sets whose
Delaunay/alpha complex changes by flips. Flips are handled by simplex
delete/insert on the CEM06 transposition kernel, and vine identity is carried
through those updates from the maintained pairing (no diagram-point matching).

Two engines share that handoff. `moving_vineyard` is frame-bound (sample motion,
diff consecutive complexes). `KineticVineyard2D` / `KineticVineyard3D` are
event-driven: linear trajectories, flips and alpha-value crossings at exact
algebraic times. For hundreds to thousands of points, `track_features` matches
prominent GUDHI diagram points across frames. Weighted (regular/Laguerre) alpha
accepts `weights=` (squared radii); use `assert_no_hidden` when a point can drop
out of the regular triangulation.

![vineyard figure](https://raw.githubusercontent.com/codingwithshawnyt/vineyards/main/examples/vineyard.png)

## Install

From PyPI (recommended):

```bash
pip install vineyards
```

That pulls `numpy` and `gudhi`. A C++17 compiler is required to build the sparse
GF(2) kernel at install time. For the optional GMP exact-arithmetic kernel:

```bash
# Debian/Ubuntu
sudo apt install build-essential libgmp-dev python3-dev

# macOS (Homebrew)
brew install gmp
```

From a clone (development):

```bash
python3 -m venv .venv
source .venv/bin/activate          # Windows: .venv\Scripts\activate
pip install -U pip setuptools wheel pybind11
pip install -e '.[test]'
python setup.py build_ext --inplace   # _sparse; with GMP also _exact_poly, _kinetic_2d, _kinetic_3d
pytest -q -m "not slow"
```

Extras: `pip install 'vineyards[plot]'` (matplotlib) or `'vineyards[viz]'`
(matplotlib + pyvista). Plotting imports those only when called. Dionysus
cross-checks: `pip install 'vineyards[dionysus]'`. Documentation:
`pip install 'vineyards[docs]'` then `cd docs && make html` (also built on
GitHub Pages / Read the Docs). Override the GMP prefix with `GMP_PREFIX` if
needed (Homebrew defaults to `/opt/homebrew` or `/usr/local`).

Environment toggles:

| Variable | Effect |
| --- | --- |
| `VINEYARDS_BACKEND=dense` | Force dense numpy R=DU (default: sparse C++ when built) |
| `VINEYARDS_BACKEND=sparse` | Require sparse C++ (error if extension missing) |
| `VINEYARDS_KINETIC_CPP=0` | Force pure-Python kinetic Delaunay (default: C++ when built) |

## Quickstart

Frame-bound vineyard on a moving point set:

```python
import numpy as np
from vineyards import (
    PersistenceState, gudhi_alpha_filtration,
    moving_vineyard, compute_vineyard, plot_vineyard,
)

points = np.random.default_rng(0).random((20, 2))
state = PersistenceState.from_simplex_tree(gudhi_alpha_filtration(points))
diagram = state.diagram()  # rows (dim, birth, death)

target = {sigma: 2.0 * v for sigma, v in state.filtration}
vineyard, events = compute_vineyard(state, target, num_samples=50)

frames = [points + 0.02 * k for k in range(10)]
vineyard, events = moving_vineyard(frames)
plot_vineyard(vineyard, filename="vineyard.png")
```

Event-driven (kinetic) vineyard:

```python
from fractions import Fraction
import numpy as np
from vineyards import LinearTrajectory, KineticVineyard2D  # or KineticVineyard3D

pts = np.random.default_rng(0).random((10, 2))
vel = 0.3 * np.random.default_rng(1).standard_normal((10, 2))
traj = LinearTrajectory(pos0=pts, vel=vel)
kv = KineticVineyard2D(traj, horizon=Fraction(1, 4))
dgm = kv.diagram_at(Fraction(1, 6))
kv.record(Fraction(1, 4))
assert kv.verify_identity()
vineyard = kv.vineyard()
```

Lower-star filtrations on a fixed complex use
`lower_star_filtration(simplices, vertex_values)`. The default R=DU backend is
the sparse C++ kernel when built (`CppSparseBackend`); force dense with
`VINEYARDS_BACKEND=dense` or `backend_cls=DenseBackend`.

## Positioning

[Dionysus 2](https://www.mrzv.org/software/dionysus2/) (≥ 2.2) implements CEM06
vineyards on a fixed complex; Dionysus 1 is the earlier public vineyards code.
[GUDHI](https://gudhi.inria.fr/) supplies alpha/Delaunay geometry and the
independent diagram oracle used throughout this repository. Fixed-complex
homotopies are checked against Dionysus when installed
(`tests/test_dionysus_comparison.py`); changing triangulations are outside
Dionysus and are the scope of `moving_vineyard` and the kinetic engines.

## Validation

Claims below name the tests that assert them (run with `pytest`):

| Claim | Tests |
| --- | --- |
| Diagrams match GUDHI after retriangulation / moving frames | `tests/test_retriangulation.py`, `tests/test_moving_vineyard.py`, `tests/test_3d.py` |
| Algebraic invariants (`D = R·U`, reduced `R`, unitriangular `U`) | `PersistenceState.verify` exercised across the suite (e.g. `tests/test_persistence.py`, `tests/test_local_ops.py`) |
| Vine identity vs reduced pairing | `tests/test_vineyard.py`, `tests/test_moving_vineyard.py` (`test_vine_identity_through_switches`) |
| Kinetic Delaunay vs GUDHI (2D / 3D) | `tests/test_kinetic_delaunay.py`, `tests/test_kinetic_delaunay_3d.py` |
| Kinetic filtration order vs GUDHI | `tests/test_kinetic_filtration.py`, `tests/test_kinetic_filtration_3d.py`, `tests/test_kinetic_filtration_dynamic.py` |
| Kinetic vineyard diagrams + vine identity vs GUDHI | `tests/test_kinetic_vineyard.py`, `tests/test_kinetic_vineyard_3d.py` |
| Dense vs sparse backend (`R`/`U`/`low` and diagrams) | `tests/test_backend_equiv.py` |
| Python vs C++ exact poly / Sturm | `tests/test_cpp_exact_poly.py` |
| SoS signs vs shrinking-ε and raw determinants | `tests/test_sos.py` |
| Weighted alpha vs weighted GUDHI | `tests/test_3d.py` (weighted cases) |
| Weighted flip continuity (bracketing) | `tests/test_3d.py::test_weighted_flip_continuity_lemma` |
| Multi-flip-at-one-τ kinetic vineyard | `tests/test_kinetic_vineyard.py::test_kinetic_vineyard_through_coincident_flip_cluster` |
| Frame-bound vs kinetic cancellation | `tests/test_frame_vs_kinetic.py` |
| Sparse bubble insert/delete vs dense | `tests/test_backend_equiv.py::test_sparse_bubble_path_matches_dense` |

## Scope and limitations

- Frame-bound engine: exact on the piecewise-linear interpolation of the
  samples; events that cancel inside one frame interval are invisible (the
  kinetic engine is the remedy; see `tests/test_frame_vs_kinetic.py`).
- Kinetic engine: exact event times, 2D and 3D (interior flips and hull
  changes via vertex-at-infinity). With GMP, `run()` uses the C++ kernels
  (`vineyards._kinetic_2d` / `vineyards._kinetic_3d`) with integer-coefficient
  certificates (scale-cleared trajectories), bit-exact on flip sequences
  (`tests/test_kinetic_cpp_2d.py`, `tests/test_kinetic_cpp_3d.py`); set
  `VINEYARDS_KINETIC_CPP=0` for pure Python. The C++ event queue uses tight
  root isolation and float-first extract-min (exact AlgT only on near-ties).
  Exact arithmetic still favors tens-low hundreds of points for long horizons;
  use `track_features` or frame-bound at scale.
- Degeneracies: geometric predicates use Edelsbrunner-Mücke Simulation of
  Simplicity; coincident flip certificates (interior InCircle/InSphere and
  hull/spoke orientation vs infinity) are resolved by SoS on time. Hull
  legality is the geometric supporting-line / extreme-vertex test (raw
  orientation so collinear hull points stay on the line). Several flips at
  one algebraic time are batched in the kinetic vineyard. A residual that
  local flips cannot order is finished by an oracle snap: GUDHI on
  float-rounded positions proposes the Delaunay complex, exact local-Delaunay
  predicates verify it, and a ``recover`` flip records the rem/add handoff.
  Only a failed proposal/verification raises at vineyard construction.
  Organic multi-cospheric residuals that force the snap are
  measure-zero and are not constructed in CI; the path is tested by
  injecting a recover flip and checking GUDHI diagrams + vine identity
  across the handoff.
- Weighted alpha: non-hiding is required (`assert_no_hidden`); the weighted
  flip-continuity handoff is confirmed numerically against weighted GUDHI
  in `tests/test_3d.py`.
- Geometry for frame-bound alpha values is GUDHI's; the kinetic path has its
  own exact predicates. **Default R=DU backend is sparse C++** when
  `vineyards._sparse` is built (`default_backend_cls()` /
  `CppSparseBackend`); dense numpy remains the bit-exact reference oracle
  (`VINEYARDS_BACKEND=dense` or `backend_cls=DenseBackend`). Install builds
  the sparse kernel when a C++17 toolchain is available. GMP enables the
  exact-poly and kinetic-2D/3D kernels (shared arithmetic in
  `cpp/kinetic_arith.hpp`; binary float-key event heaps; certificate poly
  caches; optional if GMP headers are missing; CI on Linux asserts all four
  modules import). Type stubs (`.pyi`) ship for the C extensions. Docs:
  `docs/` (Sphinx; GitHub Pages + Read the Docs configs). Releases publish
  **sdists and platform wheels** via cibuildwheel.
- CI: Linux (Ubuntu) is the primary surface. Windows builds the sparse kernel
  and runs core tests (GMP exact-poly / kinetic-2D/3D are skipped when GMP is
  absent).

## Measured sparse speedups

From `python examples/benchmark_sparse.py` on this machine after
`python setup.py build_ext --inplace` (Apple M4 Max, macOS 15, arm64, Python
3.13). Columns are dense vs C++ sparse wall time and the ratio dense/sparse;
`nnzR/m^2` and `nnzU/m^2` are filled fractions of the reduced matrices.

| n | m | nnzR/m^2 | nnzU/m^2 | reduce | update | local |
|----:|----:|---------:|---------:|-------:|-------:|------:|
| 40 | 217 | 0.006 | 0.012 | 7.1x | 123.1x | 16.4x |
| 70 | 393 | 0.004 | 0.007 | 8.0x | 200.6x | 15.6x |
| 100 | 575 | 0.003 | 0.005 | 10.3x | 211.9x | 19.0x |

Re-run the script on your hardware; numbers vary with CPU and size.

## Knee rates

Pairing-switch share of value-update transpositions under random-walk motion
(`update%` in the script). From `python examples/counter_report.py` on the same
machine (Apple M4 Max, macOS 15, arm64):

| n | m | knee/switch % | crossings/flip | changed/flip | flip frames |
|----:|-----:|------:|-------:|------:|----:|
| 8 | 33 | 9.42% | 19.8 | 9.6 | 82 |
| 30 | 159 | 3.16% | 549.4 | 91.0 | 45 |
| 100 | 572 | 1.21% | 5747.7 | 540.2 | 16 |
| 300 | 1767 | 0.52% | 27006.2 | 2181.6 | 5 |

## References

- D. Cohen-Steiner, H. Edelsbrunner, D. Morozov. Vines and Vineyards by
  Updating Persistence in Linear Time. In Proc. 22nd Annu. Symp. Comput.
  Geom. (SoCG), pp. 119-126, 2006.
- H. Edelsbrunner, D. Letscher, A. Zomorodian. Topological Persistence and
  Simplification. Discrete Comput. Geom. 28:511-533, 2002.
- H. Edelsbrunner, J. Harer. Computational Topology: An Introduction. AMS,
  2010.
- H. Edelsbrunner, E. P. Mücke. Simulation of Simplicity: A Technique to Cope
  with Degenerate Cases in Geometric Algorithms. ACM Trans. Graph. 9(1):66-104,
  1990.
- The GUDHI Project. GUDHI User and Reference Manual.
  https://gudhi.inria.fr/doc/latest/
- D. Morozov. Dionysus 2. https://www.mrzv.org/software/dionysus2/

## Citation

```bibtex
@software{ray_vineyards,
  author = {Ray, Shawn},
  title  = {Vineyards over changing triangulations},
  url    = {https://github.com/codingwithshawnyt/vineyards},
  year   = {2026}
}
```

See also `CITATION.cff`.

Research code from a summer internship at ISTA (group of Herbert Edelsbrunner),
2026.
