Sage: Ticket #14564: BinaryTree().graph() falsely claims that the graph has 0 vertices
https://trac.sagemath.org/ticket/14564
<p>
This also breaks the show() function of this trivial binary tree.
</p>
<p>
Patch coming in a couple minutes.
</p>
<p>
Warning: compatibility with queue not checked, I'm still working off 5.9 sage-main with only <a class="closed ticket" href="https://trac.sagemath.org/ticket/8703" title="enhancement: Combinatorial Rooted Ordered and Binary Trees (closed: fixed)">#8703</a> installed.
</p>
<p>
Apply: nothing. This is a duplicate ticket.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/sage_logo_trac_v2.png
https://trac.sagemath.org/ticket/14564
Trac 1.1.6darijSat, 11 May 2013 02:22:57 GMTattachment set
https://trac.sagemath.org/ticket/14564
https://trac.sagemath.org/ticket/14564
<ul>
<li><strong>attachment</strong>
set to <em>trac_14564-trivial-binary-tree.patch</em>
</li>
</ul>
<p>
Fixes graph() function. This automatically fixes show(). I have not checked all the other functions, though...
</p>
TicketdarijSat, 11 May 2013 02:23:51 GMTstatus, priority, component changed; author set
https://trac.sagemath.org/ticket/14564#comment:1
https://trac.sagemath.org/ticket/14564#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>priority</strong>
changed from <em>major</em> to <em>minor</em>
</li>
<li><strong>component</strong>
changed from <em>PLEASE CHANGE</em> to <em>combinatorics</em>
</li>
<li><strong>author</strong>
set to <em>darij</em>
</li>
</ul>
TicketdarijSat, 11 May 2013 02:24:32 GMTdescription changed
https://trac.sagemath.org/ticket/14564#comment:2
https://trac.sagemath.org/ticket/14564#comment:2
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/14564?action=diff&version=2">diff</a>)
</li>
</ul>
TicketdarijSat, 11 May 2013 02:25:28 GMTdescription changed
https://trac.sagemath.org/ticket/14564#comment:3
https://trac.sagemath.org/ticket/14564#comment:3
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/14564?action=diff&version=3">diff</a>)
</li>
</ul>
TicketncohenMon, 13 May 2013 12:00:34 GMT
https://trac.sagemath.org/ticket/14564#comment:4
https://trac.sagemath.org/ticket/14564#comment:4
<p>
Hellooooooooooooo !
</p>
<p>
You change the associated graph of an empty binary tree to a non-empty graph, but what about these things ?
</p>
<pre class="wiki">sage: t1 = BinaryTree()
sage: t1
.
sage: t1.graph().vertices()
[0]
sage: list(t1)
[]
sage: list(t1.paths())
[]
sage: t1.depth()
0
</pre><p>
Nathann
</p>
TicketncohenMon, 13 May 2013 12:00:39 GMTstatus changed
https://trac.sagemath.org/ticket/14564#comment:5
https://trac.sagemath.org/ticket/14564#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
TicketdarijTue, 14 May 2013 00:17:27 GMT
https://trac.sagemath.org/ticket/14564#comment:6
https://trac.sagemath.org/ticket/14564#comment:6
<p>
Hi Nathannnnnn! Thanks for looking in the file. <code></code>list<code></code>, <code></code>graph().vertices()<code></code> and <code></code>depth()<code></code> seem to be correct (<code></code>list<code></code> is not supposed to be the list of all vertices, as far as I understand), or am I missing something? I don't really like the <code></code>paths()<code></code> answer (isn't there a 0-length path from the root to itself?), but that answer appears precisely that way in the docstring:
</p>
<pre class="wiki"> sage: list(BinaryTree().paths())
[]
</pre><p>
so I suspect the authors (whom I'm adding to cc now) must have had something in mind.
</p>
TicketdarijTue, 14 May 2013 00:18:05 GMTcc changed
https://trac.sagemath.org/ticket/14564#comment:7
https://trac.sagemath.org/ticket/14564#comment:7
<ul>
<li><strong>cc</strong>
<em>hivert</em> added
</li>
</ul>
TicketncohenTue, 14 May 2013 10:21:15 GMT
https://trac.sagemath.org/ticket/14564#comment:8
https://trac.sagemath.org/ticket/14564#comment:8
<p>
Hellooooooooooo !!!
</p>
<blockquote class="citation">
<p>
so I suspect the authors (whom I'm adding to cc now) must have had something in mind.
</p>
</blockquote>
<p>
I do not use these classes, and I do not really understand what they had in mind indeed. But what I believe is that changing the graph function to return a graph one 1 vertex instead of 0 does not match what they had in mind when they wrote it either, so I think that it makes more sense to keep the graph as it was before, and fix the plot problem in a different way.
</p>
<p>
Just my opinion, of course, and I really do not use those classes. So if you think that it is better to change the output of this graph() function I will let somebody who understands all this better than I do review that patch !
</p>
<p>
Have fuuuuuuuuuuuuuuuuuuuuuunnn !
</p>
<p>
Nathann
</p>
TicketjdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/14564#comment:9
https://trac.sagemath.org/ticket/14564#comment:9
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketchapotonTue, 27 Aug 2013 19:39:12 GMTkeywords changed
https://trac.sagemath.org/ticket/14564#comment:10
https://trac.sagemath.org/ticket/14564#comment:10
<ul>
<li><strong>keywords</strong>
<em>trees</em> <em>trees</em> added; <em>tree</em> <em>tree</em> removed
</li>
</ul>
TicketchapotonThu, 19 Sep 2013 16:04:00 GMT
https://trac.sagemath.org/ticket/14564#comment:11
https://trac.sagemath.org/ticket/14564#comment:11
<p>
I think one could separate two methods:
</p>
<ul><li>one called <code>graph</code>, which gives the empty graph for <a class="missing wiki">BinaryTree?</a>() and satisfy t.graph().num_verts() == len(list(t)) (the vertices have valency at most 2)
</li></ul><ul><li>another one called <code>completed_graph</code>, which adds the leaves as new vertices, and builds a tree where every vertex has valency either 2 or 0. Then for <a class="missing wiki">BinaryTree?</a>(), one would have just one vertex.
</li></ul><p>
To be done..
</p>
TicketchapotonFri, 20 Sep 2013 11:42:52 GMT
https://trac.sagemath.org/ticket/14564#comment:12
https://trac.sagemath.org/ticket/14564#comment:12
<p>
There is now a similar problem with the new method <code>to_undirected_graph</code> (since <a class="closed ticket" href="https://trac.sagemath.org/ticket/14784" title="enhancement: Adding combinatorial maps from trees to poset and graphs (closed: fixed)">#14784</a>):
</p>
<pre class="wiki">sage: bt=BinaryTree()
sage: bt.to_undirected_graph()
Graph on 1 vertex
</pre><p>
It should return the empty graph. The problem come from
</p>
<pre class="wiki">sage: bt.as_ordered_tree()
o
</pre><p>
which should raise an exception.
</p>
TicketdarijThu, 03 Oct 2013 06:45:42 GMT
https://trac.sagemath.org/ticket/14564#comment:13
https://trac.sagemath.org/ticket/14564#comment:13
<p>
Patch functionality moved over to <a class="closed ticket" href="https://trac.sagemath.org/ticket/14498" title="enhancement: trees and binary trees (closed: fixed)">#14498</a>.
</p>
<p>
<code>as_ordered_tree</code> now raises an exception on empty tree.<br />
<code>to_undirected_graph</code> on empty tree gives the empty graph.<br />
Instead of renaming the currently existing <code>graph</code> method as <code>completed_graph</code>, I added a <code>reduced_graph</code> method. (My fix for the <code>graph</code> method is also in.) I did not implement anything similar for <code>to_undirected_graph</code>, because that was already done (modulo the bug I fixed) using an optional keyword variable.
</p>
<p>
I did not do anything about <code>list</code> and <code>paths</code> since these methods seem to be in a different file.
</p>
<p>
Anyone look at my <a class="closed ticket" href="https://trac.sagemath.org/ticket/14498" title="enhancement: trees and binary trees (closed: fixed)">#14498</a> patch and tell me if I'm on the right track?
</p>
TicketchapotonThu, 03 Oct 2013 18:09:31 GMT
https://trac.sagemath.org/ticket/14564#comment:14
https://trac.sagemath.org/ticket/14564#comment:14
<p>
Hello Darij,
</p>
<p>
yes, what you do seems correct.
</p>
<p>
Instead of having two methods <code>graph</code> and <code>reduced_graph</code>, I would rather have a keyword <code>with_leaves</code> added to the method <code>graph</code>.
</p>
<p>
I have discussed this matter with Viviane recently, and she had suggestions on how to do that, and even code, but she is probably very busy at the moment.
</p>
<p>
Cheers,
</p>
<p>
Frederic
</p>
TicketdarijThu, 03 Oct 2013 19:59:14 GMT
https://trac.sagemath.org/ticket/14564#comment:15
https://trac.sagemath.org/ticket/14564#comment:15
<p>
Hi Frederic,
</p>
<p>
thanks for the comments.
</p>
<p>
Having a keyword for <code>graph</code> seems more reasonable indeed, but there is a problem with this. If I set the default option to ignore leaves, then it changes the semantics of the method (currently it doesn't ignore leaves). If I set the default option to use leaves, then it is the opposite of the default option in <code>to_undirected_graph</code>. So I would be either planting a backwards compatibility landmine or a false analogy landmine. Which is better?
</p>
<p>
Or, wait. Should I deprecate <code>graph</code> and introduce a <code>to_graph</code> method instead (for better analogy with <code>to_undirected_graph</code>)?
</p>
<p>
Best regards,<br />
Darij
</p>
TicketchapotonFri, 04 Oct 2013 07:25:11 GMT
https://trac.sagemath.org/ticket/14564#comment:16
https://trac.sagemath.org/ticket/14564#comment:16
<p>
Hello,
</p>
<p>
I would vote for keeping the current behaviour as default behaviour. If this is documented, the lack of coherence with another distinct method is not a problem i.m.h.o.
</p>
<p>
F.
</p>
TicketdarijFri, 04 Oct 2013 14:00:10 GMT
https://trac.sagemath.org/ticket/14564#comment:17
https://trac.sagemath.org/ticket/14564#comment:17
<p>
Hi,
</p>
<p>
I've uploaded an improved version on the <a class="closed ticket" href="https://trac.sagemath.org/ticket/14498" title="enhancement: trees and binary trees (closed: fixed)">#14498</a> ticket (twice -- sorry for that). If you can greenlight my changes, I'll continue reviewing <a class="closed ticket" href="https://trac.sagemath.org/ticket/14498" title="enhancement: trees and binary trees (closed: fixed)">#14498</a>.
</p>
<p>
As far as I understand now, <code>list</code> and <code>paths()</code> work fine already, so there is nothing to fix about them.
</p>
<p>
Best regards,<br />
Darij
</p>
TicketchapotonFri, 04 Oct 2013 14:22:02 GMT
https://trac.sagemath.org/ticket/14564#comment:18
https://trac.sagemath.org/ticket/14564#comment:18
<p>
Yes, looks good, you have my green light.
</p>
<p>
In the <code>is_full</code> method, I have found that the sentence
</p>
<pre class="wiki">A full binary tree is a tree in which every node either has two
child nodes or has two child leaves.
</pre><p>
is not quite correct. It should say that every node which is not a leaf has two children.
</p>
TicketdarijFri, 04 Oct 2013 17:13:50 GMT
https://trac.sagemath.org/ticket/14564#comment:19
https://trac.sagemath.org/ticket/14564#comment:19
<p>
I've been following what seems to be the more common notation in the sourcecode, and understanding "node" to mean "interior node", i. e., "non-leaf vertex". Should I change this or better document this?
</p>
<p>
Also, this is not really relevant to <a class="closed ticket" href="https://trac.sagemath.org/ticket/14564" title="defect: BinaryTree().graph() falsely claims that the graph has 0 vertices (closed: duplicate)">#14564</a>, but since we're discussing in this ticket already: The q-hook length formula in <a class="closed ticket" href="https://trac.sagemath.org/ticket/14498" title="enhancement: trees and binary trees (closed: fixed)">#14498</a> still uses a q from the <a class="missing wiki">SymbolicRing?</a>. Should I change it to take any arbitrary input as q, defaulting to a polynomial variable over ZZ?
</p>
TicketchapotonFri, 04 Oct 2013 18:38:16 GMT
https://trac.sagemath.org/ticket/14564#comment:20
https://trac.sagemath.org/ticket/14564#comment:20
<p>
My comment was just remarking that a node can also have a child node and a child leaf.
</p>
<p>
Yes, please remove any occurence of symbolic ring. I.m.h.o., Symbolic ring is the source of all evil, if I dare say so.
</p>
TicketdarijFri, 04 Oct 2013 21:43:09 GMT
https://trac.sagemath.org/ticket/14564#comment:21
https://trac.sagemath.org/ticket/14564#comment:21
<p>
I completely agree with you on the symbolic ring. But I don't understand the "every node which is not a leaf has two children" thing: isn't that true for ANY binary tree in the sense of binary_tree.py? If not, I will have to fix this too:
</p>
<pre class="wiki"> 53 Binary trees contain nodes and leaves, where each node has two
54 children while each leaf has no children. The number of leaves
55 always equals the number of nodes plus 1.
</pre><p>
Either way, what is a full binary tree then?
</p>
TicketchapotonMon, 14 Oct 2013 12:29:58 GMT
https://trac.sagemath.org/ticket/14564#comment:22
https://trac.sagemath.org/ticket/14564#comment:22
<p>
Ok, I was wrong and you were right, about the definition of <code>is_full</code>. It is correct as it is now, no need for a correction.
</p>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/14564#comment:23
https://trac.sagemath.org/ticket/14564#comment:23
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
TicketchapotonWed, 12 Feb 2014 08:59:53 GMT
https://trac.sagemath.org/ticket/14564#comment:24
https://trac.sagemath.org/ticket/14564#comment:24
<p>
Maybe one can close this one as invalid, now that <a class="closed ticket" href="https://trac.sagemath.org/ticket/14498" title="enhancement: trees and binary trees (closed: fixed)">#14498</a> is closed ?
</p>
TicketdarijWed, 12 Feb 2014 12:50:25 GMTstatus changed
https://trac.sagemath.org/ticket/14564#comment:25
https://trac.sagemath.org/ticket/14564#comment:25
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>positive_review</em>
</li>
</ul>
<p>
I agree.
</p>
<p>
Please make this invalid/duplicate.
</p>
TicketdarijWed, 12 Feb 2014 12:51:19 GMTdescription changed
https://trac.sagemath.org/ticket/14564#comment:26
https://trac.sagemath.org/ticket/14564#comment:26
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/14564?action=diff&version=26">diff</a>)
</li>
</ul>
TicketchapotonMon, 17 Feb 2014 12:34:23 GMTmilestone, author changed; reviewer set
https://trac.sagemath.org/ticket/14564#comment:27
https://trac.sagemath.org/ticket/14564#comment:27
<ul>
<li><strong>reviewer</strong>
set to <em>Frédéric Chapoton</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-duplicate/invalid/wontfix</em>
</li>
<li><strong>author</strong>
changed from <em>darij</em> to <em>Darij Grinberg</em>
</li>
</ul>
TicketvbraunWed, 19 Feb 2014 18:58:52 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/14564#comment:28
https://trac.sagemath.org/ticket/14564#comment:28
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>duplicate</em>
</li>
</ul>
Ticket