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
improving shortest path all pairs through BFS computations #11053
Comments
comment:1
Before
After
|
This comment has been minimized.
This comment has been minimized.
Attachment: trac_11053.patch.gz |
comment:3
I had set this patch to "needs review", as I was wondering why Cython was apparently slower than a C code I had written independently. Turns out the different lies in how the vertices of the 2d grid (which is the graph on which I was testing the performances) were labelled. In the C code, they were labelled from left to right, then from top to bottom, why Sage's numbering is much more random, hence different performances in practice. Hail Cython Nathann |
comment:4
I reviwed the patch and it seens to be working well! |
Reviewer: Leonardo Sampaio |
Dependencies: #10905 |
Merged: sage-4.7.2.alpha2 |
After taking a look at the SparseGraph backend, it looks like some time is actually spent obtaining the list of neighbors. This patch caches so that the out_neighbors method does not have to be called so often.
Depends on #10905
CC: @sagetrac-ylchapuy
Component: graph theory
Author: Nathann Cohen
Reviewer: Leonardo Sampaio
Merged: sage-4.7.2.alpha2
Issue created by migration from https://trac.sagemath.org/ticket/11053
The text was updated successfully, but these errors were encountered: