#12052: Some distance computations remained *slow*
----------------------------+-----------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.8
Component: graph theory | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author: Nathann Cohen
Merged: | Dependencies:
----------------------------+-----------------------------------------------
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: %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
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12052>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
