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