Opened 4 years ago

Closed 4 years ago

#19712 closed defect (fixed)

strongly_regular_graph() crashes when mu=0

Reported by: ncohen Owned by:
Priority: critical Milestone: sage-7.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 dimpase)

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 4 years ago by ncohen

  • Branch set to public/19712
  • Commit set to d499a32eb2434f5165e3f27bfb075a68f7796b65
  • Status changed from new to needs_review

New commits:

d499a32trac #19712: strongly_regular_graph() crashes when mu=0

comment:2 Changed 4 years ago by dimpase

I presume you're not changing the definition, i.e. you still allow mu=0, right?

comment:3 follow-up: Changed 4 years ago by ncohen

Well, is mu=0 allowed for strongly regular graphs? If they are assumed to be connected + non-complete, then mu>0 isn't it?

Nathann

comment:4 in reply to: ↑ 3 ; follow-up: Changed 4 years ago by dimpase

Replying to ncohen:

Well, is mu=0 allowed for strongly regular graphs? If they are assumed to be connected + non-complete, 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 4 years ago by ncohen

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 4 years ago by git

  • Commit changed from d499a32eb2434f5165e3f27bfb075a68f7796b65 to ca5fdfb9419f06b84b1bc1c2c3e46f3e0ee446d8

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

ca5fdfbtrac #19712: strongly_regular_graph() crashes when mu=0

comment:7 Changed 4 years ago by ncohen

Unless you agree with that ?

Nathann

comment:8 Changed 4 years ago by dimpase

  • 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 4 years ago by dimpase

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 4 years ago by git

  • Commit changed from ca5fdfb9419f06b84b1bc1c2c3e46f3e0ee446d8 to eeedb3b4b05454c62249fe0577e4b7a84e9f2338

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

eeedb3btrac #19712: strongly_regular_graph() crashes when mu=0

comment:11 Changed 4 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:12 Changed 4 years ago by dimpase

if we allow mu=0 then the disjoint union of m copies of K_n is s.r.g. (and its complement, complete m-partite 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 4 years ago by ncohen

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 4 years ago by dimpase

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 4 years ago by dimpase

or allow mu=0, but make sure that _check_database() does not count these graphs.

comment:16 Changed 4 years ago by dimpase

well, let me know whether you like me to fix the patch, or rather do it yourself?

comment:17 follow-up: Changed 4 years ago by ncohen

If you have time to deal with it today I certainly won't mind :-P

comment:18 in reply to: ↑ 17 Changed 4 years ago by dimpase

Replying to ncohen:

If you have time to deal with it today I certainly won't mind :-P

OK, will do.

comment:19 Changed 4 years ago by git

  • Commit changed from eeedb3b4b05454c62249fe0577e4b7a84e9f2338 to 5bb551e4585722cb1be2fcb20c172b6f81262bae

Branch pushed to git repo; I updated commit sha1. New commits:

0528dceMerge branch 'public/19712' of git://trac.sagemath.org/sage into muzero
5bb551ecomplete multipartite graphs etc

comment:20 Changed 4 years ago by dimpase

OK, ready for review!

comment:21 Changed 4 years ago by dimpase

  • Authors changed from Nathann Cohen to Nathann Cohen, Dima Pasechnik
  • Description modified (diff)
  • Priority changed from major to critical

comment:22 Changed 4 years ago by git

  • Commit changed from 5bb551e4585722cb1be2fcb20c172b6f81262bae to 03c0c200a5bbe165fca95f2787be57c8fc7a51a1

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

2890c86trac #19712: strongly_regular_graph() crashes when mu=0
03c0c20complete multipartite graphs etc

comment:23 follow-up: Changed 4 years ago by 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 == k-1 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 4 years ago by dimpase

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 == k-1 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?..

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 4 years ago by ncohen

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 4 years ago by ncohen

  • Reviewers set to Nathann Cohen, Dima Pasechnik
  • Status changed from needs_review to positive_review

comment:27 Changed 4 years ago by dimpase

Great, thanks! Hopefully it can get into 6.10, still...

comment:28 Changed 4 years ago by vbraun

  • Branch changed from public/19712 to 03c0c200a5bbe165fca95f2787be57c8fc7a51a1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.