Opened 6 years ago

Closed 6 years ago

#15864 closed defect (fixed)

Graph.is_distance_regular is awfully wrong

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.2
Component: graph theory Keywords:
Cc: dimpase Merged in:
Authors: Nathann Cohen Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues: fix the mess with commits
Branch: faffd86 (Commits) Commit: faffd868037a80a5ad04a5a7cf260f13da4a0e35
Dependencies: Stopgaps:

Description

As reported in [1] is_distance_regular is SOooooooo awfully wrong that the definition it uses is ... just wrong. I'm sorry for that :-/

The current patch fixes it.

Nathann

[1] http://trac.sagemath.org/ticket/14619#comment:27

Change History (34)

comment:1 Changed 6 years ago by ncohen

  • Branch set to u/ncohen/15684
  • Status changed from new to needs_review

comment:2 Changed 6 years ago by ncohen

  • Branch changed from u/ncohen/15684 to u/ncohen/15864
  • Commit set to f6541444499809d3af167c9a3632baa98449b0f2

New commits:

f654144trac #15864: Graph.is_distance_regular is awfully wrong

comment:3 follow-up: Changed 6 years ago by dimpase

IMHO

sage: g.is_distance_regular(parameters = True)

is terribly confusing to the user. Indeed, is_distance_regular is meant to return True or False, just like any other is_blahbla member functions are. There should be a member function named something like distance_regularity_parameters which would return the parameters (what it returns for a non-distance-regular graph, is open to discussion - e.g. it can even return lists of all the different values, or empty entries for the values which are not-constant.

comment:4 in reply to: ↑ 3 Changed 6 years ago by ncohen

Yooooooooo !

is terribly confusing to the user. Indeed, is_distance_regular is meant to return True or False, just like any other is_blahbla member functions are.

Well. Not exactly "all" :-P

I did this quite quite often in the graph code, in order to avoid having to create three functions for every feature : one which returns True/False?, one which returns a certificate, and a hidden one which returns both. Besides it is weird to call a function which is meant to return a certificate when you do not even know if the graph is distance-regular or not, and there is a risk that users would call BOTH functions (first boolean check THEN certificate) and so compute everythin twice.

There should be a member function named something like distance_regularity_parameters which would return the parameters (what it returns for a non-distance-regular graph, is open to discussion - e.g. it can even return lists of all the different values, or empty entries for the values which are not-constant.

Well... It's the usual way to do stuff, but with Python we do not really have to follow this limitation as there is no return type... is_perfect can ive you an odd hole/antihole, is_forest returns cycles, is_planar gives you a K5/K33 minor. Really, it's cool :-P

Nathann

comment:5 Changed 6 years ago by dimpase

in the line A regular graph G is distance-regular if for any integers j,k the value... the word regular is not needed, as you can take j=k=0 and u=v.

comment:6 Changed 6 years ago by dimpase

in the literature the order of these lists:

sage: g.is_distance_regular(parameters = True)
        ([0, 1, 1], [3, 2, 0])

is normally the opposite, and the last entry, which is always 0, 0 in the list beginning with the valence is omitted, and the 1st entry, always 0, in the other list is omitted too. I suggest we follow this convention. I.e. here it should be ([3,2],[1,1])

comment:7 Changed 6 years ago by dimpase

I'm doing a reviewer patch.

comment:8 follow-up: Changed 6 years ago by dimpase

  • Branch changed from u/ncohen/15864 to u/dimpase/ticket/15864
  • Created changed from 02/26/14 15:13:20 to 02/26/14 15:13:20
  • Modified changed from 02/28/14 09:17:06 to 02/28/14 09:17:06

comment:9 in reply to: ↑ 8 Changed 6 years ago by dimpase

  • Commit changed from f6541444499809d3af167c9a3632baa98449b0f2 to e5a990dd8f2b0ff38dcee683e9d59182d2614eb1

Replying to dimpase: Nathann, if you're happy with my changes, I'll make it positive review. Let's postpone foo.is_bla... cleanup to another ticket.


New commits:

e5a990dfixed typos, corrected the definitions of b, c, chnaged the way they are returned, one more example

comment:10 Changed 6 years ago by git

  • Commit changed from e5a990dd8f2b0ff38dcee683e9d59182d2614eb1 to 0b540be503548ad881305f820552bc06d14b0771

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

0b540bedocs fix: returning (b,c), not (c,b)

comment:11 Changed 6 years ago by ncohen

Yooooooooooooo Dima !

I am back to work, in Brussels. That's a good news :-P

Aren't you afraid of the fact that c[i] is not c_i but c_{i+1} ? Don't you think it's dangerous ?

Nathann

comment:12 Changed 6 years ago by dimpase

Well, this is the standard notation. Might be a bit awkward, indeed. These numbers are best understood as entries of the intersection matrix, which in this case happens to be 3-diagonal.

comment:13 follow-up: Changed 6 years ago by ncohen

Why don't we set the missing entries to None ? Like c_0 and b_d ?

Nathann

comment:14 in reply to: ↑ 13 Changed 6 years ago by dimpase

Replying to ncohen:

Why don't we set the missing entries to None ? Like c_0 and b_d ?

c[i] is more of a function of i than anything else (same applied to b). You would not insist on 1/x returning None for x=0, would you?

comment:15 follow-up: Changed 6 years ago by ncohen

Come on Dima... You know people will make mistake because of that. We would just avoid them this mistake.

Nathann

comment:16 in reply to: ↑ 15 Changed 6 years ago by dimpase

Replying to ncohen:

Come on Dima... You know people will make mistake because of that. We would just avoid them this mistake.

OK, fine, if you want to pad with None entries, go for it. Let me know if you want me to update the patches, or do it yourself.

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

  • Branch changed from u/dimpase/ticket/15864 to u/ncohen/15864
  • Commit changed from 0b540be503548ad881305f820552bc06d14b0771 to f6541444499809d3af167c9a3632baa98449b0f2

Updated ! I also changed the "return" line to return b,c, as you fixed the docstring. Is that right ? O_o

Nathann

comment:18 Changed 6 years ago by git

  • Commit changed from f6541444499809d3af167c9a3632baa98449b0f2 to 20c5a2ad3ec2074eb2c89ca27622907a2e115557

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

e5a990dfixed typos, corrected the definitions of b, c, chnaged the way they are returned, one more example
0b540bedocs fix: returning (b,c), not (c,b)
20c5a2atrac #15864: bugfix et None dans bi et ci

comment:19 in reply to: ↑ 17 ; follow-up: Changed 6 years ago by dimpase

Replying to ncohen:

Updated ! I also changed the "return" line to return b,c, as you fixed the docstring. Is that right ? O_o

What? Why don't you just start from my latest commit, rather than redoing all my fixes?!

comment:20 in reply to: ↑ 19 ; follow-up: Changed 6 years ago by dimpase

Replying to dimpase:

Replying to ncohen:

Updated ! I also changed the "return" line to return b,c, as you fixed the docstring. Is that right ? O_o

What? Why don't you just start from my latest commit, rather than redoing all my fixes?!

I had the order of b and c as it must be, why are you swapping it back?

comment:21 in reply to: ↑ 20 Changed 6 years ago by dimpase

Replying to dimpase:

Replying to dimpase:

Replying to ncohen:

Updated ! I also changed the "return" line to return b,c, as you fixed the docstring. Is that right ? O_o

What? Why don't you just start from my latest commit, rather than redoing all my fixes?!

I had the order of b and c as it must be, why are you swapping it back?

I guess your code names the stuff inconsistently, i.e. the meanings of b and c are swapped, compared with your docstrings.

comment:22 Changed 6 years ago by ncohen

In the first of your two commits, you make the function return ci, bi. In the second of your two commits you change the documentation to say that the function should return bi,ci. But the code did not change ! I just changed the code to return bi,ci which follows the doc as you changed it !

Nathann

comment:23 follow-up: Changed 6 years ago by ncohen

The definitions are inconsistant since you changed it in your first commit :

http://git.sagemath.org/sage.git/commit/?h=20c5a2ad3ec2074eb2c89ca27622907a2e115557&id=e5a990dd8f2b0ff38dcee683e9d59182d2614eb1

Could you fix that to make the doc and code consistent ?

Nathann

comment:24 in reply to: ↑ 23 Changed 6 years ago by dimpase

Replying to ncohen:

The definitions are inconsistant since you changed it in your first commit :

http://git.sagemath.org/sage.git/commit/?h=20c5a2ad3ec2074eb2c89ca27622907a2e115557&id=e5a990dd8f2b0ff38dcee683e9d59182d2614eb1

Could you fix that to make the doc and code consistent ?

OK, I see, that's what happened: indeed, I changed docs (except the docs for the return value, just forgot these - that's why there was one more commit) in the first commit, as well as the order of the things returned in return. For the sake of code readability it would be great to change the code too, indeed. Do you want me to do this, or you prefer to do this yourself?

comment:25 follow-up: Changed 6 years ago by ncohen

What about this ?....

Nathann

comment:26 Changed 6 years ago by git

  • Commit changed from 20c5a2ad3ec2074eb2c89ca27622907a2e115557 to 1555dc73342281eceff49b0c0fc66d78b58bdbc6

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

f654144trac #15864: Graph.is_distance_regular is awfully wrong
e5a990dfixed typos, corrected the definitions of b, c, chnaged the way they are returned, one more example
0b540bedocs fix: returning (b,c), not (c,b)
1555dc7trac #15854: consistency between code and doc, and None in bi and ci

comment:27 in reply to: ↑ 25 ; follow-up: Changed 6 years ago by dimpase

Replying to ncohen:

What about this ?....

the diff looks good. How do I update the installation? sage --dev checkout --ticket=15864 does not get it right.

comment:28 in reply to: ↑ 27 Changed 6 years ago by dimpase

Replying to dimpase:

Replying to ncohen:

What about this ?....

the diff looks good. How do I update the installation? sage --dev checkout --ticket=15864 does not get it right.

you've mixed up the ticket number: look, the last commit line above says

​1555dc7	trac #15854: consistency between code and doc, and None in bi and ci

but we are doing #15864 ! No wonder I can't check out a sh*t, no matter what I try...

comment:29 Changed 6 years ago by dimpase

  • Status changed from needs_review to needs_work
  • Work issues set to fix the mess with commits

comment:30 Changed 6 years ago by git

  • Commit changed from 1555dc73342281eceff49b0c0fc66d78b58bdbc6 to faffd868037a80a5ad04a5a7cf260f13da4a0e35

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

f654144trac #15864: Graph.is_distance_regular is awfully wrong
e5a990dfixed typos, corrected the definitions of b, c, chnaged the way they are returned, one more example
0b540bedocs fix: returning (b,c), not (c,b)
faffd86trac #15864: consistency between code and doc, and None in bi and ci

comment:31 Changed 6 years ago by ncohen

  • Status changed from needs_work to needs_review

Ahahahah. Well, I don't think that the dev scripts are based on the commit messages, but I fixed that, just in case :-P

I think that the dev script is mostly worried over the fact that I rewrote history. That's why you should probably find a way to delete that branch from your local repository again before running your checkout command.

By the way, how is it going in Oxford ? Do you finally have an office and everything ?

Cheers from Brussels,

Nathann


New commits:

faffd86trac #15864: consistency between code and doc, and None in bi and ci

comment:32 Changed 6 years ago by dimpase

  • Status changed from needs_review to positive_review

OK, this works to get the right branch:

git fetch origin u/ncohen/15864:15864
git checkout 15864

looks good.

comment:33 Changed 6 years ago by vbraun

  • Reviewers set to Dima Pasechnik

Please fill in reviewer names

comment:34 Changed 6 years ago by vbraun

  • Branch changed from u/ncohen/15864 to faffd868037a80a5ad04a5a7cf260f13da4a0e35
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.