LightGraphs.jl icon indicating copy to clipboard operation
LightGraphs.jl copied to clipboard

`strongly_connected_components` and `strongly_connected_components_kosaraju` run in quadratic time.

Open saolof opened this issue 4 years ago • 0 comments

Currently, because they break in the middle of loops without saving their state, the Tarjan and Kosaraju algorithms have a worse asymptotic complexity than their recursive versions. Instead of being O(V + E), they are O(V + Sum_v of degree(v)^2 ) . This means that they are very slow for graphs where some nodes have a very large degree, like star graphs of high order, or for example the Julia or NPM dependency graphs.

This is fixed for Tarjan in #1559 . Kosaraju can be fixed in the same way by adding a stack for large nodes and reusing the same type inference functions used when making Tarjan O(V + E).

saolof avatar Apr 15 '21 07:04 saolof