search

dominikbraun / graph

A library for creating generic graph data structures and modifying, analyzing, and visualizing them.
https://graph.dominikbraun.io
Apache License 2.0
1.81k stars 94 forks source link

fixed TopologicalSort to run in O(V+E) instead of O(V^2) #144

Closed jonbrandenburg closed 10 months ago

jonbrandenburg commented 1 year ago

Fixed the TopologicalSort code to run in O(V+E) time rather than O(V^2). Can be easily confirmed by either instrumenting the code or creating larger graphs that make the time difference more obvious. Unit tests are passing.

dominikbraun commented 1 year ago

@jonbrandenburg Thank you! Do you have any resources or information about this tweaked approach? Where did you find it?

Maybe it would make sense to optimize StableTopologicalSort as well. CC @jonjohnsonjr

jonbrandenburg commented 1 year ago

@jonbrandenburg Thank you! Do you have any resources or information about this tweaked approach? Where did you find it?

Maybe it would make sense to optimize StableTopologicalSort as well. CC @jonjohnsonjr

I already updated StableTopologicalSort as well. As for resources regarding the change it came from a reading of the code. I saw the problem and decided to fix it. If you want any insight into it I'd suggest instrumenting the code (new and old) and verifying that the solutions do indeed perform within the stated bounds (original code O(V^2) and the new code O(V+E). That's how I went about confirming / verifying my assumptions / suspicions / implementation.

dominikbraun commented 1 year ago

@jonbrandenburg

I already updated StableTopologicalSort as well.

It's still too early in the morning here in Germany, my brain hasn't reached full capacity yet :D

As for resources regarding the change it came from a reading of the code. I saw the problem and decided to fix it.

Nice job! I'm going to take a look at it.

jonbrandenburg commented 1 year ago

I just pushed up a small change in the hopes that it makes the code easier to read. I have some additional changes I'd like to push that eliminate any potential concurrency issues / race conditions as well but decided to hold off on pushing them until I have a better idea which direction this PR is headed.