Sage: Ticket #14666: Test if a weight function is generic for a given matroid
https://trac.sagemath.org/ticket/14666
<p>
Reported by darij on <a class="ext-link" href="http://trac.sagemath.org/sage_trac/ticket/7477"><span class="icon"></span>http://trac.sagemath.org/sage_trac/ticket/7477</a> :
</p>
<p>
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.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/14666
Trac 1.1.6darijFri, 31 May 2013 06:47:52 GMTcc set
https://trac.sagemath.org/ticket/14666#comment:1
https://trac.sagemath.org/ticket/14666#comment:1
<ul>
<li><strong>cc</strong>
<em>darij</em> added
</li>
</ul>
TicketjdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/14666#comment:2
https://trac.sagemath.org/ticket/14666#comment:2
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketStefanFri, 13 Sep 2013 13:50:01 GMTowner, component changed
https://trac.sagemath.org/ticket/14666#comment:3
https://trac.sagemath.org/ticket/14666#comment:3
<ul>
<li><strong>owner</strong>
changed from <em>sage-combinat</em> to <em>Stefanf</em>
</li>
<li><strong>component</strong>
changed from <em>combinatorics</em> to <em>matroid theory</em>
</li>
</ul>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/14666#comment:4
https://trac.sagemath.org/ticket/14666#comment:4
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/14666#comment:5
https://trac.sagemath.org/ticket/14666#comment:5
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/14666#comment:6
https://trac.sagemath.org/ticket/14666#comment:6
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
TickettaraSat, 09 Apr 2016 01:28:38 GMTbranch set
https://trac.sagemath.org/ticket/14666#comment:7
https://trac.sagemath.org/ticket/14666#comment:7
<ul>
<li><strong>branch</strong>
set to <em>u/tara/test_if_a_weight_function_is_generic_for_a_given_matroid</em>
</li>
</ul>
TickettaraSat, 09 Apr 2016 01:30:56 GMTstatus changed; commit set
https://trac.sagemath.org/ticket/14666#comment:8
https://trac.sagemath.org/ticket/14666#comment:8
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>62fa4205a56150bf5301496d6dc770ffa29b5270</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=62fa4205a56150bf5301496d6dc770ffa29b5270"><span class="icon"></span>62fa420</a></td><td><code>added is_max_weight_independent_generic() and is_max_weight_coindependent_generic()</code>
</td></tr></table>
TicketdarijSat, 09 Apr 2016 06:51:06 GMT
https://trac.sagemath.org/ticket/14666#comment:9
https://trac.sagemath.org/ticket/14666#comment:9
<p>
Thank you! May I ask a couple questions before I look deeper into the code?
</p>
<ul><li>What is the difference between the two functions?
</li></ul><ul><li>What exactly is <code>X</code> used for? I assume the answer somehow depends on <code>X</code>. Is it just restricting the matroid to <code>X</code>?
</li></ul>
TickettaraSat, 09 Apr 2016 14:49:58 GMT
https://trac.sagemath.org/ticket/14666#comment:10
https://trac.sagemath.org/ticket/14666#comment:10
<p>
Hi Darij,
</p>
<p>
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$.
</p>
<p>
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.
</p>
<p>
I agree that $X$ is just restricting the matroid to $X$.
</p>
<blockquote>
<p>
smres=res
if weights is None:
</p>
<blockquote>
<p>
if self._rank(set([e]))>0:
</p>
<blockquote>
<p>
return False
</p>
</blockquote>
<p>
else:
</p>
<blockquote>
<p>
for f in res:
</p>
<blockquote>
<p>
if weights(e)==weights(f):
</p>
<blockquote>
<p>
smres.discard(f)
</p>
</blockquote>
</blockquote>
</blockquote>
</blockquote>
<p>
smres.add(e)
if self._rank(smres) > len(smres)-1:
</p>
<blockquote>
<p>
return False
</p>
</blockquote>
</blockquote>
<p>
Cheers,
Tara
</p>
TickettaraSat, 09 Apr 2016 15:26:28 GMT
https://trac.sagemath.org/ticket/14666#comment:11
https://trac.sagemath.org/ticket/14666#comment:11
<p>
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.
</p>
TicketgitSat, 09 Apr 2016 15:38:33 GMTcommit changed
https://trac.sagemath.org/ticket/14666#comment:12
https://trac.sagemath.org/ticket/14666#comment:12
<ul>
<li><strong>commit</strong>
changed from <em>62fa4205a56150bf5301496d6dc770ffa29b5270</em> to <em>da97f302b53c5a53f33ee53fe9b88a173245c9d5</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=da97f302b53c5a53f33ee53fe9b88a173245c9d5"><span class="icon"></span>da97f30</a></td><td><code>Eddited is_max_weight_independent_generic() and is_max_weight_coindependent_generic</code>
</td></tr></table>
TicketdarijMon, 11 Apr 2016 19:37:59 GMTcommit, branch, milestone changed; dependencies deleted
https://trac.sagemath.org/ticket/14666#comment:13
https://trac.sagemath.org/ticket/14666#comment:13
<ul>
<li><strong>commit</strong>
changed from <em>da97f302b53c5a53f33ee53fe9b88a173245c9d5</em> to <em>059b6d3816eae7412bc5e6570c17888fa2b75678</em>
</li>
<li><strong>dependencies</strong>
<em>7477</em> deleted
</li>
<li><strong>branch</strong>
changed from <em>u/tara/test_if_a_weight_function_is_generic_for_a_given_matroid</em> to <em>public/ticket/14666</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.4</em> to <em>sage-7.2</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=059b6d3816eae7412bc5e6570c17888fa2b75678"><span class="icon"></span>059b6d3</a></td><td><code>documentation</code>
</td></tr></table>
TicketdarijMon, 11 Apr 2016 19:41:34 GMT
https://trac.sagemath.org/ticket/14666#comment:14
https://trac.sagemath.org/ticket/14666#comment:14
<p>
I've made some changes (NB: branch change!), particularly documenting one of the undocumented codepaths (namely, passing a dictionary for <code>weight</code>). However, it exposed a bug: The algorithm assumes <code>weight</code> to be a function.
</p>
<p>
My suggestion here would be to change the way dictionaries are handled. Rather than doing the <code>try/except</code>s, I'd check whether <code>weight</code> is a dictionary, and then define a function <code>weight_fun</code> to send each <code>e</code> to <code>weight[e]</code>. Otherwise, I'd just set <code>weight_fun = weight</code>. All other uses of <code>weight</code> in the code should then be replaced by <code>weight_fun</code>. 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.)
</p>
<p>
Also, the algorithm looks nice and clean. I haven't proven it yet. Is it easy or should I know something it follows from?
</p>
<p>
Thanks for the good work!
</p>
TicketdarijMon, 11 Apr 2016 19:45:09 GMT
https://trac.sagemath.org/ticket/14666#comment:15
https://trac.sagemath.org/ticket/14666#comment:15
<p>
Also, I'm not fully sure about what goes on here:
</p>
<pre class="wiki"> 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
</pre><p>
Am I seeing it right that <code>smres</code> never has length >1 ? So you are essentially checking that <code>e</code> is a loop; if it isn't, then you return <code>False</code>? Do you really need an array for that?
</p>
TickettaraMon, 11 Apr 2016 21:09:28 GMT
https://trac.sagemath.org/ticket/14666#comment:16
https://trac.sagemath.org/ticket/14666#comment:16
<p>
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 <code>B</code> is unique if and only if for every <code>e\in E(M)-B</code>, we have <code>e</code> is in the closure of <code>{b\in B|w(b)>w(e)}</code>. In other words, <code>B</code> is unique, if when using the greedy algorithm, we never were able to choose an element of <code>E(M)-B</code>.
</p>
<p>
We don't need an array for <code>smres</code> 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 <code>smres</code> is now pointless in that case.
</p>
TicketdarijTue, 12 Apr 2016 18:43:10 GMT
https://trac.sagemath.org/ticket/14666#comment:17
https://trac.sagemath.org/ticket/14666#comment:17
<p>
OK, that's a nice algorithm! That said, I don't really understand the way you implemented it; the concrete meaning of <code>smres</code> is unclear to me (some loop invariants might be helpful).
</p>
<p>
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?
</p>
<p>
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...
</p>
TicketStefanTue, 12 Apr 2016 19:14:55 GMT
https://trac.sagemath.org/ticket/14666#comment:18
https://trac.sagemath.org/ticket/14666#comment:18
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14666#comment:14" title="Comment 14">darij</a>:
</p>
<blockquote class="citation">
<p>
I've made some changes (NB: branch change!), particularly documenting one of the undocumented codepaths (namely, passing a dictionary for <code>weight</code>). However, it exposed a bug: The algorithm assumes <code>weight</code> to be a function.
</p>
<p>
My suggestion here would be to change the way dictionaries are handled. Rather than doing the <code>try/except</code>s, I'd check whether <code>weight</code> is a dictionary, and then define a function <code>weight_fun</code> to send each <code>e</code> to <code>weight[e]</code>. Otherwise, I'd just set <code>weight_fun = weight</code>. All other uses of <code>weight</code> in the code should then be replaced by <code>weight_fun</code>. 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.)
</p>
</blockquote>
<p>
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.
</p>
<p>
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?
</p>
TicketStefanTue, 12 Apr 2016 19:15:41 GMT
https://trac.sagemath.org/ticket/14666#comment:19
https://trac.sagemath.org/ticket/14666#comment:19
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14666#comment:17" title="Comment 17">darij</a>:
</p>
<blockquote class="citation">
<p>
OK, that's a nice algorithm! That said, I don't really understand the way you implemented it; the concrete meaning of <code>smres</code> is unclear to me (some loop invariants might be helpful).
</p>
<p>
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?
</p>
<p>
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...
</p>
</blockquote>
<p>
I would expect the second function to be the dual of the first. Is that the case here?
</p>
TicketdarijTue, 12 Apr 2016 19:16:16 GMT
https://trac.sagemath.org/ticket/14666#comment:20
https://trac.sagemath.org/ticket/14666#comment:20
<p>
Yes, I've added such an example in my commit -- if you run the doctests, you'll see it fail.
</p>
<p>
What do you mean by "the dual"?
</p>
TicketStefanTue, 12 Apr 2016 19:20:24 GMT
https://trac.sagemath.org/ticket/14666#comment:21
https://trac.sagemath.org/ticket/14666#comment:21
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14666#comment:20" title="Comment 20">darij</a>:
</p>
<blockquote class="citation">
<p>
Yes, I've added such an example in my commit -- if you run the doctests, you'll see it fail.
</p>
<p>
What do you mean by "the dual"?
</p>
</blockquote>
<p>
I mean that I'd expect
</p>
<p>
M.is_max_weight_coindependent_generic
</p>
<p>
to return the output of
</p>
<p>
M.dual().is_max_weight_independent_generic
</p>
TicketdarijTue, 12 Apr 2016 19:23:17 GMT
https://trac.sagemath.org/ticket/14666#comment:22
https://trac.sagemath.org/ticket/14666#comment:22
<p>
Oh. But if so, the doc should be different!
</p>
TicketStefanTue, 12 Apr 2016 19:32:12 GMT
https://trac.sagemath.org/ticket/14666#comment:23
https://trac.sagemath.org/ticket/14666#comment:23
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14666#comment:22" title="Comment 22">darij</a>:
</p>
<blockquote class="citation">
<p>
Oh. But if so, the doc should be different!
</p>
</blockquote>
<p>
Agreed
</p>
TicketStefanTue, 12 Apr 2016 20:18:42 GMT
https://trac.sagemath.org/ticket/14666#comment:24
https://trac.sagemath.org/ticket/14666#comment:24
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14666#comment:20" title="Comment 20">darij</a>:
</p>
<blockquote class="citation">
<p>
Yes, I've added such an example in my commit -- if you run the doctests, you'll see it fail.
</p>
<p>
What do you mean by "the dual"?
</p>
</blockquote>
<p>
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 <code>wt</code> is not so useful, so I would probably define something that's guaranteed to be a function, like so:
</p>
<pre class="wiki">if callable(weights):
wts = weights
else:
wts = lambda x: weights[x]
</pre><p>
Then use wts instead of weights down the line.
</p>
<p>
For the record, to test a file, run (from the top <code>sage</code> directory):
</p>
<pre class="wiki">./sage -t src/sage/matroids/matroid.pyx
</pre>
TickettaraWed, 13 Apr 2016 04:00:05 GMT
https://trac.sagemath.org/ticket/14666#comment:25
https://trac.sagemath.org/ticket/14666#comment:25
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14666#comment:24" title="Comment 24">Stefan</a>:
</p>
<blockquote class="citation">
<p>
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 <code>wt</code> is not so useful, so I would probably define something that's guaranteed to be a function, like so:
</p>
<pre class="wiki">if callable(weights):
wts = weights
else:
wts = lambda x: weights[x]
</pre><p>
Then use wts instead of weights down the line.
</p>
</blockquote>
<p>
The reason that <code>wt</code> 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 <code>wts</code>. I tried adding the function wts, but I ended up having it not compile. I'll look at it again tomorrow.
</p>
TicketStefanWed, 13 Apr 2016 11:52:05 GMT
https://trac.sagemath.org/ticket/14666#comment:26
https://trac.sagemath.org/ticket/14666#comment:26
<p>
What's the error? Maybe callable() isn't supported in Cython?
</p>
<p>
Yeah, you'll need both. Since you need the output in order, you can't just call the max_weight_independent function either, unfortunately.
</p>
TickettaraWed, 13 Apr 2016 20:49:29 GMT
https://trac.sagemath.org/ticket/14666#comment:27
https://trac.sagemath.org/ticket/14666#comment:27
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14666#comment:26" title="Comment 26">Stefan</a>:
</p>
<blockquote class="citation">
<p>
What's the error? Maybe callable() isn't supported in Cython?
</p>
</blockquote>
<p>
It won't compile when I have the line
</p>
<pre class="wiki">wts = lambda x: weights[x]
</pre><p>
It will, however, compile when I have
</p>
<pre class="wiki">if callable(weights):
wts = weights
else:
return True
</pre><p>
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
<code>def wts(x) : return weights[x]</code>.
</p>
TicketdarijWed, 13 Apr 2016 21:56:08 GMT
https://trac.sagemath.org/ticket/14666#comment:28
https://trac.sagemath.org/ticket/14666#comment:28
<p>
Does Cython actually know lambda at all? And if so, does it allow functions without specified input and output types?
</p>
<p>
(This is not a rhetorical question; I really have no idea.)
</p>
TicketStefanFri, 15 Apr 2016 15:35:36 GMTstatus changed
https://trac.sagemath.org/ticket/14666#comment:29
https://trac.sagemath.org/ticket/14666#comment:29
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Ah, you can have them inside a def but not inside a cpdef.
</p>
<p>
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 [].
</p>
TicketdarijFri, 15 Apr 2016 17:50:03 GMT
https://trac.sagemath.org/ticket/14666#comment:30
https://trac.sagemath.org/ticket/14666#comment:30
<p>
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?
</p>
TicketyomcatTue, 03 May 2016 04:48:12 GMTcc changed
https://trac.sagemath.org/ticket/14666#comment:31
https://trac.sagemath.org/ticket/14666#comment:31
<ul>
<li><strong>cc</strong>
<em>yomcat</em> added
</li>
</ul>
TicketgitMon, 09 May 2016 13:34:19 GMTcommit changed
https://trac.sagemath.org/ticket/14666#comment:32
https://trac.sagemath.org/ticket/14666#comment:32
<ul>
<li><strong>commit</strong>
changed from <em>059b6d3816eae7412bc5e6570c17888fa2b75678</em> to <em>c75ee707326fc1cc1beb0e265359c0f93cb84ac2</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c75ee707326fc1cc1beb0e265359c0f93cb84ac2"><span class="icon"></span>c75ee70</a></td><td><code>This is eddited now to accept both functions and dictionaries for the weight parameter.</code>
</td></tr></table>
TickettaraMon, 09 May 2016 16:47:45 GMTstatus changed
https://trac.sagemath.org/ticket/14666#comment:33
https://trac.sagemath.org/ticket/14666#comment:33
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketdarijTue, 10 May 2016 06:38:01 GMT
https://trac.sagemath.org/ticket/14666#comment:34
https://trac.sagemath.org/ticket/14666#comment:34
<p>
Nice, this looks a lot better. But I still struggle to find a mental model for <code>smres</code>. From your description of the algorithm, it should be the list containing all elements of <code>res</code> having higher weight than <code>e</code>, and <code>e</code> itself. But from the code, it seems to be the list containing all elements of <code>res</code> having higher weight than <code>e</code>, and the first element of <code>res</code> that has the same weight as <code>e</code> (because <code>e</code> does not get appended to <code>smres</code> unless <code>e</code> sets a negative weight record). Am I reading the code right, and is this an actual issue? Thank you!
</p>
TickettaraTue, 10 May 2016 15:15:02 GMT
https://trac.sagemath.org/ticket/14666#comment:35
https://trac.sagemath.org/ticket/14666#comment:35
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14666#comment:34" title="Comment 34">darij</a>:
</p>
<blockquote class="citation">
<p>
Nice, this looks a lot better. But I still struggle to find a mental model for <code>smres</code>. From your description of the algorithm, it should be the list containing all elements of <code>res</code> having higher weight than <code>e</code>, and <code>e</code> itself. But from the code, it seems to be the list containing all elements of <code>res</code> having higher weight than <code>e</code>, and the first element of <code>res</code> that has the same weight as <code>e</code> (because <code>e</code> does not get appended to <code>smres</code> unless <code>e</code> sets a negative weight record). Am I reading the code right, and is this an actual issue? Thank you!
</p>
</blockquote>
<p>
You're correct, there was a problem with <code>smres</code>. I wasn't adding <code>e</code> to it all the time. I had moved some things about to make it read nicer, and introduced that bug.
</p>
TicketgitTue, 10 May 2016 15:15:29 GMTcommit changed
https://trac.sagemath.org/ticket/14666#comment:36
https://trac.sagemath.org/ticket/14666#comment:36
<ul>
<li><strong>commit</strong>
changed from <em>c75ee707326fc1cc1beb0e265359c0f93cb84ac2</em> to <em>f92c81dbf9f8bcc923a7597ede63a5bab613b397</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f92c81dbf9f8bcc923a7597ede63a5bab613b397"><span class="icon"></span>f92c81d</a></td><td><code>Fixed bug with smres and added clarifying comments.</code>
</td></tr></table>
TicketgitWed, 11 May 2016 03:20:16 GMTcommit changed
https://trac.sagemath.org/ticket/14666#comment:37
https://trac.sagemath.org/ticket/14666#comment:37
<ul>
<li><strong>commit</strong>
changed from <em>f92c81dbf9f8bcc923a7597ede63a5bab613b397</em> to <em>edb1a33e776a3371def0acc07ab123812d9c2afa</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=64f76adea329df592cf28ec6d54253de5c72ae64"><span class="icon"></span>64f76ad</a></td><td><code>Merge branch 'public/ticket/14666' of git://trac.sagemath.org/sage into matroid</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=b5d0f5f15855b20141872661ea6ffda8b89b40ad"><span class="icon"></span>b5d0f5f</a></td><td><code>documentation & comments</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=bb0b6985540afd1297a6272d50fdb6292e03ce6f"><span class="icon"></span>bb0b698</a></td><td><code>example from Hopf notes</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=1f13c962f4147de7e488a339f46aff7d895b9e7f"><span class="icon"></span>1f13c96</a></td><td><code>another doctest (one that is sensitive to max/min distinction)</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=edb1a33e776a3371def0acc07ab123812d9c2afa"><span class="icon"></span>edb1a33</a></td><td><code>fix sign error in is_max_weight_coindependent_generic</code>
</td></tr></table>
TicketdarijWed, 11 May 2016 03:22:02 GMTreviewer, author set
https://trac.sagemath.org/ticket/14666#comment:38
https://trac.sagemath.org/ticket/14666#comment:38
<ul>
<li><strong>reviewer</strong>
set to <em>Darij Grinberg</em>
</li>
<li><strong>author</strong>
set to <em>Tara Fife</em>
</li>
</ul>
<p>
Thank you!
</p>
<p>
I've made my own changes. (Only one change to the code proper: The <code>is_max_weight_coindependent_generic</code> function was doing the same as <code>is_max_weight_independent_generic</code> but for the dual matroid of <code>self</code> instead of <code>self</code>. 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!
</p>
<p>
Also, if your "we" includes some other authors, I guess they should go into the author field as well.
</p>
TicketdarijWed, 11 May 2016 03:23:23 GMT
https://trac.sagemath.org/ticket/14666#comment:39
https://trac.sagemath.org/ticket/14666#comment:39
<p>
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.)
</p>
TicketgitWed, 11 May 2016 03:30:18 GMTcommit changed
https://trac.sagemath.org/ticket/14666#comment:40
https://trac.sagemath.org/ticket/14666#comment:40
<ul>
<li><strong>commit</strong>
changed from <em>edb1a33e776a3371def0acc07ab123812d9c2afa</em> to <em>4031e326dcdf7a40072483267f45362bf2f88709</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=4031e326dcdf7a40072483267f45362bf2f88709"><span class="icon"></span>4031e32</a></td><td><code>more doc fixes</code>
</td></tr></table>
TickettaraWed, 11 May 2016 23:27:38 GMT
https://trac.sagemath.org/ticket/14666#comment:41
https://trac.sagemath.org/ticket/14666#comment:41
<p>
The only thing that looks like a problem is in edb1a33, you changed <code>wt = sorted(wt, reverse=True)</code> to <code>wt = sorted(wt)</code> in line 6667. And later changed <code>if wt_dic[e] < wt_dic[res[-1]]:</code> to <code>if wt_dic[e] > wt_dic[res[-1]]:</code>. It seems like this would test if a minimum cobasis was generic rather than a maximum cobasis. I would expect <code>M.is_max_weight_coindependent_generic()</code> to give the same results as <code>M*.is_max_weight_independent_generic()</code>, where <code>M*</code> is the dual of <code>M</code>.
</p>
<p>
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.
</p>
TicketdarijWed, 11 May 2016 23:28:53 GMT
https://trac.sagemath.org/ticket/14666#comment:42
https://trac.sagemath.org/ticket/14666#comment:42
<p>
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.
</p>
TickettaraFri, 13 May 2016 02:51:45 GMT
https://trac.sagemath.org/ticket/14666#comment:43
https://trac.sagemath.org/ticket/14666#comment:43
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14666#comment:42" title="Comment 42">darij</a>:
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
When I execute the following code, using the current version, I get <code>True</code> and then <code>False</code>. We should expect <code>True</code> in both cases, because <code>{3,4}</code> is the only maximum weighted basis of <code>M</code>.
</p>
<pre class="wiki">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)
</pre><p>
However, when I change those two lines back, I get <code>True</code> for both outputs. Furthermore, the code in <code>is_max_weight_coindependent_generic</code> looking the same as <code>is_max_weight_independent_generic</code>, excepting that <code>rank</code> is changed to <code>corank</code> makes intuitive sense to me.
</p>
TicketdarijFri, 13 May 2016 02:54:26 GMT
https://trac.sagemath.org/ticket/14666#comment:44
https://trac.sagemath.org/ticket/14666#comment:44
<p>
Feel free to change this back... but then please rewrite this documentation:
</p>
<pre class="wiki">+ The method :meth:`is_max_weight_coindependent_generic`
+ computes the same function using a different algorithm.
</pre><p>
(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!
</p>
TicketgitFri, 13 May 2016 02:59:00 GMTcommit changed
https://trac.sagemath.org/ticket/14666#comment:45
https://trac.sagemath.org/ticket/14666#comment:45
<ul>
<li><strong>commit</strong>
changed from <em>4031e326dcdf7a40072483267f45362bf2f88709</em> to <em>5baccc674c1616978db0d70360722661813cc0ce</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=5baccc674c1616978db0d70360722661813cc0ce"><span class="icon"></span>5baccc6</a></td><td><code>fix error in is_max_weight_coindependent_generic</code>
</td></tr></table>
TicketdarijFri, 13 May 2016 03:01:34 GMT
https://trac.sagemath.org/ticket/14666#comment:46
https://trac.sagemath.org/ticket/14666#comment:46
<p>
PS. This:
</p>
<pre class="wiki">+ cpdef is_max_weight_coindependent_generic(self, X=None, weights=None):
+ r"""
+ Test if only one basis of the subset ``X`` has maximal
+ weight.
</pre><p>
also should have "cobasis" rather than "basis", right?
</p>
TicketgitFri, 13 May 2016 03:10:58 GMTcommit changed
https://trac.sagemath.org/ticket/14666#comment:47
https://trac.sagemath.org/ticket/14666#comment:47
<ul>
<li><strong>commit</strong>
changed from <em>5baccc674c1616978db0d70360722661813cc0ce</em> to <em>fc8a795bdab5dd48e00b99a88a6ef0d54590314e</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=fc8a795bdab5dd48e00b99a88a6ef0d54590314e"><span class="icon"></span>fc8a795</a></td><td><code>Fixed error in documentation</code>
</td></tr></table>
TickettaraFri, 13 May 2016 03:13:55 GMT
https://trac.sagemath.org/ticket/14666#comment:48
https://trac.sagemath.org/ticket/14666#comment:48
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14666#comment:44" title="Comment 44">darij</a>:
</p>
<blockquote class="citation">
<p>
Feel free to change this back... but then please rewrite this documentation:
</p>
<pre class="wiki">+ The method :meth:`is_max_weight_coindependent_generic`
+ computes the same function using a different algorithm.
</pre><p>
(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!
</p>
</blockquote>
<p>
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.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=fc8a795bdab5dd48e00b99a88a6ef0d54590314e"><span class="icon"></span>fc8a795</a></td><td><code>Fixed error in documentation</code>
</td></tr></table>
TicketdarijFri, 13 May 2016 07:28:08 GMT
https://trac.sagemath.org/ticket/14666#comment:49
https://trac.sagemath.org/ticket/14666#comment:49
<p>
Sorry for continuous annoyance, but please also see <a class="ticket" href="https://trac.sagemath.org/ticket/14666#comment:46" title="Comment 46">comment:46</a>. (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!
</p>
TicketgitFri, 13 May 2016 11:38:25 GMTcommit changed
https://trac.sagemath.org/ticket/14666#comment:50
https://trac.sagemath.org/ticket/14666#comment:50
<ul>
<li><strong>commit</strong>
changed from <em>fc8a795bdab5dd48e00b99a88a6ef0d54590314e</em> to <em>3fa15f2a97ee6002a1efddd0360a38416ffb6844</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=3fa15f2a97ee6002a1efddd0360a38416ffb6844"><span class="icon"></span>3fa15f2</a></td><td><code>Fixed error in documentation</code>
</td></tr></table>
TicketdarijFri, 13 May 2016 14:24:27 GMTstatus changed
https://trac.sagemath.org/ticket/14666#comment:51
https://trac.sagemath.org/ticket/14666#comment:51
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Wonderful!
</p>
TicketvbraunSun, 22 May 2016 07:40:58 GMTstatus changed
https://trac.sagemath.org/ticket/14666#comment:52
https://trac.sagemath.org/ticket/14666#comment:52
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Doctests fail as evident in the patchbot report
</p>
TicketgitSun, 22 May 2016 17:05:27 GMTcommit changed
https://trac.sagemath.org/ticket/14666#comment:53
https://trac.sagemath.org/ticket/14666#comment:53
<ul>
<li><strong>commit</strong>
changed from <em>3fa15f2a97ee6002a1efddd0360a38416ffb6844</em> to <em>53dc43d1bfff644927da9352c24279bcf897ba9c</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=53dc43d1bfff644927da9352c24279bcf897ba9c"><span class="icon"></span>53dc43d</a></td><td><code>fix a wrong doctest</code>
</td></tr></table>
TicketdarijSun, 22 May 2016 17:05:55 GMTstatus changed
https://trac.sagemath.org/ticket/14666#comment:54
https://trac.sagemath.org/ticket/14666#comment:54
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
<p>
Oops! Fallout from our previous misunderstanding about what the two functions were supposed to do. Should be correct now.
</p>
TicketvbraunMon, 23 May 2016 22:23:30 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/14666#comment:55
https://trac.sagemath.org/ticket/14666#comment:55
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/ticket/14666</em> to <em>53dc43d1bfff644927da9352c24279bcf897ba9c</em>
</li>
</ul>
Ticket