4
$\begingroup$

I am implementing an algorithm to generate free unlabelled trees uniformly at random (uar). For this I found this paper by Herbert S. Wilf (The uniform selection of trees. 1981. In Journal of Algorithms). This paper defines the procedure Free which generates free unlabelled trees by calling one of two smaller procedures (either Bicenter or Forest) with a certain probability each. These two procedures, in turn, are based on the ranrut procedure, which generates rooted unlabelled trees uar. You can find the reference in Combinatorial Algorithms For Computers and Calculators. Albert Nijenhuis and Herbert S. Wilf. 2nd Edition. Academic Press. (I'll try to make this post as self-contained as I can).

First, I'm quite convinced to have managed to implement the ranrut procedure so that each rooted unlabelled tree is generated uar. However, I'm having some problems with the algorithm to generate free unlabelled trees (here) and I was hoping that you could help me. In this post I would like to ask two questions.

I have one problem with language. Specifically, with one particular word, which I do not understand in the context of the paper. The word is adjoined and appears in the Forest procedure, as seen highlighted in this image:

    

The image is an extract of Wilf's paper that shows the full procedure Forest. Now, the word adjoined is used in the sentence

Then exit with $j$ copies of $T'$ adjoined to $\mathcal{F}'$.

  • Should adjoined be understood here as the disjoint union of graphs? Namely, should I perform the operation $\mathcal{F}' \oplus T'_1 \oplus \cdots T'_j$, where $\oplus$ denotes disjoint union of graphs ? If not, how should I interpret it?

Wilf says that, in order to generate uar a forest of $m$ trees, we first choose two integers $(j,d)$ with probability (as shown in the above image)

$$ Prob(j,d) = \frac{d\cdot \alpha(m - jd,q) \cdot a_d}{m \cdot \alpha(m,q)}. $$

For this we need the values $a_n$ (the number of rooted unlabelled trees of $n$ vertices), and $\alpha(m,q)$ (the number of rooted forests of $m$ vertices whose trees have at most $q$ vertices each).

I have written an algorithm to correctly calculate $a_n$. I know it is correct because I can compare the values obtained with its integer sequence.

  • I would like to know if I'm calculating $\alpha(m,q)$ correctly. However, I haven't been able to find the integer sequences for $\alpha(m,q)$. Do you know where I can find it?

I hope to have made my doubts understandable and the questions clear.

Thanks to you all for your time.

Edit This post was motivated because my implementation of this algorithm did not generate trees uniformly at random. In my desperation I came here for help. Although the questions above still stand (because the implementation of the above might still be wrong), one of the "bugs" was caused by an error in Wilf's paper. My advisor pointed me to this document (Graph theory package for Giac/Xcas - Reference Manual, September 2018) where this error is mentioned and corrected (page 38, footnote 1.1). For the sake of self-containment, I tell you here what the error is and how it has been corrected. The Free procedure that Wilf defines in this paper, says that in order to generate an $n$-vertex free tree u.a.r. you have to generate a bicentroidal tree with probability $p$, or a random forest of $n-1$ vertices with probability $1-p$ (the roots of this forest are connected to a new vertex). Wilf says that $$p ={1 + a_{n/2} \choose 2}/a_n$$ where $a_n$ is the number of rooted unlabelled trees of $n$ vertices. As pointed out in the cited document in this edit, the denominator is wrong. Instead of $a_n$, it should be $f_n$, the number of unlabelled free trees on $n$ vertices.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Based on the images, yes, I say you have the right idea. In your disjoint union, make sure the T'_i are all isomorphic to T'. Gerhard "Follow The Recipe Very Closely" Paseman, 2019.12.26. $\endgroup$
    – Gerhard Paseman
    Commented Dec 26, 2019 at 23:13
  • $\begingroup$ Okay. That is exactly what I was doing but I wasn't sure at a 100%. Now it only remains the other question of the $\alpha(m,q)$ :) $\endgroup$
    – Lluís Alemany-Puig
    Commented Dec 27, 2019 at 6:43
  • $\begingroup$ I have edited the original post with a correction of a small error in the original paper. However, I would appreciate to have my other questions answered, since they refer to parts of my code that still need debugging. $\endgroup$
    – Lluís Alemany-Puig
    Commented Dec 28, 2019 at 8:49
  • 1
    $\begingroup$ I wonder if you actually need this algorithm, or you just need one fast in practice. Walk at random on $K_n$ until every vertex is visited (about $n\log n$ steps on average). Mark the edge along which each vertex was visited for the first time. That's a uniform random free tree. It's very fast: 6000 trees/sec on 1000 vertices for me. $\endgroup$
    – Brendan McKay
    Commented Dec 28, 2019 at 13:02
  • 1
    $\begingroup$ Why don't you compare your algorithm and your calculation of $\alpha(m,q)$ with the source code on which the cited documentation is based? In particular, this function: github.com/marohnicluka/giac/blob/master/graphe.cc#L7149 $\endgroup$
    – Timothy Budd
    Commented Jan 13, 2020 at 15:51

1 Answer 1

Reset to default
1
$\begingroup$

Thanks to the effort of several people, I got the answers I was looking for. I write this so that other people in the future can have a direct answer to the questions above without having to read the comments.

  • The first question was whether the word adjoined (in the Forest procedure) referred to disjoint union of graphs. This comment written by Gerhard Paseman confirmed this. Thanks to this comment and careful reading of the Free procedure, any interpretation of the word adjoined other than disjoint union should be ruled out.

  • The second question was about the calculation of the numbers $\alpha(m,q)$. Timothy Budd added a comment where I was pointed to an implementation of this algorithm where I could find the computation of $\alpha(m,q)$. Budd advised me to compare the result of that algorithm with mine. This proved useful, and the results of my implementation and those of the code to which I was pointed coincide.

Thanks to everyone who helped in finding the answers to my questions, even to those who did not answer them directly. I really appreciate your help.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .