Opened 9 years ago
Closed 9 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 )
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)
Change History (34)
comment:1 Changed 9 years ago by
- Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 9 years ago by
- Cc ncohen rbeezer dcoudert chapoton added; ncohen rbeezer dcoudert removed
comment:3 Changed 9 years ago by
- Status changed from new to needs_review
comment:4 Changed 9 years ago by
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 9 years ago by
Nathann, any opinion about whether complete graphs are strongly regular or not ?
comment:6 Changed 9 years ago by
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: ↓ 9 Changed 9 years ago by
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 9 years ago by
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: ↓ 10 Changed 9 years ago by
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: ↓ 11 Changed 9 years ago by
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 callself.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: ↓ 12 Changed 9 years ago by
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: ↓ 13 Changed 9 years ago by
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 9 years ago by
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 9 years ago by
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 9 years ago by
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 9 years ago by
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 9 years ago by
What happens if I make
graphs.CompleteGraph(10).complement().is_strongly_regular()
comment:18 Changed 9 years ago by
New patch, handles the complements of complete graphs : they are not strongly regular
Changed 9 years ago by
comment:19 Changed 9 years ago by
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 9 years ago by
- Description modified (diff)
A reviewer's patch that removes a couple of lines.
Nathann
comment:21 Changed 9 years ago by
Well, in the mean time I have changed the patch..
comment:22 Changed 9 years ago by
Ok, what about that ?
comment:23 Changed 9 years ago by
Why do you remove the lines about graphs with no edges ?
comment:24 Changed 9 years ago by
Because when you test self.size()==0
you deal with both cases at once : no edges, or no vertices !
Nathann
comment:25 Changed 9 years ago by
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 9 years ago by
ok, looks good to me, except the comment on the line which tests size()==0
comment:27 Changed 9 years ago by
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 9 years ago by
comment:28 Changed 9 years ago by
ok, maybe it's time for a positive review ?
comment:29 Changed 9 years ago by
- 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 9 years ago by
- Reviewers changed from Frédéric Chapoton, Nathann Cohen to Jernej Azarija, Frédéric Chapoton, Nathann Cohen
comment:32 Changed 9 years ago by
- Merged in set to sage-5.10.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
Here is a patch, please review !