I just wrote an implementation of Tarjan’s algorithm to replace the current SciPy algorithm for strongly connected components. It’s more than twice faster and uses less memory.
Is there anybody who’d like to review the code? It’s very short.
An update on this PR to scipy.sparse.csgraph.connected_components:
- the PR was reviewed positively by @rc, maintainer of SfePy: Simple Finite Elements in Python — SfePy version: 2026.1+git.b155fa83 documentation (which uses this function) and original author of the
sparse.csgraph.connected_componentsAPI:
I have just compared the previous and the proposed versions of
connected_components()on some finite element meshes - the results are correct and the computation faster. For larger meshes the speedup is even more impressive
- a new benchmark shows the following promising results on my machine:
scipy on 🎋 tarjan [?] is 📦 v1.18.0.dev0 via 🐍 via 🧚 v0.67.0
❯ pixi run bench -t sparse_csgraph.StronglyConnectedComponents --compare
...
[50.00%] · For scipy commit cd2a5476 <tarjan> (round 2/2):
[50.00%] ·· Benchmarking virtualenv-py3.14-Cython-meson-python-numpy-pybind11-pytest-pythran
[75.00%] ··· sparse_csgraph.StronglyConnectedComponents.time_strongly_connected_components ok
[75.00%] ··· ============ ============
kind
------------ ------------
random 343±0.5ms
single_scc 419±20ms
chain 10.1±0.2ms
============ ============
[75.00%] · For scipy commit be6aa872 <main> (round 2/2):
[75.00%] ·· Building for virtualenv-py3.14-Cython-meson-python-numpy-pybind11-pytest-pythran....
[75.00%] ·· Benchmarking virtualenv-py3.14-Cython-meson-python-numpy-pybind11-pytest-pythran
[100.00%] ··· sparse_csgraph.StronglyConnectedComponents.time_strongly_connected_components ok
[100.00%] ··· ============ ============
kind
------------ ------------
random 712±6ms
single_scc 786±0.9ms
chain 11.7±0.1ms
============ ============
- binary size for this module has increased from 329KB to 341KB on my machine, in virtue of switching from C to C++ as the Cython target.