Opened 22 months ago
Closed 21 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, GitHub, GitLab) | Commit: | 3bb96e6f02063476157408de02575d9c359bbef3 |
Dependencies: | Stopgaps: |
Description (last modified by )
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 22 months ago by
- Branch set to u/jhpalmieri/matroids-py3
comment:2 Changed 22 months ago by
- Commit set to 523f87e0b8b38f1623c43b791ae69465b651af91
- Status changed from new to needs_review
comment:3 Changed 22 months ago by
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: ↓ 7 Changed 22 months ago by
Maybe this line in graphic_matroid.py
comps = G.connected_components()
could use
comps = G.connected_components(sort=False)
?
comment:5 Changed 22 months ago by
- Cc Stefan Rudi zgershkoff added
comment:6 Changed 22 months ago by
- Commit changed from 523f87e0b8b38f1623c43b791ae69465b651af91 to df35a889f7bc4b668ac4e463bf0c8f41b04efd00
Branch pushed to git repo; I updated commit sha1. New commits:
df35a88 | trac 27889: a few more matroid fixes
|
comment:7 in reply to: ↑ 4 Changed 22 months ago by
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 22 months ago by
- Commit changed from df35a889f7bc4b668ac4e463bf0c8f41b04efd00 to 3bb96e6f02063476157408de02575d9c359bbef3
Branch pushed to git repo; I updated commit sha1. New commits:
3bb96e6 | trac 27889: a few clarifying comments
|
comment:9 Changed 22 months ago by
- Description modified (diff)
comment:10 Changed 21 months ago by
- 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 21 months ago by
- 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 21 months ago by
- Reviewers set to Frédéric Chapoton
- Status changed from needs_review to positive_review
ok, then let it be.
comment:13 Changed 21 months ago by
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 21 months ago by
- Branch changed from u/jhpalmieri/matroids-py3 to 3bb96e6f02063476157408de02575d9c359bbef3
- Resolution set to fixed
- Status changed from positive_review to closed
Remaining failures:
constructor.py
:I don't know what causes this.
utilities.py
:Tracked at #27787.
There is one other failure in
utilities.py
, three more ingraphic_matroid.py
, all due to sorting problems in Sage'sgraphs
module.New commits:
trac 27889: py3 fixes for matroids