summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorRelease Manager <release@sagemath.org>2017-06-11 19:18:16 +0200
committerVolker Braun <vbraun.name@gmail.com>2017-06-11 19:18:16 +0200
commitc1f07eaa4851563dafefd85b99351d3ac8d0dad4 (patch)
treea002c8518fd71ef56cf118b104cd5d92eaf69ec6
parentTrac #19457: Generator for full binary trees (diff)
parentMerge branch 'public/ticket/20778' of git://trac.sagemath.org/sage into t/207... (diff)
Trac #20778: Add certificate option to has_line_minor
Add an option to the ``has_line_minor`` method of matroids to return a witness in case a minor is found. URL: https://trac.sagemath.org/20778 Reported by: tara Ticket author(s): Tara Fife Reviewer(s): Stefan van Zwam
-rw-r--r--src/sage/matroids/linear_matroid.pxd4
-rw-r--r--src/sage/matroids/linear_matroid.pyx45
-rw-r--r--src/sage/matroids/matroid.pxd4
-rw-r--r--src/sage/matroids/matroid.pyx43
4 files changed, 73 insertions, 23 deletions
diff --git a/src/sage/matroids/linear_matroid.pxd b/src/sage/matroids/linear_matroid.pxd
index d89732d..a0ab59d 100644
--- a/src/sage/matroids/linear_matroid.pxd
+++ b/src/sage/matroids/linear_matroid.pxd
@@ -34,7 +34,7 @@ cdef class LinearMatroid(BasisExchangeMatroid):
cpdef _minor(self, contractions, deletions)
cpdef dual(self)
- cpdef has_line_minor(self, k, hyperlines=*)
+ cpdef has_line_minor(self, k, hyperlines=*, certificate=*)
cpdef has_field_minor(self, N)
cpdef _exchange_value(self, e, f)
@@ -167,7 +167,7 @@ cdef class RegularMatroid(LinearMatroid):
cpdef _projection(self)
cpdef _hypergraph(self)
cdef _hypertest(self, other)
- cpdef has_line_minor(self, k, hyperlines=*)
+ cpdef has_line_minor(self, k, hyperlines=*, certificate=*)
cpdef _linear_extension_chains(self, F, fundamentals=*)
cpdef is_graphic(self)
diff --git a/src/sage/matroids/linear_matroid.pyx b/src/sage/matroids/linear_matroid.pyx
index b56cdf0..e4a548a 100644
--- a/src/sage/matroids/linear_matroid.pyx
+++ b/src/sage/matroids/linear_matroid.pyx
@@ -1344,7 +1344,7 @@ cdef class LinearMatroid(BasisExchangeMatroid):
rows, cols = self._current_rows_cols()
return type(self)(reduced_matrix=R, groundset=cols + rows)
- cpdef has_line_minor(self, k, hyperlines=None):
+ cpdef has_line_minor(self, k, hyperlines=None, certificate=False):
"""
Test if the matroid has a `U_{2, k}`-minor.
@@ -1353,18 +1353,21 @@ cdef class LinearMatroid(BasisExchangeMatroid):
than two elements is dependent.
The optional argument ``hyperlines`` restricts the search space: this
- method returns ``False`` if `si(M/F)` is isomorphic to `U_{2, l}` with
- `l \geq k` for some `F` in ``hyperlines``, and ``True`` otherwise.
+ method returns ``True`` if `si(M/F)` is isomorphic to `U_{2, l}` with
+ `l \geq k` for some `F` in ``hyperlines``, and ``False`` otherwise.
INPUT:
- ``k`` -- the length of the line minor
- ``hyperlines`` -- (default: ``None``) a set of flats of codimension
2. Defaults to the set of all flats of codimension 2.
+ - ``certificate`` (default: ``False``); If ``True`` returns ``True, F``,
+ where ``F`` is a flat and ``self.minor(contractions=F)`` has a
+ `U_{2,k}` restriction or ``False, None``.
OUTPUT:
- Boolean.
+ Boolean or tuple.
EXAMPLES::
@@ -1378,14 +1381,23 @@ cdef class LinearMatroid(BasisExchangeMatroid):
sage: M.has_line_minor(k=4, hyperlines=[['a', 'b', 'c'],
....: ['a', 'b', 'd' ]])
True
+ sage: M.has_line_minor(4, certificate=True)
+ (True, frozenset({'a', 'b', 'd'}))
+ sage: M.has_line_minor(5, certificate=True)
+ (False, None)
+ sage: M.has_line_minor(k=4, hyperlines=[['a', 'b', 'c'],
+ ....: ['a', 'b', 'd' ]], certificate=True)
+ (True, frozenset({'a', 'b', 'd'}))
"""
try:
if k > len(self.base_ring()) + 1:
+ if certificate:
+ return False, None
return False
except TypeError:
pass
- return Matroid.has_line_minor(self, k, hyperlines)
+ return Matroid.has_line_minor(self, k, hyperlines, certificate)
cpdef has_field_minor(self, N):
"""
@@ -6106,7 +6118,7 @@ cdef class RegularMatroid(LinearMatroid):
idx={str(f):f for f in other.groundset()}
return {e:idx[m[str(e)]] for e in self.groundset() if str(e) in m}
- cpdef has_line_minor(self, k, hyperlines=None):
+ cpdef has_line_minor(self, k, hyperlines=None, certificate=False):
"""
Test if the matroid has a `U_{2, k}`-minor.
@@ -6115,18 +6127,21 @@ cdef class RegularMatroid(LinearMatroid):
than two elements is dependent.
The optional argument ``hyperlines`` restricts the search space: this
- method returns ``False`` if `si(M/F)` is isomorphic to `U_{2, l}` with
- `l \geq k` for some `F` in ``hyperlines``, and ``True`` otherwise.
+ method returns ``True`` if `si(M/F)` is isomorphic to `U_{2, l}` with
+ `l \geq k` for some `F` in ``hyperlines``, and ``False`` otherwise.
INPUT:
- ``k`` -- the length of the line minor
- ``hyperlines`` -- (default: ``None``) a set of flats of codimension
2. Defaults to the set of all flats of codimension 2.
+ - ``certificate`` (default: ``False``); If ``True`` returns ``True, F``,
+ where ``F`` is a flat and ``self.minor(contractions=F)`` has a
+ `U_{2,k}` restriction or ``False, None``.
OUTPUT:
- Boolean.
+ Boolean or tuple.
.. SEEALSO::
@@ -6137,16 +6152,24 @@ cdef class RegularMatroid(LinearMatroid):
sage: M = matroids.named_matroids.R10()
sage: M.has_line_minor(4)
False
+ sage: M.has_line_minor(4, certificate=True)
+ (False, None)
sage: M.has_line_minor(3)
True
+ sage: M.has_line_minor(3, certificate=True)
+ (True, frozenset({'a', 'b', 'c', 'g'}))
sage: M.has_line_minor(k=3, hyperlines=[['a', 'b', 'c'],
....: ['a', 'b', 'd' ]])
True
-
+ sage: M.has_line_minor(k=3, hyperlines=[['a', 'b', 'c'],
+ ....: ['a', 'b', 'd' ]], certificate=True)
+ (True, frozenset({'a', 'b', 'c'}))
"""
if k > 3:
+ if certificate:
+ return False, None
return False
- return Matroid.has_line_minor(self, k, hyperlines)
+ return Matroid.has_line_minor(self, k, hyperlines, certificate)
cpdef _linear_extension_chains(self, F, fundamentals=None):
r"""
diff --git a/src/sage/matroids/matroid.pxd b/src/sage/matroids/matroid.pxd
index 56e1c2b..08ed808 100644
--- a/src/sage/matroids/matroid.pxd
+++ b/src/sage/matroids/matroid.pxd
@@ -119,8 +119,8 @@ cdef class Matroid(SageObject):
cpdef dual(self)
cpdef truncation(self)
cpdef has_minor(self, N, bint certificate=*)
- cpdef has_line_minor(self, k, hyperlines=*)
- cpdef _has_line_minor(self, k, hyperlines)
+ cpdef has_line_minor(self, k, hyperlines=*, certificate=*)
+ cpdef _has_line_minor(self, k, hyperlines, certificate=*)
# extension
cpdef extension(self, element=*, subsets=*)
diff --git a/src/sage/matroids/matroid.pyx b/src/sage/matroids/matroid.pyx
index ae2b4c1..d4cd14b 100644
--- a/src/sage/matroids/matroid.pyx
+++ b/src/sage/matroids/matroid.pyx
@@ -3960,7 +3960,7 @@ cdef class Matroid(SageObject):
raise ValueError("N must be a matroid.")
return self._has_minor(N, certificate)
- cpdef has_line_minor(self, k, hyperlines=None):
+ cpdef has_line_minor(self, k, hyperlines=None, certificate=False):
"""
Test if the matroid has a `U_{2, k}`-minor.
@@ -3969,18 +3969,21 @@ cdef class Matroid(SageObject):
than two elements is dependent.
The optional argument ``hyperlines`` restricts the search space: this
- method returns ``False`` if `si(M/F)` is isomorphic to `U_{2, l}` with
- `l \geq k` for some `F` in ``hyperlines``, and ``True`` otherwise.
+ method returns ``True`` if `si(M/F)` is isomorphic to `U_{2, l}` with
+ `l \geq k` for some `F` in ``hyperlines``, and ``False`` otherwise.
INPUT:
- ``k`` -- the length of the line minor
- ``hyperlines`` -- (default: ``None``) a set of flats of codimension
2. Defaults to the set of all flats of codimension 2.
+ - ``certificate`` -- (default: ``False``) if ``True`` returns ``(True, F)``,
+ where ``F`` is a flat and ``self.minor(contractions=F)`` has a
+ `U_{2,k}` restriction or ``(False, None)``.
OUTPUT:
- Boolean.
+ Boolean or tuple.
.. SEEALSO::
@@ -3998,11 +4001,22 @@ cdef class Matroid(SageObject):
sage: M.has_line_minor(k=4, hyperlines=[['a', 'b', 'c'],
....: ['a', 'b', 'd' ]])
True
+ sage: M.has_line_minor(4, certificate=True)
+ (True, frozenset({'a', 'b', 'd'}))
+ sage: M.has_line_minor(5, certificate=True)
+ (False, None)
+ sage: M.has_line_minor(k=4, hyperlines=[['a', 'b', 'c'],
+ ....: ['a', 'b', 'd' ]], certificate=True)
+ (True, frozenset({'a', 'b', 'd'}))
"""
if self.full_rank() < 2:
+ if certificate:
+ return False, None
return False
if self.full_corank() < k - 2:
+ if certificate:
+ return False, None
return False
if hyperlines is None:
hyperlines = self.flats(self.full_rank() - 2)
@@ -4016,14 +4030,18 @@ cdef class Matroid(SageObject):
raise ValueError("input sets need to have rank 2 less than the rank of the matroid.")
# Note that we don't check if the sets are flats, because loops
# get simplified away anyway.
- return self._has_line_minor(k, hyperlines)
+ return self._has_line_minor(k, hyperlines, certificate)
- cpdef _has_line_minor(self, k, hyperlines):
+ cpdef _has_line_minor(self, k, hyperlines, certificate=False):
"""
Test if the matroid has a `U_{2, k}`-minor.
Internal version that does no input checking.
+ The optional argument ``hyperlines`` restricts the search space: this
+ method returns ``True`` if `si(M/F)` is isomorphic to `U_{2, l}` with
+ `l \geq k` for some `F` in ``hyperlines``, and ``False`` otherwise.
+
INPUT:
- ``k`` -- the length of the line minor
@@ -4032,22 +4050,31 @@ cdef class Matroid(SageObject):
OUTPUT:
- Boolean. ``False`` if `si(M/F)` is isomorphic to `U_{2, l}` with
- `l \geq k` for some `F` in ``hyperlines``. ``True``, otherwise.
+ Boolean or tuple.
EXAMPLES::
sage: M = matroids.named_matroids.NonPappus()
sage: M._has_line_minor(5, M.flats(1))
True
+ sage: M._has_line_minor(5, M.flats(1), certificate=True)
+ (True, frozenset({'a'}))
"""
if self.full_rank() < 2:
+ if certificate:
+ return False, None
return False
if self.full_corank() < k - 2:
+ if certificate:
+ return False, None
return False
for F in hyperlines:
if self._line_length(F) >= k:
+ if certificate:
+ return True, F
return True
+ if certificate:
+ return False, None
return False
# extensions