some code clean up for sage/graphs/graph.py

[sagetrac-eisermbi]

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 attachment: trac_13192-cleanup-v3.patch and attachment: trac_13192_whitespace.patch.

Depends on #13109

CC: @nathanncohen

Component: graph theory

Keywords: sparse6_string

Author: Birk Eisermann

Reviewer: Nathann Cohen, Karl-Dieter Crisman

Merged: sage-5.3.beta1

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

[nathanncohen]

Reviewer: Nathann Cohen

[nathanncohen]

comment:2

Dead right ! Good to go :-)

Nathann

[nathanncohen]

Author: Birk Eisermann

[mwhansen]

comment:3

I'm not sure the advantage of moving it to a local function and removing tests.

[nathanncohen]

comment:4

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

[sagetrac-eisermbi]

comment:5

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

[nathanncohen]

comment:7

I still agree with the patch.. Even more, actually. Mike ? :-)

Nathann

[kcrisman]

comment:8

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.

[sagetrac-eisermbi]

comment:9

Okay, will update... Is removal of trailing space within the modified function a problem assuming noone else is working on that function?

Birk

[kcrisman]

comment:10

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.

[sagetrac-eisermbi]

Dependencies: #13109

[sagetrac-eisermbi]

comment:11

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

[sagetrac-eisermbi]

comment:12

Updated because of an doctest error...

[kcrisman]

Changed reviewer from Nathann Cohen to Nathann Cohen, Karl-Dieter Crisman

[kcrisman]

comment:13

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.

[sagetrac-eisermbi]

Attachment: trac_13192_cleanup.patch.gz

[sagetrac-eisermbi]

comment:14

Attachment: trac_13192_whitespace.patch.gz

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

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

[kcrisman]

comment:15

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.

[sagetrac-eisermbi]

comment:16

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?

[kcrisman]

comment:17

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.

[kcrisman]

Attachment: trac_13192-cleanup-v2.patch.gz

[kcrisman]

comment:18

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 attachment: trac_13192-cleanup-v2.patch and attachment: trac_13192_whitespace.patch.

[kini]

comment:20

patchbot: apply trac_13192-cleanup-v2.patch trac_13192_whitespace.patch

[kini]

comment:21

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.

[sagetrac-eisermbi]

comment:22

Thanks. Patches are fine.
(And thanks, Keshav, for helping that patchbot reads only plain text.)

[kini]

comment:23

The patches don't seem to apply to 5.2.rc1 (see the patchbot results).

[sagetrac-eisermbi]

comment:24

Attachment: trac_13192-cleanup-v3.patch.gz

Let's try this one......

patchbot: apply trac_13192-cleanup-v3.patch trac_13192_whitespace.patch

[jdemeyer]

Merged: sage-5.3.beta1