Compute bases/circuits in MatroidUnion
trevorkarn opened this issue · 19 comments
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
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.
Commit: c4aa4a0
Branch: u/tkarn/matroid_union_33744
Reviewer: Travis Scrimshaw
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.
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.
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.
Ok, that makes sense! Thanks!
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 |
Thank you. Green bot => positive review.
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?
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.
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.
author name missing
Ope!
Author: Trevor K. Karn
Changed branch from u/tkarn/matroid_union_33744 to 8fffb1c