Opened 14 months ago

Last modified 13 months ago

#27889 closed enhancement

py3 fixes for matroids — at Version 9

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:
Report Upstream: N/A Work issues:
Branch: u/jhpalmieri/matroids-py3 (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 (9)

comment:1 Changed 14 months ago by jhpalmieri

  • Branch set to u/jhpalmieri/matroids-py3

comment:2 Changed 14 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 14 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 13 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 13 months ago by chapoton

  • Cc Stefan Rudi zgershkoff added

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

  • Description modified (diff)
Note: See TracTickets for help on using tickets.