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?
6
-
1$\begingroup$ See stackoverflow.com. $\endgroup$– user5810Commented Jan 18, 2011 at 2:46
-
2$\begingroup$ 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. $\endgroup$– Derrick StoleeCommented Jan 18, 2011 at 3:52
-
3$\begingroup$ 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. $\endgroup$– Neil StricklandCommented Jan 18, 2011 at 11:35
-
2$\begingroup$ 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. $\endgroup$– Harry GindiCommented Jan 18, 2011 at 11:42
-
2$\begingroup$ 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. $\endgroup$– James MartinCommented Jan 18, 2011 at 13:01
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
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.
answered Jan 18, 2011 at 2:58
$\begingroup$
$\endgroup$
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.
answered Jan 18, 2011 at 15:09