Opened 9 years ago
Closed 9 years ago
#15836 closed defect (fixed)
BasisMatroid.circuits() returns a malformed SetSystem when called on the empty matroid
Reported by: | Rudi Pendavingh | Owned by: | Rudi Pendavingh |
---|---|---|---|
Priority: | minor | Milestone: | sage-6.2 |
Component: | matroid theory | Keywords: | |
Cc: | stefan, Michael Welsh | Merged in: | |
Authors: | Rudi Pendavingh | Reviewers: | Jayant Apte |
Report Upstream: | N/A | Work issues: | |
Branch: | 3295660 (Commits, GitHub, GitLab) | Commit: | 329566023aaef2d2f534bfe7cf1753052055b335 |
Dependencies: | Stopgaps: |
Description
The following produces an error:
from sage.matroids.advanced import * M=Basismatroid(groundset=[], rank =0) for C in M.circuits(): print C
Also, len(M.circuits()) is reported to be 1, whereas len(M.cocircuits()) is 0 and the latter is not malformed. It is a bit of a theological issue, but I think we agree that the matroid on zero elements has circuits nor cocircuits:
in general a matroid of rank 0 on k elements has k circuits and no cocircuits.
So I want to make sure that M.circuits() returns that empty SetSystem? (easy enough) but I also want to find out how it is possible that the SetSystem? becomes malformed in this case.
Change History (7)
comment:1 Changed 9 years ago by
Branch: | → u/Rudi/ticket/15836 |
---|---|
Created: | Feb 19, 2014, 9:12:51 AM → Feb 19, 2014, 9:12:51 AM |
Modified: | Feb 19, 2014, 9:12:51 AM → Feb 19, 2014, 9:12:51 AM |
comment:2 Changed 9 years ago by
Commit: | → 329566023aaef2d2f534bfe7cf1753052055b335 |
---|---|
Owner: | set to Rudi Pendavingh |
comment:3 Changed 9 years ago by
Status: | new → needs_review |
---|
The other functions seem to be safe from this bitset problem. Ready for a review.
comment:4 Changed 9 years ago by
Status: | needs_review → positive_review |
---|
The error no longer occurs because of ground set size checks added.
On an unrelated note, I noticed that if one gives bad input e.g. asking for size 9 independent sets of (ground set size 8) vamos matroid:
from sage.matroids.advanced import * M = BasisMatroid(matroids.named_matroids.Vamos()) len(M.independent_r_sets(9))
creates a segfault. There is a check in code for negative numbers passed but not for positive numbers strictly greater than ground set size. I suppose making the code stupid-proof would be a different ticket by itself.
comment:6 Changed 9 years ago by
Authors: | → Rudi Pendavingh |
---|---|
Reviewers: | → Jayant Apte |
Thanks Jayant for reviewing this ticket! Will you create a new ticket for that other issue?
Added author and reviewer.
comment:7 Changed 9 years ago by
Branch: | u/Rudi/ticket/15836 → 329566023aaef2d2f534bfe7cf1753052055b335 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
The problem here is essentially due to the fact that one cannot create a bitset of length 0. To adjust for this, I worked with bitsets of length 1 in the exceptional case of a BasisExchangeMatroid? (or SetSystem?) with an empty ground set. But then bitset_complement() does not precisely do what it should do, and may create a set containing an element index pointing outside the ground set.
So what I did now is catch the possibility of an empty ground set in several enumerative functions. I will go on to have a look at the more low-level functions. I hope that they simply work, because I would hate to incur a speed penalty to repair a problem that arises only for the empty matroid.
New commits:
Adjusted several enumerative functions BasisExchangeMatroid to separately handle the fringe