Opened 10 years ago

Closed 10 years ago

# Some distance computations remained *slow*

Reported by: Owned by: ncohen jason, ncohen, rlm major sage-4.8 graph theory dcoudert sage-4.8.alpha3 Nathann Cohen David Coudert N/A

### 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

### comment:1 Changed 10 years ago by ncohen

• Status changed from new to needs_review

### comment:2 Changed 10 years ago by ncohen

• Description modified (diff)

### comment:3 Changed 10 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 10 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 10 years ago by ncohen

• Status changed from positive_review to needs_work

### comment:6 Changed 10 years ago by ncohen

• Status changed from needs_work to needs_review

### comment:7 follow-up: ↓ 8 Changed 10 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 10 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 10 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 10 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 10 years ago by ncohen

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

Nathann

### comment:12 Changed 10 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

### comment:13 Changed 10 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 10 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.