Quadratic Time Complexity

[ekzhang]

On line 53 of StronglyConnectedComponentFinder, the Stack.Contains method is being used, which runs in O(V) time, which is a bottleneck for the algorithm that can cause it to run in worst-case O(V^2) time. This small bug unfortunately renders the implementation useless, as it can be superseded easily by a naive solution.

CycleDetection/StronglyConnectedComponents/StronglyConnectedComponentFinder.cs

Line 53 in 10cf461

else if (stack.Contains(w))

@danielrbradley Could you modify the code to use, for example, an array of boolean flags to see if the vertex is in the stack or not? This would fix the bug and make the algorithm run in linear time as expected. Sorry that I am not able to make this change myself; I do not have enough experience working with C#.

[danielrbradley]

Thanks for the suggestion. I'm not actively maintaining this project (haven't opened it in 5 years now), but am happy to merge any PRs if someone wants to take a stab at it 🙂