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 ncohen)

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)

trac_12052.patch (52.8 KB) - added by ncohen 8 years ago.

Download all attachments as: .zip

Change History (15)

comment:1 Changed 8 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 8 years ago by ncohen

  • Description modified (diff)

comment:3 Changed 8 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

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 !

comment:4 Changed 8 years ago by ncohen

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 ncohen

  • Status changed from positive_review to needs_work

comment:6 Changed 8 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:7 follow-up: Changed 8 years ago by dcoudert

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 ncohen

  • 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 ncohen

  • 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 dcoudert

  • 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 ncohen

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

Nathann

comment:12 Changed 8 years ago by ncohen

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 ncohen

comment:13 Changed 8 years ago by dcoudert

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 jdemeyer

  • Merged in set to sage-4.8.alpha3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.