summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTara Fife <fi.tara@gmail.com>2016-06-05 11:59:13 -0500
committerTara Fife <fi.tara@gmail.com>2016-06-05 11:59:13 -0500
commitd909a084578b8112e449b4de61935349896b75a3 (patch)
tree6150cc197bb385e533668ca98e5ee8fc6df06243
parentUpdated SageMath version to 7.3.beta1 (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 357767c..661494b 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 58dbf33..50b5aaf 100644
--- a/src/sage/matroids/linear_matroid.pyx
+++ b/src/sage/matroids/linear_matroid.pyx
@@ -1343,7 +1343,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.
@@ -1352,18 +1352,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::
@@ -1384,7 +1387,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):
"""
@@ -6061,7 +6064,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.
@@ -6070,18 +6073,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 1325ddc..ff6b94c 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)
- 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 52fc77e..c8db0d4 100644
--- a/src/sage/matroids/matroid.pyx
+++ b/src/sage/matroids/matroid.pyx
@@ -3918,7 +3918,7 @@ cdef class Matroid(SageObject):
raise ValueError("N must be a matroid.")
return self._has_minor(N)
- 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.
@@ -3927,18 +3927,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::
@@ -3974,14 +3977,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
@@ -3990,8 +3997,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::
@@ -4005,7 +4011,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