1

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?

flag
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

closed as off topic by Harry Gindi, Igor Pak, Felipe Voloch, Mark Sapir, Andy Putman Jan 18 2011 at 17:14

2 Answers

14

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.

link|flag
5

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.

link|flag

Not the answer you're looking for? Browse other questions tagged or ask your own question.