Opened 6 years ago

Closed 6 years ago

#14297 closed enhancement (fixed)

is_strongly_regular does not handle complete graphs

Reported by: azi Owned by: jason, ncohen, rlm
Priority: minor Milestone: sage-5.10
Component: graph theory Keywords:
Cc: ncohen, rbeezer, dcoudert, chapoton Merged in: sage-5.10.beta2
Authors: Frédéric Chapoton Reviewers: Jernej Azarija, Frédéric Chapoton, Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

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:

Attachments (2)

trac-14297-fc.patch (2.4 KB) - added by chapoton 6 years ago.
trac_14297-rev.patch (907 bytes) - added by ncohen 6 years ago.

Download all attachments as: .zip

Change History (34)

comment:1 Changed 6 years ago by kcrisman

  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 6 years ago by chapoton

  • Cc ncohen rbeezer dcoudert chapoton added; ncohen rbeezer dcoudert removed

comment:3 Changed 6 years ago by chapoton

  • Authors set to Frédéric Chapoton
  • Status changed from new to needs_review

Here is a patch, please review !

comment:4 Changed 6 years ago by azi

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

comment:5 Changed 6 years ago by chapoton

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

comment:6 Changed 6 years ago by ncohen

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

comment:7 follow-up: Changed 6 years ago by azi

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)

comment:8 Changed 6 years ago by azi

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

comment:9 in reply to: ↑ 7 ; follow-up: Changed 6 years ago by 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

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

comment:10 in reply to: ↑ 9 ; follow-up: Changed 6 years ago by azi

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

comment:11 in reply to: ↑ 10 ; follow-up: Changed 6 years ago by 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

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

comment:12 in reply to: ↑ 11 ; follow-up: Changed 6 years ago by azi

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

comment:13 in reply to: ↑ 12 Changed 6 years ago by ncohen

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

comment:14 Changed 6 years ago by azi

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

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

comment:15 Changed 6 years ago by 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.

comment:16 Changed 6 years ago by ncohen

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

Nathann

comment:17 Changed 6 years ago by azi

What happens if I make

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

comment:18 Changed 6 years ago by chapoton

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

Changed 6 years ago by chapoton

comment:19 Changed 6 years ago by 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

comment:20 Changed 6 years ago by ncohen

  • Description modified (diff)

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

Nathann

comment:21 Changed 6 years ago by chapoton

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

comment:22 Changed 6 years ago by ncohen

Ok, what about that ?

comment:23 Changed 6 years ago by chapoton

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

comment:24 Changed 6 years ago by ncohen

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

Nathann

comment:25 Changed 6 years ago by ncohen

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

comment:26 Changed 6 years ago by chapoton

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

comment:27 Changed 6 years ago by ncohen

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

Changed 6 years ago by ncohen

comment:28 Changed 6 years ago by chapoton

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

comment:29 Changed 6 years ago by ncohen

  • Reviewers set to Frédéric Chapoton, Nathann Cohen

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

Nathann

comment:30 Changed 6 years ago by ncohen

  • Reviewers changed from Frédéric Chapoton, Nathann Cohen to Jernej Azarija, Frédéric Chapoton, Nathann Cohen

comment:31 Changed 6 years ago by chapoton

  • Status changed from needs_review to positive_review

ok, done

comment:32 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.10.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.