Opened 4 years ago

Closed 4 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 darij)

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)

trac_14564-trivial-binary-tree.patch (1.5 KB) - added by darij 4 years ago.
Fixes graph() function. This automatically fixes show(). I have not checked all the other functions, though…

Download all attachments as: .zip

Change History (29)

Changed 4 years ago by darij

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

comment:1 Changed 4 years ago by darij

  • Authors set to darij
  • Component changed from PLEASE CHANGE to combinatorics
  • Priority changed from major to minor
  • Status changed from new to needs_review

comment:2 Changed 4 years ago by darij

  • Description modified (diff)

comment:3 Changed 4 years ago by darij

  • Description modified (diff)

comment:4 Changed 4 years ago by ncohen

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 4 years ago by ncohen

  • Status changed from needs_review to needs_info

comment:6 follow-up: Changed 4 years ago by darij

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 4 years ago by darij

  • Cc hivert added

comment:8 in reply to: ↑ 6 Changed 4 years ago by ncohen

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 4 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:10 Changed 4 years ago by chapoton

  • Keywords trees trees added; tree tree removed

comment:11 Changed 4 years ago by chapoton

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 4 years ago by chapoton

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 4 years ago by darij

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?

Last edited 4 years ago by darij (previous) (diff)

comment:14 Changed 4 years ago by chapoton

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 4 years ago by darij

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

Last edited 4 years ago by darij (previous) (diff)

comment:16 Changed 4 years ago by chapoton

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 4 years ago by darij

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

comment:18 Changed 4 years ago by chapoton

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 4 years ago by darij

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 4 years ago by chapoton

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 4 years ago by darij

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 4 years ago by chapoton

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 4 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:24 Changed 4 years ago by chapoton

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

comment:25 Changed 4 years ago by darij

  • Status changed from needs_info to positive_review

I agree.

Please make this invalid/duplicate.

Last edited 4 years ago by darij (previous) (diff)

comment:26 Changed 4 years ago by darij

  • Description modified (diff)

comment:27 Changed 4 years ago by chapoton

  • Authors changed from darij to Darij Grinberg
  • Milestone changed from sage-6.2 to sage-duplicate/invalid/wontfix
  • Reviewers set to Frédéric Chapoton

comment:28 Changed 4 years ago by vbraun

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.