MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

See – Ricky Demer Jan 18 '11 at 2:46
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 '11 at 3:52
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 '11 at 11:35
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 '11 at 11:42
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 '11 at 13:01

In sage the command


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

[ for tt in graphs.trees(9)]

will provide the adjacency matrices.

share|cite|improve this answer

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.

share|cite|improve this answer

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