Opened 4 years ago

Closed 17 months 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: sage-7.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 Hopf-algebraic constructions.

Change History (55)

comment:1 Changed 4 years ago by darij

  • Cc darij added

comment:2 Changed 4 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:3 Changed 4 years ago by Stefan

  • Component changed from combinatorics to matroid theory
  • Owner changed from sage-combinat to Stefanf

comment:4 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:6 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:7 Changed 19 months ago by tara

  • Branch set to u/tara/test_if_a_weight_function_is_generic_for_a_given_matroid

comment:8 Changed 19 months ago by tara

  • Commit set to 62fa4205a56150bf5301496d6dc770ffa29b5270
  • Status changed from new to needs_review

New commits:

62fa420added is_max_weight_independent_generic() and is_max_weight_coindependent_generic()

comment:9 Changed 19 months ago by darij

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 on X. Is it just restricting the matroid to X?

comment:10 Changed 19 months ago 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

comment:11 Changed 19 months ago by tara

I realized, as I was writing that last comment, that I was doing more work than necessary, because I was re-building smres each time it was needed, instead of keeping it updated. I re-wrote the code to avoid that. I also moved the conditional if weights(e)==weights(f) to the outside of the for-loop, 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 19 months ago by git

  • Commit changed from 62fa4205a56150bf5301496d6dc770ffa29b5270 to da97f302b53c5a53f33ee53fe9b88a173245c9d5

Branch pushed to git repo; I updated commit sha1. New commits:

da97f30Eddited is_max_weight_independent_generic() and is_max_weight_coindependent_generic

comment:13 Changed 18 months ago by darij

  • 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 sage-6.4 to sage-7.2

New commits:

059b6d3documentation

comment:14 follow-up: Changed 18 months ago by 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 assumes weight to be a function.

My suggestion here would be to change the way dictionaries are handled. Rather than doing the try/excepts, 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!

Version 0, edited 18 months ago by darij (next)

comment:15 Changed 18 months ago by darij

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 18 months ago by tara

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 B|w(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 follow-up: Changed 18 months ago by 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...

comment:18 in reply to: ↑ 14 Changed 18 months ago by Stefan

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 assumes weight to be a function.

My suggestion here would be to change the way dictionaries are handled. Rather than doing the try/excepts, 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.)

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 18 months ago by Stefan

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 follow-ups: Changed 18 months ago by 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"?

comment:21 in reply to: ↑ 20 Changed 18 months ago by Stefan

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 follow-up: Changed 18 months ago by darij

Oh. But if so, the doc should be different!

comment:23 in reply to: ↑ 22 Changed 18 months ago by Stefan

Replying to darij:

Oh. But if so, the doc should be different!

Agreed

comment:24 in reply to: ↑ 20 ; follow-up: Changed 18 months ago by Stefan

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 18 months ago by tara

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 follow-up: Changed 18 months ago by Stefan

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 18 months ago by tara

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 18 months ago by darij

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 18 months ago by Stefan

  • 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 18 months ago by darij

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 18 months ago by yomcat

  • Cc yomcat added

comment:32 Changed 18 months ago by git

  • Commit changed from 059b6d3816eae7412bc5e6570c17888fa2b75678 to c75ee707326fc1cc1beb0e265359c0f93cb84ac2

Branch pushed to git repo; I updated commit sha1. New commits:

c75ee70This is eddited now to accept both functions and dictionaries for the weight parameter.

comment:33 Changed 18 months ago by tara

  • Status changed from needs_work to needs_review

comment:34 follow-up: Changed 18 months ago by 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 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 18 months ago by tara

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 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!

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 18 months ago by git

  • Commit changed from c75ee707326fc1cc1beb0e265359c0f93cb84ac2 to f92c81dbf9f8bcc923a7597ede63a5bab613b397

Branch pushed to git repo; I updated commit sha1. New commits:

f92c81dFixed bug with smres and added clarifying comments.

comment:37 Changed 18 months ago by git

  • Commit changed from f92c81dbf9f8bcc923a7597ede63a5bab613b397 to edb1a33e776a3371def0acc07ab123812d9c2afa

Branch pushed to git repo; I updated commit sha1. New commits:

64f76adMerge branch 'public/ticket/14666' of git://trac.sagemath.org/sage into matroid
b5d0f5fdocumentation & comments
bb0b698example from Hopf notes
1f13c96another doctest (one that is sensitive to max/min distinction)
edb1a33fix sign error in is_max_weight_coindependent_generic

comment:38 Changed 18 months ago by darij

  • Authors set to Tara Fife
  • 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 18 months ago by darij

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 18 months ago by git

  • Commit changed from edb1a33e776a3371def0acc07ab123812d9c2afa to 4031e326dcdf7a40072483267f45362bf2f88709

Branch pushed to git repo; I updated commit sha1. New commits:

4031e32more doc fixes

comment:41 Changed 17 months ago by tara

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.

My "we" sometimes included Stefan. He and I are both at LSU, and he's given recommendations. He might have avoided writing code so that he would be free to review it.

Last edited 17 months ago by tara (previous) (diff)

comment:42 follow-up: Changed 17 months ago by 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.

comment:43 in reply to: ↑ 42 Changed 17 months ago by tara

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 follow-up: Changed 17 months ago by 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!

comment:45 Changed 17 months ago by git

  • Commit changed from 4031e326dcdf7a40072483267f45362bf2f88709 to 5baccc674c1616978db0d70360722661813cc0ce

Branch pushed to git repo; I updated commit sha1. New commits:

5baccc6fix error in is_max_weight_coindependent_generic

comment:46 Changed 17 months ago by darij

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 17 months ago by git

  • Commit changed from 5baccc674c1616978db0d70360722661813cc0ce to fc8a795bdab5dd48e00b99a88a6ef0d54590314e

Branch pushed to git repo; I updated commit sha1. New commits:

fc8a795Fixed error in documentation

comment:48 in reply to: ↑ 44 Changed 17 months ago by tara

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:

fc8a795Fixed error in documentation

comment:49 Changed 17 months ago by darij

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 17 months ago by git

  • Commit changed from fc8a795bdab5dd48e00b99a88a6ef0d54590314e to 3fa15f2a97ee6002a1efddd0360a38416ffb6844

Branch pushed to git repo; I updated commit sha1. New commits:

3fa15f2Fixed error in documentation

comment:51 Changed 17 months ago by darij

  • Status changed from needs_review to positive_review

Wonderful!

comment:52 Changed 17 months ago by vbraun

  • Status changed from positive_review to needs_work

Doctests fail as evident in the patchbot report

comment:53 Changed 17 months ago by git

  • Commit changed from 3fa15f2a97ee6002a1efddd0360a38416ffb6844 to 53dc43d1bfff644927da9352c24279bcf897ba9c

Branch pushed to git repo; I updated commit sha1. New commits:

53dc43dfix a wrong doctest

comment:54 Changed 17 months ago by darij

  • 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 17 months ago by vbraun

  • Branch changed from public/ticket/14666 to 53dc43d1bfff644927da9352c24279bcf897ba9c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.