code that produces all possible trees with n nodes. [closed]

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

I'm looking for code that produces all possible trees with no self edges (or their adjacent matrices) with n nodes, anyone have any idea if this is written anywhere?

-

1
See stackoverflow.com. – Ricky Demer Jan 18 2011 at 2:46

2
To prevent comments such as the one above, ask "An algorithm that..." instead of "code that...". Usually, you'll also get an implementation of that algorithm. – Derrick Stolee Jan 18 2011 at 3:52

3
Why is this not appropriate? There are plenty of contexts (often involving operads) where it is useful to have lists of trees to test conjectures and so on. – Neil Strickland Jan 18 2011 at 11:35

2
Dear Neil, if marvin wants to use it for some mathematical reason (for operads, for instance), then he should give background on his application. The more background one gives, the less likely one will be sent to SO. – Harry Gindi Jan 18 2011 at 11:42

2
The question seems completely fine. Trees are a basic mathematical object; maybe the poster is just interested in properties of the set of trees on n nodes. For the purpose of asking for the code, he really doesn't need to tell us precisely which properties. I don't think being pointed to stackoverflow is helpful: stackoverflow is for questions about programming. It seems just as likely that professional mathematicians will know of a tool for generating lists of trees than that professional programmers will, so mathoverflow seems at least as suitable as stackoverflow, probably more so. – James Martin Jan 18 2011 at 13:01
show 1 more comment

2 Answers

In sage the command

list(graphs.trees(9))

produces a list of all trees on 9 vertices. As sage is open source, the code is available for inspection. The command

[tt.am() for tt in graphs.trees(9)]

will provide the adjacency matrices.

-

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

It is well known that there is a bijection between the set of trees on $n$ nodes and sequences of length $n-2$ with values in $[n]$. These sequences are called Prüfer sequences. Indeed, the wikipedia page has code which will convert any Prüfer sequence into a tree. So a naïve algorithm would be to run the wikipedia algorithm over all Prüfer sequences.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 3, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9414250254631042, "perplexity_flag": "middle"}