summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorRelease Manager <release@sagemath.org>2016-05-30 12:10:20 +0200
committerVolker Braun <vbraun.name@gmail.com>2016-05-30 12:10:20 +0200
commit00a843681ab917afdd3fa589faa167989bd81811 (patch)
tree27fbe32d7c2e6a3000d520b32737eff2cdc66d85
parentTrac #17808: Preparse old-style octals as strings (diff)
parentA bug was added accidentally. Removed. (diff)
Trac #20660: Add Certificate to is_isomorphic() in the matroids package
We are going to add an option to get certificate when testing if two matroids are isomorphic. I will be doing this. URL: http://trac.sagemath.org/20660 Reported by: tara Ticket author(s): Tara Fife Reviewer(s): Michael Welsh
-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.pyx14
-rw-r--r--src/sage/matroids/circuit_closures_matroid.pxd2
-rw-r--r--src/sage/matroids/circuit_closures_matroid.pyx19
-rw-r--r--src/sage/matroids/linear_matroid.pxd8
-rw-r--r--src/sage/matroids/linear_matroid.pyx53
-rw-r--r--src/sage/matroids/matroid.pxd4
-rw-r--r--src/sage/matroids/matroid.pyx30
10 files changed, 117 insertions, 35 deletions
diff --git a/src/sage/matroids/basis_exchange_matroid.pxd b/src/sage/matroids/basis_exchange_matroid.pxd
index ad65cd8..e7dca68 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, certificate=*)
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..88955d2 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, certificate=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 ``certificate`` -- Boolean.
OUTPUT:
- Boolean.
+ Boolean,
+ and, if certificate = True, a dictionary giving the isomophism 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, certificate=True)
+ (True, {0: 0, 1: 1, 2: 2, 3: 3, 4: 5, 5: 4})
sage: M1 = BasisMatroid(matroids.named_matroids.Fano())
sage: M2 = matroids.named_matroids.NonFano()
sage: M1._is_isomorphic(M2)
False
+ sage: M1._is_isomorphic(M2, certificate=True)
+ (False, None)
"""
+ if certificate:
+ 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..4f53e89 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, certificate=*)
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..89574bf 100644
--- a/src/sage/matroids/basis_matroid.pyx
+++ b/src/sage/matroids/basis_matroid.pyx
@@ -978,7 +978,7 @@ cdef class BasisMatroid(BasisExchangeMatroid):
False
"""
if not isinstance(other, BasisMatroid):
- return BasisExchangeMatroid._is_isomorphic(self, other)
+ return self.isomorphism(BasisMatroid(other))
if self is other:
return {e:e for e in self.groundset()}
if len(self) != len(other):
@@ -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, certificate=False):
"""
Return if this matroid is isomorphic to the given matroid.
INPUT:
- - ``other`` -- a matroid.
+ - ``other`` -- A matroid,
+ - optional parameter ``certificate`` -- Boolean.
OUTPUT:
- Boolean.
+ Boolean,
+ and, if certificate = True, a dictionary giving the isomophism 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, certificate=True)
+ (False, None)
"""
+ if certificate:
+ 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..fc139ed 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, certificate=*)
diff --git a/src/sage/matroids/circuit_closures_matroid.pyx b/src/sage/matroids/circuit_closures_matroid.pyx
index 8bf979d..20ece77 100644
--- a/src/sage/matroids/circuit_closures_matroid.pyx
+++ b/src/sage/matroids/circuit_closures_matroid.pyx
@@ -355,7 +355,7 @@ cdef class CircuitClosuresMatroid(Matroid):
"""
return self._circuit_closures
- cpdef _is_isomorphic(self, other):
+ cpdef _is_isomorphic(self, other, certificate=False):
"""
Test if ``self`` is isomorphic to ``other``.
@@ -363,11 +363,17 @@ cdef class CircuitClosuresMatroid(Matroid):
INPUT:
- - ``other`` -- A matroid.
+ - ``other`` -- A matroid,
+ - optional parameter ``certificate`` -- Boolean.
OUTPUT:
- Boolean.
+ Boolean,
+ and, if certificate = True, a dictionary giving the isomophism 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, certificate=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, certificate=True)
+ (False, None)
+
"""
+ if certificate:
+ 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..51b8181 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, certificate=*)
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, certificate=*)
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, certificate=*)
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, certificate=*)
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..b3e6bc5 100644
--- a/src/sage/matroids/linear_matroid.pyx
+++ b/src/sage/matroids/linear_matroid.pyx
@@ -3265,7 +3265,7 @@ cdef class BinaryMatroid(LinearMatroid):
# isomorphism
- cpdef _is_isomorphic(self, other):
+ cpdef _is_isomorphic(self, other, certificate=False):
"""
Test if ``self`` is isomorphic to ``other``.
@@ -3273,11 +3273,17 @@ cdef class BinaryMatroid(LinearMatroid):
INPUT:
- - ``other`` -- A matroid.
+ - ``other`` -- A matroid,
+ - optional parameter ``certificate`` -- Boolean.
OUTPUT:
- Boolean.
+ Boolean,
+ and, if certificate = True, a dictionary giving the isomophism or None
+
+ .. NOTE::
+
+ Internal version that does no input checking.
EXAMPLES::
@@ -3286,14 +3292,23 @@ cdef class BinaryMatroid(LinearMatroid):
....: reduced_matrix=[[1, 0, 1, 1], [0, 1, 1, 1], [1, 1, 0, 1]])
sage: M1._is_isomorphic(M2)
True
+ sage: M1._is_isomorphic(M2, certificate=True)
+ (True, {'a': 0, 'b': 1, 'c': 2, 'd': 4, 'e': 3, 'f': 5, 'g': 6})
sage: M1 = matroids.named_matroids.Fano().delete('a')
sage: M2 = matroids.Whirl(3)
sage: M1._is_isomorphic(M2)
False
+ sage: M1._is_isomorphic(M2, certificate=True)
+ (False, None)
sage: M1._is_isomorphic(matroids.Wheel(3))
True
+ sage: M1._is_isomorphic(matroids.Wheel(3), certificate=True)
+ (True, {'b': 1, 'c': 2, 'd': 4, 'e': 3, 'f': 5, 'g': 0})
+
"""
+ if certificate:
+ return self._is_isomorphic(other), self._isomorphism(other)
if isinstance(other, BinaryMatroid):
return self.is_field_isomorphic(other)
else:
@@ -4312,18 +4327,24 @@ cdef class TernaryMatroid(LinearMatroid):
# isomorphism
- cpdef _is_isomorphic(self, other):
+ cpdef _is_isomorphic(self, other, certificate=False):
"""
Test if ``self`` is isomorphic to ``other``. Internal version that
performs no checks on input.
INPUT:
- - ``other`` -- A matroid.
+ - ``other`` -- A matroid,
+ - optional parameter ``certificate`` -- Boolean.
OUTPUT:
- Boolean.
+ Boolean,
+ and, if certificate = True, a dictionary giving the isomophism or None
+
+ .. NOTE::
+
+ Internal version that does no input checking.
EXAMPLES::
@@ -4336,6 +4357,8 @@ cdef class TernaryMatroid(LinearMatroid):
sage: M1._is_isomorphic(M2)
False
"""
+ if certificate:
+ return self._is_isomorphic(other), self._isomorphism(other)
if type(other) == TernaryMatroid:
return self.is_field_isomorphic(other)
else:
@@ -5941,7 +5964,7 @@ 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, certificate=False):
"""
Test if ``self`` is isomorphic to ``other``.
@@ -5949,11 +5972,17 @@ cdef class RegularMatroid(LinearMatroid):
INPUT:
- - ``other`` -- A matroid.
+ - ``other`` -- A matroid,
+ - optional parameter ``certificate`` -- Boolean.
OUTPUT:
- Boolean.
+ Boolean,
+ and, if certificate = True, a dictionary giving the isomophism or None
+
+ .. NOTE::
+
+ Internal version that does no input checking.
EXAMPLES::
@@ -5961,6 +5990,8 @@ cdef class RegularMatroid(LinearMatroid):
sage: M2 = matroids.CompleteGraphic(4)
sage: M1._is_isomorphic(M2)
True
+ sage: M1._is_isomorphic(M2, certificate=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 +5999,8 @@ cdef class RegularMatroid(LinearMatroid):
False
sage: M1._is_isomorphic(M2.delete('a'))
True
+ sage: M1._is_isomorphic(M2.delete('a'), certificate=True)
+ (True, {0: 'g', 1: 'b', 2: 'c', 3: 'e', 4: 'd', 5: 'f'})
Check that :trac:`17316` was fixed::
@@ -5991,6 +6024,8 @@ cdef class RegularMatroid(LinearMatroid):
sage: len(Mnew.circuits()) == len(Nnew.circuits())
False
"""
+ if certificate:
+ 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..71bf59c 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, certificate=*)
+ cpdef _is_isomorphic(self, other, certificate=*)
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..875ab1b 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, certificate=False):
r"""
Test matroid isomorphism.
@@ -3080,11 +3080,13 @@ cdef class Matroid(SageObject):
INPUT:
- - ``other`` -- A matroid.
+ - ``other`` -- A matroid,
+ - optional parameter ``certificate`` -- Boolean.
OUTPUT:
- Boolean.
+ Boolean,
+ and, if certificate = 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, certificate=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, certificate=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, certificate)
- cpdef _is_isomorphic(self, other):
+ cpdef _is_isomorphic(self, other, certificate=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 ``certificate`` -- Boolean.
OUTPUT:
- Boolean.
+ Boolean,
+ and, if certificate = True, a dictionary giving the isomophism or None
+
+ .. NOTE::
+
+ Internal version that does no input checking.
EXAMPLES::
@@ -3128,6 +3140,8 @@ cdef class Matroid(SageObject):
sage: M2 = matroids.CompleteGraphic(4)
sage: M1._is_isomorphic(M2)
True
+ sage: M1._is_isomorphic(M2, certificate=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 +3149,8 @@ cdef class Matroid(SageObject):
False
"""
+ if certificate:
+ 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)