is_strongly_regular does not handle complete graphs

[Jernej Azarija]

It appears that the strongly regular thing does not handle complete graphs

sage: G.is_strongly_regular()
sage: 

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.

Apply:

• trac-14297-fc.patch​
• trac_14297-rev.patch​

[Frédéric Chapoton]

Here is a patch, please review !

[Jernej Azarija]

Hello!

Thank you for the patch!

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.

Hence I am not sure what to do in this case :-)

[Frédéric Chapoton]

Nathann, any opinion about whether complete graphs are strongly regular or not ?

[Nathann Cohen]

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 if self.is_clique() in this code, which returns nothing :-P

This is a problem of Dogma, though. What about deciding with head or tails ? Looks like the only honorable way out :-P

Nathann

[Jernej Azarija]

Eeeehm just checked in the book (​http://www.win.tue.nl/~aeb/2WF02/spectra.pdf page 123 lol) by Brower and Haemers they exclude the complete graph and its complement as well.

I like gambling so we can toss a coin though I prefer to exclude complete graphs.

Also while we are at it:

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():

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 EmptyGraph? (corner cases lol)

[Jernej Azarija]

Also once we do the regularity check it might be better to simply check if the degree of self is order()-1?

[Nathann Cohen]

Eeeehm just checked in the book (​http://www.win.tue.nl/~aeb/2WF02/spectra.pdf page 123 lol) by Brower and Haemers they exclude the complete graph and its complement as well.

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 :-P

I like gambling so we can toss a coin though I prefer to exclude complete graphs.

Also while we are at it:

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():

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 EmptyGraph? (corner cases lol)

Oh. Well, then one would first have to take "any" vertex of the graph, compute its degree, then call is_regular on it with this degree as parameter. Otherwise it will call self.degree() twice. It's up to you !

Nathann

[Jernej Azarija]

Replying to ncohen:

Eeeehm just checked in the book (​http://www.win.tue.nl/~aeb/2WF02/spectra.pdf page 123 lol) by Brower and Haemers they exclude the complete graph and its complement as well.

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 :-P

Luckily we don't have as many books saying different things as religions do :-)

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)

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!

I like gambling so we can toss a coin though I prefer to exclude complete graphs.

Also while we are at it:

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():

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 EmptyGraph? (corner cases lol)

Oh. Well, then one would first have to take "any" vertex of the graph, compute its degree, then call is_regular on it with this degree as parameter. Otherwise it will call self.degree() twice. It's up to you !

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??

Nathann

[Nathann Cohen]

Hellooooooooo !!!

Luckily we don't have as many books saying different things as religions do :-)

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 :-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)

Oh ? I didn't know that !

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!

Well, if you have a nice theorem like that, after all... So, Frederic ?

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??

Ahahahah. And what if is_clique just computes the number of edges, and if the number of edges is cached ? :-P

I don't know if it is, though. But calling .size() probably does not list all edges..... At least I hope !

Nathann

[Jernej Azarija]

Replying to ncohen:

Hellooooooooo !!!

Luckily we don't have as many books saying different things as religions do :-)

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 :-P

That's the proper way to do it.. Isn't there only one God after all?

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)

Oh ? I didn't know that !

Yey,yes there are some nice results like that for SR graphs.

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!

Well, if you have a nice theorem like that, after all... So, Frederic ?

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??

Ahahahah. And what if is_clique just computes the number of edges, and if the number of edges is cached ? :-P

LOL

I don't know if it is, though. But calling .size() probably does not list all edges..... At least I hope !

Of course it does and it does so in a fancy manner

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

Seems like we can add this to a new ticket? Or am I missing a detail that makes this code actually efficient?

Nathann

[Nathann Cohen]

Seems like we can add this to a new ticket? Or am I missing a detail that makes this code actually efficient?

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...

Nathann

[Jernej Azarija]

Aaah, you're right! I just realized that.

Good, then its just for Frederic to decide the fate of the definition of SR graphs.

[Frédéric Chapoton]

Here is new patch, that says that complete graphs are not strongly regular, and also that the empty graph is not strongly regular either.

[Nathann Cohen]

HMmm... Looks like you can remove the if len(self)==0 and move the return False it contains to elif self.size()==0 !

Nathann

[Jernej Azarija]

What happens if I make

graphs.CompleteGraph(10).complement().is_strongly_regular()

[Frédéric Chapoton]

New patch, handles the complements of complete graphs : they are not strongly regular

[Frédéric Chapoton]

new patch. Nathann, your suggestion does not work because of the line k=degree[0]

instead I have removed the case self.size()==0

[Nathann Cohen]

A reviewer's patch that removes a couple of lines.

Nathann

[Frédéric Chapoton]

Well, in the mean time I have changed the patch..

[Nathann Cohen]

Ok, what about that ?

[Frédéric Chapoton]

Why do you remove the lines about graphs with no edges ?

[Nathann Cohen]

Because when you test self.size()==0 you deal with both cases at once : no edges, or no vertices !

Nathann

[Nathann Cohen]

oh, scuse me : self.size() is the number of edges. self.order() is the number of vertices. That's not very clear, it is true.

Nathann

[Frédéric Chapoton]

ok, looks good to me, except the comment on the line which tests size()==0

[Nathann Cohen]

Nobody would really mind if you talked about an "empty graph" for a graph with no edges I guess, but it is now fixed !

Nathann

[Frédéric Chapoton]

ok, maybe it's time for a positive review ?

[Nathann Cohen]

Well, I agree with your patch so if you agree with mine... :-)

Nathann

[Frédéric Chapoton]

ok, done