Sage: Ticket #14297: is_strongly_regular does not handle complete graphs
https://trac.sagemath.org/ticket/14297
<p>
It appears that the strongly regular thing does not handle complete graphs
</p>
<pre class="wiki">sage: G.is_strongly_regular()
sage:
</pre><p>
what it should return is false. I am currently too lazy to fix this so I am reporting it in case anyone of you guys is willing to fix it. Otherwise I might do it at some undefined time in the future.
</p>
<p>
Apply:
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/14297/trac-14297-fc.patch" title="Attachment 'trac-14297-fc.patch' in Ticket #14297">trac-14297-fc.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/14297/trac-14297-fc.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/14297/trac_14297-rev.patch" title="Attachment 'trac_14297-rev.patch' in Ticket #14297">trac_14297-rev.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/14297/trac_14297-rev.patch" title="Download"></a>
</li></ul>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/14297
Trac 1.1.6kcrismanTue, 19 Mar 2013 01:39:11 GMTtype changed
https://trac.sagemath.org/ticket/14297#comment:1
https://trac.sagemath.org/ticket/14297#comment:1
<ul>
<li><strong>type</strong>
changed from <em>PLEASE CHANGE</em> to <em>enhancement</em>
</li>
</ul>
TicketchapotonFri, 29 Mar 2013 13:37:51 GMTcc changed
https://trac.sagemath.org/ticket/14297#comment:2
https://trac.sagemath.org/ticket/14297#comment:2
<ul>
<li><strong>cc</strong>
<em>ncohen</em> <em>rbeezer</em> <em>dcoudert</em> <em>chapoton</em> added; <em>ncohen rbeezer dcoudert</em> removed
</li>
</ul>
TicketchapotonFri, 29 Mar 2013 19:48:37 GMTstatus changed; author set
https://trac.sagemath.org/ticket/14297#comment:3
https://trac.sagemath.org/ticket/14297#comment:3
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>Frédéric Chapoton</em>
</li>
</ul>
<p>
Here is a patch, please review !
</p>
TicketaziFri, 29 Mar 2013 20:05:15 GMT
https://trac.sagemath.org/ticket/14297#comment:4
https://trac.sagemath.org/ticket/14297#comment:4
<p>
Hello!
</p>
<p>
Thank you for the patch!
</p>
<p>
The patch appears to be correct but I am not sure it implements the proper conventions. For example on wolfram it is said that the complete graph is strongly regular while wikipedia and the book by Godsil and Royle (algebraic graph theory) both exclude complete graphs from the class of strongly regular graphs.
</p>
<p>
Hence I am not sure what to do in this case :-)
</p>
TicketchapotonFri, 03 May 2013 08:43:21 GMT
https://trac.sagemath.org/ticket/14297#comment:5
https://trac.sagemath.org/ticket/14297#comment:5
<p>
Nathann, any opinion about whether complete graphs are strongly regular or not ?
</p>
TicketncohenFri, 03 May 2013 08:50:54 GMT
https://trac.sagemath.org/ticket/14297#comment:6
https://trac.sagemath.org/ticket/14297#comment:6
<p>
I would say that they are. And that when I look at the code and your patch, it is probably what I tried to do but failed by giving the last block a wrong indentation, which you fixed... As there is an <code>if self.is_clique()</code> in this code, which returns nothing <code>:-P</code>
</p>
<p>
This is a problem of Dogma, though. What about deciding with head or tails ? Looks like the only honorable way out <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketaziFri, 03 May 2013 09:53:07 GMT
https://trac.sagemath.org/ticket/14297#comment:7
https://trac.sagemath.org/ticket/14297#comment:7
<p>
Eeeehm just checked in the book (<a class="ext-link" href="http://www.win.tue.nl/~aeb/2WF02/spectra.pdf"><span class="icon"></span>http://www.win.tue.nl/~aeb/2WF02/spectra.pdf</a> page 123 lol) by Brower and Haemers they exclude the complete graph and its complement as well.
</p>
<p>
I like gambling so we can toss a coin though I prefer to exclude complete graphs.
</p>
<p>
Also while we are at it:
</p>
<pre class="wiki">2293 degree = self.degree()
2294 k = degree[0]
2295 if not all(d == k for d in degree):
2296 return False
2297
2298 if self.is_clique():
</pre><p>
is it perhaps better to call self.is_regular()? I would like that since it somehow leaves any optimizations that is_regular *could* do and has the added benefit that this method does not break for the <a class="missing wiki">EmptyGraph?</a> (corner cases lol)
</p>
TicketaziFri, 03 May 2013 09:54:26 GMT
https://trac.sagemath.org/ticket/14297#comment:8
https://trac.sagemath.org/ticket/14297#comment:8
<p>
Also once we do the regularity check it might be better to simply check if the degree of self is order()-1?
</p>
TicketncohenFri, 03 May 2013 09:58:16 GMT
https://trac.sagemath.org/ticket/14297#comment:9
https://trac.sagemath.org/ticket/14297#comment:9
<blockquote class="citation">
<p>
Eeeehm just checked in the book (<a class="ext-link" href="http://www.win.tue.nl/~aeb/2WF02/spectra.pdf"><span class="icon"></span>http://www.win.tue.nl/~aeb/2WF02/spectra.pdf</a> page 123 lol) by Brower and Haemers they exclude the complete graph and its complement as well.
</p>
</blockquote>
<p>
Well, they are free to have their own opinion too. Mine is that I like to consider them as strongly regular graphs. Now we can put whatever you want in Sage, the one who agrees with a book is usually the one who is acknowledged to be right, nowadays <code>:-P</code>
</p>
<blockquote class="citation">
<p>
I like gambling so we can toss a coin though I prefer to exclude complete graphs.
</p>
<p>
Also while we are at it:
</p>
<pre class="wiki">2293 degree = self.degree()
2294 k = degree[0]
2295 if not all(d == k for d in degree):
2296 return False
2297
2298 if self.is_clique():
</pre><p>
is it perhaps better to call self.is_regular()? I would like that since it somehow leaves any optimizations that is_regular *could* do and has the added benefit that this method does not break for the <a class="missing wiki">EmptyGraph?</a> (corner cases lol)
</p>
</blockquote>
<p>
Oh. Well, then one would first have to take "any" vertex of the graph, compute its degree, then call <code>is_regular</code> on it with this degree as parameter. Otherwise it will call <code>self.degree()</code> twice. It's up to you !
</p>
<p>
Nathann
</p>
TicketaziFri, 03 May 2013 10:16:26 GMT
https://trac.sagemath.org/ticket/14297#comment:10
https://trac.sagemath.org/ticket/14297#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14297#comment:9" title="Comment 9">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Eeeehm just checked in the book (<a class="ext-link" href="http://www.win.tue.nl/~aeb/2WF02/spectra.pdf"><span class="icon"></span>http://www.win.tue.nl/~aeb/2WF02/spectra.pdf</a> page 123 lol) by Brower and Haemers they exclude the complete graph and its complement as well.
</p>
</blockquote>
<p>
Well, they are free to have their own opinion too. Mine is that I like to consider them as strongly regular graphs. Now we can put whatever you want in Sage, the one who agrees with a book is usually the one who is acknowledged to be right, nowadays <code>:-P</code>
</p>
</blockquote>
<p>
Luckily we don't have as many books saying different things as religions do :-)
</p>
<p>
Anyways, I personally like to have it that way because then there are other theorems for strongly regular graphs that follow naturally. For example a strongly regular graphs has precisely three distinct eigenvalues (which does not hold for the empty graph and complete graph)
</p>
<p>
That said I don't care what we do with this as long as its fine with you guys. Hence I let you and Frederic decide!
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
I like gambling so we can toss a coin though I prefer to exclude complete graphs.
</p>
<p>
Also while we are at it:
</p>
<pre class="wiki">2293 degree = self.degree()
2294 k = degree[0]
2295 if not all(d == k for d in degree):
2296 return False
2297
2298 if self.is_clique():
</pre><p>
is it perhaps better to call self.is_regular()? I would like that since it somehow leaves any optimizations that is_regular *could* do and has the added benefit that this method does not break for the <a class="missing wiki">EmptyGraph?</a> (corner cases lol)
</p>
</blockquote>
<p>
Oh. Well, then one would first have to take "any" vertex of the graph, compute its degree, then call <code>is_regular</code> on it with this degree as parameter. Otherwise it will call <code>self.degree()</code> twice. It's up to you !
</p>
</blockquote>
<p>
You got a point I overlooked that! BUT we can at least remove the is_clique part and check if the degree is order()-1 once we know its regular right??
</p>
<blockquote class="citation">
<p>
Nathann
</p>
</blockquote>
TicketncohenFri, 03 May 2013 10:21:07 GMT
https://trac.sagemath.org/ticket/14297#comment:11
https://trac.sagemath.org/ticket/14297#comment:11
<p>
Hellooooooooo !!!
</p>
<blockquote class="citation">
<p>
Luckily we don't have as many books saying different things as religions do :-)
</p>
</blockquote>
<p>
Yeah ? Well, try to publish a paper with you own notations for everything and see if it goes through. We don't have many religions because only one religion is allowed to exist <code>:-P</code>
</p>
<blockquote class="citation">
<p>
Anyways, I personally like to have it that way because then there are other theorems for strongly regular graphs that follow naturally. For example a strongly regular graphs has precisely three distinct eigenvalues (which does not hold for the empty graph and complete graph)
</p>
</blockquote>
<p>
Oh ? I didn't know that !
</p>
<blockquote class="citation">
<p>
That said I don't care what we do with this as long as its fine with you guys. Hence I let you and Frederic decide!
</p>
</blockquote>
<p>
Well, if you have a nice theorem like that, after all... So, Frederic ?
</p>
<blockquote class="citation">
<p>
You got a point I overlooked that! BUT we can at least remove the is_clique part and check if the degree is order()-1 once we know its regular right??
</p>
</blockquote>
<p>
Ahahahah. And what if is_clique just computes the number of edges, and if the number of edges is cached ? <code>:-P</code>
</p>
<p>
I don't know if it is, though. But calling <code>.size()</code> probably does not list all edges..... At least I hope !
</p>
<p>
Nathann
</p>
TicketaziFri, 03 May 2013 10:29:59 GMT
https://trac.sagemath.org/ticket/14297#comment:12
https://trac.sagemath.org/ticket/14297#comment:12
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14297#comment:11" title="Comment 11">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Hellooooooooo !!!
</p>
<blockquote class="citation">
<p>
Luckily we don't have as many books saying different things as religions do :-)
</p>
</blockquote>
<p>
Yeah ? Well, try to publish a paper with you own notations for everything and see if it goes through. We don't have many religions because only one religion is allowed to exist <code>:-P</code>
</p>
</blockquote>
<p>
That's the proper way to do it.. Isn't there only one God after all?
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Anyways, I personally like to have it that way because then there are other theorems for strongly regular graphs that follow naturally. For example a strongly regular graphs has precisely three distinct eigenvalues (which does not hold for the empty graph and complete graph)
</p>
</blockquote>
<p>
Oh ? I didn't know that !
</p>
</blockquote>
<p>
Yey,yes there are some nice results like that for SR graphs.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
That said I don't care what we do with this as long as its fine with you guys. Hence I let you and Frederic decide!
</p>
</blockquote>
<p>
Well, if you have a nice theorem like that, after all... So, Frederic ?
</p>
<blockquote class="citation">
<p>
You got a point I overlooked that! BUT we can at least remove the is_clique part and check if the degree is order()-1 once we know its regular right??
</p>
</blockquote>
<p>
Ahahahah. And what if is_clique just computes the number of edges, and if the number of edges is cached ? <code>:-P</code>
</p>
</blockquote>
<p>
LOL
</p>
<blockquote class="citation">
<p>
I don't know if it is, though. But calling <code>.size()</code> probably does not list all edges..... At least I hope !
</p>
</blockquote>
<p>
Of course it does and it does so in a fancy manner
</p>
<pre class="wiki">
2001 if self.loops(None):
2002 if self.multiple_edges(None):
2003 for j in self.iterator_verts():
2004 if self.has_edge(j, j, None):
2005 k += len(self.get_edge_label(j, j))
2006 else:
2007 for j in self.iterator_verts():
2008 if self.has_edge(j, j, None):
2009 k += 1
2010 i = (i - k) / 2
2011 return i + k
</pre><p>
Seems like we can add this to a new ticket? Or am I missing a detail that makes this code actually efficient?
</p>
<blockquote class="citation">
<p>
Nathann
</p>
</blockquote>
TicketncohenFri, 03 May 2013 10:35:18 GMT
https://trac.sagemath.org/ticket/14297#comment:13
https://trac.sagemath.org/ticket/14297#comment:13
<blockquote class="citation">
<p>
Seems like we can add this to a new ticket? Or am I missing a detail that makes this code actually efficient?
</p>
</blockquote>
<p>
Well, it's just for multiple edges and loops, and no sensible being would use that. This being said I do not know how to skip those tests, unless you create another counter for loops...
</p>
<p>
Nathann
</p>
TicketaziFri, 03 May 2013 10:40:38 GMT
https://trac.sagemath.org/ticket/14297#comment:14
https://trac.sagemath.org/ticket/14297#comment:14
<p>
Aaah, you're right! I just realized that.
</p>
<p>
Good, then its just for Frederic to decide the fate of the definition of SR graphs.
</p>
TicketchapotonSat, 04 May 2013 08:49:05 GMT
https://trac.sagemath.org/ticket/14297#comment:15
https://trac.sagemath.org/ticket/14297#comment:15
<p>
Here is new patch, that says that complete graphs are not strongly regular, and also that the empty graph is not strongly regular either.
</p>
TicketncohenSat, 04 May 2013 08:55:29 GMT
https://trac.sagemath.org/ticket/14297#comment:16
https://trac.sagemath.org/ticket/14297#comment:16
<p>
HMmm... Looks like you can remove the <code>if len(self)==0</code> and move the <code>return False</code> it contains to <code>elif self.size()==0</code> !
</p>
<p>
Nathann
</p>
TicketaziSat, 04 May 2013 09:02:50 GMT
https://trac.sagemath.org/ticket/14297#comment:17
https://trac.sagemath.org/ticket/14297#comment:17
<p>
What happens if I make
</p>
<pre class="wiki">graphs.CompleteGraph(10).complement().is_strongly_regular()
</pre>
TicketchapotonSat, 04 May 2013 09:15:58 GMT
https://trac.sagemath.org/ticket/14297#comment:18
https://trac.sagemath.org/ticket/14297#comment:18
<p>
New patch, handles the complements of complete graphs : they are not strongly regular
</p>
TicketchapotonSat, 04 May 2013 09:18:46 GMTattachment set
https://trac.sagemath.org/ticket/14297
https://trac.sagemath.org/ticket/14297
<ul>
<li><strong>attachment</strong>
set to <em>trac-14297-fc.patch</em>
</li>
</ul>
TicketchapotonSat, 04 May 2013 09:19:41 GMT
https://trac.sagemath.org/ticket/14297#comment:19
https://trac.sagemath.org/ticket/14297#comment:19
<p>
new patch. Nathann, your suggestion does not work because of the line <code>k=degree[0]</code>
</p>
<p>
instead I have removed the case self.size()==0
</p>
TicketncohenSat, 04 May 2013 09:21:00 GMTdescription changed
https://trac.sagemath.org/ticket/14297#comment:20
https://trac.sagemath.org/ticket/14297#comment:20
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/14297?action=diff&version=20">diff</a>)
</li>
</ul>
<p>
A reviewer's patch that removes a couple of lines.
</p>
<p>
Nathann
</p>
TicketchapotonSat, 04 May 2013 09:23:03 GMT
https://trac.sagemath.org/ticket/14297#comment:21
https://trac.sagemath.org/ticket/14297#comment:21
<p>
Well, in the mean time I have changed the patch..
</p>
TicketncohenSat, 04 May 2013 09:24:05 GMT
https://trac.sagemath.org/ticket/14297#comment:22
https://trac.sagemath.org/ticket/14297#comment:22
<p>
Ok, what about that ?
</p>
TicketchapotonSat, 04 May 2013 09:26:09 GMT
https://trac.sagemath.org/ticket/14297#comment:23
https://trac.sagemath.org/ticket/14297#comment:23
<p>
Why do you remove the lines about graphs with no edges ?
</p>
TicketncohenSat, 04 May 2013 09:27:07 GMT
https://trac.sagemath.org/ticket/14297#comment:24
https://trac.sagemath.org/ticket/14297#comment:24
<p>
Because when you test <code>self.size()==0</code> you deal with both cases at once : no edges, or no vertices !
</p>
<p>
Nathann
</p>
TicketncohenSat, 04 May 2013 09:28:00 GMT
https://trac.sagemath.org/ticket/14297#comment:25
https://trac.sagemath.org/ticket/14297#comment:25
<p>
oh, scuse me : <code>self.size()</code> is the number of edges. <code>self.order()</code> is the number of vertices. That's not very clear, it is true.
</p>
<p>
Nathann
</p>
TicketchapotonSat, 04 May 2013 09:30:29 GMT
https://trac.sagemath.org/ticket/14297#comment:26
https://trac.sagemath.org/ticket/14297#comment:26
<p>
ok, looks good to me, except the comment on the line which tests size()==0
</p>
TicketncohenSat, 04 May 2013 09:34:10 GMT
https://trac.sagemath.org/ticket/14297#comment:27
https://trac.sagemath.org/ticket/14297#comment:27
<p>
Nobody would really mind if you talked about an "empty graph" for a graph with no edges I guess, but it is now fixed !
</p>
<p>
Nathann
</p>
TicketncohenSat, 04 May 2013 09:34:22 GMTattachment set
https://trac.sagemath.org/ticket/14297
https://trac.sagemath.org/ticket/14297
<ul>
<li><strong>attachment</strong>
set to <em>trac_14297-rev.patch</em>
</li>
</ul>
TicketchapotonSat, 04 May 2013 09:40:16 GMT
https://trac.sagemath.org/ticket/14297#comment:28
https://trac.sagemath.org/ticket/14297#comment:28
<p>
ok, maybe it's time for a positive review ?
</p>
TicketncohenSat, 04 May 2013 09:59:49 GMTreviewer set
https://trac.sagemath.org/ticket/14297#comment:29
https://trac.sagemath.org/ticket/14297#comment:29
<ul>
<li><strong>reviewer</strong>
set to <em>Frédéric Chapoton, Nathann Cohen</em>
</li>
</ul>
<p>
Well, I agree with your patch so if you agree with mine... <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketncohenSat, 04 May 2013 10:00:41 GMTreviewer changed
https://trac.sagemath.org/ticket/14297#comment:30
https://trac.sagemath.org/ticket/14297#comment:30
<ul>
<li><strong>reviewer</strong>
changed from <em>Frédéric Chapoton, Nathann Cohen</em> to <em>Jernej Azarija, Frédéric Chapoton, Nathann Cohen</em>
</li>
</ul>
TicketchapotonSat, 04 May 2013 10:02:10 GMTstatus changed
https://trac.sagemath.org/ticket/14297#comment:31
https://trac.sagemath.org/ticket/14297#comment:31
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
ok, done
</p>
TicketjdemeyerTue, 07 May 2013 09:05:32 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/14297#comment:32
https://trac.sagemath.org/ticket/14297#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>
<li><strong>merged</strong>
set to <em>sage-5.10.beta2</em>
</li>
</ul>
Ticket