#14666: Test if a weight function is generic for a given matroid
-------------------------------------+-------------------------------------
Reporter: Stefan | Owner: Stefanf
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-6.4
Component: matroid theory | Resolution:
Keywords: matroid, weight | Merged in:
function | Reviewers:
Authors: | Work issues:
Report Upstream: N/A | Commit:
Branch: | 62fa4205a56150bf5301496d6dc770ffa29b5270
u/tara/test_if_a_weight_function_is_generic_for_a_given_matroid| Stopgaps:
Dependencies: 7477 |
-------------------------------------+-------------------------------------
Comment (by tara):
Hi Darij,
We decided to avoid the suggestion given in the ticket, because it would
require checking if up to $r(|E|$-r)$ additional sets were independent.
(This could have been reduced, by only checking exchanges where the two
elements had the same weight.) Our strategy was whenever we decided not to
put an element $e$ into our basis $B$, we checked if would have been
allowed to put it in if we had done so as soon as possible. In the case
where we were not passed a weight function, this amounts to checking
whether or not $\{e\}$ is independent. If we were passed a weight
function, we check if the set smres is independent, where smres is all the
things in res which have strictly more weight than $e$ together with $e$.
Essentially what I did was to copy the code for max_weight_independent()
and modify it to see if it through out something that could have been kept
in some application of the greedy algorithm. Other than declaring smres
and changing the return statements to give booleans, I added the code
following code to the case where I wanted to discard $e$. The only
difference between is_max_weight_independent_generic() and
is_max_weight_coindependent_generic() is that 'rank' was replaced with
'corank' in both places.
I agree that $X$ is just restricting the matroid to $X$.
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:
return False
Cheers,
Tara
--
Ticket URL: <http://trac.sagemath.org/ticket/14666#comment:10>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
