BinaryTree().graph() falsely claims that the graph has 0 vertices

[darijgr]

This also breaks the show() function of this trivial binary tree.

Patch coming in a couple minutes.

Warning: compatibility with queue not checked, I'm still working off 5.9 sage-main with only #8703 installed.

Apply: nothing. This is a duplicate ticket.

CC: @fchapoton @sagetrac-sage-combinat @VivianePons @hivert

Component: combinatorics

Keywords: binary trees, trees

Author: Darij Grinberg

Reviewer: Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/14564

[darijgr]

Attachment: trac_14564-trivial-binary-tree.patch.gz

Fixes graph() function. This automatically fixes show(). I have not checked all the other functions, though...

[darijgr]

Author: darij

[nathanncohen]

comment:4

Hellooooooooooooo !

You change the associated graph of an empty binary tree to a non-empty graph, but what about these things ?

sage: t1 = BinaryTree()
sage: t1
.
sage: t1.graph().vertices()
[0]
sage: list(t1)
[]
sage: list(t1.paths())
[]
sage: t1.depth()
0

Nathann

[darijgr]

comment:6

Hi Nathannnnnn! Thanks for looking in the file. list, graph().vertices() and depth() seem to be correct (list 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 paths() answer (isn't there a 0-length path from the root to itself?), but that answer appears precisely that way in the docstring:

      sage: list(BinaryTree().paths())
      []

so I suspect the authors (whom I'm adding to cc now) must have had something in mind.

[nathanncohen]

comment:8

Hellooooooooooo !!!

so I suspect the authors (whom I'm adding to cc now) must have had something in mind.

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.

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 !

Have fuuuuuuuuuuuuuuuuuuuuuunnn !

Nathann

[fchapoton]

Changed keywords from binary tree, tree to binary trees, trees

[fchapoton]

comment:11

I think one could separate two methods:

• one called graph, which gives the empty graph for BinaryTree() and satisfy t.graph().num_verts() == len(list(t)) (the vertices have valency at most 2)

• another one called completed_graph, which adds the leaves as new vertices, and builds a tree where every vertex has valency either 2 or 0. Then for BinaryTree(), one would have just one vertex.

To be done..

[fchapoton]

comment:12

There is now a similar problem with the new method to_undirected_graph (since #14784):

sage: bt=BinaryTree()
sage: bt.to_undirected_graph()
Graph on 1 vertex

It should return the empty graph. The problem come from

sage: bt.as_ordered_tree()
o

which should raise an exception.

[darijgr]

comment:13

Patch functionality moved over to #14498.

as_ordered_tree now raises an exception on empty tree.

to_undirected_graph on empty tree gives the empty graph.

Instead of renaming the currently existing graph method as completed_graph, I added a reduced_graph method. (My fix for the graph method is also in.) I did not implement anything similar for to_undirected_graph, because that was already done (modulo the bug I fixed) using an optional keyword variable.

I did not do anything about list and paths since these methods seem to be in a different file.

Anyone look at my #14498 patch and tell me if I'm on the right track?

[fchapoton]

comment:14

Hello Darij,

yes, what you do seems correct.

Instead of having two methods graph and reduced_graph, I would rather have a keyword with_leaves added to the method graph.

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.

Cheers,

Frederic

[darijgr]

comment:15

Hi Frederic,

thanks for the comments.

Having a keyword for graph 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 to_undirected_graph. So I would be either planting a backwards compatibility landmine or a false analogy landmine. Which is better?

Or, wait. Should I deprecate graph and introduce a to_graph method instead (for better analogy with to_undirected_graph)?

Best regards,

Darij

[fchapoton]

comment:16

Hello,

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.

F.

[darijgr]

comment:17

Hi,

I've uploaded an improved version on the #14498 ticket (twice -- sorry for that). If you can greenlight my changes, I'll continue reviewing #14498.

As far as I understand now, list and paths() work fine already, so there is nothing to fix about them.

Best regards,

Darij

[fchapoton]

comment:18

Yes, looks good, you have my green light.

In the is_full method, I have found that the sentence

A full binary tree is a tree in which every node either has two 
child nodes or has two child leaves. 

is not quite correct. It should say that every node which is not a leaf has two children.

[darijgr]

comment:19

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?

Also, this is not really relevant to #14564, but since we're discussing in this ticket already: The q-hook length formula in #14498 still uses a q from the SymbolicRing. Should I change it to take any arbitrary input as q, defaulting to a polynomial variable over ZZ?

[fchapoton]

comment:20

My comment was just remarking that a node can also have a child node and a child leaf.

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.

[darijgr]

comment:21

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:

 	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.

Either way, what is a full binary tree then?

[fchapoton]

comment:22

Ok, I was wrong and you were right, about the definition of is_full. It is correct as it is now, no need for a correction.

[fchapoton]

comment:24

Maybe one can close this one as invalid, now that #14498 is closed ?

[darijgr]

comment:25

I agree.

Please make this invalid/duplicate.

[fchapoton]

Changed author from darij to Darij Grinberg

[fchapoton]

Reviewer: Frédéric Chapoton