Sage: Ticket #11046: Some comments in the code of SparseGraph
https://trac.sagemath.org/ticket/11046
<p>
I was reading this code to understand a bit better how the <a class="missing wiki">SparseGraph?</a> 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.. <code>:-)</code>
</p>
<p>
Before :
</p>
<pre class="wiki">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
</pre><p>
After
</p>
<pre class="wiki">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
</pre><p>
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 <code>:-)</code>
</p>
<p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/11046
Trac 1.1.6ncohenSat, 26 Mar 2011 16:52:36 GMTstatus, description changed; cc set
https://trac.sagemath.org/ticket/11046#comment:1
https://trac.sagemath.org/ticket/11046#comment:1
<ul>
<li><strong>cc</strong>
<em>rlm</em> added
</li>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11046?action=diff&version=1">diff</a>)
</li>
</ul>
TicketrlmSun, 10 Apr 2011 20:12:32 GMTstatus changed
https://trac.sagemath.org/ticket/11046#comment:2
https://trac.sagemath.org/ticket/11046#comment:2
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Nathann,
</p>
<p>
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 <a class="missing wiki">SparseGraph?</a> code. The reason being that <a class="missing wiki">SparseGraphs?</a> are never directed as implemented, and I think using the word arc helps keep this clear throughout.
</p>
<p>
Otherwise it looks fine to me. Any extra explanation of the rather complicated <a class="missing wiki">SparseGraph?</a> structure will be helpful, I think.
</p>
TicketncohenSun, 10 Apr 2011 20:14:33 GMT
https://trac.sagemath.org/ticket/11046#comment:3
https://trac.sagemath.org/ticket/11046#comment:3
<p>
+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 <code>:-D</code>
</p>
<p>
Nathann
</p>
TicketncohenSun, 10 Apr 2011 20:17:32 GMTattachment set
https://trac.sagemath.org/ticket/11046
https://trac.sagemath.org/ticket/11046
<ul>
<li><strong>attachment</strong>
set to <em>trac_11046.patch</em>
</li>
</ul>
TicketncohenSun, 10 Apr 2011 20:22:53 GMTstatus changed
https://trac.sagemath.org/ticket/11046#comment:4
https://trac.sagemath.org/ticket/11046#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
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 <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketrlmSun, 10 Apr 2011 20:33:13 GMTstatus changed; reviewer, author set
https://trac.sagemath.org/ticket/11046#comment:5
https://trac.sagemath.org/ticket/11046#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Robert Miller</em>
</li>
<li><strong>author</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
TicketjdemeyerWed, 13 Apr 2011 07:44:56 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/11046#comment:6
https://trac.sagemath.org/ticket/11046#comment:6
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.7.alpha5</em>
</li>
</ul>
Ticket