Sage: Ticket #14589: binary matrices, dense graphs, and faster is_strongly_regular
https://trac.sagemath.org/ticket/14589
<p>
As the title says !!
</p>
<p>
With the patch applied
</p>
<pre class="wiki">sage: g = graphs.PaleyGraph(primes_first_n(70)[-1])
sage: %time g.is_strongly_regular()
CPU times: user 0.16 s, sys: 0.00 s, total: 0.16 s
Wall time: 0.16 s
True
</pre><p>
Without it
</p>
<pre class="wiki">sage: g = graphs.PaleyGraph(primes_first_n(70)[-1])
sage: %time g.is_strongly_regular()
CPU times: user 20.43 s, sys: 0.00 s, total: 20.43 s
Wall time: 20.44 s
True
</pre><p>
Ahhhh.. It is so nice to implement an algorithm with the right data structure ! <code>:-P</code>
</p>
<p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/14589
Trac 1.1.6ncohenWed, 15 May 2013 10:23:58 GMTstatus changed
https://trac.sagemath.org/ticket/14589#comment:1
https://trac.sagemath.org/ticket/14589#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketncohenWed, 15 May 2013 15:53:44 GMTcc, description changed
https://trac.sagemath.org/ticket/14589#comment:2
https://trac.sagemath.org/ticket/14589#comment:2
<ul>
<li><strong>cc</strong>
<em>dimpase</em> added; <em>jernej</em> <em>dimpae</em> removed
</li>
<li><strong>description</strong>
modified (<a href="/ticket/14589?action=diff&version=2">diff</a>)
</li>
</ul>
TicketdimpaseThu, 16 May 2013 02:04:10 GMT
https://trac.sagemath.org/ticket/14589#comment:3
https://trac.sagemath.org/ticket/14589#comment:3
<p>
how about (complements of) disjoint unions of complete graphs with the same number of vertices? Are they s.r.g. for you?
</p>
TicketncohenThu, 16 May 2013 09:28:48 GMT
https://trac.sagemath.org/ticket/14589#comment:4
https://trac.sagemath.org/ticket/14589#comment:4
<p>
Well, to me even a complete graph is strongly regular. We just had a discussion on Mathematical Dogma there : <a class="closed ticket" href="https://trac.sagemath.org/ticket/14297" title="enhancement: is_strongly_regular does not handle complete graphs (closed: fixed)">#14297</a>. What do you think ?
</p>
<p>
In this case, as there are non-adjacent vertices, I'd say that the graph is strongly regular.... Dogma <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketaziSun, 19 May 2013 07:58:55 GMT
https://trac.sagemath.org/ticket/14589#comment:5
https://trac.sagemath.org/ticket/14589#comment:5
<p>
Nathann,
</p>
<p>
I think it would make much sense to test the "is_triangle_free" thing with this data structure as well. It should be much more efficient using the same approach.
</p>
TicketncohenSun, 19 May 2013 08:16:03 GMT
https://trac.sagemath.org/ticket/14589#comment:6
https://trac.sagemath.org/ticket/14589#comment:6
<blockquote class="citation">
<p>
I think it would make much sense to test the "is_triangle_free" thing with this data structure as well. It should be much more efficient using the same approach.
</p>
</blockquote>
<p>
I don't know which kind of speedup we can expect, but that's definitely something that should be implemented, if only to run that test <code>:-)</code>
</p>
<p>
Could we make this another ticket ? Then you can implement it or I will, it's up to you !
</p>
<p>
Nathann
</p>
TicketaziSun, 19 May 2013 08:17:46 GMT
https://trac.sagemath.org/ticket/14589#comment:7
https://trac.sagemath.org/ticket/14589#comment:7
<p>
Sure I'll make make a ticket soon
</p>
TicketStefanSun, 19 May 2013 12:48:21 GMT
https://trac.sagemath.org/ticket/14589#comment:8
https://trac.sagemath.org/ticket/14589#comment:8
<p>
Hmmm. I wonder how much of the speedup remains if you use a GF(2)-matrix or integer matrix instead of the bitset matrix. You're only doing get and set, and I'd say the real power of these bitset-matrices lies in row operations. You could use Sage's get_unsafe and set_unsafe to bypass range checking. It'll be slower than inline methods, but maybe not by much.
</p>
TicketvdelecroixWed, 05 Jun 2013 11:37:47 GMT
https://trac.sagemath.org/ticket/14589#comment:9
https://trac.sagemath.org/ticket/14589#comment:9
<p>
Hello,
</p>
<p>
I am a bit naive but would like to understand the following
</p>
<ul><li><strong>pxi against C</strong> why do you use a pxi file ? It would cause multiple compilation wherever it is included. I think a pure C file would be much more suited to that purpose (I know that this is the way it is for bitset)
</li><li><strong>mutability</strong> why don't you mimic what is done for <code>DenseGraph</code> to allow mutability (ie having a bitset of active vertices that allow to use any subset of 0, ..., n-1 as vertices). Virtually there will be the good number of vertices but in backend you treat your graph with many isolated vertices. Augmenting the number of vertices may then be done with realloc.
</li><li><strong>sparse graphs</strong> What do we do with current implementation of <code>SparseGraph</code> ?
</li></ul>
TicketncohenWed, 05 Jun 2013 12:18:42 GMT
https://trac.sagemath.org/ticket/14589#comment:10
https://trac.sagemath.org/ticket/14589#comment:10
<p>
Hellooooooo !
</p>
<blockquote class="citation">
<p>
I am a bit naive but would like to understand the following
</p>
<ul><li><strong>pxi against C</strong> why do you use a pxi file ?
</li></ul></blockquote>
<p>
If you compile the file independently then the functions cannot be inlined.
</p>
<blockquote class="citation">
<ul><li><strong>mutability</strong> why don't you mimic what is done for <code>DenseGraph</code> to allow mutability (ie having a bitset of active vertices that allow to use any subset of 0, ..., n-1 as vertices). Virtually there will be the good number of vertices but in backend you treat your graph with many isolated vertices. Augmenting the number of vertices may then be done with realloc.
</li></ul></blockquote>
<p>
Because I want to write simple things. It is not meant to replace a real graph backend, and it will probably be used later on by the future dense backend, but I would really like to have a simple structure somewhere, that does nothing but store bits.
</p>
<blockquote class="citation">
<ul><li><strong>sparse graphs</strong> What do we do with current implementation of <code>SparseGraph</code> ?
</li></ul></blockquote>
<p>
Well, first I will have to read your patch <a class="closed ticket" href="https://trac.sagemath.org/ticket/14690" title="enhancement: Useless memory allocation in listing neighbors of a graph (closed: invalid)">#14690</a>. Then, each time we read this file it would be nice to add comments to it, to explain the parts of it that we have understood. Then we can do whatever we want with this backend : rewrite it or improve it if we can. We can't really throw it out right now, can we ? <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketncohenWed, 03 Jul 2013 16:47:15 GMTattachment set
https://trac.sagemath.org/ticket/14589
https://trac.sagemath.org/ticket/14589
<ul>
<li><strong>attachment</strong>
set to <em>trac_14589.patch</em>
</li>
</ul>
TicketncohenWed, 03 Jul 2013 16:47:49 GMTdependencies set
https://trac.sagemath.org/ticket/14589#comment:11
https://trac.sagemath.org/ticket/14589#comment:11
<ul>
<li><strong>dependencies</strong>
set to <em>#14805</em>
</li>
</ul>
TicketjdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/14589#comment:12
https://trac.sagemath.org/ticket/14589#comment:12
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketjasonMon, 02 Sep 2013 16:46:43 GMT
https://trac.sagemath.org/ticket/14589#comment:13
https://trac.sagemath.org/ticket/14589#comment:13
<p>
Thanks for doing this. Often the first thing I do is to convert the graph to an array of bitsets and then work with that. I do this a lot in the minimum rank library, for example: <a class="ext-link" href="https://github.com/jasongrout/minimum_rank/blob/master/zero_forcing_wavefront.pyx#L124"><span class="icon"></span>https://github.com/jasongrout/minimum_rank/blob/master/zero_forcing_wavefront.pyx#L124</a>
</p>
<p>
Next time I write some code like this, I'll have to look at this implementation. When I get some time to do research coding work, if this hasn't been reviewed, I'll have to review this!
</p>
TicketaziWed, 08 Jan 2014 21:36:38 GMT
https://trac.sagemath.org/ticket/14589#comment:14
https://trac.sagemath.org/ticket/14589#comment:14
<p>
Hello!
</p>
<p>
As promised I took the time to review your patch. The entire thing is easy to read and looks good. The fact that it was not reviewed for so long makes me wonder if I am overlooking some non obvious caveat?
</p>
<p>
Anyways, before giving another check let me ask
</p>
<ol><li>Line 67 - can we always assume that g.vertices() will return a sorted list of vertices? Also, it looks like this can be written in a better way?
</li></ol><ol start="2"><li>Line 48 function inline binary_matrix_free. Shouldn't you free m.rows[1],...,m.rows[n_rows] as well?
</li></ol><ol start="3"><li>Line 69 in inline binary_matrix_set0 the comment should really say set matrix entry to 0
</li></ol><p>
Also off topic to this patch - am I the only one being tempted to change the function edges() and set edge_labels to false as default?
</p>
TicketncohenThu, 09 Jan 2014 08:59:27 GMT
https://trac.sagemath.org/ticket/14589#comment:15
https://trac.sagemath.org/ticket/14589#comment:15
<p>
Yooooooo !
</p>
<blockquote class="citation">
<p>
As promised I took the time to review your patch.
</p>
</blockquote>
<p>
Thaaaaaaaaaaanks !! <code>;-)</code>
</p>
<blockquote class="citation">
<p>
The entire thing is easy to read and looks good. The fact that it was not reviewed for so long makes me wonder if I am overlooking some non obvious caveat?
</p>
</blockquote>
<p>
The "someone else with do it" syndrome. And the fact that with git the developpers as a whole probably suffered a loss of enthusiasm <code>:-P</code>
</p>
<blockquote class="citation">
<ol><li>Line 67 - can we always assume that g.vertices() will return a sorted list of vertices? Also, it looks like this can be written in a better way?
</li></ol></blockquote>
<p>
Unfortunately I think we can. Though I try not to rely on that. Did I do it in this patch ?
</p>
<p>
The problem is that while the vertices are indeed "sorted" before being returned, but that this sorting can be meaningless : the "natural" ordering on the vertices may be a partial ordering from time to time (i.e. when the vertices are set : <code>graphs.KneserGraph</code>) and well, that causes bugs from time to time.
</p>
<blockquote class="citation">
<ol start="2"><li>Line 48 function inline binary_matrix_free. Shouldn't you free m.rows[1],...,m.rows[n_rows] as well?
</li></ol></blockquote>
<p>
No, because only <code>m.rows[0]</code> is allocated on line 39. All of <code>m.rows[i]</code> point toward some part of this very long vector, but regardless of that if you deallocate <code>m.rows[0]</code> the whole segment is deallocated.
</p>
<blockquote class="citation">
<ol start="3"><li>Line 69 in inline binary_matrix_set0 the comment should really say set matrix entry to 0
</li></ol></blockquote>
<p>
Oh. Right <code>:-PPPPPPPPP</code>
</p>
<blockquote class="citation">
<p>
Also off topic to this patch - am I the only one being tempted to change the function edges() and set edge_labels to false as default?
</p>
</blockquote>
<p>
<code>T_T</code>
</p>
<p>
I hate labels. And I also type <code>.edges(labels=False)</code> much more often than <code>.edges()</code>. Well. I didn't try to change this kind of stuff because I consider that it is just "my own use of graphs"... But well, if many of us begin to hate labels/loops/multiple edges now that's a different story <code>:-P</code>
The combinat/word guys may probably not agree, though... But really, I have no idea. I just never did that because I don't want to change stuff just because it makes it easier for me, without knowing how useful it can be for others.
</p>
<p>
Nathann
</p>
TicketncohenThu, 09 Jan 2014 10:09:00 GMTbranch set
https://trac.sagemath.org/ticket/14589#comment:16
https://trac.sagemath.org/ticket/14589#comment:16
<ul>
<li><strong>branch</strong>
set to <em>u/ncohen/14589</em>
</li>
</ul>
<p>
Rebased. As a git branch.
</p>
<p>
Nathann
</p>
TicketgitThu, 09 Jan 2014 10:09:18 GMTcommit set
https://trac.sagemath.org/ticket/14589#comment:17
https://trac.sagemath.org/ticket/14589#comment:17
<ul>
<li><strong>commit</strong>
set to <em>9f0f8382c21eee8d76282661bbdc9e1dcfc597a8</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=9f0f8382c21eee8d76282661bbdc9e1dcfc597a8"><span class="icon"></span>9f0f838</a></td><td><code>trac #14589: binary matrices, dense graphs, and faster is_strongly_regular</code>
</td></tr></table>
TicketncohenThu, 09 Jan 2014 10:20:19 GMT
https://trac.sagemath.org/ticket/14589#comment:18
https://trac.sagemath.org/ticket/14589#comment:18
<p>
Hmmmm.. bitset.pyx has been renamed since <code>:-P</code>
</p>
<p>
And actually.. We don't need it.
</p>
<p>
Nathann
</p>
TicketgitThu, 09 Jan 2014 10:20:45 GMTcommit changed
https://trac.sagemath.org/ticket/14589#comment:19
https://trac.sagemath.org/ticket/14589#comment:19
<ul>
<li><strong>commit</strong>
changed from <em>9f0f8382c21eee8d76282661bbdc9e1dcfc597a8</em> to <em>b56444ba216f3c2e6d7f20e34daf80f5d5aec781</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=b56444ba216f3c2e6d7f20e34daf80f5d5aec781"><span class="icon"></span>b56444b</a></td><td><code>trac #14589: binary matrices, dense graphs, and faster is_strongly_regular</code>
</td></tr></table>
TicketaziThu, 09 Jan 2014 18:51:23 GMT
https://trac.sagemath.org/ticket/14589#comment:20
https://trac.sagemath.org/ticket/14589#comment:20
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14589#comment:15" title="Comment 15">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Yooooooo !
</p>
<blockquote class="citation">
<p>
As promised I took the time to review your patch.
</p>
</blockquote>
<p>
Thaaaaaaaaaaanks !! <code>;-)</code>
</p>
<blockquote class="citation">
<p>
The entire thing is easy to read and looks good. The fact that it was not reviewed for so long makes me wonder if I am overlooking some non obvious caveat?
</p>
</blockquote>
<p>
The "someone else with do it" syndrome. And the fact that with git the developpers as a whole probably suffered a loss of enthusiasm <code>:-P</code>
</p>
<blockquote class="citation">
<ol><li>Line 67 - can we always assume that g.vertices() will return a sorted list of vertices? Also, it looks like this can be written in a better way?
</li></ol></blockquote>
<p>
Unfortunately I think we can. Though I try not to rely on that. Did I do it in this patch ?
</p>
</blockquote>
<p>
Yes didn't you?
</p>
<blockquote class="citation">
<p>
The problem is that while the vertices are indeed "sorted" before being returned, but that this sorting can be meaningless : the "natural" ordering on the vertices may be a partial ordering from time to time (i.e. when the vertices are set : <code>graphs.KneserGraph</code>) and well, that causes bugs from time to time.
</p>
<blockquote class="citation">
<ol start="2"><li>Line 48 function inline binary_matrix_free. Shouldn't you free m.rows[1],...,m.rows[n_rows] as well?
</li></ol></blockquote>
<p>
No, because only <code>m.rows[0]</code> is allocated on line 39. All of <code>m.rows[i]</code> point toward some part of this very long vector, but regardless of that if you deallocate <code>m.rows[0]</code> the whole segment is deallocated.
</p>
</blockquote>
<p>
Right! I completely misread something somewhere.
</p>
<blockquote class="citation">
<blockquote class="citation">
<ol start="3"><li>Line 69 in inline binary_matrix_set0 the comment should really say set matrix entry to 0
</li></ol></blockquote>
<p>
Oh. Right <code>:-PPPPPPPPP</code>
</p>
<blockquote class="citation">
<p>
Also off topic to this patch - am I the only one being tempted to change the function edges() and set edge_labels to false as default?
</p>
</blockquote>
<p>
<code>T_T</code>
</p>
<p>
I hate labels. And I also type <code>.edges(labels=False)</code> much more often than <code>.edges()</code>. Well. I didn't try to change this kind of stuff because I consider that it is just "my own use of graphs"... But well, if many of us begin to hate labels/loops/multiple edges now that's a different story <code>:-P</code>
The combinat/word guys may probably not agree, though... But really, I have no idea. I just never did that because I don't want to change stuff just because it makes it easier for me, without knowing how useful it can be for others.
</p>
</blockquote>
<p>
For me they are veeeery annoying so I assumed they were for everyone .
</p>
<p>
Anyways, this is all I got to say about the patch. It looks good to me provided u changed the above things and ran the doctests (which I did not)
</p>
<p>
Best,
</p>
<p>
Jernej
</p>
<blockquote class="citation">
<p>
Nathann
</p>
</blockquote>
TicketncohenThu, 09 Jan 2014 21:04:03 GMT
https://trac.sagemath.org/ticket/14589#comment:21
https://trac.sagemath.org/ticket/14589#comment:21
<blockquote class="citation">
<p>
Yes didn't you?
</p>
</blockquote>
<p>
Well if I did I do not remember where <code>:-P</code>
</p>
<blockquote class="citation">
<p>
For me they are veeeery annoying so I assumed they were for everyone.
</p>
</blockquote>
<p>
Hmmmm.. It is true that a graph is a collection of pairs, and that you always have to explain "what the hell all these <code>None</code> are" when you show the result of <code>g.edges()</code> to beginners... <code>:-/</code>
</p>
<blockquote class="citation">
<p>
Anyways, this is all I got to say about the patch. It looks good to me provided u changed the above things and ran the doctests (which I did not)
</p>
</blockquote>
<p>
Well the patchbot complains but the two errors seem unrelated.
</p>
<p>
Nathann
</p>
TicketaziThu, 09 Jan 2014 21:28:31 GMT
https://trac.sagemath.org/ticket/14589#comment:22
https://trac.sagemath.org/ticket/14589#comment:22
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14589#comment:21" title="Comment 21">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Yes didn't you?
</p>
</blockquote>
<p>
Well if I did I do not remember where <code>:-P</code>
</p>
</blockquote>
<p>
Line 67. g.vertices() == range(n)
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
For me they are veeeery annoying so I assumed they were for everyone.
</p>
</blockquote>
<p>
Hmmmm.. It is true that a graph is a collection of pairs, and that you always have to explain "what the hell all these <code>None</code> are" when you show the result of <code>g.edges()</code> to beginners... <code>:-/</code>
</p>
<blockquote class="citation">
<p>
Anyways, this is all I got to say about the patch. It looks good to me provided u changed the above things and ran the doctests (which I did not)
</p>
</blockquote>
<p>
Well the patchbot complains but the two errors seem unrelated.
</p>
<p>
Nathann
</p>
</blockquote>
TicketncohenThu, 09 Jan 2014 21:32:37 GMT
https://trac.sagemath.org/ticket/14589#comment:23
https://trac.sagemath.org/ticket/14589#comment:23
<p>
Hellooo !
</p>
<blockquote class="citation">
<p>
Line 67. g.vertices() == range(n)
</p>
</blockquote>
<p>
Oh, right. But in this case the vertices are integers. It indeed relies on the fact that vertices are sorted (and they are), but there is no problem if the natural order on the vertices is not total. The equality will be false in that case.
</p>
<p>
Nathann
</p>
TicketaziThu, 09 Jan 2014 21:34:39 GMT
https://trac.sagemath.org/ticket/14589#comment:24
https://trac.sagemath.org/ticket/14589#comment:24
<p>
I see. Well if you feel safe about that (the documentation afaik does not guarantee sorted order of vertices) then this thing is fine with me.
</p>
TicketncohenThu, 09 Jan 2014 21:36:44 GMT
https://trac.sagemath.org/ticket/14589#comment:25
https://trac.sagemath.org/ticket/14589#comment:25
<p>
Hmmmmmm... Well, we can re-sort it but I think it's overkill. If that ever changes we will have to look at all occurrences of <code>g.vertices()</code> anyway... And I really think that this isn't going to happen anytime soon <code>O_o</code>
</p>
<p>
Nathann
</p>
TicketaziThu, 09 Jan 2014 21:40:05 GMT
https://trac.sagemath.org/ticket/14589#comment:26
https://trac.sagemath.org/ticket/14589#comment:26
<p>
Indeed. Of course there is the stupid, thing of checking that the sum is n(n+1)/2 but I think that looks even more weird in this context?
</p>
TicketncohenThu, 09 Jan 2014 21:46:48 GMT
https://trac.sagemath.org/ticket/14589#comment:27
https://trac.sagemath.org/ticket/14589#comment:27
<blockquote class="citation">
<p>
Indeed. Of course there is the stupid, thing of checking that the sum is n(n+1)/2 but I think that looks even more weird in this context?
</p>
</blockquote>
<p>
<code>O_o</code>
</p>
<p>
Instead of that test, you mean ?
</p>
<p>
Well, we have no way to be sure that the vertices CAN be summed. I mean, this test is meant to check whether there is any need to store a label_to_int dictionary. If the vertices are 0...n-1 there is no need and so we do without. But if the vertices are... I don't know, anything ! Strings, Sets, partitions, tuples.. immutables graphs ? Well in that case we remember labels. And we cannot be sure that those can all be summed together.
</p>
<p>
Nathann
</p>
TicketaziThu, 09 Jan 2014 21:49:06 GMT
https://trac.sagemath.org/ticket/14589#comment:28
https://trac.sagemath.org/ticket/14589#comment:28
<p>
Yes sure! That's what I said its stupid cause you also have to make sure every element is actually an int.
</p>
<p>
As said this was more of a stupid comment than anything else, as far as I am concerned the patch is good to go!
</p>
TicketncohenThu, 09 Jan 2014 21:54:08 GMT
https://trac.sagemath.org/ticket/14589#comment:29
https://trac.sagemath.org/ticket/14589#comment:29
<p>
Sooooooooooooooo positive review ?... <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketaziThu, 09 Jan 2014 21:57:38 GMTstatus changed
https://trac.sagemath.org/ticket/14589#comment:30
https://trac.sagemath.org/ticket/14589#comment:30
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketncohenThu, 09 Jan 2014 21:59:24 GMTreviewer set
https://trac.sagemath.org/ticket/14589#comment:31
https://trac.sagemath.org/ticket/14589#comment:31
<ul>
<li><strong>reviewer</strong>
set to <em>Jernej Azarija</em>
</li>
</ul>
<p>
Thaaaaaaaaaaanks !
</p>
<p>
At long last, I can test if a graph is strongly regular without fearing it might hang on forever <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketvbraunMon, 20 Jan 2014 23:52:25 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/14589#comment:32
https://trac.sagemath.org/ticket/14589#comment:32
<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>
</ul>
Ticket