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

Install

Python 3.10 or higher is required.

Install from PyPI:

pip install kdedge

The core package depends only on NumPy. SciPy and Numba are optional and are automatically used when installed. To install both optional dependencies, run:

pip install kdedge[perf]

Documentation

Sphinx documentation sources live in docs/.

Documentation is hosted on Read the Docs.

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

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.

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

from kdedge import kdeeb

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

Results

Example output images are in results.

Development

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

Tests can be run with pytest for a specific Python version or for multiple Python versions with tox:

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 or pyright:

pip install pyright
pyright

pip install mypy
mypy kdedge

Runtime type checking can be tested with pytest and the beartype or typeguard plugin:

pip install pytest-beartype
pytest --beartype-packages="kdedge"

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

Code formatting can be checked with ruff:

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

Run the benchmarks with:

python -m benchmarks

References

• KDEEB website: 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).
• KDEEB authors' demo software: https://webspace.science.uu.nl/~telea001/uploads/Software/KDEEB