Sage: Ticket #9676: Random Tree constructor for graphs section
https://trac.sagemath.org/ticket/9676
<p>
This adds a <a class="wiki" href="https://trac.sagemath.org/wiki/RandomTree">RandomTree</a> constructor to the graphs class. Users can type g=graphs.<a class="wiki" href="https://trac.sagemath.org/wiki/RandomTree">RandomTree</a>(n) to create a new random tree with n vertices named 0 through n-1.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/9676
Trac 1.1.6ncohenWed, 04 Aug 2010 08:15:16 GMTstatus changed
https://trac.sagemath.org/ticket/9676#comment:1
https://trac.sagemath.org/ticket/9676#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_work</em>
</li>
</ul>
<p>
Hellooooo !!
</p>
<p>
Well, a long list of comments, which is perfectly normal for a first patch :-)
</p>
<ul><li>First of all, you forgot to set our ticket as "needs_review". It means that if you hadn't given me its number by email, I would never had noticed this ticket, as I usually list those who are waiting to be reviewed
</li></ul><ul><li>I am really sorry, but I totally forgot to tell you about a patch which was reviewed a few days ago <a class="closed ticket" href="https://trac.sagemath.org/ticket/9373" title="enhancement: some overhaul in organization of database of common graph generators (closed: fixed)">#9373</a>. Among other things, it removes one of the two lists of generators given in graph_generators (where you added your constructor), and the other one is reformatted. This means that your patch can not be applied once <a class="closed ticket" href="https://trac.sagemath.org/ticket/9373" title="enhancement: some overhaul in organization of database of common graph generators (closed: fixed)">#9373</a> has been... Hence, your patch needs to be rebased on top of this one. (It means you first need to create a new branch, then apply <a class="closed ticket" href="https://trac.sagemath.org/ticket/9373" title="enhancement: some overhaul in organization of database of common graph generators (closed: fixed)">#9373</a>, then write your patch on top of it).
</li></ul><ul><li>When writing docstrins, you can indeed use LaTeX formulas. For this, you need to add a special character, so that Sphinx notices you are indeed using LaTeX. In your case,
</li></ul><pre class="wiki"> n^(n-2) and {0,1,...,n-1}
</pre><blockquote>
<blockquote>
<p>
should become
</p>
</blockquote>
</blockquote>
<pre class="wiki"> `n^(n-2)` and `\{0,1,...,n-1\}`
</pre><ul><li>If you build the documentation after applying your patch ( sage -docbuild reference hmtl ), you will also notice that your example does not appear like the other ones. This is because we make use of the double-column "::". You can give these other methods a look to see how it works, and build the documentation to mak sure it does.
</li></ul><ul><li>The result you mention is, if I remember correctly, for Labelled trees. It means that trees with a large automorphism group will appear more often, so I think this method should be renamed <a class="missing wiki">RandomLabelledTree?</a>.
</li></ul><ul><li>I see how you are building those trees, but I do not know how to prove this is indeed a uniform sampling. Could you add a reference for this (even a textbook, if it is a result I should know ?). You can even add this reference in the documentation (look for occurences of the string REFERENCES in the code to see how it works -- as usual, uild the documentation to ensure it is correctly understood by Sphinx).
</li></ul><ul><li>If you need a random permutation of [0..(n-1)], you should use something like Permutations(n).random_element()
</li></ul><ul><li>In Sage's documentation, the examples you see are not just examples. They are used to ensure that the code remains correct. This is what happens when you write something like {{{ sage -t graph_generators.py }} Sage reads all the docstring, and ensure what they output is what it expects. If it is not the case, the error is reported and we know something is wrong. Your doctest only prints it, which is not useful.. Here is one I could write, but it's really up to you, if you find something more interesting, funnier, or can check a known result using your function...
</li></ul><pre class="wiki"> Checking the generated graphs are indeed trees::
sage: all( graphs.RandomTree(10).is_tree() for i in range(30) )
True
</pre><blockquote>
<blockquote>
<p>
It does not need to be complicatd, most of the time. It is just a way for Sage to check it "seems" fine, so that we notice something has gone wrong is we modify the method is_tree or anything related.
</p>
</blockquote>
</blockquote>
<p>
And I am sure there is something else I had to say but forgot it O_o
</p>
<p>
Well, if you have any question, I'll be behind my emails <code>:-)</code>
</p>
<p>
Nathann
</p>
Ticketedward.scheinermanTue, 10 Aug 2010 23:12:26 GMTstatus changed
https://trac.sagemath.org/ticket/9676#comment:2
https://trac.sagemath.org/ticket/9676#comment:2
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Dear all,
I have uploaded a new version of the <a class="wiki" href="https://trac.sagemath.org/wiki/RandomTree">RandomTree</a> constructor. The algorithm is an inverse Prufer code method. We generate an (n-2)-long sequence of random values in {0,...,n-1} and use that to build a tree. Looking forward to seeing if this new version passes muster.
Ed
</p>
Ticketedward.scheinermanWed, 11 Aug 2010 14:55:44 GMT
https://trac.sagemath.org/ticket/9676#comment:3
https://trac.sagemath.org/ticket/9676#comment:3
<p>
The patch I uploaded yesterday was incorrectly built. I believe this one should be OK.
</p>
TicketncohenThu, 12 Aug 2010 01:57:44 GMTstatus changed
https://trac.sagemath.org/ticket/9676#comment:4
https://trac.sagemath.org/ticket/9676#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Helloooooo !!!
</p>
<p>
Well, I hold nothing against this new version... I did not know about this encoding for trees, and I am glad I learned about it <code>:-)</code>
</p>
<p>
I still have several remarks... From top to bottom :
</p>
<ul><li>It is very nice that you are describing how the algorithm works. I try to do that with my patches but I do not always make a good work of it. Could you add "ALGORITHM:" just before, though ? That's how it is done in other patches, we create a small "section" dedicated to that. Nothing important actually.
</li></ul><ul><li>Instead of checking just one tree (is_tree()), could you test something like 20 ? This method is very quick anyway. These doctests are actually automated tests to ensure there is nothing wrong with the function, so it is not just about explaining how to use the commands. The call to show is not very useful in this setting.
</li></ul><p>
Ok, some explanations may be needed with the docstrings. In any Sage method you will see a lot of examples, like the ones you just wrote yourself. It is nice for the users, who have an idea how to use the methods, and it is also tested automatically. A new version of Sage is *NOT* released if ALL the tests do not pass. This way, if some mistake in a part of Sage's code creates a problem 10 methods further, we can locate it. And here is how it works : You have been copying a list of commands, and the result they give. When running tests on only one file, in your case by <code>sage -t graph_generators.py</code>, you will see a rather long (in this case) output. Those are errors reported when automatically testing the lines of code you entered. Let's see why.
</p>
<ul><li>First, and don't ask me why because I have absolutely no idea, there is something to change about the indentation when one is typing those doctests. This does not work :
</li></ul><pre class="wiki">sage: for i in xrange(reps):
sage: g = graphs.RandomTree(6)
sage: if max(g.degree_sequence()) == 2: count += 1
</pre><blockquote>
<blockquote>
<p>
Write this instead:
</p>
</blockquote>
</blockquote>
<pre class="wiki">sage: for i in xrange(reps):
... g = graphs.RandomTree(6)
... if max(g.degree_sequence()) == 2: count += 1
</pre><blockquote>
<blockquote>
<p>
Syntaxically, I still think it was possible to understand the code with <code>sage:</code> at the beginning of the line, but well... This is not so bad anyway.
</p>
</blockquote>
</blockquote>
<ul><li>Oh. A consequence of all that. What happens if you test random algorithms ? They give random results. Which means that if your doctest says that 0.276920000000000 is the expected value, Sage will complain as soon as it is not EXACTLY that. Let's face it, this will never happen. I do not like this constraint, as it prevents one from writing doctests interesting for the user. Two ways around it :
</li></ul><ul><li>A doctest line containing <code># not tested</code> will not be tested. You can find other occurrences of this in the code. This way, the user gets to see your example, but Sage does not complain. Of course, the developpers will complain for as long as your have not added enough docstrings to your method so that we can be somehow sure its behaviour is under close surveillance. (hence the "<code>is_tree()</code>" at least 20 different times)
</li></ul><ul><li>Instead of controlling the exact value, check the distance with the expected value is not large. Each tree has a specific probability of being a path, so testing many of them amounts to studying a binomial distribution. So if you make a *BIG* number of trials, you can be somehow sure (?) that the mean you get empirically is not far from the theoretical mean. And I mean *BIG*. I recently had this very problem in <a class="closed ticket" href="https://trac.sagemath.org/ticket/9715" title="defect: Failing doctest in even_hole_free (closed: duplicate)">#9715</a>, and there was nothing wrong very large samplings... Actually, this kind of example is not very good either, it would be better to add #not tested in front of them, but it there was a way around with <a class="closed ticket" href="https://trac.sagemath.org/ticket/9815" title="defect: ATLAS fails to build on a PA-RISC system running HP-UX (closed: invalid)">#9815</a>, I can not think of any trick in this case <code>:-/</code>
</li></ul><p>
The actual code, now. Mostly asthetics:
</p>
<ul><li>I read
<pre class="wiki"> while idx < len(code):
(things)
idx += 1
</pre></li></ul><blockquote>
<blockquote>
<p>
What about a "for" loop ? By the way, do you really need to have a idx variable in this case ? It just keeps increasing to point to a different element of code.. That's C style !! (just joking, I *LOVE* C). In Python, you can do instead :
</p>
</blockquote>
</blockquote>
<pre class="wiki">for s in code:
(whatever_you_want)
</pre><blockquote>
<blockquote>
<p>
Which is enough in this situation.
</p>
</blockquote>
</blockquote>
<ul><li>About <code>avail</code>. Why do you need such a list ? Isn't <code>count</code> enough ?
</li></ul><pre class="wiki">xlist = [k for k,d in count.iteritems() if d==0 ]
</pre><blockquote>
<blockquote>
<p>
When you are adding a new leaf to your graph, simply do
</p>
</blockquote>
</blockquote>
<pre class="wiki">count[k] = -1
</pre><ul><li>By the way, you are at each loop building a list that you do not need. You are just interested in its first element. So instead of this <code>xlist</code> stuff, what about just :
</li></ul><pre class="wiki"> for x in range(n):
if count[x] == 0:
break
</pre><p>
</p>
<blockquote>
<blockquote>
<p>
This way <code>x</code> is directly the value you need. No <code>xlist</code>, no <code>avail</code>. And it is faster.
</p>
</blockquote>
</blockquote>
<p>
</p>
<ul><li>I also read
</li></ul><pre class="wiki">if len(xlist)==0: break
</pre><blockquote>
<blockquote>
<p>
When I read the algorithm, I though : This should never happen. I added a "print", to ensure it did not, and all my attempts shown it was never used. Is there any situation in which it is required ?
</p>
</blockquote>
</blockquote>
<p>
Well, this was a long list again. Many of my remarks being just aesthetic, disregard those if you do not like them. And please forgive me <code>:-)</code>.
</p>
<p>
Generally, a method can not be accepted if all the doctests do not pass. So ensure that <code>sage -t graph_generators.py</code> reports nothing wrong before anything.
</p>
<p>
I expect the next one version will be the last <code>:-)</code>
</p>
<p>
Nathann
</p>
<p>
</p>
Ticketedward.scheinermanSun, 15 Aug 2010 21:56:13 GMTstatus changed
https://trac.sagemath.org/ticket/9676#comment:5
https://trac.sagemath.org/ticket/9676#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Now passes all tests.
</p>
TicketncohenMon, 23 Aug 2010 02:41:39 GMTmilestone set
https://trac.sagemath.org/ticket/9676#comment:6
https://trac.sagemath.org/ticket/9676#comment:6
<ul>
<li><strong>milestone</strong>
set to <em>sage-4.5.3</em>
</li>
</ul>
<p>
Hello Edward !!
</p>
<p>
Well, as you told me you were busy these times, and I am on vacation waiting for a plane.... If you like these modifications, you can set my patch (and so this whole tiket, as I reviewed yours) as positively reviewed <code>:-)</code>
</p>
<p>
Thank you for your additions ! I'll try to take care of your other patches now.
</p>
<p>
Nathann
</p>
TicketncohenMon, 23 Aug 2010 02:42:07 GMTattachment set
https://trac.sagemath.org/ticket/9676
https://trac.sagemath.org/ticket/9676
<ul>
<li><strong>attachment</strong>
set to <em>trac_9676-cosmetics.patch</em>
</li>
</ul>
<p>
Cosmetics on top of Edward's patch
</p>
Ticketedward.scheinermanTue, 24 Aug 2010 22:59:09 GMTstatus changed
https://trac.sagemath.org/ticket/9676#comment:7
https://trac.sagemath.org/ticket/9676#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Hi Nathann, I tested the new code and am satisfied with the results. I think this is fine to incorporate into the next Sage release. Thanks for the help!!! -Ed
</p>
TicketncohenWed, 25 Aug 2010 00:47:59 GMT
https://trac.sagemath.org/ticket/9676#comment:8
https://trac.sagemath.org/ticket/9676#comment:8
<p>
Yet another graph patch !
</p>
<p>
Yeahhhhhhhhhhhhhhhhhhhh !!! <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketmpatelSun, 05 Sep 2010 03:50:13 GMTstatus changed
https://trac.sagemath.org/ticket/9676#comment:9
https://trac.sagemath.org/ticket/9676#comment:9
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Could someone prepend the ticket number to the commit string for <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9676/trac_9676.patch" title="Attachment 'trac_9676.patch' in Ticket #9676">trac_9676.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9676/trac_9676.patch" title="Download"></a> (and restore the status to "positive review")?
</p>
<p>
Also, please update the "Author(s)" and/or "Reviewer(s)" fields.
</p>
Ticketedward.scheinermanMon, 06 Sep 2010 00:41:29 GMTattachment set
https://trac.sagemath.org/ticket/9676
https://trac.sagemath.org/ticket/9676
<ul>
<li><strong>attachment</strong>
set to <em>trac_9676.patch</em>
</li>
</ul>
<p>
New, improved, repaired <a class="wiki" href="https://trac.sagemath.org/wiki/RandomTree">RandomTree</a> graph constructor
</p>
Ticketedward.scheinermanMon, 06 Sep 2010 00:42:07 GMTstatus changed
https://trac.sagemath.org/ticket/9676#comment:10
https://trac.sagemath.org/ticket/9676#comment:10
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
<p>
Commit string edited as requested.
</p>
TicketmpatelWed, 15 Sep 2010 22:19:08 GMTreviewer set
https://trac.sagemath.org/ticket/9676#comment:11
https://trac.sagemath.org/ticket/9676#comment:11
<ul>
<li><strong>reviewer</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
TicketmpatelWed, 15 Sep 2010 22:52:30 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/9676#comment:12
https://trac.sagemath.org/ticket/9676#comment:12
<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>merged</strong>
set to <em>sage-4.6.alpha1</em>
</li>
</ul>
Ticket