Metadata-Version: 2.4
Name: kdedge
Version: 0.0.1
Summary: Edge bundling algorithms for graph visualization using kernel density estimation (KDE).
Author-email: cuzi <cuzi@openmail.cc>
License-Expression: MIT
Project-URL: homepage, https://github.com/cvzi/kdedge
Project-URL: documentation, https://kdedge.readthedocs.io/
Project-URL: repository, https://github.com/cvzi/kdedge
Project-URL: downloads, https://pypi.org/project/kdedge/
Classifier: Development Status :: 5 - Production/Stable
Classifier: Programming Language :: Python
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: Programming Language :: Python :: 3.14
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: Implementation :: CPython
Classifier: Programming Language :: Python :: Implementation :: PyPy
Classifier: Typing :: Typed
Classifier: Topic :: Scientific/Engineering :: Visualization
Classifier: Intended Audience :: Science/Research
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy~=2.0
Provides-Extra: perf
Requires-Dist: scipy~=1.15; extra == "perf"
Requires-Dist: numba~=0.65; extra == "perf"
Provides-Extra: test
Requires-Dist: pytest~=9.0; extra == "test"
Requires-Dist: tox~=4.0; extra == "test"
Requires-Dist: hypothesis~=6.0; extra == "test"
Provides-Extra: typetests
Requires-Dist: pyright>=1.1; extra == "typetests"
Requires-Dist: pytest-beartype>=0.2.0; extra == "typetests"
Requires-Dist: mypy>=1.16; extra == "typetests"
Requires-Dist: scipy_stubs>=1.15.0; extra == "typetests"
Requires-Dist: typeguard>=4.5; extra == "typetests"
Provides-Extra: coverage
Requires-Dist: coverage>=7.5.1; extra == "coverage"
Requires-Dist: codacy_coverage>=1.3.11; extra == "coverage"
Provides-Extra: ruff
Requires-Dist: ruff>=0.15; extra == "ruff"
Provides-Extra: docs
Requires-Dist: sphinx>=9; extra == "docs"
Dynamic: license-file

# KDEdge

KDEEB-style edge bundling for Python.

This package bundles graph edges into smooth polylines for visualization.
It currently supports one bundling method:

- `kdeeb`: kernel-density edge bundling

<kbd>
    <img width="1200" height="634" alt="Edge bundling of US migration" src="https://github.com/user-attachments/assets/a346db98-3367-4b52-aa69-17ed3f7ac53f" />
</kbd>


## Install

Python 3.10 or higher is required.

Install from [PyPI](https://pypi.org/project/kdedge/):

```bash
pip install kdedge
```

The core package depends only on [NumPy](https://pypi.org/project/numpy/). [SciPy](https://pypi.org/project/scipy/) and [Numba](https://numba.pydata.org/) are optional and are automatically used when installed.
To install both optional dependencies, run:

```bash
pip install kdedge[perf]
```


## Documentation

Sphinx documentation sources live in [`docs/`](docs/).

Documentation is hosted on [Read the Docs](https://kdedge.readthedocs.io/).


## How it works

The input is a set of 2D node positions and an edge list.

Each edge starts as a straight segment between its source and target node. The edges are then sampled into polylines with control points along the edge.

Each sample point contributes to a density field, a scalar field that counts the number of edges passing through it. The density field is smoothed with a kernel, for example a Gaussian blur.

The sample points are then moved toward the gradient of the density field. This means edges are pulled toward high-density regions where many edges overlap. After moving the sample points, the polylines are smoothed to reduce sharp corners.

This process is repeated for a number of iterations, the edges are resampled, the density field is recomputed, and the sample points are moved again. Over time, edges that share similar routes are pulled together into bundles.

In `kdeeb` mode, all edges share one density field, so similar routes collapse into common bundles.


## Example

```python
import numpy as np

from kdedge import bundle

nodes = np.array(
    [
        [-1.0, 0.0],
        [0.0, 1.0],
        [1.0, 0.0],
        [0.0, -1.0],
    ],
    dtype=np.float64,
)

edges = np.array(
    [
        [0, 2],
        [1, 3],
        [0, 1],
        [2, 3],
    ],
    dtype=np.int64,
)

polylines = bundle(
    nodes=nodes,
    edges=edges,
    iterations=10,
    mode="kdeeb",
)

print(len(polylines))
print(polylines[0].shape)
```

The result is a list of polylines as NumPy arrays.
Each polyline keeps the original edge endpoints and adds interior control points as needed.


## Kernel Density Estimation Implementation

This package follows the KDEEB idea from *Graph Bundling by Kernel Density Estimation* (2012) by Hurter, C., Ersoy, O. and Telea, A. The implementation is inspired by the authors' [C# demo](https://webspace.science.uu.nl/~telea001/uploads/Software/KDEEB).

However, the numerical approximations and the default parameters in this package are different, so values are not directly interchangeable and results are not comparable. This package defaults to a more Python-friendly implementation and default parameters that are efficient in NumPy/SciPy, especially for very dense graphs. A wrapper function `kdeeb()` is provided for a preset that is closer to the original KDEEB algorithm.

Key differences:

- **Density field:** by default this package builds a point-count grid and smooths the entire grid with `gaussian_filter` (`density_mode="gaussian_filter"`). The KDEEB paper describes kernel-density estimation in general, and the paper authors' C# demo uses explicit point splatting with an `11x11` radial kernel on a `300x300` accumulation grid.
- **Python-friendly:** the default `gaussian_filter` path is chosen because it is efficient to compute with SciPy for dense for dense graphs. Use `density_mode="point_splat"` for a kernel closer to the KDEEB authors' splatting idea. For sparse graphs, explicit point splatting may be more efficient. Custom kernels can be defined by passing a splatting function or by operating on the density grid (`numpy.ndarray`).
- **Gradient estimation:** this package computes `np.gradient(...)` on the full density image and bilinearly interpolates the gradient at each sample point. The authors' demo estimates a local gradient in a `15x15` window around every sample point.
- **Coordinate system and grid:** this package internally operates on a square pixel grid with `grid_size=512` by default. The authors' demo instead operates on normalized coordinates.
- **Resampling:** this package resamples each polyline by uniform arc length with spacing `sampling * grid_size` (default `0.01 * 512 = 5.12` pixels). The authors' demo uses split/remove thresholds in normalized coordinates (`splitDistance=0.005`, `removeDistance=0.0025`).
- **Smoothing:** after moving the sample points, the polylines are smoothed to achieve smooth curves. This package defaults to Laplacian smoothing with factor `smooth=0.35` and `smooth_iterations=1`. The authors' CPU demo instead applies much stronger smoothing, with 50 iterations after every bundling step, with a smoothing factor that is roughly comparable to `smooth=0.333`.
- **Scheduling:** the KDEEB paper uses a shared schedule `h_i = l^i h_max` for both bandwidth and advection. This effectively limits movement of the sample points to the bandwidth of the kernel function. The authors'C# demo instead uses fixed constants such as `KernelSize = 11` and `attractionFactor = 1.0`. The `bundle()` function in this package uses the parameters `sigma` (for Gaussian kernel) and `attract`-strength as separate controls unless they are explicitly coupled by using the same schedule parameter.


## KDEEB-style wrapper ``kdeeb()``

This function provides a preset that is closer to the original KDEEB algorithm, with the following defaults:
- a shared schedule `h_i = l^i h_max` for both density bandwidth and advection
- default `bandwidth_decay = 0.7`
- automatic `h_max` estimation from the initial straight edges
- `density_mode="point_splat"` with an [Epanechnikov](https://www.researchgate.net/figure/Examples-of-kernel-functions-a-Gaussian-b-Epanechnikov-c-Triangular-and-d_fig1_321982186) splat kernel
- moderate smoothing with `smooth=1/3` and `smooth_iterations=8` (Note: the KDEEB C# demo instead applies `50` smoothing passes)
- fixed sampling near `1%` of the graph bounding box via `sampling=0.01`

Example:

```python
from kdedge import kdeeb

polylines = kdeeb(
    nodes=nodes,
    edges=edges,
    iterations=10,
)
```

## Results

Example output images are in [`results`](https://github.com/cvzi/kdedge/tree/results).


## Development

The core API is in kdedge/algo.py, the kernel functions are in kdedge/kernels.py.

Tests can be run with [pytest](https://pytest.org/) for a specific Python version or for multiple Python versions with [tox](https://tox.wiki/):

```bash
pip install pytest
pytest

pip install tox
tox
# Optionally install more Python versions, e.g. with: pyenv install 3.11.8
```

Static type checking can be tested with [mypy](https://www.mypy-lang.org/) or [pyright](https://github.com/microsoft/pyright):
```bash
pip install pyright
pyright

pip install mypy
mypy kdedge
```

Runtime type checking can be tested with `pytest` and the [beartype](https://beartype.readthedocs.io/) or [typeguard](https://typeguard.readthedocs.io/) plugin:
```bash
pip install pytest-beartype
pytest --beartype-packages="kdedge"

pip install typeguard
pytest --typeguard-packages="kdedge"
```

Code formatting can be checked with [ruff](https://docs.astral.sh/ruff/):

```bash
pip install ruff
ruff check kdedge tests

# Autofix simple issues:
ruff check --fix kdedge tests

# Formatting a file:
ruff format kdedge/algo.py
```

### Numba and SciPy implementations

Some functions are implemented multiple times with different backends (pure NumPy, SciPy or Numba) for performance reasons.
See kdedge/impl/impl_numpy.py,  kdedge/impl/impl_scipy.py and kdedge/impl/impl_numba.py for the implementations.

The fastest implementation for each function is currently hardcoded (based on benchmarking results). A pure NumPy implementation is used if SciPy or Numba are not available.

Benchmark tests to compare some of the Numba and NumPy functions are in [benchmarks/](./benchmarks).

Run the benchmarks with:

```bash
python -m benchmarks
```

## References

- KDEEB website: [https://webspace.science.uu.nl/~telea001/InfoVis/KDEEB](https://webspace.science.uu.nl/~telea001/InfoVis/KDEEB)
- KDEEB paper: [Hurter, C., Ersoy, O. and Telea, A. (2012), *Graph Bundling by Kernel Density Estimation*, Computer Graphics Forum 31(3).](https://webspace.science.uu.nl/~telea001/uploads/PAPERS/EuroVis12/kdeeb.pdf)
- KDEEB authors' demo software: [https://webspace.science.uu.nl/~telea001/uploads/Software/KDEEB](https://webspace.science.uu.nl/~telea001/uploads/Software/KDEEB)
