summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTara Fife <fi.tara@gmail.com>2016-06-05 11:59:13 -0500
committerZachary Gershkoff <zgersh2@math.lsu.edu>2017-05-18 14:43:11 -0500
commitc172f5549ddfc3e8b4c6278b9a1218f56d131978 (patch)
tree175bf11ef0b241ef725dbb9e76a999d93d9a0f9a
parentUpdated SageMath version to 8.0.beta5 (diff)
Added the option to get a certificate
Fixed error in documentation
-rw-r--r--src/sage/matroids/linear_matroid.pxd4
-rw-r--r--src/sage/matroids/linear_matroid.pyx24
-rw-r--r--src/sage/matroids/matroid.pxd4
-rw-r--r--src/sage/matroids/matroid.pyx26
4 files changed, 37 insertions, 21 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 12e45f9..8fe1940 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::
@@ -1385,7 +1388,7 @@ cdef class LinearMatroid(BasisExchangeMatroid):
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 +6109,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 +6118,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::
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 225af7d..d65569a 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::
@@ -4016,14 +4019,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,8 +4039,7 @@ 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::
@@ -4047,7 +4053,11 @@ cdef class Matroid(SageObject):
return False
for F in hyperlines:
if self._line_length(F) >= k:
+ if certificate:
+ return True, F
return True
+ if certificate:
+ return False, True
return False
# extensions