Opened 5 years ago
Last modified 5 years ago
#19712 closed defect
strongly_regular_graph() crashes when mu=0 — at Version 21
Reported by:  ncohen  Owned by:  

Priority:  critical  Milestone:  sage7.0 
Component:  graph theory  Keywords:  
Cc:  dimpase  Merged in:  
Authors:  Nathann Cohen, Dima Pasechnik  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  public/19712 (Commits, GitHub, GitLab)  Commit:  5bb551e4585722cb1be2fcb20c172b6f81262bae 
Dependencies:  Stopgaps: 
Description (last modified by )
Reported by Georgi Guninski:
sage: graphs.strongly_regular_graph(10,2,1) <crash>
(and more of these).
This is because of a "<whatever>%0" and "<whatever>/0" in the code in several places. Which happened, as it was confusion over the corner cases mu=0 and mu=k.
Change History (21)
comment:1 Changed 5 years ago by
 Branch set to public/19712
 Commit set to d499a32eb2434f5165e3f27bfb075a68f7796b65
 Status changed from new to needs_review
comment:2 Changed 5 years ago by
I presume you're not changing the definition, i.e. you still allow mu=0, right?
comment:3 followup: ↓ 4 Changed 5 years ago by
Well, is mu=0 allowed for strongly regular graphs? If they are assumed to be connected + noncomplete, then mu>0 isn't it?
Nathann
comment:4 in reply to: ↑ 3 ; followup: ↓ 5 Changed 5 years ago by
Replying to ncohen:
Well, is mu=0 allowed for strongly regular graphs? If they are assumed to be connected + noncomplete, then mu>0 isn't it?
Well, either we require that the graph AND its complement are connected, or we live with mu=0.
Don't we have mu=0 in 6.9? If yes, we'd need to do deprecation to switch to mu>0...
I'd rather keep mu=0  the classification of graphs in this case is trivial.
comment:5 in reply to: ↑ 4 Changed 5 years ago by
I'd rather keep mu=0  the classification of graphs in this case is trivial.
Okayokay. Can you update the branch then?
Nathann
comment:6 Changed 5 years ago by
 Commit changed from d499a32eb2434f5165e3f27bfb075a68f7796b65 to ca5fdfb9419f06b84b1bc1c2c3e46f3e0ee446d8
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
ca5fdfb  trac #19712: strongly_regular_graph() crashes when mu=0

comment:7 Changed 5 years ago by
Unless you agree with that ?
Nathann
comment:8 Changed 5 years ago by
 Status changed from needs_review to needs_work
here is a problem; not everything to do with strong regularity goes through the function you just changed:
sage: g=graphs.CompleteBipartiteGraph(3,3) sage: g.is_strongly_regular() True sage: g.is_strongly_regular(parameters=True) (6, 3, 0, 3) sage: graphs.strongly_regular_graph(*g.is_strongly_regular(parameters=True))  ValueError Traceback (most recent call last) ... ValueError: There exists no (6, 3, 0, 3)strongly regular graph
comment:9 Changed 5 years ago by
because of the latter, I always thought that Sage does allow mu=0... In fact, this is an inconsistency present already before this branch.
Also, note the docs of is_strongly_regular()
that do not forbig mu=0 (or mu=0 for the complementary graph).
comment:10 Changed 5 years ago by
 Commit changed from ca5fdfb9419f06b84b1bc1c2c3e46f3e0ee446d8 to eeedb3b4b05454c62249fe0577e4b7a84e9f2338
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
eeedb3b  trac #19712: strongly_regular_graph() crashes when mu=0

comment:11 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:12 Changed 5 years ago by
if we allow mu=0 then the disjoint union of m copies of K_n
is s.r.g.
(and its complement, complete mpartite graph with parts of size n). not only for m=2.
E.g. for m=3, n=5 one gets
(15, 4, 3, 0)
and
(15, 10, 5, 10)
comment:13 Changed 5 years ago by
The wikipedia page says that often both are excluded, i.e. both the disjoint complete graphs and the complete bipartite graphs.
Now, my former patch excluded both and you complained about it. Now, you seem to complain that I only exclude one of the two.
Make up your mind.
Nathann
comment:14 Changed 5 years ago by
well, I am OK with anything that makes is_strongly_regular()
and strongly_regular_graph()
consistent with each other.
It looks easier after all to make is_strongly_regular()
reject more things (to exclude mu=0 for graph or its complement); an added benefit of this is that it will be consistent with Andries' DB.
comment:15 Changed 5 years ago by
or allow mu=0, but make sure that _check_database() does not count these graphs.
comment:16 Changed 5 years ago by
well, let me know whether you like me to fix the patch, or rather do it yourself?
comment:17 followup: ↓ 18 Changed 5 years ago by
If you have time to deal with it today I certainly won't mind :P
comment:18 in reply to: ↑ 17 Changed 5 years ago by
comment:19 Changed 5 years ago by
 Commit changed from eeedb3b4b05454c62249fe0577e4b7a84e9f2338 to 5bb551e4585722cb1be2fcb20c172b6f81262bae
comment:20 Changed 5 years ago by
OK, ready for review!
comment:21 Changed 5 years ago by
 Description modified (diff)
 Priority changed from major to critical
New commits:
trac #19712: strongly_regular_graph() crashes when mu=0