Opened 3 years ago
Closed 3 years ago
#19712 closed defect (fixed)
strongly_regular_graph() crashes when mu=0
Reported by:  ncohen  Owned by:  

Priority:  critical  Milestone:  sage7.0 
Component:  graph theory  Keywords:  
Cc:  dimpase  Merged in:  
Authors:  Nathann Cohen, Dima Pasechnik  Reviewers:  Nathann Cohen, Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  03c0c20 (Commits)  Commit:  03c0c200a5bbe165fca95f2787be57c8fc7a51a1 
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 (28)
comment:1 Changed 3 years ago by
 Branch set to public/19712
 Commit set to d499a32eb2434f5165e3f27bfb075a68f7796b65
 Status changed from new to needs_review
comment:2 Changed 3 years ago by
I presume you're not changing the definition, i.e. you still allow mu=0, right?
comment:3 followup: ↓ 4 Changed 3 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 3 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 3 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 3 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 3 years ago by
Unless you agree with that ?
Nathann
comment:8 Changed 3 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 3 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 3 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 3 years ago by
 Status changed from needs_work to needs_review
comment:12 Changed 3 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 3 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 3 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 3 years ago by
or allow mu=0, but make sure that _check_database() does not count these graphs.
comment:16 Changed 3 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 3 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 3 years ago by
comment:19 Changed 3 years ago by
 Commit changed from eeedb3b4b05454c62249fe0577e4b7a84e9f2338 to 5bb551e4585722cb1be2fcb20c172b6f81262bae
comment:20 Changed 3 years ago by
OK, ready for review!
comment:21 Changed 3 years ago by
 Description modified (diff)
 Priority changed from major to critical
comment:22 Changed 3 years ago by
 Commit changed from 5bb551e4585722cb1be2fcb20c172b6f81262bae to 03c0c200a5bbe165fca95f2787be57c8fc7a51a1
comment:23 followup: ↓ 24 Changed 3 years ago by
Looks good to me. I don't like the 'mu=0' much, given that it actually "isn't defined" but well, that's life. Well. What would you think of testing l == k1
instead or testing mu=0
, however? Would do the trick to, and so we wouldn't suppose that the undefined 'mu' must be equal to 0?..
As you like.
Nathann
comment:24 in reply to: ↑ 23 Changed 3 years ago by
Replying to ncohen:
Looks good to me. I don't like the 'mu=0' much, given that it actually "isn't defined" but well, that's life. Well. What would you think of testing
l == k1
instead or testingmu=0
, however? Would do the trick to, and so we wouldn't suppose that the undefined 'mu' must be equal to 0?..
I don't see what do you mean when you say "the undefined 'mu'". Do you mean that it is an optional parameter? But it is uniquely determined by the other parameters, so it's not what I call "undefined"...
comment:25 Changed 3 years ago by
Oh, sorry. I meant that for complete graphs it is undefined. But indeed it is not 'as bad' as I thought. No problem then. I'll run the tests and change this ticket's status. Thanks.
Nathann
comment:26 Changed 3 years ago by
 Reviewers set to Nathann Cohen, Dima Pasechnik
 Status changed from needs_review to positive_review
comment:27 Changed 3 years ago by
Great, thanks! Hopefully it can get into 6.10, still...
comment:28 Changed 3 years ago by
 Branch changed from public/19712 to 03c0c200a5bbe165fca95f2787be57c8fc7a51a1
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #19712: strongly_regular_graph() crashes when mu=0