summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTara Fife <fi.tara@gmail.com>2016-05-26 21:11:01 -0500
committerTara Fife <fi.tara@gmail.com>2016-05-26 21:11:01 -0500
commitca19af1eabcaa84698633fb8e2f2dcbf23cd32a7 (patch)
tree2ea600fcd6443362de93e8eceb93d590bc2707bb
parentUpdated SageMath version to 7.3.beta1 (diff)
Added the option to get the sets `X` and `Y`, where `N` is `M/X\Y`.
-rw-r--r--src/sage/matroids/matroid.pxd4
-rw-r--r--src/sage/matroids/matroid.pyx31
2 files changed, 25 insertions, 10 deletions
diff --git a/src/sage/matroids/matroid.pxd b/src/sage/matroids/matroid.pxd
index 1325ddc..1b3af89 100644
--- a/src/sage/matroids/matroid.pxd
+++ b/src/sage/matroids/matroid.pxd
@@ -33,7 +33,7 @@ cdef class Matroid(SageObject):
cpdef _is_coclosed(self, X)
cpdef _minor(self, contractions, deletions)
- cpdef _has_minor(self, N)
+ cpdef _has_minor(self, N, certificate=*)
cpdef _line_length(self, F)
cpdef _extension(self, element, hyperplanes)
@@ -118,7 +118,7 @@ cdef class Matroid(SageObject):
cpdef _backslash_(self, X)
cpdef dual(self)
cpdef truncation(self)
- cpdef has_minor(self, N)
+ cpdef has_minor(self, N, certificate=*)
cpdef has_line_minor(self, k, hyperlines=*)
cpdef _has_line_minor(self, k, hyperlines)
diff --git a/src/sage/matroids/matroid.pyx b/src/sage/matroids/matroid.pyx
index 52fc77e..85f9a4a 100644
--- a/src/sage/matroids/matroid.pyx
+++ b/src/sage/matroids/matroid.pyx
@@ -85,7 +85,7 @@ additional functionality (e.g. linear extensions).
- :meth:`delete() <sage.matroids.matroid.Matroid.delete>`
- :meth:`dual() <sage.matroids.matroid.Matroid.dual>`
- :meth:`truncation() <sage.matroids.matroid.Matroid.truncation>`
- - :meth:`has_minor() <sage.matroids.matroid.Matroid.has_minor>`
+ - :meth:`() <sage.matroids.matroid.Matroid.has_minor>`
- :meth:`has_line_minor() <sage.matroids.matroid.Matroid.has_line_minor>`
@@ -1101,17 +1101,18 @@ cdef class Matroid(SageObject):
import minor_matroid
return minor_matroid.MinorMatroid(self, contractions, deletions)
- cpdef _has_minor(self, N):
+ cpdef _has_minor(self, N, certificate=False):
"""
Test if matroid has the specified minor.
INPUT:
- - ``N`` -- An instance of a ``Matroid`` object.
+ - ``N`` -- An instance of a ``Matroid`` object.- optional parameter `certificate` -- a boolean.
OUTPUT:
- Boolean.
+ Boolean,
+ and `(X,Y)` -- frozen sets, where `N` is `M/X\Y`.
EXAMPLES::
@@ -1120,6 +1121,8 @@ cdef class Matroid(SageObject):
False
sage: M._has_minor(matroids.Uniform(2, 4))
True
+ sage: M._has_minor(matroids.Uniform(2, 4), True)
+ (True, (frozenset({'a', 'c'}), frozenset({'b', 'e'})))
.. TODO::
@@ -1127,17 +1130,25 @@ cdef class Matroid(SageObject):
See [Hlineny]_ p.1219 for hints to that end.
"""
if self is N:
+ if certificate:
+ return True, None
return True
rd = self.full_rank() - N.full_rank()
cd = self.full_corank() - N.full_corank()
if rd < 0 or cd < 0:
+ if certificate:
+ return False, None
return False
YY = self.dual().independent_r_sets(cd)
for X in self.independent_r_sets(rd):
for Y in YY:
if X.isdisjoint(Y):
if N._is_isomorphic(self._minor(contractions=X, deletions=Y)):
+ if certificate:
+ return True, (X,Y)
return True
+ if certificate:
+ return False, None
return False
cpdef _line_length(self, F):
@@ -3884,17 +3895,19 @@ cdef class Matroid(SageObject):
return self._extension(l, [])._minor(contractions=frozenset([l]),
deletions=frozenset([]))
- cpdef has_minor(self, N):
+ cpdef has_minor(self, N, certificate=False):
"""
Check if ``self`` has a minor isomorphic to ``N``.
INPUT:
- - ``N`` -- A matroid.
+ - ``N`` -- A matroid,
+ - optional parameter `certificate` -- a boolean.
OUTPUT:
- Boolean.
+ Boolean,
+ and `(X,Y)` -- frozen sets, where `N` is `M/X\Y`.
.. SEEALSO::
@@ -3913,10 +3926,12 @@ cdef class Matroid(SageObject):
False
sage: matroids.named_matroids.NonFano().has_minor(M)
True
+ sage: matroids.named_matroids.NonFano().has_minor(M, True)
+ (True, (frozenset(), frozenset({'g'})))
"""
if not isinstance(N, Matroid):
raise ValueError("N must be a matroid.")
- return self._has_minor(N)
+ return self._has_minor(N, certificate)
cpdef has_line_minor(self, k, hyperlines=None):
"""