Opened 6 years ago
Closed 3 years ago
#14666 closed enhancement (fixed)
Test if a weight function is generic for a given matroid
Reported by:  Stefan  Owned by:  Stefanf 

Priority:  minor  Milestone:  sage7.2 
Component:  matroid theory  Keywords:  matroid, weight function 
Cc:  darij, yomcat  Merged in:  
Authors:  Tara Fife  Reviewers:  Darij Grinberg 
Report Upstream:  N/A  Work issues:  
Branch:  53dc43d (Commits)  Commit:  53dc43d1bfff644927da9352c24279bcf897ba9c 
Dependencies:  Stopgaps: 
Description
Reported by darij on http://trac.sagemath.org/sage_trac/ticket/7477 :
Feature suggestion, if not already implemented: a method to test if a given weight function is generic, i. e., has exactly one maximizing basis. Of course, this is easy thanks to the exchange graph, as one only needs to find a maximizing basis and then check that all its exchange neighbours have strictly smaller weight. This function is useful to some Hopfalgebraic constructions.
Change History (55)
comment:1 Changed 6 years ago by
 Cc darij added
comment:2 Changed 6 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:3 Changed 5 years ago by
 Component changed from combinatorics to matroid theory
 Owner changed from sagecombinat to Stefanf
comment:4 Changed 5 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:5 Changed 5 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:6 Changed 5 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:7 Changed 3 years ago by
 Branch set to u/tara/test_if_a_weight_function_is_generic_for_a_given_matroid
comment:8 Changed 3 years ago by
 Commit set to 62fa4205a56150bf5301496d6dc770ffa29b5270
 Status changed from new to needs_review
comment:9 Changed 3 years ago by
Thank you! May I ask a couple questions before I look deeper into the code?
 What is the difference between the two functions?
 What exactly is
X
used for? I assume the answer somehow depends onX
. Is it just restricting the matroid toX
?
comment:10 Changed 3 years ago by
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
comment:11 Changed 3 years ago by
I realized, as I was writing that last comment, that I was doing more work than necessary, because I was rebuilding smres each time it was needed, instead of keeping it updated. I rewrote the code to avoid that. I also moved the conditional if weights(e)==weights(f) to the outside of the forloop, so that it wasn't asked each time. I think that this also improves code readability, but I'm not entirely sure about that.
comment:12 Changed 3 years ago by
 Commit changed from 62fa4205a56150bf5301496d6dc770ffa29b5270 to da97f302b53c5a53f33ee53fe9b88a173245c9d5
Branch pushed to git repo; I updated commit sha1. New commits:
da97f30  Eddited is_max_weight_independent_generic() and is_max_weight_coindependent_generic

comment:13 Changed 3 years ago by
 Branch changed from u/tara/test_if_a_weight_function_is_generic_for_a_given_matroid to public/ticket/14666
 Commit changed from da97f302b53c5a53f33ee53fe9b88a173245c9d5 to 059b6d3816eae7412bc5e6570c17888fa2b75678
 Dependencies 7477 deleted
 Milestone changed from sage6.4 to sage7.2
New commits:
059b6d3  documentation

comment:14 followup: ↓ 18 Changed 3 years ago by
I've made some changes (NB: branch change!), particularly documenting one of the undocumented codepaths (namely, passing a dictionary for weight
). However, it exposed a bug: The algorithm assumes weight
to be a function.
My suggestion here would be to change the way dictionaries are handled. Rather than doing the try/except
s, I'd check whether weight
is a dictionary, and then define a function weight_fun
to send each e
to weight[e]
. Otherwise, I'd just set weight_fun = weight
. All other uses of weight
in the code should then be replaced by weight_fun
. Does this sound reasonable to you? (I haven't done any speed comparisons or other tests, so this might not actually be a good idea.)
Also, the algorithm looks nice and clean. I haven't proven it yet. Is it easy or should I know something it follows from?
Thanks for the good work!
comment:15 Changed 3 years ago by
Also, I'm not fully sure about what goes on here:
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
Am I seeing it right that smres
never has length >1 ? So you are essentially checking that e
is a loop; if it isn't, then you return False
? Do you really need an array for that?
comment:16 Changed 3 years ago by
The algorithm follows from the idea that whenever we apply the greedy algorithm, we get a maximal basis, and we can get each maximal basis by using the greedy algorithm. A maximal weighted basis B
is unique if and only if for every e\in E(M)B
, we have e
is in the closure of {b\in Bw(b)>w(e)}
. In other words, B
is unique, if when using the greedy algorithm, we never were able to choose an element of E(M)B
.
We don't need an array for smres
in the weights is None case. I had originally put both cases in one for loop, until I realized that that was gross, and I didn't notice, when I changed it, that smres
is now pointless in that case.
comment:17 followup: ↓ 19 Changed 3 years ago by
OK, that's a nice algorithm! That said, I don't really understand the way you implemented it; the concrete meaning of smres
is unclear to me (some loop invariants might be helpful).
The two methods are really supposed to do the same thing, just in different ways? Are the ways really functionally different, i.e. one is a lot faster in some situations and the other in others?
I'd also be indebted if you could do the fixes I suggested in my previous post. I don't trust myself that much with cpdefs...
comment:18 in reply to: ↑ 14 Changed 3 years ago by
Replying to darij:
I've made some changes (NB: branch change!), particularly documenting one of the undocumented codepaths (namely, passing a dictionary for
weight
). However, it exposed a bug: The algorithm assumesweight
to be a function.My suggestion here would be to change the way dictionaries are handled. Rather than doing the
try/except
s, I'd check whetherweight
is a dictionary, and then define a functionweight_fun
to send eache
toweight[e]
. Otherwise, I'd just setweight_fun = weight
. All other uses ofweight
in the code should then be replaced byweight_fun
. Does this sound reasonable to you? (I haven't done any speed comparisons or other tests, so this might not actually be a good idea.)
In Python, any object can implement the square bracket and round bracket notation. Your suggestion would make it impossible to have a matroid with ground set 0..n and weight function just a list.
This code was borrowed from the max_weight_independent method, where in the examples both dictionary and function specifications are tested. Do you have an example of when your bug occurs?
comment:19 in reply to: ↑ 17 Changed 3 years ago by
Replying to darij:
OK, that's a nice algorithm! That said, I don't really understand the way you implemented it; the concrete meaning of
smres
is unclear to me (some loop invariants might be helpful).The two methods are really supposed to do the same thing, just in different ways? Are the ways really functionally different, i.e. one is a lot faster in some situations and the other in others?
I'd also be indebted if you could do the fixes I suggested in my previous post. I don't trust myself that much with cpdefs...
I would expect the second function to be the dual of the first. Is that the case here?
comment:20 followups: ↓ 21 ↓ 24 Changed 3 years ago by
Yes, I've added such an example in my commit  if you run the doctests, you'll see it fail.
What do you mean by "the dual"?
comment:21 in reply to: ↑ 20 Changed 3 years ago by
Replying to darij:
Yes, I've added such an example in my commit  if you run the doctests, you'll see it fail.
What do you mean by "the dual"?
I mean that I'd expect
M.is_max_weight_coindependent_generic
to return the output of
M.dual().is_max_weight_independent_generic
comment:22 followup: ↓ 23 Changed 3 years ago by
Oh. But if so, the doc should be different!
comment:23 in reply to: ↑ 22 Changed 3 years ago by
comment:24 in reply to: ↑ 20 ; followup: ↓ 25 Changed 3 years ago by
Replying to darij:
Yes, I've added such an example in my commit  if you run the doctests, you'll see it fail.
What do you mean by "the dual"?
I see it. The problem is that the user input variable "weights" is used down the line, as opposed to the object created in the try/except blocks. The list wt
is not so useful, so I would probably define something that's guaranteed to be a function, like so:
if callable(weights): wts = weights else: wts = lambda x: weights[x]
Then use wts instead of weights down the line.
For the record, to test a file, run (from the top sage
directory):
./sage t src/sage/matroids/matroid.pyx
comment:25 in reply to: ↑ 24 Changed 3 years ago by
Replying to Stefan:
I see it. The problem is that the user input variable "weights" is used down the line, as opposed to the object created in the try/except blocks. The list
wt
is not so useful, so I would probably define something that's guaranteed to be a function, like so:if callable(weights): wts = weights else: wts = lambda x: weights[x]Then use wts instead of weights down the line.
The reason that wt
is currently useful, is that it is used to sort the elements in decreasing order of weight. I'm not sure how to do that with only a function wts
. I tried adding the function wts, but I ended up having it not compile. I'll look at it again tomorrow.
comment:26 followup: ↓ 27 Changed 3 years ago by
What's the error? Maybe callable() isn't supported in Cython?
Yeah, you'll need both. Since you need the output in order, you can't just call the max_weight_independent function either, unfortunately.
comment:27 in reply to: ↑ 26 Changed 3 years ago by
Replying to Stefan:
What's the error? Maybe callable() isn't supported in Cython?
It won't compile when I have the line
wts = lambda x: weights[x]
It will, however, compile when I have
if callable(weights): wts = weights else: return True
So for some reason, that I don't understand, we're not allowed to use lambda in this way. Functions in other places in the file use lambda inside a function call, and I don't see a difference in the syntax that we are using. I have also tried using
def wts(x) : return weights[x]
.
comment:28 Changed 3 years ago by
Does Cython actually know lambda at all? And if so, does it allow functions without specified input and output types?
(This is not a rhetorical question; I really have no idea.)
comment:29 Changed 3 years ago by
 Status changed from needs_review to needs_work
Ah, you can have them inside a def but not inside a cpdef.
So you're going to need a less elegant solution. Easiest but least elegant is to repeat the code twice, once with () and once with [].
comment:30 Changed 3 years ago by
What about a def frontend and a cpdef backend? Of course, we'd need to figure out whether the backend should take a dict or a function... Is it possible to wrap up a dict in a function and send it to the backend, or will the backend not accept such a function?
comment:31 Changed 3 years ago by
 Cc yomcat added
comment:32 Changed 3 years ago by
 Commit changed from 059b6d3816eae7412bc5e6570c17888fa2b75678 to c75ee707326fc1cc1beb0e265359c0f93cb84ac2
Branch pushed to git repo; I updated commit sha1. New commits:
c75ee70  This is eddited now to accept both functions and dictionaries for the weight parameter.

comment:33 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:34 followup: ↓ 35 Changed 3 years ago by
Nice, this looks a lot better. But I still struggle to find a mental model for smres
. From your description of the algorithm, it should be the list containing all elements of res
having higher weight than e
, and e
itself. But from the code, it seems to be the list containing all elements of res
having higher weight than e
, and the first element of res
that has the same weight as e
(because e
does not get appended to smres
unless e
sets a negative weight record). Am I reading the code right, and is this an actual issue? Thank you!
comment:35 in reply to: ↑ 34 Changed 3 years ago by
Replying to darij:
Nice, this looks a lot better. But I still struggle to find a mental model for
smres
. From your description of the algorithm, it should be the list containing all elements ofres
having higher weight thane
, ande
itself. But from the code, it seems to be the list containing all elements ofres
having higher weight thane
, and the first element ofres
that has the same weight ase
(becausee
does not get appended tosmres
unlesse
sets a negative weight record). Am I reading the code right, and is this an actual issue? Thank you!
You're correct, there was a problem with smres
. I wasn't adding e
to it all the time. I had moved some things about to make it read nicer, and introduced that bug.
comment:36 Changed 3 years ago by
 Commit changed from c75ee707326fc1cc1beb0e265359c0f93cb84ac2 to f92c81dbf9f8bcc923a7597ede63a5bab613b397
Branch pushed to git repo; I updated commit sha1. New commits:
f92c81d  Fixed bug with smres and added clarifying comments.

comment:37 Changed 3 years ago by
 Commit changed from f92c81dbf9f8bcc923a7597ede63a5bab613b397 to edb1a33e776a3371def0acc07ab123812d9c2afa
Branch pushed to git repo; I updated commit sha1. New commits:
64f76ad  Merge branch 'public/ticket/14666' of git://trac.sagemath.org/sage into matroid

b5d0f5f  documentation & comments

bb0b698  example from Hopf notes

1f13c96  another doctest (one that is sensitive to max/min distinction)

edb1a33  fix sign error in is_max_weight_coindependent_generic

comment:38 Changed 3 years ago by
 Reviewers set to Darij Grinberg
Thank you!
I've made my own changes. (Only one change to the code proper: The is_max_weight_coindependent_generic
function was doing the same as is_max_weight_independent_generic
but for the dual matroid of self
instead of self
. Now it does what it claims to do.) If the result looks good to you, please set this to positive_review. Thanks again for implementing this!
Also, if your "we" includes some other authors, I guess they should go into the author field as well.
comment:39 Changed 3 years ago by
PS. I replaced your "iterable" by "list, tuple or set" because I don't think an iterator would have worked. (That said, I haven't tried.)
comment:40 Changed 3 years ago by
 Commit changed from edb1a33e776a3371def0acc07ab123812d9c2afa to 4031e326dcdf7a40072483267f45362bf2f88709
Branch pushed to git repo; I updated commit sha1. New commits:
4031e32  more doc fixes

comment:41 Changed 3 years ago by
The only thing that looks like a problem is in edb1a33, you changed wt = sorted(wt, reverse=True)
to wt = sorted(wt)
in line 6667. And later changed if wt_dic[e] < wt_dic[res[1]]:
to if wt_dic[e] > wt_dic[res[1]]:
. It seems like this would test if a minimum cobasis was generic rather than a maximum cobasis. I would expect M.is_max_weight_coindependent_generic()
to give the same results as M*.is_max_weight_independent_generic()
, where M*
is the dual of M
.
comment:42 followup: ↓ 43 Changed 3 years ago by
Oh! But then you should not be claiming that the two methods are doing the same thing. I changed the methods to achieve precisely this effect.
comment:43 in reply to: ↑ 42 Changed 3 years ago by
Replying to darij:
Oh! But then you should not be claiming that the two methods are doing the same thing. I changed the methods to achieve precisely this effect.
When I execute the following code, using the current version, I get True
and then False
. We should expect True
in both cases, because {3,4}
is the only maximum weighted basis of M
.
from sage.matroids.advanced import setprint M=matroids.Uniform(2,5) wt={0: 1, 1: 1, 2: 1, 3: 2, 4: 2} M.is_max_weight_independent_generic(weights=wt) M.dual().is_max_weight_coindependent_generic(weights=wt)
However, when I change those two lines back, I get True
for both outputs. Furthermore, the code in is_max_weight_coindependent_generic
looking the same as is_max_weight_independent_generic
, excepting that rank
is changed to corank
makes intuitive sense to me.
comment:44 followup: ↓ 48 Changed 3 years ago by
Feel free to change this back... but then please rewrite this documentation:
+ The method :meth:`is_max_weight_coindependent_generic` + computes the same function using a different algorithm.
(and the similar claim on the other method). "The same function", in my eyes, means literally the same function, not the same function on the dual matroid!
comment:45 Changed 3 years ago by
 Commit changed from 4031e326dcdf7a40072483267f45362bf2f88709 to 5baccc674c1616978db0d70360722661813cc0ce
Branch pushed to git repo; I updated commit sha1. New commits:
5baccc6  fix error in is_max_weight_coindependent_generic

comment:46 Changed 3 years ago by
PS. This:
+ cpdef is_max_weight_coindependent_generic(self, X=None, weights=None): + r""" + Test if only one basis of the subset ``X`` has maximal + weight.
also should have "cobasis" rather than "basis", right?
comment:47 Changed 3 years ago by
 Commit changed from 5baccc674c1616978db0d70360722661813cc0ce to fc8a795bdab5dd48e00b99a88a6ef0d54590314e
Branch pushed to git repo; I updated commit sha1. New commits:
fc8a795  Fixed error in documentation

comment:48 in reply to: ↑ 44 Changed 3 years ago by
Replying to darij:
Feel free to change this back... but then please rewrite this documentation:
+ The method :meth:`is_max_weight_coindependent_generic` + computes the same function using a different algorithm.(and the similar claim on the other method). "The same function", in my eyes, means literally the same function, not the same function on the dual matroid!
You're right, that sentence is confusing. I haven't been checking the documentation as well as I should have been doing. I think that i was trying to say there is covered in the Algorithm section, and I didn't see other functions having a method section, so I don't know why I put that in in the first place. Thanks for being so scrupulous.
New commits:
fc8a795  Fixed error in documentation

comment:49 Changed 3 years ago by
Sorry for continuous annoyance, but please also see comment:46. (I would do this myself, but I'll probably have a negative amount of spare time today...) Once you've fixed the doc, you have my positive review!
comment:50 Changed 3 years ago by
 Commit changed from fc8a795bdab5dd48e00b99a88a6ef0d54590314e to 3fa15f2a97ee6002a1efddd0360a38416ffb6844
Branch pushed to git repo; I updated commit sha1. New commits:
3fa15f2  Fixed error in documentation

comment:52 Changed 3 years ago by
 Status changed from positive_review to needs_work
Doctests fail as evident in the patchbot report
comment:53 Changed 3 years ago by
 Commit changed from 3fa15f2a97ee6002a1efddd0360a38416ffb6844 to 53dc43d1bfff644927da9352c24279bcf897ba9c
Branch pushed to git repo; I updated commit sha1. New commits:
53dc43d  fix a wrong doctest

comment:54 Changed 3 years ago by
 Status changed from needs_work to positive_review
Oops! Fallout from our previous misunderstanding about what the two functions were supposed to do. Should be correct now.
comment:55 Changed 3 years ago by
 Branch changed from public/ticket/14666 to 53dc43d1bfff644927da9352c24279bcf897ba9c
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
added is_max_weight_independent_generic() and is_max_weight_coindependent_generic()