Opened 8 years ago
Closed 8 years ago
#12052 closed enhancement (fixed)
Some distance computations remained *slow*
Reported by: | ncohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.8 |
Component: | graph theory | Keywords: | |
Cc: | dcoudert | Merged in: | sage-4.8.alpha3 |
Authors: | Nathann Cohen | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
It turns out that we have a very fast code to compute the distances between all pairs of vertices, but that it was not used to compute the diameter of a graph, or its radius, or all of the vertices' eccentricities.
We were in this situation
sage: g = graphs.RandomGNM(200,10000) sage: %timeit g.diameter() 5 loops, best of 3: 1.22 s per loop
The Cython function computing the distance was in the c_graph file, and took a lot of space there. Besides, it seemed useful to split it into smaller functions, for if this function can compute the diameter quickly, or the distances, or the shortest paths between all pairs of vertices, it is useless to compute all of that at the same time if one is only interested in one of the answers.
I moved this method to a new module distances_all_pairs that deals with whatever can be associated with the distances between all pairs of vertices (in this case, the diameter, shortest paths, distances and eccentricities), and updated several methods of the GenericGraph? class so that they use these methods.
Now, here is where we are :
sage: g = graphs.RandomGNM(200,10000) sage: %timeit g.diameter() 25 loops, best of 3: 11.6 ms per loop
Nathann
Attachments (1)
Change History (15)
comment:1 Changed 8 years ago by
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Description modified (diff)
comment:3 Changed 8 years ago by
- Reviewers set to David Coudert
- Status changed from needs_review to positive_review
comment:4 Changed 8 years ago by
Hmmm.. I noticed there was a doctest error in generic_graph.py, after testing the whole library. Can you check it is ok now ? :-)
All -long doctests pass on my version of Sage !
Nathann
comment:5 Changed 8 years ago by
- Status changed from positive_review to needs_work
comment:6 Changed 8 years ago by
- Status changed from needs_work to needs_review
comment:7 follow-up: ↓ 8 Changed 8 years ago by
The following variable declaration is made lines 399 and 485, but the variable is apparently not used. Could it be removed ?
cdef CGraph cg = <CGraph> G._backend._cg
comment:8 in reply to: ↑ 7 Changed 8 years ago by
- Status changed from needs_review to needs_work
The following variable declaration is made lines 399 and 485, but the variable is apparently not used. Could it be removed ?
cdef CGraph cg = <CGraph> G._backend._cg
Right. It will be done (1). I also noticed in between that the code use a quadratic memory when computing the eccentricities, which is far beyond necessary. I will modify that (2) as soon as alpha2 will be compiled, as this patch will probably need to be rebased on top of it (3).
Nathann
comment:9 Changed 8 years ago by
- Status changed from needs_work to needs_review
Without useless variables, rebased on top of alpha2, without additional memory cost when computing the eccentricity (and hence for the diameter of for the radius of the graph).
Here it is ! :-)
Nathann
comment:10 Changed 8 years ago by
- Status changed from needs_review to positive_review
Installation OK, doc OK for me, and running times/memory requirements more than OK
Before applying the patch
sage: G = graphs.RandomGNM(1000,15000) sage: %time G.diameter() CPU times: user 23.71 s, sys: 0.00 s, total: 23.72 s Wall time: 23.83 s 3
After:
sage: G = graphs.RandomGNM(1000,15000) sage: %time G.diameter() CPU times: user 0.11 s, sys: 0.00 s, total: 0.11 s Wall time: 0.11 s 3
That's impressive !
I give positive review.
comment:11 Changed 8 years ago by
(with a small fix for another unrelated function that does not deserve another ticket :-p
)
Nathann
comment:12 Changed 8 years ago by
Oops.. Looks like we were working on the ticket at the same time :-p
David, could you give the ticket another look for the patch fixing the bug in vertex_separation we talked about by email ? It should be working now :-)
And I swear it's the last time you review this ticket :-P
Nathann
Changed 8 years ago by
comment:13 Changed 8 years ago by
I'm still satisfied for the distance / eccentricity / ... running time and space improvements.
Concerning vertex_separation, the bug is fixed. I now have to learn how to make a patch to propose improvements ;)
Thanks.
comment:14 Changed 8 years ago by
- Merged in set to sage-4.8.alpha3
- Resolution set to fixed
- Status changed from positive_review to closed
I did several tests on graphs with up to 10.000 nodes and its really fast (>10 s). For small graphs, it only takes few ms.
I have not seen any problem in the code or in the doc.
Nice work Nathann !