summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTara Fife <fi.tara@gmail.com>2016-05-26 16:35:53 -0500
committerTara Fife <fi.tara@gmail.com>2016-05-26 16:35:53 -0500
commit4ee8641a27d6ac2492f0233c057754af7acfc99f (patch)
tree91ca6e30082f1d44d8cd2e44c0f6ec3241144f12
parentUpdated SageMath version to 7.3.beta1 (diff)
Added an optional parameter cert to allow the user to ask for a certificate if the two matroids are isomorphic.
-rw-r--r--src/sage/matroids/basis_exchange_matroid.pxd2
-rw-r--r--src/sage/matroids/basis_exchange_matroid.pyx18
-rw-r--r--src/sage/matroids/basis_matroid.pxd2
-rw-r--r--src/sage/matroids/basis_matroid.pyx12
-rw-r--r--src/sage/matroids/circuit_closures_matroid.pxd2
-rw-r--r--src/sage/matroids/circuit_closures_matroid.pyx21
-rw-r--r--src/sage/matroids/linear_matroid.pxd8
-rw-r--r--src/sage/matroids/linear_matroid.pyx52
-rw-r--r--src/sage/matroids/matroid.pxd4
-rw-r--r--src/sage/matroids/matroid.pyx31
10 files changed, 114 insertions, 38 deletions
diff --git a/src/sage/matroids/basis_exchange_matroid.pxd b/src/sage/matroids/basis_exchange_matroid.pxd
index ad65cd8..9537d43 100644
--- a/src/sage/matroids/basis_exchange_matroid.pxd
+++ b/src/sage/matroids/basis_exchange_matroid.pxd
@@ -89,7 +89,7 @@ cdef class BasisExchangeMatroid(Matroid):
cdef _flush(self)
cpdef _equitable_partition(self, P=*)
- cpdef _is_isomorphic(self, other)
+ cpdef _is_isomorphic(self, other, cert=*)
cpdef _isomorphism(self, other)
cpdef _is_isomorphism(self, other, morphism)
cdef bint __is_isomorphism(self, BasisExchangeMatroid other, morphism)
diff --git a/src/sage/matroids/basis_exchange_matroid.pyx b/src/sage/matroids/basis_exchange_matroid.pyx
index b9110d1..8f65c2e 100644
--- a/src/sage/matroids/basis_exchange_matroid.pyx
+++ b/src/sage/matroids/basis_exchange_matroid.pyx
@@ -2242,7 +2242,7 @@ cdef class BasisExchangeMatroid(Matroid):
return self._characteristic_setsystem()._isomorphism(other._characteristic_setsystem(), PS, PO)
- cpdef _is_isomorphic(self, other):
+ cpdef _is_isomorphic(self, other, cert=False):
"""
Test if ``self`` is isomorphic to ``other``.
@@ -2250,11 +2250,17 @@ cdef class BasisExchangeMatroid(Matroid):
INPUT:
- - ``other`` -- A matroid.
+ - ``other`` -- A matroid,
+ - optional parameter ``cert`` -- Boolean.
OUTPUT:
- Boolean.
+ Boolean,
+ and, if cert = True, a dictionary or None
+
+ .. NOTE::
+
+ Internal version that does no input checking.
EXAMPLES::
@@ -2263,12 +2269,18 @@ cdef class BasisExchangeMatroid(Matroid):
sage: M2 = matroids.CompleteGraphic(4)
sage: M1._is_isomorphic(M2)
True
+ sage: M1._is_isomorphic(M2, True)
+ (True, True)
sage: M1 = BasisMatroid(matroids.named_matroids.Fano())
sage: M2 = matroids.named_matroids.NonFano()
sage: M1._is_isomorphic(M2)
False
+ sage: M1._is_isomorphic(M2, True)
+ (False, False)
"""
+ if cert:
+ return self._is_isomorphic(other), self._isomorphism(other)
if not isinstance(other, BasisExchangeMatroid):
return other._is_isomorphic(self)
# Either generic test, which converts other to BasisMatroid,
diff --git a/src/sage/matroids/basis_matroid.pxd b/src/sage/matroids/basis_matroid.pxd
index f933083..1e0d21b 100644
--- a/src/sage/matroids/basis_matroid.pxd
+++ b/src/sage/matroids/basis_matroid.pxd
@@ -38,7 +38,7 @@ cdef class BasisMatroid(BasisExchangeMatroid):
cpdef _is_relaxation(self, M, morphism)
cpdef _is_isomorphism(self, M, morphism)
cpdef _isomorphism(self, other)
- cpdef _is_isomorphic(self, other)
+ cpdef _is_isomorphic(self, other, cert=*)
cdef binom_init(long n, long k)
diff --git a/src/sage/matroids/basis_matroid.pyx b/src/sage/matroids/basis_matroid.pyx
index fc7dc2e..89ddc5d 100644
--- a/src/sage/matroids/basis_matroid.pyx
+++ b/src/sage/matroids/basis_matroid.pyx
@@ -1027,17 +1027,19 @@ cdef class BasisMatroid(BasisExchangeMatroid):
return self.nonbases()._isomorphism(other.nonbases(), PS, PO)
- cpdef _is_isomorphic(self, other):
+ cpdef _is_isomorphic(self, other, cert=False):
"""
Return if this matroid is isomorphic to the given matroid.
INPUT:
- - ``other`` -- a matroid.
+ - ``other`` -- A matroid,
+ - optional parameter ``cert`` -- Boolean.
OUTPUT:
- Boolean.
+ Boolean,
+ and, if cert = True, a dictionary or None
.. NOTE::
@@ -1050,7 +1052,11 @@ cdef class BasisMatroid(BasisExchangeMatroid):
sage: N = BasisMatroid(matroids.named_matroids.Fano())
sage: M._is_isomorphic(N)
False
+ sage: M._is_isomorphic(N, True)
+ (False, None)
"""
+ if cert:
+ return self._is_isomorphic(other), self._isomorphism(other)
if not isinstance(other, BasisMatroid):
return BasisExchangeMatroid._is_isomorphic(self, other)
if self is other:
diff --git a/src/sage/matroids/circuit_closures_matroid.pxd b/src/sage/matroids/circuit_closures_matroid.pxd
index 97e8190..5af62ba 100644
--- a/src/sage/matroids/circuit_closures_matroid.pxd
+++ b/src/sage/matroids/circuit_closures_matroid.pxd
@@ -11,4 +11,4 @@ cdef class CircuitClosuresMatroid(Matroid):
cpdef _max_independent(self, F)
cpdef _circuit(self, F)
cpdef circuit_closures(self)
- cpdef _is_isomorphic(self, other)
+ cpdef _is_isomorphic(self, other, cert=*)
diff --git a/src/sage/matroids/circuit_closures_matroid.pyx b/src/sage/matroids/circuit_closures_matroid.pyx
index 8bf979d..c3c2ed7 100644
--- a/src/sage/matroids/circuit_closures_matroid.pyx
+++ b/src/sage/matroids/circuit_closures_matroid.pyx
@@ -355,19 +355,25 @@ cdef class CircuitClosuresMatroid(Matroid):
"""
return self._circuit_closures
- cpdef _is_isomorphic(self, other):
+ cpdef _is_isomorphic(self, other, cert=False):
"""
Test if ``self`` is isomorphic to ``other``.
Internal version that performs no checks on input.
- INPUT:
+ NPUT:
- - ``other`` -- A matroid.
+ - ``other`` -- A matroid,
+ - optional parameter ``cert`` -- Boolean.
OUTPUT:
- Boolean.
+ Boolean,
+ and, if cert = True, a dictionary or None
+
+ .. NOTE::
+
+ Internal version that does no input checking.
EXAMPLES::
@@ -376,12 +382,19 @@ cdef class CircuitClosuresMatroid(Matroid):
sage: M2 = matroids.CompleteGraphic(4)
sage: M1._is_isomorphic(M2)
True
+ sage: M1._is_isomorphic(M2, True)
+ (True, {0: 0, 1: 1, 2: 2, 3: 3, 4: 5, 5: 4})
sage: M1 = CircuitClosuresMatroid(matroids.named_matroids.Fano())
sage: M2 = matroids.named_matroids.NonFano()
sage: M1._is_isomorphic(M2)
False
+ sage: M1._is_isomorphic(M2, True)
+ (False, None)
+
"""
+ if cert:
+ return self._is_isomorphic(other), self._isomorphism(other)
N = CircuitClosuresMatroid(other)
if sorted(self._circuit_closures.keys()) != sorted(N._circuit_closures.keys()):
return False
diff --git a/src/sage/matroids/linear_matroid.pxd b/src/sage/matroids/linear_matroid.pxd
index 357767c..887b948 100644
--- a/src/sage/matroids/linear_matroid.pxd
+++ b/src/sage/matroids/linear_matroid.pxd
@@ -79,7 +79,7 @@ cdef class BinaryMatroid(LinearMatroid):
cdef __fundamental_cocircuit(self, bitset_t, long x)
- cpdef _is_isomorphic(self, other)
+ cpdef _is_isomorphic(self, other, cert=*)
cpdef _minor(self, contractions, deletions)
@@ -110,7 +110,7 @@ cdef class TernaryMatroid(LinearMatroid):
cdef __fundamental_cocircuit(self, bitset_t, long x)
- cpdef _is_isomorphic(self, other)
+ cpdef _is_isomorphic(self, other, cert=*)
cpdef _minor(self, contractions, deletions)
@@ -138,7 +138,7 @@ cdef class QuaternaryMatroid(LinearMatroid):
cdef __fundamental_cocircuit(self, bitset_t, long x)
- cpdef _is_isomorphic(self, other)
+ cpdef _is_isomorphic(self, other, cert=*)
cpdef _minor(self, contractions, deletions)
@@ -158,7 +158,7 @@ cdef class RegularMatroid(LinearMatroid):
cpdef base_ring(self)
cpdef characteristic(self)
- cpdef _is_isomorphic(self, other)
+ cpdef _is_isomorphic(self, other, cert=*)
cpdef _invariant(self)
cpdef _fast_isom_test(self, other)
diff --git a/src/sage/matroids/linear_matroid.pyx b/src/sage/matroids/linear_matroid.pyx
index 58dbf33..f951405 100644
--- a/src/sage/matroids/linear_matroid.pyx
+++ b/src/sage/matroids/linear_matroid.pyx
@@ -3265,19 +3265,25 @@ cdef class BinaryMatroid(LinearMatroid):
# isomorphism
- cpdef _is_isomorphic(self, other):
+ cpdef _is_isomorphic(self, other, cert=False):
"""
Test if ``self`` is isomorphic to ``other``.
Internal version that performs no checks on input.
- INPUT:
+ NPUT:
- - ``other`` -- A matroid.
+ - ``other`` -- A matroid,
+ - optional parameter ``cert`` -- Boolean.
OUTPUT:
- Boolean.
+ Boolean,
+ and, if cert = True, a dictionary or None
+
+ .. NOTE::
+
+ Internal version that does no input checking.
EXAMPLES::
@@ -3294,6 +3300,8 @@ cdef class BinaryMatroid(LinearMatroid):
sage: M1._is_isomorphic(matroids.Wheel(3))
True
"""
+ if cert:
+ return self._is_isomorphic(other), self._isomorphism(other)
if isinstance(other, BinaryMatroid):
return self.is_field_isomorphic(other)
else:
@@ -4312,18 +4320,24 @@ cdef class TernaryMatroid(LinearMatroid):
# isomorphism
- cpdef _is_isomorphic(self, other):
+ cpdef _is_isomorphic(self, other, cert=False):
"""
Test if ``self`` is isomorphic to ``other``. Internal version that
performs no checks on input.
- INPUT:
+ NPUT:
- - ``other`` -- A matroid.
+ - ``other`` -- A matroid,
+ - optional parameter ``cert`` -- Boolean.
OUTPUT:
- Boolean.
+ Boolean,
+ and, if cert = True, a dictionary or None
+
+ .. NOTE::
+
+ Internal version that does no input checking.
EXAMPLES::
@@ -4336,6 +4350,8 @@ cdef class TernaryMatroid(LinearMatroid):
sage: M1._is_isomorphic(M2)
False
"""
+ if cert:
+ return self._is_isomorphic(other), self._isomorphism(other)
if type(other) == TernaryMatroid:
return self.is_field_isomorphic(other)
else:
@@ -5941,19 +5957,25 @@ cdef class RegularMatroid(LinearMatroid):
# self._r_hypergraph = self._r_hypergraph.max_refined()
# return self._r_hypergraph
- cpdef _is_isomorphic(self, other):
+ cpdef _is_isomorphic(self, other, cert=False):
"""
Test if ``self`` is isomorphic to ``other``.
Internal version that performs no checks on input.
- INPUT:
+ NPUT:
- - ``other`` -- A matroid.
+ - ``other`` -- A matroid,
+ - optional parameter ``cert`` -- Boolean.
OUTPUT:
- Boolean.
+ Boolean,
+ and, if cert = True, a dictionary or None
+
+ .. NOTE::
+
+ Internal version that does no input checking.
EXAMPLES::
@@ -5961,6 +5983,8 @@ cdef class RegularMatroid(LinearMatroid):
sage: M2 = matroids.CompleteGraphic(4)
sage: M1._is_isomorphic(M2)
True
+ sage: M1._is_isomorphic(M2, True)
+ (True, {0: 0, 1: 1, 2: 2, 3: 3, 4: 5, 5: 4})
sage: M1 = matroids.Wheel(3)
sage: M2 = matroids.named_matroids.Fano()
@@ -5968,6 +5992,8 @@ cdef class RegularMatroid(LinearMatroid):
False
sage: M1._is_isomorphic(M2.delete('a'))
True
+ sage: M1._is_isomorphic(M2.delete('a'), True)
+ (True, {0: 'g', 1: 'b', 2: 'c', 3: 'e', 4: 'd', 5: 'f'})
Check that :trac:`17316` was fixed::
@@ -5991,6 +6017,8 @@ cdef class RegularMatroid(LinearMatroid):
sage: len(Mnew.circuits()) == len(Nnew.circuits())
False
"""
+ if cert:
+ return self._is_isomorphic(other), self._isomorphism(other)
if type(other) == RegularMatroid:
return self.is_field_isomorphic(other)
else:
diff --git a/src/sage/matroids/matroid.pxd b/src/sage/matroids/matroid.pxd
index 1325ddc..e488b6a 100644
--- a/src/sage/matroids/matroid.pxd
+++ b/src/sage/matroids/matroid.pxd
@@ -103,8 +103,8 @@ cdef class Matroid(SageObject):
cpdef no_broken_circuits_sets(self, ordering=*)
# isomorphism
- cpdef is_isomorphic(self, other)
- cpdef _is_isomorphic(self, other)
+ cpdef is_isomorphic(self, other, cert=*)
+ cpdef _is_isomorphic(self, other, cert=*)
cpdef isomorphism(self, other)
cpdef _isomorphism(self, other)
cpdef equals(self, other)
diff --git a/src/sage/matroids/matroid.pyx b/src/sage/matroids/matroid.pyx
index 52fc77e..45c1f95 100644
--- a/src/sage/matroids/matroid.pyx
+++ b/src/sage/matroids/matroid.pyx
@@ -3070,7 +3070,7 @@ cdef class Matroid(SageObject):
# isomorphism and equality
- cpdef is_isomorphic(self, other):
+ cpdef is_isomorphic(self, other, cert=False):
r"""
Test matroid isomorphism.
@@ -3080,11 +3080,13 @@ cdef class Matroid(SageObject):
INPUT:
- - ``other`` -- A matroid.
+ - ``other`` -- A matroid,
+ - optional parameter ``cert`` -- Boolean.
OUTPUT:
- Boolean.
+ Boolean,
+ and, if cert = True, a dictionary or None
EXAMPLES::
@@ -3092,6 +3094,8 @@ cdef class Matroid(SageObject):
sage: M2 = matroids.CompleteGraphic(4)
sage: M1.is_isomorphic(M2)
True
+ sage: M1.is_isomorphic(M2, True)
+ (True, {0: 0, 1: 1, 2: 2, 3: 3, 4: 5, 5: 4})
sage: G3 = graphs.CompleteGraph(4)
sage: M1.is_isomorphic(G3)
Traceback (most recent call last):
@@ -3103,12 +3107,14 @@ cdef class Matroid(SageObject):
sage: M2 = matroids.named_matroids.NonFano()
sage: M1.is_isomorphic(M2)
False
+ sage: M1.is_isomorphic(M2, True)
+ (False, None)
"""
if not isinstance(other, Matroid):
raise TypeError("can only test for isomorphism between matroids.")
- return self._is_isomorphic(other)
+ return self._is_isomorphic(other, cert)
- cpdef _is_isomorphic(self, other):
+ cpdef _is_isomorphic(self, other, cert=False):
"""
Test if ``self`` is isomorphic to ``other``.
@@ -3116,11 +3122,17 @@ cdef class Matroid(SageObject):
INPUT:
- - ``other`` -- A matroid.
+ - ``other`` -- A matroid,
+ - optional parameter ``cert`` -- Boolean.
OUTPUT:
- Boolean.
+ Boolean,
+ and, if cert = True, a dictionary or None
+
+ .. NOTE::
+
+ Internal version that does no input checking.
EXAMPLES::
@@ -3128,6 +3140,9 @@ cdef class Matroid(SageObject):
sage: M2 = matroids.CompleteGraphic(4)
sage: M1._is_isomorphic(M2)
True
+ sage: M1._is_isomorphic(M2, True)
+ (True, {0: 0, 1: 1, 2: 2, 3: 3, 4: 5, 5: 4})
+
sage: M1 = matroids.named_matroids.Fano()
sage: M2 = matroids.named_matroids.NonFano()
@@ -3135,6 +3150,8 @@ cdef class Matroid(SageObject):
False
"""
+ if cert:
+ return self._is_isomorphic(other), self._isomorphism(other)
if self is other:
return True
return (self.full_rank() == other.full_rank() and self.nonbases()._isomorphism(other.nonbases()) is not None)