summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTara Fife <fi.tara@gmail.com>2016-06-07 12:30:09 -0500
committerZachary Gershkoff <zgersh2@math.lsu.edu>2017-05-18 14:43:32 -0500
commit392d8c2509098281284a95aced146a0ccc63e53f (patch)
treec891a6b31215cbca063346f331d1400c5c64a1b9
parentAdded the option to get a certificate (diff)
Added doctests and fixed errors.
-rw-r--r--src/sage/matroids/linear_matroid.pyx21
-rw-r--r--src/sage/matroids/matroid.pyx19
2 files changed, 37 insertions, 3 deletions
diff --git a/src/sage/matroids/linear_matroid.pyx b/src/sage/matroids/linear_matroid.pyx
index 8fe1940..1fc9ef1 100644
--- a/src/sage/matroids/linear_matroid.pyx
+++ b/src/sage/matroids/linear_matroid.pyx
@@ -1381,10 +1381,19 @@ 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
@@ -6143,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.pyx b/src/sage/matroids/matroid.pyx
index d65569a..f5fef7f 100644
--- a/src/sage/matroids/matroid.pyx
+++ b/src/sage/matroids/matroid.pyx
@@ -4001,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)
@@ -4046,10 +4057,16 @@ cdef class Matroid(SageObject):
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:
@@ -4057,7 +4074,7 @@ cdef class Matroid(SageObject):
return True, F
return True
if certificate:
- return False, True
+ return False, None
return False
# extensions