strongly_regular_graph() crashes when mu=0

[nathanncohen]

Reported by Georgi Guninski:

sage: graphs.strongly_regular_graph(10,2,1)
<crash>

(and more of these).

This is because of a "%0" and "/0" in the code in several places. Which happened, as it was confusion over the corner cases mu=0 and mu=k.

CC: @dimpase

Component: graph theory

Author: Nathann Cohen, Dima Pasechnik

Branch/Commit: 03c0c20

Reviewer: Nathann Cohen, Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/19712

[nathanncohen]

New commits:

d499a32

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

[nathanncohen]

Commit: d499a32

[nathanncohen]

Branch: public/19712

[dimpase]

comment:2

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

[nathanncohen]

comment:3

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

[dimpase]

comment:4

Replying to @nathanncohen:

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.

[nathanncohen]

comment:5

I'd rather keep mu=0 - the classification of graphs in this case is trivial.

Okayokay. Can you update the branch then?

Nathann

[sagetrac-git]

Changed commit from d499a32 to ca5fdfb

[sagetrac-git]

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

[nathanncohen]

comment:7

Unless you agree with that ?

Nathann

[dimpase]

comment:8

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

[dimpase]

comment:9

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).

[sagetrac-git]

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

[sagetrac-git]

Changed commit from ca5fdfb to eeedb3b

[dimpase]

comment:12

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)

[nathanncohen]

comment:13

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

[dimpase]

comment:14

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.

[dimpase]

comment:15

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

[dimpase]

comment:16

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

[nathanncohen]

comment:17

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

[dimpase]

comment:18

Replying to @nathanncohen:

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

OK, will do.

[sagetrac-git]

Changed commit from eeedb3b to 5bb551e

[sagetrac-git]

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

0528dce	Merge branch 'public/19712' of git://trac.sagemath.org/sage into muzero
5bb551e	complete multipartite graphs etc

[dimpase]

comment:20

OK, ready for review!

[dimpase]

Changed author from Nathann Cohen to Nathann Cohen, Dima Pasechnik

[sagetrac-git]

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

2890c86	trac #19712: strongly_regular_graph() crashes when mu=0
03c0c20	complete multipartite graphs etc

[sagetrac-git]

Changed commit from 5bb551e to 03c0c20

[nathanncohen]

comment:23

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

[dimpase]

comment:24

Replying to @nathanncohen:

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"...

[nathanncohen]

comment:25

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

[nathanncohen]

Reviewer: Nathann Cohen, Dima Pasechnik

[dimpase]

comment:27

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

[vbraun]

Changed branch from public/19712 to 03c0c20