Some distance computations remained *slow*

[nathanncohen]

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

CC: @dcoudert

Component: graph theory

Author: Nathann Cohen

Reviewer: David Coudert

Merged: sage-4.8.alpha3

Issue created by migration from https://trac.sagemath.org/ticket/12052

[dcoudert]

comment:3

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 !

[dcoudert]

Reviewer: David Coudert

[nathanncohen]

comment:4

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

[dcoudert]

comment:7

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

[nathanncohen]

comment:8

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

[nathanncohen]

comment:9

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

[dcoudert]

comment:10

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.

[nathanncohen]

comment:11

(with a small fix for another unrelated function that does not deserve another ticket :-p)

Nathann

[nathanncohen]

comment:12

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

[dcoudert]

comment:13

Attachment: trac_12052.patch.gz

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.

[jdemeyer]

Merged: sage-4.8.alpha3