Opened 10 years ago
Closed 9 years ago
#14589 closed enhancement (fixed)
binary matrices, dense graphs, and faster is_strongly_regular
Reported by:  Nathann Cohen  Owned by:  jason, ncohen, rlm 

Priority:  major  Milestone:  sage6.1 
Component:  graph theory  Keywords:  
Cc:  Slani, Stefan, Jernej Azarija, Dima Pasechnik  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Jernej Azarija 
Report Upstream:  N/A  Work issues:  
Branch:  u/ncohen/14589 (Commits, GitHub, GitLab)  Commit:  b56444ba216f3c2e6d7f20e34daf80f5d5aec781 
Dependencies:  #14805  Stopgaps: 
Description (last modified by )
As the title says !!
With the patch applied
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
Without it
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
Ahhhh.. It is so nice to implement an algorithm with the right data structure ! :P
Nathann
Attachments (1)
Change History (33)
comment:1 Changed 10 years ago by
Status:  new → needs_review 

comment:2 Changed 10 years ago by
Cc:  Dima Pasechnik added; jernej dimpae removed 

Description:  modified (diff) 
comment:3 followup: 4 Changed 10 years ago by
comment:4 Changed 10 years ago by
Well, to me even a complete graph is strongly regular. We just had a discussion on Mathematical Dogma there : #14297. What do you think ?
In this case, as there are nonadjacent vertices, I'd say that the graph is strongly regular.... Dogma :P
Nathann
comment:5 followup: 6 Changed 10 years ago by
Nathann,
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.
comment:6 Changed 10 years ago by
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.
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 :)
Could we make this another ticket ? Then you can implement it or I will, it's up to you !
Nathann
comment:8 Changed 10 years ago by
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 bitsetmatrices 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.
comment:9 followup: 10 Changed 10 years ago by
Hello,
I am a bit naive but would like to understand the following
 pxi against C 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)
 mutability why don't you mimic what is done for
DenseGraph
to allow mutability (ie having a bitset of active vertices that allow to use any subset of 0, ..., n1 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.  sparse graphs What do we do with current implementation of
SparseGraph
?
comment:10 Changed 10 years ago by
Hellooooooo !
I am a bit naive but would like to understand the following
 pxi against C why do you use a pxi file ?
If you compile the file independently then the functions cannot be inlined.
 mutability why don't you mimic what is done for
DenseGraph
to allow mutability (ie having a bitset of active vertices that allow to use any subset of 0, ..., n1 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.
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.
 sparse graphs What do we do with current implementation of
SparseGraph
?
Well, first I will have to read your patch #14690. 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 ? :P
Nathann
Changed 9 years ago by
Attachment:  trac_14589.patch added 

comment:11 Changed 9 years ago by
Dependencies:  → #14805 

comment:12 Changed 9 years ago by
Milestone:  sage5.11 → sage5.12 

comment:13 Changed 9 years ago by
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: https://github.com/jasongrout/minimum_rank/blob/master/zero_forcing_wavefront.pyx#L124
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!
comment:14 followup: 15 Changed 9 years ago by
Hello!
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?
Anyways, before giving another check let me ask
 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?
 Line 48 function inline binary_matrix_free. Shouldn't you free m.rows[1],...,m.rows[n_rows] as well?
 Line 69 in inline binary_matrix_set0 the comment should really say set matrix entry to 0
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?
comment:15 followup: 20 Changed 9 years ago by
Yooooooo !
As promised I took the time to review your patch.
Thaaaaaaaaaaanks !! ;)
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?
The "someone else with do it" syndrome. And the fact that with git the developpers as a whole probably suffered a loss of enthusiasm :P
 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?
Unfortunately I think we can. Though I try not to rely on that. Did I do it in this patch ?
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 : graphs.KneserGraph
) and well, that causes bugs from time to time.
 Line 48 function inline binary_matrix_free. Shouldn't you free m.rows[1],...,m.rows[n_rows] as well?
No, because only m.rows[0]
is allocated on line 39. All of m.rows[i]
point toward some part of this very long vector, but regardless of that if you deallocate m.rows[0]
the whole segment is deallocated.
 Line 69 in inline binary_matrix_set0 the comment should really say set matrix entry to 0
Oh. Right :PPPPPPPPP
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?
T_T
I hate labels. And I also type .edges(labels=False)
much more often than .edges()
. 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 :P
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.
Nathann
comment:17 Changed 9 years ago by
Commit:  → 9f0f8382c21eee8d76282661bbdc9e1dcfc597a8 

Branch pushed to git repo; I updated commit sha1. New commits:
9f0f838  trac #14589: binary matrices, dense graphs, and faster is_strongly_regular

comment:18 Changed 9 years ago by
Hmmmm.. bitset.pyx has been renamed since :P
And actually.. We don't need it.
Nathann
comment:19 Changed 9 years ago by
Commit:  9f0f8382c21eee8d76282661bbdc9e1dcfc597a8 → b56444ba216f3c2e6d7f20e34daf80f5d5aec781 

Branch pushed to git repo; I updated commit sha1. New commits:
b56444b  trac #14589: binary matrices, dense graphs, and faster is_strongly_regular

comment:20 followup: 21 Changed 9 years ago by
Replying to ncohen:
Yooooooo !
As promised I took the time to review your patch.
Thaaaaaaaaaaanks !!
;)
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?
The "someone else with do it" syndrome. And the fact that with git the developpers as a whole probably suffered a loss of enthusiasm
:P
 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?
Unfortunately I think we can. Though I try not to rely on that. Did I do it in this patch ?
Yes didn't you?
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 :
graphs.KneserGraph
) and well, that causes bugs from time to time.
 Line 48 function inline binary_matrix_free. Shouldn't you free m.rows[1],...,m.rows[n_rows] as well?
No, because only
m.rows[0]
is allocated on line 39. All ofm.rows[i]
point toward some part of this very long vector, but regardless of that if you deallocatem.rows[0]
the whole segment is deallocated.
Right! I completely misread something somewhere.
 Line 69 in inline binary_matrix_set0 the comment should really say set matrix entry to 0
Oh. Right
:PPPPPPPPP
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?
T_T
I hate labels. And I also type
.edges(labels=False)
much more often than.edges()
. 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:P
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.
For me they are veeeery annoying so I assumed they were for everyone .
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)
Best,
Jernej
Nathann
comment:21 followup: 22 Changed 9 years ago by
Yes didn't you?
Well if I did I do not remember where :P
For me they are veeeery annoying so I assumed they were for everyone.
Hmmmm.. It is true that a graph is a collection of pairs, and that you always have to explain "what the hell all these None
are" when you show the result of g.edges()
to beginners... :/
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)
Well the patchbot complains but the two errors seem unrelated.
Nathann
comment:22 followup: 23 Changed 9 years ago by
Replying to ncohen:
Yes didn't you?
Well if I did I do not remember where
:P
Line 67. g.vertices() == range(n)
For me they are veeeery annoying so I assumed they were for everyone.
Hmmmm.. It is true that a graph is a collection of pairs, and that you always have to explain "what the hell all these
None
are" when you show the result ofg.edges()
to beginners...:/
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)
Well the patchbot complains but the two errors seem unrelated.
Nathann
comment:23 Changed 9 years ago by
Hellooo !
Line 67. g.vertices() == range(n)
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.
Nathann
comment:24 Changed 9 years ago by
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.
comment:25 Changed 9 years ago by
Hmmmmmm... Well, we can resort it but I think it's overkill. If that ever changes we will have to look at all occurrences of g.vertices()
anyway... And I really think that this isn't going to happen anytime soon O_o
Nathann
comment:26 followup: 27 Changed 9 years ago by
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?
comment:27 Changed 9 years ago by
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?
O_o
Instead of that test, you mean ?
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...n1 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.
Nathann
comment:28 Changed 9 years ago by
Yes sure! That's what I said its stupid cause you also have to make sure every element is actually an int.
As said this was more of a stupid comment than anything else, as far as I am concerned the patch is good to go!
comment:30 Changed 9 years ago by
Status:  needs_review → positive_review 

comment:31 Changed 9 years ago by
Reviewers:  → Jernej Azarija 

Thaaaaaaaaaaanks !
At long last, I can test if a graph is strongly regular without fearing it might hang on forever :P
Nathann
comment:32 Changed 9 years ago by
Resolution:  → fixed 

Status:  positive_review → closed 
how about (complements of) disjoint unions of complete graphs with the same number of vertices? Are they s.r.g. for you?