Opened 8 years ago
Closed 8 years ago
#15836 closed defect (fixed)
BasisMatroid.circuits() returns a malformed SetSystem when called on the empty matroid
Reported by: | Rudi | Owned by: | Rudi |
---|---|---|---|
Priority: | minor | Milestone: | sage-6.2 |
Component: | matroid theory | Keywords: | |
Cc: | stefan, yomcat | 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 8 years ago by
- Branch set to u/Rudi/ticket/15836
- Created changed from 02/19/14 09:12:51 to 02/19/14 09:12:51
- Modified changed from 02/19/14 09:12:51 to 02/19/14 09:12:51
comment:2 Changed 8 years ago by
- Commit set to 329566023aaef2d2f534bfe7cf1753052055b335
- Owner changed from (none) to Rudi
comment:3 Changed 8 years ago by
- Status changed from new to needs_review
The other functions seem to be safe from this bitset problem. Ready for a review.
comment:4 Changed 8 years ago by
- Status changed from needs_review to 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:5 Changed 8 years ago by
author/reviewer names
comment:6 Changed 8 years ago by
- Reviewers set to 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 8 years ago by
- Branch changed from u/Rudi/ticket/15836 to 329566023aaef2d2f534bfe7cf1753052055b335
- Resolution set to fixed
- Status changed from positive_review to 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