Opened 9 years ago
Closed 9 years ago
#15864 closed defect (fixed)
Graph.is_distance_regular is awfully wrong
Reported by:  Nathann Cohen  Owned by:  

Priority:  major  Milestone:  sage6.2 
Component:  graph theory  Keywords:  
Cc:  Dima Pasechnik  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  fix the mess with commits 
Branch:  faffd86 (Commits, GitHub, GitLab)  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
Change History (34)
comment:1 Changed 9 years ago by
Branch:  → u/ncohen/15684 

Status:  new → needs_review 
comment:2 Changed 9 years ago by
Branch:  u/ncohen/15684 → u/ncohen/15864 

Commit:  → f6541444499809d3af167c9a3632baa98449b0f2 
comment:3 followup: 4 Changed 9 years ago by
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 nondistanceregular 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 notconstant.
comment:4 Changed 9 years ago by
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 distanceregular 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 nondistanceregular 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 notconstant.
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 9 years ago by
in the line
A regular graph
G is distanceregular 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 9 years ago by
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:8 followup: 9 Changed 9 years ago by
Branch:  u/ncohen/15864 → u/dimpase/ticket/15864 

Created:  Feb 26, 2014, 3:13:20 PM → Feb 26, 2014, 3:13:20 PM 
Modified:  Feb 28, 2014, 9:17:06 AM → Feb 28, 2014, 9:17:06 AM 
comment:9 Changed 9 years ago by
Commit:  f6541444499809d3af167c9a3632baa98449b0f2 → e5a990dd8f2b0ff38dcee683e9d59182d2614eb1 

comment:10 Changed 9 years ago by
Commit:  e5a990dd8f2b0ff38dcee683e9d59182d2614eb1 → 0b540be503548ad881305f820552bc06d14b0771 

Branch pushed to git repo; I updated commit sha1. New commits:
0b540be  docs fix: returning (b,c), not (c,b)

comment:11 Changed 9 years ago by
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 9 years ago by
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 3diagonal.
comment:13 followup: 14 Changed 9 years ago by
Why don't we set the missing entries to None
? Like c_0
and b_d
?
Nathann
comment:14 Changed 9 years ago by
Replying to ncohen:
Why don't we set the missing entries to
None
? Likec_0
andb_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 followup: 16 Changed 9 years ago by
Come on Dima... You know people will make mistake because of that. We would just avoid them this mistake.
Nathann
comment:16 Changed 9 years ago by
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 followup: 19 Changed 9 years ago by
Branch:  u/dimpase/ticket/15864 → u/ncohen/15864 

Commit:  0b540be503548ad881305f820552bc06d14b0771 → 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 9 years ago by
Commit:  f6541444499809d3af167c9a3632baa98449b0f2 → 20c5a2ad3ec2074eb2c89ca27622907a2e115557 

comment:19 followup: 20 Changed 9 years ago by
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 followup: 21 Changed 9 years ago by
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 Changed 9 years ago by
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 9 years ago by
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 followup: 24 Changed 9 years ago by
The definitions are inconsistant since you changed it in your first commit :
Could you fix that to make the doc and code consistent ?
Nathann
comment:24 Changed 9 years ago by
Replying to ncohen:
The definitions are inconsistant since you changed it in your first commit :
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:26 Changed 9 years ago by
Commit:  20c5a2ad3ec2074eb2c89ca27622907a2e115557 → 1555dc73342281eceff49b0c0fc66d78b58bdbc6 

Branch pushed to git repo; I updated commit sha1. New commits:
f654144  trac #15864: Graph.is_distance_regular is awfully wrong

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

0b540be  docs fix: returning (b,c), not (c,b)

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

comment:27 followup: 28 Changed 9 years ago by
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 Changed 9 years ago by
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 9 years ago by
Status:  needs_review → needs_work 

Work issues:  → fix the mess with commits 
comment:30 Changed 9 years ago by
Commit:  1555dc73342281eceff49b0c0fc66d78b58bdbc6 → faffd868037a80a5ad04a5a7cf260f13da4a0e35 

Branch pushed to git repo; I updated commit sha1. New commits:
f654144  trac #15864: Graph.is_distance_regular is awfully wrong

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

0b540be  docs fix: returning (b,c), not (c,b)

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

comment:31 Changed 9 years ago by
Status:  needs_work → 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:
faffd86  trac #15864: consistency between code and doc, and None in bi and ci

comment:32 Changed 9 years ago by
Status:  needs_review → positive_review 

OK, this works to get the right branch:
git fetch origin u/ncohen/15864:15864 git checkout 15864
looks good.
comment:34 Changed 9 years ago by
Branch:  u/ncohen/15864 → faffd868037a80a5ad04a5a7cf260f13da4a0e35 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
trac #15864: Graph.is_distance_regular is awfully wrong