Opened 9 years ago
Closed 8 years ago
#13192 closed defect (fixed)
some code clean up for sage/graphs/graph.py
Reported by: | eisermbi | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-5.3 |
Component: | graph theory | Keywords: | sparse6_string |
Cc: | ncohen | Merged in: | sage-5.3.beta1 |
Authors: | Birk Eisermann | Reviewers: | Nathann Cohen, Karl-Dieter Crisman |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #13109 | Stopgaps: |
Description (last modified by )
The function compare_edges() of module 'sage.graphs.graph.py' is a simple comparison function used only in function sparse6_string(), and it works only on graphs whose vertices can be compared with the < operator, e.g. integers. Furthermore, the documentation is incomplete.
Suggesting to replace it by a built-in function at the place where it was used.
Apply trac_13192-cleanup-v3.patch and trac_13192_whitespace.patch.
Attachments (4)
Change History (29)
comment:1 Changed 9 years ago by
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
- Reviewers set to Nathann Cohen
- Status changed from needs_review to positive_review
comment:3 Changed 9 years ago by
- Status changed from positive_review to needs_info
I'm not sure the advantage of moving it to a local function and removing tests.
comment:4 Changed 9 years ago by
Hmmm... Well. It's true that there are two tests, but that's more or less just for the show -- or rather because of the "-coverage" Sage flag :-P
The thing is that Birk noticed that its documentation was missing some information, and reading its code we noticed that the function would behave very badly if used of graphs whose vertices are something different from integers. We already had some problems of the kind with other codes that assumed vertices were totally ordered. Soooooooo as it looks like a custom function, made only to be called by the function above, and in order to prevent somebody from using it without knowing that it may be wrong sometimes.... It sounded better to move it inside of that function.
... And to document its behaviour better, which Birk did :-)
What do you think ?
Nathann
comment:5 Changed 9 years ago by
Okay, okay, - you are making me learn python... ;-) I took some information from http://wiki.python.org/moin/HowTo/Sorting/
How about my following one liner? (included in recent patch)
edges.sort(key=lambda e: (e[1],e[0]))
This needs Python version >= 2.4 . Is this dependency okay for sage?
Otherwise, we could write
edges.sort(cmp=lambda e,f: cmp(e[1],f[1]) or cmp(e[0],f[0]))
which seems Python 3.x incompatible though not an issue yet.
For testing, I run
sage -c "for g in graphs(8): print g.sparse6_string()" > gr8-old.out
for all three version (old, key-version, cmp-verison) and the output was the same.
Now, how about giving up the 30 lines of compare_edges() with a good feeling?
Birk
comment:6 Changed 9 years ago by
- Description modified (diff)
- Status changed from needs_info to needs_review
comment:7 Changed 9 years ago by
I still agree with the patch.. Even more, actually. Mike ? :-)
Nathann
comment:8 Changed 9 years ago by
This is indeed better. Sage uses Python 2.7 so 2.4 is no problem :) And it looks like the edges in question will already have integer labels at this point in the code, right? Nathann, I think this should be ok now. There is the deprecation period issue, but I'm assuming that you are vouching that this function had no actual graph-theoretic use, correct? I suppose you could do the deprecation thing to cover all bases. But this is a better solution in any case.
I'm wondering about the whitespace changes - could give problems with conflicts with other patches. You really only need two hunks here.
comment:9 Changed 9 years ago by
- Status changed from needs_review to needs_work
Okay, will update... Is removal of trailing space within the modified function a problem assuming noone else is working on that function?
Birk
comment:10 Changed 9 years ago by
No, removing whitespace right nearby isn't really a problem, but sometimes people are working on the same function (especially if it's a large one, like plot
or something, so it's best to keep it relatively minimal. In this case, for instance, I could imagine someone working on fixing a type in the doc (say) where you removed whitespace, and then this might conflict.
By the way, your commit message is good but maybe you could remove the mq
part.
comment:11 Changed 9 years ago by
- Dependencies set to #13109
- Status changed from needs_work to needs_review
Okay! I reduced the whitespace changes and added a "new style" deprecation warning in case anyone would use this simple yet quite specific function. (I have not removed the old function. Hope it was meant like that...)
comment:12 Changed 9 years ago by
Updated because of an doctest error...
comment:13 follow-up: ↓ 14 Changed 9 years ago by
- Reviewers changed from Nathann Cohen to Nathann Cohen, Karl-Dieter Crisman
- Status changed from needs_review to needs_work
Your update apparently added a lot of whitespace changes again. Also, what was the doctest error? Did you change the code at all?
I think generally in doctests we go with
doctest:...: DeprecationWarning: compare
instead of
doctest:1: DeprecationWarning: compare
in case things were to go in a different order. At any rate, that's what I've seen.
Also, even if you aren't removing the function, presumably it was still testing something useful. Would it be possible to add a graph like the kind Nathann suggests (with non-integer vertices) that shows that this new code is properly comparing, as well as showing it properly compares the edges tested before? I agree that it's good (or at least I said I did above!), just that we want to have documentation.
Basically, what you could do is move the tests in the old function to the tests for the actual meaningful function, and then leave only a very minimal doctest in the old function that states that this is deprecated in the docstring, and has one test exactly to test the deprecation warning.
Sorry that this is more work, but I think it's good as a model for others as well.
Changed 9 years ago by
Changed 9 years ago by
comment:14 in reply to: ↑ 13 Changed 9 years ago by
- Status changed from needs_work to needs_review
Replying to kcrisman:
Your update apparently added a lot of whitespace changes again.
My last update did not touch the whitespaces. In a previous update I reduced the number of changed lines from 10 to 6 lines. These trailing whitespace changes are only within the documentation of the method sparse6_string
, which does not seem to be modified for years(?, ...according to my search on sage-trac). It reads like removing trailing whitespace is forbidden. Hence, I have moved all these changes into a separate file and you are at liberty to exclude or include them - no question asked! ;-)
Also, what was the doctest error? Did you change the code at all?
Am I lying? - joke - Okay, the change was small! It added exactly the line on that you were commenting. When (restoring and) deprecating the old function I did not think about that the deprecation will affect all doctests where this functions is called. (In my case luckily only one place - the doctest of the deprecated function.)
I think generally in doctests we go with
doctest:...: DeprecationWarning: compareinstead of
doctest:1: DeprecationWarning: comparein case things were to go in a different order. At any rate, that's what I've seen.
Unfortunately, my first discovery was "doctest:1:" (and there are a few such places in the source code) and I copied that. - Now it is changed.
Also, even if you aren't removing the function, presumably it was still testing something useful. Would it be possible to add a graph like the kind Nathann suggests (with non-integer vertices) that shows that this new code is properly comparing, as well as showing it properly compares the edges tested before? I agree that it's good (or at least I said I did above!), just that we want to have documentation.
The change was about sorting graph edges. Thus, I added some doctests that sort the edges once by the old method and once by the new method and compare the results. As suggested I put these doctests in the deprecated function.
Basically, what you could do is move the tests in the old function to the tests for the actual meaningful function, and then leave only a very minimal doctest in the old function that states that this is deprecated in the docstring, and has one test exactly to test the deprecation warning.
I reduced the old doctests to just one. It will save a few millionths of a second for doctesting ;-) Well, in this case there was not much doctesting to remove...
Birk
comment:15 follow-up: ↓ 16 Changed 9 years ago by
Sorry, I wasn't meaning to be too picky. I was just trying to avoid craziness. I thought maybe your error in doctests was due to the doctest:1:
, so that is why I harped on it, same with the whitespace, since it seemed to be in an unrelated place.
Anyway, my main point with the testing wasn't to show that it was the same as before (though at least one non-trivial example would be nice), but rather to test the thing you yourself (I though it was Nathann) first noted in the description :-)
it works only on graphs whose vertices can be compared with the < operator, e.g. integers
So I figured that at least one graph that was not properly representable/represented/could have been bad in the sparse_6string
format before should be shown to operate properly now. And that should be in the sparse_6string
documentation.
I don't think you need to include a million examples in the other doctest, though. My concern was that whatever the sorting was for in normal graphs needed to be tested, and perhaps that is already done elsewhere. I'm not familiar enough with that format to know why they have to be sorted that way. Besides, once the function was removed, the tests in the deprecated function would disappear anyway.
comment:16 in reply to: ↑ 15 Changed 8 years ago by
Okay, I think I got the meaning. First, there was nothing really wrong before. The quote does not refer to sparse6_string. It refers to compare_edges which can only be apply to graph edges whose vertices are comparable with "<". It has always been possible to use sparse6_string with any graph (since vertices are map to integers before sorting). So actually everything has already been tested.
In the sparse6 format (see http://cs.anu.edu.au/~bdm/data/formats.txt) to write a graph with vertices {0,1,...,k} the edges are traversed in the following order (and that is why they need to be sorted):
(0,1),
(0,2),(1,2),
...,
(0,k), (1,k), ..., (k-1,k).
Any comments?
comment:17 Changed 8 years ago by
Oh, so you are saying that even with graphs with non-integer (say matrix) edges, there never was a problem? Only with the silly method itself... I see. Nathann's comment about "other codes" misled me.
Okay, then this is all a little overkill and I apologize. Now that you've written the deprecation, might as well keep it, but the last thing graph.py needs is lots of long tests, so just remove those tests; I think we've already more than verified here that the results are the same.
I'm attaching a different version. If you like it, I think this should be ok to go.
Changed 8 years ago by
comment:18 Changed 8 years ago by
- Description modified (diff)
- Status changed from needs_review to positive_review
Just change the status if you have a problem with this, or if the patchbot complains. I qrefreshed the patch to v2. Presumably the whitespace still applies.
Patchbot, apply trac_13192-cleanup-v2.patch and trac_13192_whitespace.patch.
comment:19 Changed 8 years ago by
- Milestone changed from sage-5.2 to sage-5.3
comment:20 Changed 8 years ago by
patchbot: apply trac_13192-cleanup-v2.patch trac_13192_whitespace.patch
comment:21 Changed 8 years ago by
kcrisman: the patchbot can't read the patch filenames when you link them to the actual attachments, which is why I made the comment just before this one.
comment:22 Changed 8 years ago by
Thanks. Patches are fine. (And thanks, Keshav, for helping that patchbot reads only plain text.)
comment:23 Changed 8 years ago by
The patches don't seem to apply to 5.2.rc1 (see the patchbot results).
Changed 8 years ago by
comment:24 Changed 8 years ago by
- Description modified (diff)
Let's try this one......
patchbot: apply trac_13192-cleanup-v3.patch trac_13192_whitespace.patch
comment:25 Changed 8 years ago by
- Merged in set to sage-5.3.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
Dead right ! Good to go
:-)
Nathann