2
$\begingroup$

For a vertex set $v = \left\{v_1...v_n \right\}$ and a common root $r$, is there an efficient (maybe $O(1)$ per tree) algorithm that generates all non-isomorphic trees on all nodes $v$ and with root $r$.

Two trees are isomorphic if all the parent-child relationships are the same, i.e. all equivalent nodes in the two trees have the same parent and the same children.

Example: $v = \left\{v_1, v_2, v_3\right\}$

All trees should have the same root an the same node set. The following image shows some valid trees:

Trees that should be generated

Including a tree should lead to all other isomorphic trees being ignored Example how repetitions of isomorphic trees should be avoided


Another SO post shows a implementation that finds unrooted topologies:

https://codereview.stackexchange.com/questions/202773/generating-all-unlabeled-trees-with-up-to-n-nodes

In one answer, there appears this algorithm for creating unrooted non-isomorphic topologies on $n$ nodes in constant time per tree.

Robert Alan Wrights, Bruce Richmond, Andrew Odlyzko and Brendan D. Mckay (1986). “Constant time generation of free trees”. SIAM J. Comput. 15:2, pp. 540–548.

I am not sure if it is possible to extend this algorithm efficiently to generate the desired rooted trees.

$\endgroup$
  • 1
    $\begingroup$ Of course there's an algorithm, it's a finite problem. $\endgroup$ – Gerry Myerson Apr 10 at 2:19
  • $\begingroup$ Thanks for that comment, I clarified the question. I wanted an efficient algorithm. Tree space grows quickly and enumerating everything takes forever. $\endgroup$ – user36028 Apr 10 at 2:25
  • $\begingroup$ Your sample of "all trees to generate" seems to just be a black rectangle. Also...you might want to give a definition of "isomorphism" here, just to make the problem unambiguous and avoid wasting people's time. $\endgroup$ – John Hughes Apr 10 at 2:34
  • $\begingroup$ For instance, in the first tree (now included in your question), if I swap the positions of v1 and v2 in the middle tree, is the resulting tree isomorphic to the middle tree or not? $\endgroup$ – John Hughes Apr 10 at 2:36
  • 1
    $\begingroup$ The Algorithmic Encyclopedia linked in the second link gives a good overview. I read the article a few days ago. They also give the algorithm mentioned above, but this yields only the topology. Assigning the node labels in all possible ways leads to double counts. Extending this approach starting with the topology alone was my first thought, but then you have to make sure that you don't create isomorphic trees when assigning labels. $\endgroup$ – user36028 Apr 10 at 2:59
2
$\begingroup$

I can do it in $O(n^2)$ per tree.

The number of possible trees is $(n+1)^{n-1}$, since choosing a tree in your problem is equivalent to choosing an undirected tree on the vertex set $v\cup \{r\}=\{v_1,\dots,v_n,r\}$, and then directing all edges towards the root. The number of undirected trees on $n+1$ vertices is $(n+1)^{n-1}$ (this is Cayley's theorem), and these trees can be generated efficiently using Prüfer codes.

Specifically, iterate through all lists of length $n-1$ with entries in $\{0,1,2,\dots,n\}$, where $0$ represents $r$ and $1$ through $n$ represent $v_1$ through $v_n$. For each list, generate the corresponding tree with vertices $\{r,v_1,\dots,v_n\}$ using the algorithm to convert a Prüfer sequence into an undirected tree. Finally, turn this into a directed tree using breadth first search starting from vertex $r$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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