Opened 10 years ago
Closed 9 years ago
#11053 closed enhancement (fixed)
improving shortest path all pairs through BFS computations
Reported by: | ncohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.7.2 |
Component: | graph theory | Keywords: | |
Cc: | ylchapuy | Merged in: | sage-4.7.2.alpha2 |
Authors: | Nathann Cohen | Reviewers: | Leonardo Sampaio |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #10905 | Stopgaps: |
Description (last modified by )
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.
Attachments (1)
Change History (7)
comment:1 Changed 10 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
- Status changed from needs_review to needs_work
Changed 10 years ago by
comment:3 Changed 10 years ago by
- Status changed from needs_work to needs_review
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 Changed 9 years ago by
- Reviewers set to Leonardo Sampaio
- Status changed from needs_review to positive_review
I reviwed the patch and it seens to be working well!
comment:5 Changed 9 years ago by
- Milestone changed from sage-4.7.1 to sage-4.7.2
comment:6 Changed 9 years ago by
- Dependencies set to #10905
- Description modified (diff)
- Merged in set to sage-4.7.2.alpha2
- Resolution set to fixed
- Status changed from positive_review to closed
Before
After