0

We have been trying to find a way to enumerate and index all possible trees with n labelled vertices. By Cayley's theorem there shall be nn−2 number of trees from n labelled vertices. Is there a way, in C/C++, to index all the possible trees so that when a user inputs an integer/number a unique tree will generated in real time?

rici
  • 234,347
  • 28
  • 237
  • 341
solarsoul1776
  • 25
  • 1
  • 1
    Welcome to Stack Overflow. Please take the time to read [The Tour](http://stackoverflow.com/tour) and refer to the material from the [Help Center](http://stackoverflow.com/help/asking) what and how you can ask here. – πάντα ῥεῖ Mar 13 '17 at 02:36
  • @πάνταῥεῖ this looks on topic. Please don't blindly flood the site with the template. – Tatsuyuki Ishi Mar 13 '17 at 02:37
  • @TatsuyukiIshi The question looks way too broad for me, doesn't contain any specific c++ code (which is required for that tag), there's no language like c/c++, etc. so what? – πάντα ῥεῖ Mar 13 '17 at 02:41
  • @πάνταῥεῖ This question clearly has the requirements for input and output. It's common for algorithm question to have no code snippet, since we have no idea to write the algorithm. (It would be good to indicate the tree struct he has, though.) – Tatsuyuki Ishi Mar 13 '17 at 02:43
  • @TatsuyukiIshi IMO even [tag:algorithm] questions should show some effort, a pseudocode attempt or whatever. That tag shouldn't be misused as a charter to ask _gimme teh codez_ like questions. – πάντα ῥεῖ Mar 13 '17 at 02:48
  • @TatsuyukiIshi There's not even a _question_ in the question BTW. – πάντα ῥεῖ Mar 13 '17 at 03:01

2 Answers2

1

A quick glance at the Wikipedia article on Cayley's formula (the nn−2 formula you mention) pointed me to Prüfer sequences, which is a sequence of length n−2 consisting of (possibly repeated) node labels. It's obvious that there are nn−2 such sequences, and each sequence can be represented as an n−2 digit base n number. It's less obvious that every Prüfer sequence corresponds to a unique tree with n labeled nodes, but that fact is sufficient to demonstrate Cayley's formula.

The Wikipedia article on Prüfer sequences explains how to turn a sequence into its corresponding tree; which is equivalent to turning an integer into a tree.

I haven't tried any of this, but it looks convincing.

rici
  • 234,347
  • 28
  • 237
  • 341
  • @istvan: it's trivial to produce the next Prüfer sequence, since it is just an n-2 digit base-n number, which can simply be incremented in amortised O(1). (Scan backwards until you find a number other than n-1; increment it and change the following numbers to 0.) It is not trivial to turn the new Prüfer sequence into a tree but it's not that difficult and it can be done in O(n). – rici Jan 31 '19 at 21:46
  • @istvan: and now that i look at it, the OP does not ask for all trees to be generated; it simply requests an algorithm to convert an index within range to the corresponding tree, which my answer provides (admittedly by reference; maybe I should fix that.) – rici Jan 31 '19 at 22:06
  • Could you please elaborate on how to find the next Prüfer sequence, potentially without random trials? Perhaps my misunderstanding stems from the fact that I am working with binary trees, which is more restrictive than all planar trees. – István Zachar Feb 01 '19 at 06:04
  • @istvan: indeed, for binary trees it's more complicated. But the Q is not about binary trees. It's about unrooted labelled trees, which is the set for which Cayley's theorem applies. For that set, any sequence of n-2 node labels is a valid Prüfer sequence representing a unique tree. – rici Feb 01 '19 at 07:05
  • I'm not sure I can follow you. For `n=5` leaves, there are `v=2n-1=9` vertices alltogether, and `C_(n-1)=14` distinct, non-isomorphic labelled binary trees. However, all 14 valid Prüfer sequences of length `v-2=7` are much less than the 630 permutations of the sequence elements `{6, 6, 7, 7, 8, 8, 9}` (given that vertices are labelled `1..9`). What am I missing here? – István Zachar Feb 01 '19 at 08:43
  • @istvan: you are insisting on different problems than the one actually being addressed here. Look at the first Wikipedia link in my answer which has a nice graphic of the trees of size 2, 3 and 4 which are actually been ng counted in *this* counting exercise. – rici Feb 01 '19 at 13:40
  • @istvan: also, its not clear to me what *you* mean by Prüfer sequence, or valid Prüfer sequence, since your context seems to be ordered unlabeled trees. – rici Feb 01 '19 at 14:59
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/187749/discussion-between-istvan-zachar-and-rici). – István Zachar Feb 01 '19 at 15:36
  • @istvan: does [this answer](https://stackoverflow.com/a/14901512/1566221) match your problem? – rici Feb 03 '19 at 05:39
0

I'm not well-versed in C or C++, but I think I can provide the theory such that enumerating every tree shouldn't be too hard. Comment if I need to clarify anything.

Think Binary.

Take an adjacency matrix. To describe whether one vertex is connected to another, we use 1 or 0. So to find all the graphs using adjacency matrices, we would fill up a matrix with all the combos of 1 and 0. The only constraint is that for trees, a node can't be its own parent, and can't have multiple parents. Example with three vertices:

0 1 1  0 1 1  0 0 1
1 0 0  0 0 0  1 0 0
0 0 0  1 0 0  0 1 0 etc.

What we can do is to lay the rows out side-by-side such that a binary sequence describes every matrix. Example:

0 1 1 1 0 0 0 0 0  0 1 1 0 0 0 1 0 0  0 0 1 1 0 0 0 1 0 etc.

So given nine bits, we can describe all graphs with three vertices. This translates to one tree for every number 1-2^9, minus the numbers which are rotations of each other.

To turn a number into a tree, you just convert the number to binary, and turn the binary into a matrix. To fix the self-connections, for every "1" that is on or past the diagonal, move it further by one. So then:

1 0 0         1 0 1 
0 1 0    ->   0 0 0
0 0 1         0 1 0
J369
  • 436
  • 7
  • 12
  • _"I'm not well-versed in C/C++"_ No wonder, there isn't such language as C/C++. – πάντα ῥεῖ Mar 13 '17 at 03:13
  • @πάνταῥεῖ lol I've edited it "C or C++" – J369 Mar 13 '17 at 03:18
  • 1
    But that's going to produce lots of non-trees, so you can't really use it to find the tree for a given ordinal. If you use the correction proposed at the end, then you will end up with a many-to-one relationship between numbers and trees. – rici Mar 13 '17 at 06:06
  • @rici the correction eliminates non-trees, but the multiple-trees issue was present before the correction. There will be some constant number of numbers per tree. I'll get to fixing that later today. – J369 Mar 13 '17 at 14:06
  • 1
    @J369: your proposal seems to start with an *n* x *n* boolean array, of which there are 2^( *n* ^2) but Cayley's formula predicts *n* ^( *n* -2). Those two values are not related in an obvious way; I'll be curious to see how you manage to square that circle. – rici Mar 13 '17 at 14:29
  • You also include unconnected graphs, which are also not part of the enumeration. – rici Mar 13 '17 at 14:37