PATHPACK.jl computes shortest paths, widest paths, reachability and their relatives between all pairs of vertices of a sparse graph, as one sparse factorization. One call, any semiring, on multithreaded CPUs and on one GPU or many.
The logo is a graph: 35,483 points. Click anywhere to send a distance wave from there: one Dijkstra in your browser. PATHPACK.jl computes all 1.26 billion pairs in 44 ms on one NVIDIA B200.
0.14 sall 15.9 billion distances of the US road network, on one GPU
760×faster than Fast-APSP on that network; 130× faster than cuGraph
70×faster than igraph for the closeness of every street in Paris
8 GPUsfor 190 billion distances in 0.39 s; one GPU or many, one call
Try it
Distance to everywhere, at once.
Move across Paris. Your browser recomputes one source's distances on every move. PATHPACK.jl answers the whole question, the distance from every junction to every other one, in one call.
PATHPACK.jl's factorization, queried in your browser: ms
The star of a matrix depends on the semiring it is computed in. Switch the semiring and the same landscape answers a different question: the cheapest route, the worst barrier on the way, or where a wandering animal spends its time.
mstar(MinPlus(), land)
What is the cheapest route?
From the Ocala National Forest, recomputed live in your browser: ms. Click anywhere on the map to move the source.
nearfar
98 msfor all 4.5 billion pairs of cells on one NVIDIA B200
Land cover: NLCD 2021 (USGS, public domain), 600 m cells; illustrative resistances for a forest mammal.
Built for real workloads
Faster inside the tools you already use.
Many methods need the distance between every pair of points. PATHPACK.jl computes it directly, and measured head to head, same answers, it is faster than the call each field uses today.
Neuroscience
Brain maps on the folded cortex
Spatial null models compare brain maps through the distance along the cortex between every pair of its points.
2,000×faster than BrainSMASH's distance step: 1.6 hours to 2.6 seconds
MinPlus
Machine learning
Manifold learning
Isomap unrolls data by the shortest paths of its nearest-neighbour graph: every pair of points.
105×faster than scikit-learn's Isomap shortest-path step
MinPlus
Graph neural networks
Exact diffusion
Personalized PageRank diffusion, as PyTorch Geometric's GDC computes it, is a sum over every walk.
119×faster than PyTorch Geometric's exact diffusion on a 47k-node mesh; 23× on PubMed
PlusProd
Urban planning
How central is every street?
Closeness: each street's mean walking distance to all the others, from all 140 million distances of Paris.
70×faster than igraph; 3.4× faster than graph-tool on the same 16 cores
MinPlus
Ecology
Landscape connectivity
Least-cost distances between every pair of habitat cells, and where a wandering animal goes.
15×faster than NetworKit on the same 16 cores, every cell to every cell
MinPlus · MinMax · PlusProd
Geography
River networks
Every pair of points on the Amazon river system, by boat, from OpenStreetMap waterways.
9.5 msfor all 12,785 junctions, every pair, on one GPU
MinPlus
Any graph
Atoms, scans, surfaces.
Proteins through their atomic contacts, surfaces through their meshes. Click the bunny to measure from anywhere on it; below, drag to turn an object and double-click to move the source of its bands.
mstar(MinPlus(), surface)
Click the bunny.
Distance along the surface from where you click to every other point, with moving contours. Drag to turn it. PATHPACK.jl's factorization of the mesh's 8,146-vertex graph, queried in your browser: … ms.
55.6 msfor every pair of the full 34,834-vertex scan on one NVIDIA B200, 2× faster than ROME and 31× faster than cuGraph
Stanford Bunny, Stanford 3D Scanning Repository. Distances along mesh edges, which run about 7% longer than exact surface distances.
Coronavirus spike21,539 atoms, contacts within 4.5 Åall pairs: 48 ms on one GPUPDB 6VYBFolded human cortex163,842 verticesall pairs: 0.90 s on one GPUfsaverage (FreeSurfer, via neuromaps)Stanford dragon436,846 verticesall pairs: 0.70 s on 8 GPUsStanford 3D Scanning RepositoryVirus capsid, 60 copies85,620 atomsall pairs: 296 ms on one GPUPDB 2BUKSpace Shuttle71,279 verticesall pairs: 114 ms on one GPUSmithsonian Open Access (CC0)Palm tree25,115 verticesall pairs: 31 ms on one GPUQuaternius (CC0)
Measured
Faster than what you use now.
On one GPU against the GPU state of the art, and on the same CPU cores against the libraries people use.
All 15.9 billion distances of the US road network one NVIDIA B200 each
PATHPACK.jl139 ms
ROME750 ms5.4× slower
cuGraph18.1 s130× slower
Fast-APSP106 s760× slower
Closeness of every street in Paris (11,840 junctions) one 32-core AMD EPYC node; igraph and NetworkX single-threaded
PATHPACK.jl282 ms
graph-tool952 ms3.4× slower
NetworKit2.49 s8.8× slower
igraph19.9 s70× slower
NetworkX290 s1026× slower
Isomap on 10,000 points: the shortest-path step one 32-core AMD EPYC node
PATHPACK.jl206 ms
NetworKit1.27 s6.2× slower
SciPy, 16 processes1.68 s8.1× slower
scikit-learn21.8 s106× slower
Exact personalized PageRank (GDC) on a 47k-node mesh 16 CPU cores, float64
PATHPACK.jl4.58 s
PyTorch dense inverse545 s119× slower
Every pair of a 32k-vertex cortex one 32-core AMD EPYC node
PATHPACK.jl2.64 s
NetworKit17.2 s6.5× slower
neuromaps, 16 workers24.1 s9.1× slower
Wall-clock times from the graph in memory to the full answer in memory, the same answers checked between tools. Scripts and raw measurements are public.
Get started
Two lines.
using PATHPACK
using PATHPACK.CPU: MinPlus, MaxMin, mstar
D = mstar(MinPlus(), A) # shortest paths between all pairs
W = mstar(MaxMin(), A) # widest paths, same call
Any semiring
Shortest, widest, bottleneck, most reliable, reachability, sums over all walks: one solver.
Multithreaded CPUs
One sparse factorization, then independent rows: every core busy, no write conflicts.
One GPU or many
The CPU factorizes the small parts, the GPU the large ones; the rows split over every GPU you have.
Queries, fast
Factorize once, then answer single-source and single-target queries with two triangular solves.
