Metadata-Version: 2.4
Name: vineyards
Version: 1.0.3
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: Documentation, https://codingwithshawnyt.github.io/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: pydata-sphinx-theme>=0.15; extra == "docs"
Requires-Dist: sphinx-copybutton>=0.5; extra == "docs"
Requires-Dist: sphinx-design>=0.5; extra == "docs"
Requires-Dist: myst-parser>=3.0; extra == "docs"
Dynamic: license-file

# Vineyards over changing triangulations

[![PyPI](https://img.shields.io/pypi/v/vineyards.svg)](https://pypi.org/project/vineyards/)
[![Docs](https://img.shields.io/badge/docs-GitHub%20Pages-1f6f5f)](https://codingwithshawnyt.github.io/vineyards/)
[![Python](https://img.shields.io/pypi/pyversions/vineyards.svg)](https://pypi.org/project/vineyards/)

**Documentation:** https://codingwithshawnyt.github.io/vineyards/

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
```

**Binary wheels** are published for Linux, macOS, and Windows. When a wheel
matches your platform you do not need a local C++ toolchain. Runtime deps are
`numpy` and `gudhi`.

Optional extras: `vineyards[plot]` (matplotlib), `vineyards[viz]` (matplotlib +
pyvista), `vineyards[dionysus]`, `vineyards[docs]`, `vineyards[test]`.

If pip builds from the **sdist**, a C++17 compiler is required for the sparse
GF(2) kernel. GMP enables the exact-poly and kinetic C++ kernels:

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

# macOS (Homebrew)
brew install gmp
```

Development install:

```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
pytest -q -m "not slow"
```

Override the GMP prefix with `GMP_PREFIX` if needed. 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 moving_vineyard, plot_vineyard

frames = [np.random.default_rng(k).random((20, 2)) for k in range(12)]
# or: stacked = np.stack(frames, axis=0)  # shape (T, n, d)
vineyard, events = moving_vineyard(frames)
plot_vineyard(vineyard, filename="vineyard.png")
```

Event-driven (kinetic) vineyard — one shot:

```python
from fractions import Fraction
import numpy as np
from vineyards import LinearTrajectory, run_kinetic_vineyard

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)
vineyard = run_kinetic_vineyard(traj, Fraction(1, 4), num_samples=17)
```

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`.

## Docs map

| Want… | Go to… |
| --- | --- |
| Copy-paste recipes | [Recipes](https://codingwithshawnyt.github.io/vineyards/user_guide/recipes.html) |
| Install / extras / env toggles | [Installation](https://codingwithshawnyt.github.io/vineyards/user_guide/installation.html) |
| Which engine to use | [Choosing an engine](https://codingwithshawnyt.github.io/vineyards/user_guide/choosing_an_engine.html) |
| Worked examples with figures | [Tutorials](https://codingwithshawnyt.github.io/vineyards/tutorials/index.html) |
| Full public API | [API reference](https://codingwithshawnyt.github.io/vineyards/api/index.html) |
| Scope & limitations | [Limitations](https://codingwithshawnyt.github.io/vineyards/user_guide/limitations.html) |
| Release notes | [Changelog](https://codingwithshawnyt.github.io/vineyards/changelog.html) |

## 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). Exact arithmetic still favors tens–low
  hundreds of points for long horizons; use `track_features` or frame-bound at
  scale. With GMP, `run()` uses the C++ kernels by default
  (`VINEYARDS_KINETIC_CPP=0` for pure Python). A residual 3D multi-cospheric
  instant that local flips cannot order is finished by an oracle snap
  (propose / exact-verify / restore); only a failed snap raises.
- Weighted alpha: non-hiding is required (`assert_no_hidden`).
- Default R=DU backend is sparse C++ when built; dense numpy remains the
  bit-exact reference oracle.
- CI: Linux is primary. Windows builds sparse and runs core tests; GMP kinetic
  kernels are skipped when GMP is absent.

See the [full limitations page](https://codingwithshawnyt.github.io/vineyards/user_guide/limitations.html)
in the docs for more detail.

## 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.
