Ask Your Question

tree ordering in sage

asked 2019-08-07 06:18:41 +0200

GA316 gravatar image

updated 2019-08-28 10:24:07 +0200

FrédéricC gravatar image

I am using the following code to generate the isomorphism class of trees of order $n$.

sage: from sage.graphs.trees import TreeIterator
sage: def check_trees(n):
....:     trees = []
....:     for t in TreeIterator(n):    
....:         if not t.is_tree():  
....:             return False 
....:         if t.num_verts() != n: 
....:             return False   
....:         if t.num_edges() != n - 1:
....:             return False
....:         for tree in trees:
....:             if tree.is_isomorphic(t):
....:                 return False
....:         trees.append(t)
....:     return True

Then when I print the trees in TreeIterator using loops it is giving the trees in a particular order.

Can anyone explain to me what is this predefined order on trees of order $n$ on sage?

For n = 6, we have the following order.

image description

image description

image description

image description

image description

image description

edit retag flag offensive close merge delete



As a side-comment, when pasting code in your question please mark it as pre-formatted code (there's a button on the WYSIWYG toolbar, but you can also select the code and press Ctrl-K to indent it all at once, which causes it to be treated as pre-formatted text. I have gone ahead and fixed it for you in this case.

Iguananaut gravatar imageIguananaut ( 2019-08-07 14:18:49 +0200 )edit

That's a good question though. I looked at the code, and even the code does not include any commentary explaining how it works. Yes, one can read the code and figure it out, but I don't think it's at all "obvious".

Iguananaut gravatar imageIguananaut ( 2019-08-07 14:23:51 +0200 )edit

Sorry, I shall paste it like this in future. Thanks for your comment.

GA316 gravatar imageGA316 ( 2019-08-08 08:13:05 +0200 )edit

2 Answers

Sort by » oldest newest most voted

answered 2019-08-07 20:47:18 +0200

The documentation in the reference manual says that it is using the algorithm from this paper.

edit flag offensive delete link more

answered 2019-08-07 19:56:27 +0200

Emmanuel Charpentier gravatar image
sage: r.library("fortunes")
sage: r.fortune("'WTFM'")

This is all documented in TFM. Those who WTFM don't want to have to WTFM again
on the mailing list. RTFM.
   -- Barry Rowlingson
      R-help (October 2003)

This won't give you a "ready-made" answer, but may point you in the right direction. In last resort, try the source code...

edit flag offensive delete link more


It's really not that obvious. No need for snark.

Iguananaut gravatar imageIguananaut ( 2019-08-14 12:38:56 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2019-08-07 06:18:41 +0200

Seen: 448 times

Last updated: Aug 07 '19