Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add benchmarks for Tarjan's SCC algorithm #421

Merged
merged 1 commit into from Apr 30, 2021

Conversation

ABorgna
Copy link
Member

@ABorgna ABorgna commented Apr 26, 2021

Rename the current SCC benchmarks to indicate they are using Kosaraju's algorithm, and add similar benchs for the Tarjan implementation.

The goal is to have a baseline for #413.

@saolof
Copy link
Contributor

saolof commented Apr 27, 2021

Adding ready-made benchmarks to a project is great and makes the contribution process a lot easier. One thing I noticed from the benchmarks in the other thread is that the tarjan_scc function is substantially faster than the Kosaraju implementation, roughly by a factor of 2 (makes sense, we're looking at one traversal vs two).

This suggests that making Tarjan imperative so that it can't stack overflow and can replace Kosaraju as the default algorithm, is probably the right path to making SCC's faster.

@ABorgna
Copy link
Member Author

ABorgna commented Apr 27, 2021

Yes, but the Tarjan implementation requires NodeIndexable, so it cannot be used with GraphMap. The scc method is deprecated, so there is no default implementation.
We could perhaps mention that Tarjan's tends to be a faster option in Kosaraju's documentation.

It will be nice to see the benchmarks for the imperative implementation :)

@ABorgna
Copy link
Member Author

ABorgna commented Apr 30, 2021

I'll self-approve this since it's a simple change, and may be useful for contributors.

@ABorgna ABorgna merged commit 37e7348 into petgraph:master Apr 30, 2021
@ABorgna ABorgna deleted the scc_benchmarks branch April 30, 2021 10:46
@bluss
Copy link
Member

bluss commented Apr 30, 2021

IMO self-approve is a good way to work, when you feel like it is appropriate.

@ABorgna ABorgna added this to the 0.6 milestone May 16, 2021
teuron pushed a commit to teuron/petgraph that referenced this pull request Oct 9, 2022
teuron pushed a commit to teuron/petgraph that referenced this pull request Oct 9, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

3 participants