Compute bases/circuits in MatroidUnion

[trevorkarn]

It appears there is a bug computing the bases and circuits of a MatroidUnion.

sage: k, h, n = 4, 3, 5
sage: M1 = matroids.Uniform(k-1, h)
sage: M2 = Matroid(bases = [frozenset({3}),frozenset({4})])
sage: M = M1.union(M2); M
Matroid of rank 4 on 5 elements as matroid union of 
Matroid of rank 3 on 3 elements with circuit-closures
{}
Matroid of rank 1 on 2 elements with 2 bases
sage: M.bases()
sage: M.bases()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-48-a32efdfad611> in <module>
----> 1 M.bases()

~/Applications/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/matroids/matroid.pyx in sage.matroids.matroid.Matroid.bases (build/cythonized/sage/matroids/matroid.c:21764)()
   2615         return res
   2616 
-> 2617     cpdef bases(self):
   2618         r"""
   2619         Return the list of bases of the matroid.

~/Applications/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/matroids/matroid.pyx in sage.matroids.matroid.Matroid.bases (build/cythonized/sage/matroids/matroid.c:21661)()
   2643         res = SetSystem(list(self.groundset()))
   2644         for X in combinations(self.groundset(), self.full_rank()):
-> 2645             if self._rank(X) == len(X):
   2646                 res.append(X)
   2647         return res

~/Applications/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/matroids/union_matroid.pyx in sage.matroids.union_matroid.MatroidUnion._rank (build/cythonized/sage/matroids/union_matroid.c:3080)()
     90         summands = []
     91         for e in self.matroids:
---> 92             summands.append(e.delete(e.groundset()-X))
     93         sum_matroid = MatroidSum(summands)
     94         d = {}

TypeError: unsupported operand type(s) for -: 'frozenset' and 'tuple'
sage: M.circuits()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-47-8adfde621a57> in <module>
----> 1 M.circuits()

~/Applications/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/matroids/matroid.pyx in sage.matroids.matroid.Matroid.circuits (build/cythonized/sage/matroids/matroid.c:19192)()
   2370     # enumeration
   2371 
-> 2372     cpdef circuits(self):
   2373         """
   2374         Return the list of circuits of the matroid.

~/Applications/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/matroids/matroid.pyx in sage.matroids.matroid.Matroid.circuits (build/cythonized/sage/matroids/matroid.c:18928)()
   2393         """
   2394         C = set()
-> 2395         for B in self.bases():
   2396             C.update([self._circuit(B.union(set([e])))
   2397                       for e in self.groundset().difference(B)])

~/Applications/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/matroids/matroid.pyx in sage.matroids.matroid.Matroid.bases (build/cythonized/sage/matroids/matroid.c:21661)()
   2643         res = SetSystem(list(self.groundset()))
   2644         for X in combinations(self.groundset(), self.full_rank()):
-> 2645             if self._rank(X) == len(X):
   2646                 res.append(X)
   2647         return res

~/Applications/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/matroids/union_matroid.pyx in sage.matroids.union_matroid.MatroidUnion._rank (build/cythonized/sage/matroids/union_matroid.c:3080)()
     90         summands = []
     91         for e in self.matroids:
---> 92             summands.append(e.delete(e.groundset()-X))
     93         sum_matroid = MatroidSum(summands)
     94         d = {}

TypeError: unsupported operand type(s) for -: 'frozenset' and 'tuple'

CC: @trevorkarn @tscrim @sagetrac-Stefan @sagetrac-Rudi @sagetrac-yomcat

Component: matroid theory

Keywords: union

Author: Trevor K. Karn

Branch/Commit: 8fffb1c

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/33744

[tscrim]

comment:2

Indeed, the issue comes from _rank assuming the input is a frozenset. To fix this, you just need to cast to a frozenset when _rank is called in these methods.

[trevorkarn]

Commit: c4aa4a0

[trevorkarn]

New commits:

7a09a30	Initial commit
c4aa4a0	Add tests

[trevorkarn]

Branch: u/tkarn/matroid_union_33744

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:5

While this will fix the problem, this introduces a slowdown in the code: the _rank() method is assuming the input is good and of the compatible type. Consequently, where you should make changes is in the functions that call into this method that are not satisfying its assumptions.

[trevorkarn]

comment:6

I did think about that. However, if I were to make the change in the way you suggest, the place I see to change is on line 2645 of matroids.pyx. The .basis() and .circuit() methods still work for matroids that are not instances of MatroidUnion, so changing them seems to touch more things than necessary. By comparison the CircuitClosureMatroid._rank(X) method assumes X is a frozenset, but then calls CircuitClosureMatroid._max_independent(), which casts to a set anyway. So I was thinking that the implementation I provided was more in keeping with the implementation of other matroid classes. Plus, casting a frozenset to a frozenset seems to take nanoseconds, even for big frozensets, so I thought it would be negligible.

[tscrim]

comment:7

I disagree. Sometimes you need to make a cast as a necessary part of the code. Here we are trying to balance things: speed versus robustness. It was decided that speed was more important here, and the requirements of the method are clearly documented. This means we have to change more things as a result, but that is not a detractor. Nanoseconds done millions of times add up too.

[trevorkarn]

comment:8

Ok, that makes sense! Thanks!

[sagetrac-git]

Changed commit from c4aa4a0 to 8fffb1c

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

8fffb1c

Add cast to frozenset in determining bases, add tests of trac 33744 to union_matroid.pyx

[tscrim]

comment:11

Thank you. Green bot => positive review.

[trevorkarn]

comment:12

I just want to make sure I'm not going crazy - is the bot is still showing that it has not started running yet for you as well?

[tscrim]

comment:13

No, it hasn’t. I probably won’t be able to test for another 3 weeks. If tests pass for you, then we can set a positive review.

[trevorkarn]

comment:14

The tests on matroid.pyx and union_matroid.pyx pass for me. I see now that the bot has started running, so I will wait for that to be green before setting positive review.

[mkoeppe]

comment:16

author name missing

[trevorkarn]

comment:17

Ope!

[trevorkarn]

Author: Trevor K. Karn

[vbraun]

Changed branch from u/tkarn/matroid_union_33744 to 8fffb1c