Opened 10 years ago

Closed 10 years ago

#14297 closed enhancement (fixed)

is_strongly_regular does not handle complete graphs

Reported by: Jernej Azarija Owned by: jason, ncohen, rlm
Priority: minor Milestone: sage-5.10
Component: graph theory Keywords:
Cc: Nathann Cohen, Rob Beezer, David Coudert, Frédéric 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:

Status badges

Description (last modified by Nathann Cohen)

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 Frédéric Chapoton 10 years ago.
trac_14297-rev.patch (907 bytes) - added by Nathann Cohen 10 years ago.

Download all attachments as: .zip

Change History (34)

comment:1 Changed 10 years ago by Karl-Dieter Crisman

Type: PLEASE CHANGEenhancement

comment:2 Changed 10 years ago by Frédéric Chapoton

Cc: Nathann Cohen Rob Beezer David Coudert Frédéric Chapoton added; ncohen rbeezer dcoudert removed

comment:3 Changed 10 years ago by Frédéric Chapoton

Authors: Frédéric Chapoton
Status: newneeds_review

Here is a patch, please review !

comment:4 Changed 10 years ago by 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 :-)

comment:5 Changed 10 years ago by Frédéric Chapoton

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

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

comment:7 Changed 10 years ago by 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)

comment:8 Changed 10 years ago by Jernej Azarija

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 ; Changed 10 years ago by 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

comment:10 in reply to:  9 ; Changed 10 years ago by 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

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

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

comment:13 in reply to:  12 Changed 10 years ago by 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

comment:14 Changed 10 years ago by 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.

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

comment:16 Changed 10 years ago by 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

comment:17 Changed 10 years ago by Jernej Azarija

What happens if I make

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

comment:18 Changed 10 years ago by Frédéric Chapoton

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

Changed 10 years ago by Frédéric Chapoton

Attachment: trac-14297-fc.patch added

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

comment:20 Changed 10 years ago by Nathann Cohen

Description: modified (diff)

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

Nathann

comment:21 Changed 10 years ago by Frédéric Chapoton

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

comment:22 Changed 10 years ago by Nathann Cohen

Ok, what about that ?

comment:23 Changed 10 years ago by Frédéric Chapoton

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

comment:24 Changed 10 years ago by Nathann Cohen

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

Nathann

comment:25 Changed 10 years ago by 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

comment:26 Changed 10 years ago by Frédéric Chapoton

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

comment:27 Changed 10 years ago by 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

Changed 10 years ago by Nathann Cohen

Attachment: trac_14297-rev.patch added

comment:28 Changed 10 years ago by Frédéric Chapoton

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

comment:29 Changed 10 years ago by Nathann Cohen

Reviewers: Frédéric Chapoton, Nathann Cohen

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

Nathann

comment:30 Changed 10 years ago by Nathann Cohen

Reviewers: Frédéric Chapoton, Nathann CohenJernej Azarija, Frédéric Chapoton, Nathann Cohen

comment:31 Changed 10 years ago by Frédéric Chapoton

Status: needs_reviewpositive_review

ok, done

comment:32 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.10.beta2
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.