summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDarij Grinberg <darijgrinberg@gmail.com>2016-05-11 04:00:56 +0200
committerDarij Grinberg <darijgrinberg@gmail.com>2016-05-11 04:00:56 +0200
commit64f76adea329df592cf28ec6d54253de5c72ae64 (patch)
treed43baf527dd151984ce615fb9cae1fb4d7f25481
parentUpdated SageMath version to 7.2.rc1 (diff)
parentFixed bug with smres and added clarifying comments. (diff)
Merge branch 'public/ticket/14666' of git://trac.sagemath.org/sage into matroid
-rw-r--r--src/sage/matroids/matroid.pxd2
-rw-r--r--src/sage/matroids/matroid.pyx238
2 files changed, 240 insertions, 0 deletions
diff --git a/src/sage/matroids/matroid.pxd b/src/sage/matroids/matroid.pxd
index eb4fc8e..1325ddc 100644
--- a/src/sage/matroids/matroid.pxd
+++ b/src/sage/matroids/matroid.pxd
@@ -171,6 +171,8 @@ cdef class Matroid(SageObject):
# optimization
cpdef max_weight_independent(self, X=*, weights=*)
cpdef max_weight_coindependent(self, X=*, weights=*)
+ cpdef is_max_weight_independent_generic(self, X=*, weights=*)
+ cpdef is_max_weight_coindependent_generic(self, X=*, weights=*)
cpdef intersection(self, other, weights=*)
cpdef _intersection(self, other, weights)
cpdef _intersection_augmentation(self, other, weights, Y)
diff --git a/src/sage/matroids/matroid.pyx b/src/sage/matroids/matroid.pyx
index e33522c..fddb1c1 100644
--- a/src/sage/matroids/matroid.pyx
+++ b/src/sage/matroids/matroid.pyx
@@ -120,6 +120,7 @@ additional functionality (e.g. linear extensions).
- Optimization
- :meth:`max_weight_independent() <sage.matroids.matroid.Matroid.max_weight_independent>`
- :meth:`max_weight_coindependent() <sage.matroids.matroid.Matroid.max_weight_coindependent>`
+ - :meth:`is_max_weight_independent_generic() <sage.matroids.matroid.Matroid.is_max_weight_independent_generic>`
- :meth:`intersection() <sage.matroids.matroid.Matroid.intersection>`
- :meth:`intersection_unweighted() <sage.matroids.matroid.Matroid.intersection_unweighted>`
@@ -6408,6 +6409,243 @@ cdef class Matroid(SageObject):
res.discard(e)
return frozenset(res)
+ cpdef is_max_weight_independent_generic(self, X=None, weights=None):
+ r"""
+ Test if only one basis of the subset ``X`` has maximal
+ weight.
+
+ The *weight* of a subset ``S`` is ``sum(weights(e) for e in S)``.
+
+ The method :meth:`is_max_weight_coindependent_generic`
+ computes the same function using a different algorithm.
+
+ INPUT:
+
+ - ``X`` -- (default: the ground set of ``self``) a subset of
+ ``self.groundset()`` (given as an iterable).
+ - ``weights`` -- a dictionary or function mapping the elements of
+ ``X`` to nonnegative weights.
+
+ OUTPUT:
+
+ Boolean.
+
+ ALGORITHM:
+
+ The greedy algorithm. If a weight function is given, then sort the elements
+ of ``X`` by decreasing weight, and otherwise use the ordering in which ``X``
+ lists its elements. Then greedily select elements if they are independent
+ of all that was selected before. If an element is not independent of the
+ previously selected elements, then we check if it is independent with the
+ previously selected elements with higher weight.
+
+
+ EXAMPLES::
+
+ sage: from sage.matroids.advanced import setprint
+ sage: M = matroids.named_matroids.Fano()
+ sage: M.is_max_weight_independent_generic()
+ False
+
+ sage: def wt(x):
+ ....: return x
+ ....:
+ sage: M = matroids.Uniform(2, 8)
+ sage: M.is_max_weight_independent_generic(weights=wt)
+ True
+ sage: M.is_max_weight_independent_generic(weights={x: x for x in M.groundset()})
+ True
+ sage: M.is_max_weight_independent_generic()
+ False
+ """
+ res = []
+ r = 0
+ if X is None:
+ X = self.groundset()
+ else:
+ if not self.groundset().issuperset(X):
+ raise ValueError("input is not a subset of the groundset.")
+ if len(X) == 0:
+ return True
+
+ # If there are no weights, then our elements are already in weakly decreasing order
+ if weights is None:
+ Y = list(X)
+ for e in Y:
+ res.append(e)
+ if self._rank(res) > r:
+ r += 1
+ else:
+ del res[-1]
+ if self._rank([e]) >= 1:
+ return False
+ return True
+
+
+ # Construct ``Y``: a list of all elements of ``X``
+ # in order of weakly decreasing weight.
+ # and a dictionary that gives the weights of the elementns of X.
+ else:
+ wt = []
+ wt_dic = {}
+ try:
+ for e in X:
+ wt.append((weights[e], e))
+ wt_dic[e] = weights[e]
+ except (IndexError, TypeError, ValueError):
+ try:
+ wt = []
+ for e in X:
+ wt.append((weights(e), e))
+ wt_dic[e] = weights(e)
+ except (TypeError, ValueError):
+ raise TypeError("the weights argument does not seem to be a collection of weights for the set X.")
+
+ wt = sorted(wt, reverse=True)
+ if wt[-1][1] < 0:
+ raise ValueError("nonnegative weights were expected.")
+ Y = [e for (w, e) in wt]
+
+ # res is a partally built maximal weighted basis. smres, when used is the elements of
+ # e that are strictly larger than e, together with e itself.
+ # If smres is independent when e was not added to res, then it could have been added to res
+ # if we made different choices in the greedy algorithm, so our building or res does not result
+ # in a unique maximal weight basis.
+ smres = []
+ for e in Y:
+ if len(res) >= 1: #This guarantees that smres is the elements of res that are strictly larger than e.
+ if wt_dic[e] < wt_dic[res[-1]]:
+ smres=res[:]
+ res.append(e)
+ if self._rank(res) > r:
+ r += 1
+ else:
+ smres.append(e)
+ if self._rank(smres) >= len(smres):
+ return False
+ del smres[-1]
+ del res[-1]
+ return True
+
+ cpdef is_max_weight_coindependent_generic(self, X=None, weights=None):
+ r"""
+ Test if only one basis of the subset ``X`` has maximal
+ weight.
+
+ The *weight* of a subset ``S`` is ``sum(weights(e) for e in S)``.
+
+ The method :meth:`is_max_weight_independent_generic`
+ computes the same function using a different algorithm.
+
+ INPUT:
+
+ - ``X`` -- (default: the ground set of ``self``) a subset of
+ ``self.groundset()`` (given as an iterable).
+ - ``weights`` -- a dictionary or function mapping the elements of
+ ``X`` to nonnegative weights.
+
+ OUTPUT:
+
+ Boolean.
+
+ ALGORITHM:
+
+ The greedy algorithm. If a weight function is given, then sort the elements
+ of ``X`` by decreasing weight, and otherwise use the ordering in which ``X``
+ lists its elements. Then greedily select elements if they are coindependent
+ of all that was selected before. If an element is not coindependent of the
+ previously selected elements, then we check if it is coindependent with the
+ previously selected elements with higher weight.
+
+
+ EXAMPLES::
+
+ sage: from sage.matroids.advanced import setprint
+ sage: M = matroids.named_matroids.Fano()
+ sage: M.is_max_weight_coindependent_generic()
+ False
+
+ sage: def wt(x):
+ ....: return x
+ ....:
+ sage: M = matroids.Uniform(2, 8)
+ sage: M.is_max_weight_coindependent_generic(weights=wt)
+ True
+ sage: M.is_max_weight_coindependent_generic(weights={x: x for x in M.groundset()})
+ True
+ sage: M.is_max_weight_coindependent_generic()
+ False
+ """
+ res = []
+ r = 0
+ if X is None:
+ X = self.groundset()
+ else:
+ if not self.groundset().issuperset(X):
+ raise ValueError("input is not a subset of the groundset.")
+ if len(X) == 0:
+ return True
+
+ # If there are no weights, then our elements are already in weakly decreasing order
+ if weights is None:
+ Y = list(X)
+ for e in Y:
+ res.append(e)
+ if self._corank(res) > r:
+ r += 1
+ else:
+ del res[-1]
+ if self._corank([e]) >= 1:
+ return False
+ return True
+
+
+ # Construct ``Y``: a list of all elements of ``X``
+ # in order of weakly decreasing weight.
+ # and a dictionary that gives the weights of the elementns of X.
+ else:
+ wt = []
+ wt_dic = {}
+ try:
+ for e in X:
+ wt.append((weights[e], e))
+ wt_dic[e] = weights[e]
+ except (IndexError, TypeError, ValueError):
+ try:
+ wt = []
+ for e in X:
+ wt.append((weights(e), e))
+ wt_dic[e] = weights(e)
+ except (TypeError, ValueError):
+ raise TypeError("the weights argument does not seem to be a collection of weights for the set X.")
+
+ wt = sorted(wt, reverse=True)
+ if wt[-1][1] < 0:
+ raise ValueError("nonnegative weights were expected.")
+ Y = [e for (w, e) in wt]
+
+ # res is a partally built maximal weighted cobasis. smres, when used is the elements of
+ # e that are strictly larger than e, together with e itself.
+ # If smres is coindependent when e was not added to res, then it could have been added to res
+ # if we made different choices in the greedy algorithm, so our building or res does not result
+ # in a unique maximal weight cobasis.
+ smres = []
+ for e in Y:
+ if len(res) >= 1: #This guarantees that smres is the elements of res that are strictly larger than e.
+ if wt_dic[e] < wt_dic[res[-1]]:
+ smres=res[:]
+ res.append(e)
+ if self._corank(res) > r:
+ r += 1
+ else:
+ smres.append(e)
+ if self._corank(smres) >= len(smres):
+ return False
+ del smres[-1]
+ del res[-1]
+ return True
+
+
cpdef intersection(self, other, weights=None):
r"""
Return a maximum-weight common independent set.