summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTara Fife <fi.tara@gmail.com>2016-06-07 12:30:09 -0500
committerTara Fife <fi.tara@gmail.com>2016-06-07 12:30:09 -0500
commitbddc173cb69188deec576e559245683d11c5f304 (patch)
tree3bb3c1fa8e3064357477e8b488eb49a4ba4e70fe
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 50b5aaf..e398c04 100644
--- a/src/sage/matroids/linear_matroid.pyx
+++ b/src/sage/matroids/linear_matroid.pyx
@@ -1380,10 +1380,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
@@ -6098,16 +6107,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 c8db0d4..6ecf3b4 100644
--- a/src/sage/matroids/matroid.pyx
+++ b/src/sage/matroids/matroid.pyx
@@ -3959,11 +3959,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)
@@ -4004,10 +4015,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:
@@ -4015,7 +4032,7 @@ cdef class Matroid(SageObject):
return True, F
return True
if certificate:
- return False, True
+ return False, None
return False
# extensions