Metadata-Version: 2.4
Name: mwatershed
Version: 0.6.0
Classifier: Development Status :: 2 - Pre-Alpha
Classifier: Intended Audience :: Developers
Classifier: License :: OSI Approved :: MIT License
Classifier: Natural Language :: English
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Requires-Dist: numpy>=1.18.0
Requires-Dist: bump-my-version>=1.1.2 ; extra == 'dev'
Requires-Dist: maturin>=1.9 ; extra == 'dev'
Requires-Dist: pytest>=8.3.3 ; extra == 'dev'
Requires-Dist: ruff>=0.6.9 ; extra == 'dev'
Requires-Dist: ipykernel>=6.29.5 ; extra == 'docs'
Requires-Dist: nbsphinx>=0.9.6 ; extra == 'docs'
Requires-Dist: sphinx>=8.2.3 ; extra == 'docs'
Requires-Dist: sphinx-autodoc-typehints>=2.0 ; extra == 'docs'
Requires-Dist: sphinx-material>=0.0.36 ; extra == 'docs'
Requires-Dist: sphinx-rtd-theme>=2.0 ; extra == 'docs'
Requires-Dist: myst-parser>=4.0 ; extra == 'docs'
Requires-Dist: jupytext>=1.16.7 ; extra == 'docs'
Provides-Extra: dev
Provides-Extra: docs
License-File: LICENSE
License-File: AUTHORS.rst
Summary: A rusty mutex watershed
Author-email: William Patton <wllmpttn24@gmail.com>
Requires-Python: >=3.11
Description-Content-Type: text/markdown; charset=UTF-8; variant=GFM

# mwatershed
[![pytest](https://github.com/pattonw/mwatershed/actions/workflows/pytest.yaml/badge.svg)](https://github.com/pattonw/mwatershed/actions/workflows/pytest.yaml)
[![ruff](https://github.com/pattonw/mwatershed/actions/workflows/ruff.yaml/badge.svg)](https://github.com/pattonw/mwatershed/actions/workflows/ruff.yaml)
[![cargo](https://github.com/pattonw/mwatershed/actions/workflows/cargo.yaml/badge.svg)](https://github.com/pattonw/mwatershed/actions/workflows/cargo.yaml)

[![pypi](https://img.shields.io/pypi/pyversions/mwatershed.svg)](https://pypi.python.org/pypi/mwatershed)


## A rusty mutex watershed

See docs [here](https://pattonw.github.io/mwatershed)

### Installation

`pip install mwatershed`

### Features

* A mutex watershed implementation for affinities
* Should handle up to 6 dimensional arrays of fragments (7 dimensions if you include offsets in affinities) but only tested on 2 and 3 dimensions

### Usage

```python
components = mwatershed.agglom(
    affinities: NDArray[np.float64],
    offsets: list[list[int]],
    seeds: NDArray[np.uint64],
    edges: Optional[list[tuple[usize, usize, f64]]] = None,
)
```
where:
* `affinities` is a `k+1` dimensional array of non `nan` affinities with leading dimension having size `n`
* `offsets` is a list of length `n` of offset tuples of `k` integers
* `seeds` is a `k` dimensional array of fragment ids. Note `seeds.shape` must be equal to `affinities.shape[1:]`. Any entry not equal to 0 is guaranteed to stay that way, any entry equal to zero has no priors.
* `edges` is a list of `(u, v, aff)` tuples to insert arbitrary extra affinities between fragment ids

### Graphs as arrays

For a graph that already lives in numpy arrays, `cluster_arrays` runs the mutex
watershed without building a Python object per edge:

```python
nodes, labels = mwatershed.cluster_arrays(
    u, v, weights,            # one edge per position; positive attracts, else repels
    nodes=None,               # sorted unique node ids; default: those in the edges
    sorted=False,             # set if the edges are already in processing order
    prefix=None,              # (u, v, positive) hard decisions processed first
    linkage="abs_max",        # or any GASP linkage below
    cannot_link=True,
)
```

Node ids are arbitrary `uint64`. Edges are processed by descending `|weight|`
with ties in input order, after the `prefix` edges, which are processed in
their own order. The result is one label per entry of `nodes`: the smallest
node id in that node's cluster, so the partition equals `cluster` on the same
edges in the same order.

### Linkage criteria (GASP)

`agglom`, `cluster_edges` and `cluster_arrays` accept a `linkage` argument that selects how the
interaction between two clusters is computed from the affinities connecting
them, following the GASP framework of
[Bailoni et al. (2022)](https://arxiv.org/abs/1906.11713):

| `linkage`   | Interaction between two clusters            | Known as                     |
|-------------|---------------------------------------------|------------------------------|
| `"abs_max"` | the connecting edge with the largest magnitude (default) | Mutex watershed |
| `"sum"`     | sum of the connecting affinities            | GAEC / HCC-Sum               |
| `"mean"`    | mean of the connecting affinities           | average linkage (HC-Avg / HCC-Avg) |
| `"max"`     | largest connecting affinity                 | single linkage               |
| `"min"`     | smallest connecting affinity                | complete linkage             |

```python
components = mwatershed.agglom(affinities, offsets, linkage="mean")
```

Pairs of clusters are visited in order of decreasing interaction magnitude.
An attractive pair is merged; a repulsive pair receives a cannot-link
constraint when `cannot_link=True` (the default). Once every remaining pair is
repulsive or constrained, the constraints are lifted and any pairs that are
still attractive are merged. With `"abs_max"` the constraints never change the
result, which is exactly the mutex watershed. Seeds and the `edges` argument
always act as hard constraints regardless of the linkage.

The generic linkages use a contracted-graph priority queue and are several
times slower than the dedicated mutex watershed path; see
[`LINKAGE_REPORT.md`](LINKAGE_REPORT.md) for timings
(`cargo run --release --example benchmark_linkages`) or run
`cargo bench` for the Criterion comparison.

