id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
12052,Some distance computations remained *slow*,ncohen,jason ncohen rlm,"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",enhancement,closed,major,sage-4.8,graph theory,fixed,,dcoudert,sage-4.8.alpha3,Nathann Cohen,David Coudert,N/A,,,,,