Some comments in the code of SparseGraph

[ncohen]

I was reading this code to understand a bit better how the SparseGraph? backend worked (as it is the default one in Sage), and added comments while I was at it. I also replaced some loops initializing values by a memset, as it is usually faster. This produces next-to-zero improvement in Sage, but well.. :-)

Before :

625 loops, best of 3: 1.26 ms per loop
sage: %timeit Graph(10000)
625 loops, best of 3: 1.25 ms per loop
sage: %timeit Graph(10000)
625 loops, best of 3: 1.47 ms per loop
sage: %timeit Graph(10000)
625 loops, best of 3: 1.25 ms per loop
sage: %timeit Graph(10000)
625 loops, best of 3: 1.25 ms per loop
sage: %timeit Graph(100)
625 loops, best of 3: 94.7 µs per loop
sage: %timeit Graph(100)
625 loops, best of 3: 98.8 µs per loop
sage: %timeit Graph(100)
625 loops, best of 3: 95.8 µs per loop
sage: %timeit Graph(100)
625 loops, best of 3: 95.2 µs per loop
sage: %timeit Graph(100)
625 loops, best of 3: 96.6 µs per loop
sage: %timeit Graph(100)
625 loops, best of 3: 95.2 µs per loop

After

sage: %timeit Graph(10000)
625 loops, best of 3: 1.15 ms per loop
sage: %timeit Graph(10000)
625 loops, best of 3: 1.15 ms per loop
sage: %timeit Graph(10000)
625 loops, best of 3: 1.15 ms per loop
sage: %timeit Graph(10000)
625 loops, best of 3: 1.21 ms per loop
sage: %timeit Graph(10000)
625 loops, best of 3: 1.15 ms per loop
sage: %timeit Graph(100)
625 loops, best of 3: 94.5 µs per loop
sage: %timeit Graph(100)
625 loops, best of 3: 92.7 µs per loop
sage: %timeit Graph(100)
625 loops, best of 3: 93.5 µs per loop

By the way Robert, this is all mostly about touching your code and adding comments, and as I am trespassing I expect you may not like some of those :-)

Nathann

[rlm]

Nathann,

I'm happy with this patch except for one thing: I'd like you to change each added occurrence of the word "edge" to "arc" in the SparseGraph? code. The reason being that SparseGraphs? are never directed as implemented, and I think using the word arc helps keep this clear throughout.

Otherwise it looks fine to me. Any extra explanation of the rather complicated SparseGraph? structure will be helpful, I think.

[ncohen]

+1 ! An old patch of mine was refused once because I was told "We stick to the terminology "edge" instead of arc". I completely agree with you on that one :-D

Nathann

[ncohen]

Patch updated... I have been thinking about the graph structure for a while now... I have had to write some C code for a fast computation of "all pairs distance" (did you get my email about it ?), and I had to quickly redefine a Graph in C which lists all of its edges in a contiguous memory area so that it is optimal to list all edges of a graph. I also thought that because of the lack of red/black trees you mentionned in that code, your good implementation is badly misused : very often the edges of a graph are added in "lexicographical order", and in this case all your trees are actually linked lists.... But I need to think a bit more before coming up with a good solution :-)

Nathann