Opened 8 years ago

Closed 7 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:

Status badges

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 Rudi

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

  • Commit set to 329566023aaef2d2f534bfe7cf1753052055b335
  • Owner changed from (none) to Rudi

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 8 years ago by Rudi

  • 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 7 years ago by Jayant

  • 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 7 years ago by vbraun

author/reviewer names

comment:6 Changed 7 years ago by Rudi

  • Authors set to Rudi Pendavingh
  • 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 7 years ago by vbraun

  • Branch changed from u/Rudi/ticket/15836 to 329566023aaef2d2f534bfe7cf1753052055b335
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.