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:

Status badges


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 Rudi Pendavingh

Branch: u/Rudi/ticket/15836
Created: Feb 19, 2014, 9:12:51 AMFeb 19, 2014, 9:12:51 AM
Modified: Feb 19, 2014, 9:12:51 AMFeb 19, 2014, 9:12:51 AM

comment:2 Changed 9 years ago by Rudi Pendavingh

Commit: 329566023aaef2d2f534bfe7cf1753052055b335
Owner: set to Rudi Pendavingh

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:

3295660Adjusted several enumerative functions BasisExchangeMatroid to separately handle the fringe

comment:3 Changed 9 years ago by Rudi Pendavingh

Status: newneeds_review

The other functions seem to be safe from this bitset problem. Ready for a review.

comment:4 Changed 9 years ago by Jayant Apte

Status: needs_reviewpositive_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())

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 9 years ago by Volker Braun

author/reviewer names

comment:6 Changed 9 years ago by Rudi Pendavingh

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 Volker Braun

Branch: u/Rudi/ticket/15836329566023aaef2d2f534bfe7cf1753052055b335
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.