summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorRelease Manager <release@sagemath.org>2016-08-17 22:49:49 +0200
committerVolker Braun <vbraun.name@gmail.com>2016-08-21 00:27:51 +0200
commitbcb98ec00cc0378338515d8525e0ea861b66be17 (patch)
tree446122539c342a88c86c47b0bfea25cd2304b42a
parentTrac #20655: R installation failing on Cygwin (diff)
parentDeleted some periods (diff)
Trac #20696: Add certificate option to the chordal functions
URL: https://trac.sagemath.org/20696 Reported by: tara Ticket author(s): Tara Fife Reviewer(s): Travis Scrimshaw
-rw-r--r--src/sage/matroids/matroid.pxd6
-rw-r--r--src/sage/matroids/matroid.pyx55
2 files changed, 54 insertions, 7 deletions
diff --git a/src/sage/matroids/matroid.pxd b/src/sage/matroids/matroid.pxd
index c793037..fa61afc 100644
--- a/src/sage/matroids/matroid.pxd
+++ b/src/sage/matroids/matroid.pxd
@@ -163,9 +163,9 @@ cdef class Matroid(SageObject):
cpdef is_k_closed(self, int k)
# matroid chordality
- cpdef _is_circuit_chordal(self, frozenset C)
- cpdef is_circuit_chordal(self, C)
- cpdef is_chordal(self, k1=*, k2=*)
+ cpdef _is_circuit_chordal(self, frozenset C, bint certificate=*)
+ cpdef is_circuit_chordal(self, C, bint certificate=*)
+ cpdef is_chordal(self, k1=*, k2=*, bint certificate=*)
cpdef chordality(self)
# optimization
diff --git a/src/sage/matroids/matroid.pyx b/src/sage/matroids/matroid.pyx
index 8ab6790..3309478 100644
--- a/src/sage/matroids/matroid.pyx
+++ b/src/sage/matroids/matroid.pyx
@@ -6138,10 +6138,22 @@ cdef class Matroid(SageObject):
# matroid chordality
- cpdef _is_circuit_chordal(self, frozenset C):
+ cpdef _is_circuit_chordal(self, frozenset C, bint certificate=False):
"""
Check if the circuit ``C`` has a chord.
+ INPUT:
+
+ - ``C`` -- a circuit
+ - ``certificate`` -- (default: ``False``) a boolean, if ``True``
+ return ``True, (x, Ax, Bx)``, where ``x`` is a chord and ``Ax`` and
+ ``Bx`` are circuits whose union is the elements of ``C``
+ together with ``x``, if ``False`` return ``False, None``
+
+ OUTPUT:
+
+ - boolean or tuple
+
EXAMPLES::
sage: M = matroids.Uniform(2,4)
@@ -6150,8 +6162,12 @@ cdef class Matroid(SageObject):
sage: M = matroids.named_matroids.Fano()
sage: M._is_circuit_chordal(frozenset(['b','c','d']))
False
+ sage: M._is_circuit_chordal(frozenset(['b','c','d']), certificate=True)
+ (False, None)
sage: M._is_circuit_chordal(frozenset(['a','b','d','e']))
True
+ sage: M._is_circuit_chordal(frozenset(['a','b','d','e']), certificate=True)
+ (True, ('c', frozenset({'b', 'c', 'd'}), frozenset({'a', 'c', 'e'})))
"""
cdef set X
cdef frozenset Ax, Bx
@@ -6165,10 +6181,14 @@ cdef class Matroid(SageObject):
if not self._is_independent(Bx):
# If x is spanned by C, then A+x is the unique circuit in C-e+x;
# so x is a chord iff the complementary B is a circuit.
+ if certificate:
+ return True, (x, frozenset(Ax), frozenset(Bx))
return True
+ if certificate:
+ return False, None
return False
- cpdef is_circuit_chordal(self, C):
+ cpdef is_circuit_chordal(self, C, bint certificate=False):
r"""
Check if the circuit ``C`` has a chord.
@@ -6176,19 +6196,35 @@ cdef class Matroid(SageObject):
exists sets `A, B` such that `C = A \sqcup B` and `A + x` and
`B + x` are circuits.
+ INPUT:
+
+ - ``C`` -- a circuit
+ - ``certificate`` -- (default: ``False``) a boolean, if ``True``
+ return ``True, (x, Ax, Bx)``, where ``x`` is a chord and ``Ax`` and
+ ``Bx`` are circuits whose union is the elements of ``C``
+ together with ``x``, if ``False`` return ``False, None``
+
+ OUTPUT:
+
+ - boolean or tuple
+
EXAMPLES::
sage: M = matroids.named_matroids.Fano()
sage: M.is_circuit_chordal(['b','c','d'])
False
+ sage: M.is_circuit_chordal(['b','c','d'], certificate=True)
+ (False, None)
sage: M.is_circuit_chordal(['a','b','d','e'])
True
+ sage: M.is_circuit_chordal(['a','b','d','e'], certificate=True)
+ (True, ('c', frozenset({'b', 'c', 'd'}), frozenset({'a', 'c', 'e'})))
"""
if not self.is_circuit(C):
raise ValueError("input C is not a circuit")
- return self._is_circuit_chordal(frozenset(C))
+ return self._is_circuit_chordal(frozenset(C), certificate)
- cpdef is_chordal(self, k1=4, k2=None):
+ cpdef is_chordal(self, k1=4, k2=None, bint certificate=False):
r"""
Return if a matroid is ``[k1, k2]``-chordal.
@@ -6203,6 +6239,13 @@ cdef class Matroid(SageObject):
- ``k1`` -- (optional) the integer `k_1`
- ``k2`` -- (optional) the integer `k_2`; if not specified,
then this method returns if ``self`` is `k_1`-chordal
+ - ``certificate`` -- (default: ``False``) boolean; if
+ ``True`` return ``True, C``, where ``C`` is a non
+ ``k1`` ``k2`` circuit
+
+ Output:
+
+ - boolean or tuple
.. SEEALSO::
@@ -6221,6 +6264,8 @@ cdef class Matroid(SageObject):
[False, False, False, False, True, True]
sage: M.is_chordal(4, 5)
False
+ sage: M.is_chordal(4, 5, certificate=True)
+ (False, frozenset({'a', 'b', 'e', 'f', 'g'}))
"""
cdef frozenset C
if k2 is None:
@@ -6229,6 +6274,8 @@ cdef class Matroid(SageObject):
if len(C) < k1 or len(C) > k2:
continue
if not self._is_circuit_chordal(C):
+ if certificate:
+ return False, frozenset(C)
return False
return True