py3 fixes for matroids

[jhpalmieri]

This fixes most of the Python 3 doctest failures in matroids. Many of the tests rely on sorting: not just sorting the output, but sorting while computing the answer. So when we ask for a maximal independent set, we shouldn't print it, because the answer may change between Python versions, and indeed it may change if we run Python 3 several times. Instead, we should check that it is maximal independent.

One failure remains. See the comments below and #27787.

[jhpalmieri]

Remaining failures: constructor.py:

File "src/sage/matroids/constructor.py", line 607, in sage.matroids.constructor.Matroid
Failed example:
    Matrix(N)
Expected:
    [1 0 0 1 1 0]
    [0 1 0 1 1 1]
    [0 0 1 0 1 1]
Got:
    [1 0 0 1 0 1]
    [0 1 0 0 1 1]
    [0 0 1 1 1 1]

I don't know what causes this.

utilities.py:

File "src/sage/matroids/utilities.py", line 543, in sage.matroids.utilities.lift_cross_ratios
Failed example:
    Z
Expected:
    [ 1  0  1  1  1]
    [ 1  1  0  0  z]
    [ 0  1 -z -1  0]
Got:
    [ 1  0  1  1  1]
    [ 1  1  0  0  z]
    [ 0 -1  z  1  0]

Tracked at #27787.

There is one other failure in utilities.py, three more in graphic_matroid.py, all due to sorting problems in Sage's graphs module.

---

New commits:

​523f87e

trac 27889: py3 fixes for matroids

[jhpalmieri]

Oh, one more thing: in matroids.pyx, there was a bug in the code, repeated several times:

            wt = sorted(wt, reverse=True)
            if wt[-1][1] < 0:
                raise ValueError(...)

The problem is that each entry of the list wt was a pair (integer, label), and so it should have been testing whether wt[-1][0] was negative. And then the sorting was not correct, so there was no guarantee that wt[-1] would have the smallest weight. So I added code to check whether each weight was nonnegative during an already existing loop over the entries. The old code was inside a few try ... except blocks, so when a weight is negative, the new code sets a flag and tries to break out of the loop and the try ... except block, and then it raises the error.

I added a few doctests for this.

[chapoton]

Maybe this line in graphic_matroid.py

comps = G.connected_components()

could use

comps = G.connected_components(sort=False)

?

[git]

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

​df35a88

trac 27889: a few more matroid fixes

[jhpalmieri]

Replying to chapoton:

Maybe this line in graphic_matroid.py

comps = G.connected_components()

could use

comps = G.connected_components(sort=False)

?

Good idea. This, plus a few other fixes, has gotten us down to the single failure from #27787. If I have time, I will try to understand the underlying mathematics and see what's going on, but someone who is more familiar with matroids would be more efficient at that.

[git]

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

​3bb96e6

trac 27889: a few clarifying comments

[chapoton]

Looks good to me, and this is a real progress. But I would like to have the approval of at least one the authors of the matroid code. Hey guys, are you listening ?

If no answer comes back soon enough, I will set this to positive review.

[Rudi]

I'm one of the original authors of this code.

I do not have sage set up at the moment for experimenting with the code proposed in this ticket. Reading the change files, all proposed changes seem to make good sense.

You are right about the

        if wt[-1][1] < 0:
                raise ValueError(...)

being an error. It is in one of the routines I wrote, so I'm probably responsable. Thanks for fixing.

I saw changes in code that was written by Travis Scrimshaw, so I will add him in the cc. It all looked fine though.

Thanks for your effort to update this code to python 3.

[chapoton]

ok, then let it be.

[zgershkoff]

I'm the author of the graphic matroid code, and the changes look good.

I do confess I'm out of the loop on how to get python3 running in sage, so I don't know how to test it myself.