summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTara Fife <fi.tara@gmail.com>2016-04-09 10:35:32 -0500
committerTara Fife <fi.tara@gmail.com>2016-04-09 10:35:32 -0500
commitda97f302b53c5a53f33ee53fe9b88a173245c9d5 (patch)
tree6393aa6713d3910331e874ed0c1538eae4f7b535
parentadded is_max_weight_independent_generic() and is_max_weight_coindependent_gen... (diff)
Eddited is_max_weight_independent_generic() and is_max_weight_coindependent_genericu/tara/test_if_a_weight_function_is_generic_for_a_given_matroid
Broke the for loop into two cases, one where weights is None, and one where weights is defined. I also changed res and smres to lists so that I could update smres instead of rebuilding it whenever it was needed.
-rw-r--r--src/sage/matroids/matroid.pyx92
1 files changed, 57 insertions, 35 deletions
diff --git a/src/sage/matroids/matroid.pyx b/src/sage/matroids/matroid.pyx
index c727673..c82fa46 100644
--- a/src/sage/matroids/matroid.pyx
+++ b/src/sage/matroids/matroid.pyx
@@ -6440,7 +6440,7 @@ cdef class Matroid(SageObject):
sage: from sage.matroids.advanced import setprint
sage: M = matroids.named_matroids.Fano()
- sage: M.max_weight_independent()
+ sage: M.is_max_weight_independent_generic()
False
sage: def wt(x):
@@ -6477,25 +6477,36 @@ cdef class Matroid(SageObject):
if wt[-1][1] < 0:
raise ValueError("nonnegative weights were expected.")
Y = [e for (w, e) in wt]
- res = set([])
- smres= set([])
+ res = []
+ smres= []
r = 0
+ if weights is None:
+ for e in Y:
+ res.append(e)
+ if self._rank(res) > r:
+ r += 1
+ else:
+ del res[-1]
+ smres.append(e)
+ if self._rank(smres) >= 1:
+ return False
+ else:
+ del smres[-1]
+ return True
for e in Y:
- res.add(e)
+ res.append(e)
if self._rank(res) > r:
r += 1
+ if len(res) >= 2:
+ if weights(e) < weights(res[-2]):
+ smres=res[:]
+ del smres[-1]
else:
- res.discard(e)
- smres=res
- if weights is None:
- if self._rank(set([e]))>0:
- return False
- else:
- for f in res:
- if weights(e)==weights(f):
- smres.discard(f)
- smres.add(e)
- if self._rank(smres) > len(smres)-1:
+ if len(res) >= 2:
+ if weights(e) < weights(res[-2]):
+ smres=res[:]
+ del res[-1]
+ if self._rank(smres) >= len(smres):
return False
return True
@@ -6520,9 +6531,9 @@ cdef class Matroid(SageObject):
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
+ 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.
@@ -6530,16 +6541,16 @@ cdef class Matroid(SageObject):
sage: from sage.matroids.advanced import setprint
sage: M = matroids.named_matroids.Fano()
- sage: M.max_weight_independent()
+ 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_independent_generic(weights=wt)
+ sage: M.is_max_weight_coindependent_generic(weights=wt)
True
- sage: M.is_max_weight_independent_generic()
+ sage: M.is_max_weight_coindependent_generic()
False
"""
if X is None:
@@ -6567,25 +6578,36 @@ cdef class Matroid(SageObject):
if wt[-1][1] < 0:
raise ValueError("nonnegative weights were expected.")
Y = [e for (w, e) in wt]
- res = set([])
- smres= set([])
+ res = []
+ smres= []
r = 0
+ if weights is None:
+ for e in Y:
+ res.append(e)
+ if self._corank(res) > r:
+ r += 1
+ else:
+ del res[-1]
+ smres.append(e)
+ if self._corank(smres) >= 1:
+ return False
+ else:
+ del smres[-1]
+ return True
for e in Y:
- res.add(e)
+ res.append(e)
if self._corank(res) > r:
r += 1
+ if len(res) >= 2:
+ if weights(e) < weights(res[-2]):
+ smres=res[:]
+ del smres[-1]
else:
- res.discard(e)
- smres=res
- if weights is None:
- if self._rank(set([e]))>0:
- return False
- else:
- for f in res:
- if weights(e)==weights(f):
- smres.discard(f)
- smres.add(e)
- if self._corank(smres) > len(smres)-1:
+ if len(res) >= 2:
+ if weights(e) < weights(res[-2]):
+ smres=res[:]
+ del res[-1]
+ if self._corank(smres) >= len(smres):
return False
return True