Opened 6 months ago

Closed 6 months ago

#27889 closed enhancement (fixed)

py3 fixes for matroids

Reported by: jhpalmieri Owned by:
Priority: major Milestone: sage-8.8
Component: python3 Keywords:
Cc: Stefan, Rudi, zgershkoff, yomcat, tscrim Merged in:
Authors: John Palmieri Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: 3bb96e6 (Commits) Commit: 3bb96e6f02063476157408de02575d9c359bbef3
Dependencies: Stopgaps:

Description (last modified by 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.

Change History (14)

comment:1 Changed 6 months ago by jhpalmieri

  • Branch set to u/jhpalmieri/matroids-py3

comment:2 Changed 6 months ago by jhpalmieri

  • Commit set to 523f87e0b8b38f1623c43b791ae69465b651af91
  • Status changed from new to needs_review

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:

523f87etrac 27889: py3 fixes for matroids

comment:3 Changed 6 months ago by 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.

comment:4 follow-up: Changed 6 months ago by chapoton

Maybe this line in graphic_matroid.py

comps = G.connected_components()

could use

comps = G.connected_components(sort=False)

?

comment:5 Changed 6 months ago by chapoton

  • Cc Stefan Rudi zgershkoff added

comment:6 Changed 6 months ago by git

  • Commit changed from 523f87e0b8b38f1623c43b791ae69465b651af91 to df35a889f7bc4b668ac4e463bf0c8f41b04efd00

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

df35a88trac 27889: a few more matroid fixes

comment:7 in reply to: ↑ 4 Changed 6 months ago by 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.

comment:8 Changed 6 months ago by git

  • Commit changed from df35a889f7bc4b668ac4e463bf0c8f41b04efd00 to 3bb96e6f02063476157408de02575d9c359bbef3

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

3bb96e6trac 27889: a few clarifying comments

comment:9 Changed 6 months ago by jhpalmieri

  • Description modified (diff)

comment:10 Changed 6 months ago by chapoton

  • Cc yomcat added

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.

comment:11 Changed 6 months ago by Rudi

  • Cc tscrim added

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.

comment:12 Changed 6 months ago by chapoton

  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, then let it be.

comment:13 Changed 6 months ago by 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.

comment:14 Changed 6 months ago by vbraun

  • Branch changed from u/jhpalmieri/matroids-py3 to 3bb96e6f02063476157408de02575d9c359bbef3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.