Opened 6 years ago
Closed 6 years ago
#14564 closed defect (duplicate)
BinaryTree().graph() falsely claims that the graph has 0 vertices
Reported by: | darij | Owned by: | tbd |
---|---|---|---|
Priority: | minor | Milestone: | sage-duplicate/invalid/wontfix |
Component: | combinatorics | Keywords: | binary trees, trees |
Cc: | chapoton, sage-combinat, VivianePons, hivert | Merged in: | |
Authors: | Darij Grinberg | Reviewers: | Frédéric Chapoton |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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.
Attachments (1)
Change History (29)
Changed 6 years ago by
comment:1 Changed 6 years ago by
- Component changed from PLEASE CHANGE to combinatorics
- Priority changed from major to minor
- Status changed from new to needs_review
comment:2 Changed 6 years ago by
- Description modified (diff)
comment:3 Changed 6 years ago by
- Description modified (diff)
comment:4 Changed 6 years ago by
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
comment:5 Changed 6 years ago by
- Status changed from needs_review to needs_info
comment:6 follow-up: ↓ 8 Changed 6 years ago by
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.
comment:7 Changed 6 years ago by
- Cc hivert added
comment:8 in reply to: ↑ 6 Changed 6 years ago by
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
comment:9 Changed 6 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:10 Changed 6 years ago by
- Keywords trees trees added; tree tree removed
comment:11 Changed 6 years ago by
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..
comment:12 Changed 6 years ago by
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.
comment:13 Changed 6 years ago by
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?
comment:14 Changed 6 years ago by
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
comment:15 Changed 6 years ago by
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
comment:16 Changed 6 years ago by
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.
comment:17 Changed 6 years ago by
comment:18 Changed 6 years ago by
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.
comment:19 Changed 6 years ago by
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?
comment:20 Changed 6 years ago by
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.
comment:21 Changed 6 years ago by
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?
comment:22 Changed 6 years ago by
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.
comment:23 Changed 6 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:24 Changed 6 years ago by
Maybe one can close this one as invalid, now that #14498 is closed ?
comment:25 Changed 6 years ago by
- Status changed from needs_info to positive_review
I agree.
Please make this invalid/duplicate.
comment:26 Changed 6 years ago by
- Description modified (diff)
comment:27 Changed 6 years ago by
- Milestone changed from sage-6.2 to sage-duplicate/invalid/wontfix
- Reviewers set to Frédéric Chapoton
comment:28 Changed 6 years ago by
- Resolution set to duplicate
- Status changed from positive_review to closed
Fixes graph() function. This automatically fixes show(). I have not checked all the other functions, though...