# Generation of weighted trees, block trees and block graphs ††thanks: The
first and the second author acknowledge the support of the The Scientific and
Technological Research Council of Turkey TÜBİTAK Grant number 122M452.

Tınaz Ekim  Department of Industrial Engineering, Bogazici University,
Istanbul, Turkey<EMAIL_ADDRESS>Mordechai Shalom  Peres Academic
Center, Rehovot, Israel<EMAIL_ADDRESS>Mehmet Aziz Yirik  Department of
Mathematics and Computer Science, The University of Southern Denmark, Odense,
Denmark<EMAIL_ADDRESS>
###### Abstract

We present a general framework to generate trees every vertex of which has a
non-negative weight and a color. The colors are used to impose certain
restrictions on the weight and colors of other vertices. We first extend the
enumeration algorithms of unweighted trees given in [20, 19] to generate
weighted trees that allow zero weight. We avoid isomorphisms by generalizing
the concept of centroids to weighted trees and then using the so-called
centroid-rooted canonical weighted trees. We provide a time complexity
analysis of unranking algorithms and also show that the output delay
complexity of enumeration is linear. The framework can be used to generate
graph classes taking advantage of their tree-based
decompositions/representations. We demonstrate our framework by generating
weighted block trees which are in one-to-one correspondence with connected
block graphs. All connected block graphs up to 19 vertices are publicly
available at [1].

Keywords: Enumeration, unranking, generation uniformly at random, graph
classes, block tree.

##  1 Introduction

Background: Graphs provide a very useful tool to model many important real-
life problems such as drug design, DNA sequencing, temporal reasoning in
artificial intelligence, etc. [7]. In each application, the related graph
model admits local structural properties that are embodied by various graph
classes. It is therefore important to solve optimization problems in graph
classes defined by special structures. Accordingly, many algorithms have been
developed for various optimization problems in these classes. Yet, no random
graph generators for these graph classes have been provided in the literature
to measure the performance of exact/approximation/parameterized algorithms
apart from a few exceptions. This especially holds for the average case
performance, since most of the theoretical analyzes focus on the worst case
performance of the algorithms. This shortcoming was even mentioned as an
important open task at a Dagstuhl Seminar [3].

An important use-case of graph generation with specified restrictions is in
chemical graph theory, such as drug discovery and natural product studies
[21]. To elucidate the structure of unknown molecules, chemists need the
entire chemical space to be constructed, in other words, the isomorphism-free
graph class. Constructing the entire graph class can be a very time-consuming
task. Therefore, chemists aim to get a grasp of a subset of the class as the
first step towards conducting in-depth analyses. One way to construct such an
unbiased subset is the uniformly at random generation of the graph classes
[13].

It is well-known that various types of trees are used to represent structures
of graphs. Clique-trees, block-trees, tree decompositions, clique-width
decompositions, decompositions by clique-separators are some of the well-known
such representations. Whenever a one-to-one mapping between graphs of a
certain family and their tree representations can be established, the
generation of the representative trees uniformly at random provides us with a
tool to generate the graphs in the family uniformly at random as well.
Motivated by the above examples, in this study, we present a generic framework
to enumerate trees with some color scheme to express additional properties and
demonstrate our approach to generate block graphs (with a given number of
vertices).

Enumeration of rooted trees is a well-studied problem. We will mention here a
few works that are closely related to our work. The book [20] contains
enumeration algorithms for numerous sets of combinatorial objects and a
general framework to obtain such algorithms. It also provides FORTRAN
implementations of the algorithms. As such, these algorithms are iterative (as
opposed to recursive) since FORTRAN, at that time, did not have a direct
support for recursive subroutines. Among others, the book presents enumeration
algorithms for (unlabeled, unordered) rooted trees. Enumeration algorithms for
free (i.e., unrooted) trees are presented in the paper [19] by providing a
one-to-one-mapping between free trees and sets of at most two rooted trees.

The work [15] presents recursive enumeration algorithms for rooted and free
trees with Pascal implementations. It extends the results to trees with degree
restrictions. Being recursive, their implementation is, by far, simpler. They
show that the enumeration algorithm is CAT, i.e., it runs in constant
amortized time. Namely, the time needed to enumerate all the trees is
proportional to the number of trees. In [12], the author presents alternative
recursive ranking and unranking algorithms for binary trees of bounded height
and for height-balanced trees.

Our Contribution: In this work, we present a general framework to enumerate
and unrank trees that are weighted and colored. These are trees every vertex
of which has a non-negative weight and a color. The colors may be used to
impose certain restrictions on the weight and colors of other vertices. We
demonstrate this framework by generating block graphs and call this algorithm
BlockGraphGen. For this purpose, we assign colors and weights to the vertices
of the block tree of a hypothetical graph on $n$ vertices and we
enumerate/unrank all such trees. Since block trees are in one-to-one
correspondence with block graphs, the enumeration/unranking of block graphs
follows. All non-isomorphic connected block graphs with up to 19 vertices are
downloadable at [1], the House of Graphs searchable database of ”interesting
graphs” [4].

Organization of the paper: In Section 2, we start with a discussion on
enumeration problems and introduce the terminology related to trees. We
continue with our implementation of the algorithms in [20] and [19] in Section
3. We present them as a set of generators involving indirect recursion. Taking
advantage of features available today in many programming languages, our
pseudo code is very simple. Moreover, it is almost identical to its Python
implementation [16]. We show that the enumeration of rooted trees and forests
can be done in linear output delay time (in Theorem 1) and their unranking
takes ${\cal O}(n^{3})$ time (Theorem 2).

In Section 4, we extend the techniques to weighted trees. For this purpose, we
first extend the well-known structural properties of the centroids to the case
of weighted trees that allow for zero-weight vertices.

In Section 5 we represent block trees as vertex-colored weighted trees with
specific restrictions. Then, we show that there is a one-to-one correspondence
between block trees and block graphs (Theorem 4). This enables us to enumerate
block graphs using the generation algorithm BlockGraphGen.

In Section 6, we present a framework that generalizes the algorithms developed
in the previous sections and give references to a Python implementation of it.

Lastly, in Section 7, we discuss possible extensions of our work, the
ingredients needed to adapt our approach to enumeration problems in other
graph classes and point out promising research directions.

##  2 Preliminaries

To develop algorithmic solutions in networked systems, it is important to test
algorithms on instances that are generated uniformly at random (u.a.r. for
short) so that the experimental results are not biased. Two important issues
make generating structured graphs u.a.r. an extremely challenging question. i)
Forcing structural properties requires interventions to the generation process
that harms randomness. The remedy depends very much on the required structure
and how well this graph structure is captured and exploited for a generation.
ii) To avoid the generation of the same graphs repetitively, one should
perform a high number of isomorphism checks efficiently (which is a
computationally very hard task [8]) or avoid isomorphisms using powerful
structural results. Generating (unlabeled) graphs u.a.r. means that, up to
isomorphism, every graph in the target graph class is produced with equal
probability.

As pointed out in [18], counting, generating u.a.r., and enumerating unlabeled
graphs in a special class are closely related to each other. Yet, these
problems are not equivalent [11, 20], and among them, random generation seems
to be the less investigated. _Counting_ is the task of finding the cardinality
of a set $S$ of combinatorial objects. _Enumeration_ is the task of
constructing all the objects in such a set $S$ without repetition, in some
order $s_{0},s_{1},\ldots$. The task of _ranking_ consists of determining the
index of a given object $s\in S$ in the enumeration. _Unranking_ (a.k.a)
_random access_ is the opposite task, i.e., the task of finding the object
$s_{i}\in S$ corresponding to a given non-negative integer $i$ (without
enumerating $S$). We will refer to this family of four problems as
_enumeration problems_ through the text.

Clearly, the ability to count and unrank a set $S$ enables us to generate an
element of $S$ u.a.r. as described in Algorithm 1.

Algorithm 1 Choose u.a.r.

1:$N\leftarrow\left|S\right|$ $\triangleright$ Use the counting algorithm

2:Choose an integer $i\in[0,N-1]$ u.a.r.

3:return the $i$-th element of $S$. $\triangleright$ Use the unranking
algorithm

These building blocks can also be used to parallelize the task of enumerating
objects of the set $S$ as suggested in Algorithm 2.

Algorithm 2 Parallel Enumeration

1:$P$ the number of processors available

2:$N\leftarrow\left|S\right|$ $\triangleright$ Use the counting algorithm

3:$k\leftarrow\lfloor\frac{N}{P}\rfloor$

4:for $i=0$ to $P-1$ in parallel do

5: for $j=i\cdot k$ to $\min\left\\{(i+1)\cdot k-1,N-1\right\\}$ do

6: return the $j$-th element of $S$. $\triangleright$ Use the unranking
algorithm

We use standard terminology and notation for graphs (see, for instance [5]).
We denote by $[n]$ the set of positive integers not larger than $n$. Given a
simple undirected graph $G$, we denote by $V(G)$ the set of vertices of $G$
and by $E(G)$ the set of the edges of $G$. We use $\left|G\right|$ as a
shortcut for $\left|V(G)\right|$. We denote an edge between two vertices $u$
and $v$ as $uv$. In this work we consider only _unlabeled_ , _unordered_
graphs. That is, the vertices of the graph do not have labels and the
neighbors of a vertex do not have a particular order.

Throughout the paper, we consider both _undirected_ (a.k.a. _unrooted_ ,
a.k.a. _free_) trees and _directed_ (a.k.a. _rooted_) trees. A directed tree
is obtained from an undirected one by designating a vertex $r$ as its root,
and directing the edges from the root outwards. Unless stated otherwise, a
tree under consideration is undirected.

Let $T$ be a tree on $n$ vertices and $v$ a vertex of $T$. The _subtrees_ of
$v$ in $T$ are the subtrees of $T$ obtained by the removal of $v$, i.e., the
connected components of $T-v$. The _heaviest subtree weight_ of $v$ in $T$
denoted by $\operatorname{hs}_{T}(v)$ is the largest number of vertices in any
of its subtrees in $T$. When the tree $T$ is clear from the context, we refer
the subtrees simply as the _subtrees_ of $v$ and we denote the heaviest
subtree weight of $v$ as $\operatorname{hs}(v)$. A _centroid_ of $T$ is a
vertex with minimum heaviest subtree weight in $T$. The following fact
regarding the centroids of a tree $T$ is well known [14].

###### Fact 1

Let $T$ be a tree on $n$ vertices.

  * •

$T$ has at most two centroids;

  * •

if $T$ has two centroids then they are adjacent and the removal of the edge
joining them separates $T$ into two trees of equal sizes, i.e., the heaviest
subtree weights of the centroids is $n/2$;

  * •

if $v$ is the unique centroid of $T$ then $\operatorname{hs}(v)\leq(n-1)/2$.

##  3 Unweighted Trees

In this section, we present enumeration and unranking algorithms for
unweighted trees. The algorithms in Section 3.1 and Section 3.2 are very
similar to the algorithms presented in [20] and [19], respectively. Here, we
provide an adaptation of these algorithms so that it will suit our needs in
the upcoming sections. We present recursive algorithms for unweighted rooted
trees and then algorithms for free trees that use these recursive algorithms
as a subroutine. Technically, we enumerate all (unlabeled) trees using an
adaptation of the formula counting unlabeled trees in [19]. We avoid
isomorphisms by exploiting the fact that every tree has either one or two
adjacent centroids, as noted in Fact 1. In this section, we prepare the
technical basis for the development of the extensions of these algorithms to
weighted trees in Section 4 and block trees in Section 5. Last but not least,
we provide a time complexity analysis for the unranking algorithm and an
output delay time complexity analysis for the enumeration algorithm.

###  3.1 Rooted Trees

In this section, a tree is a rooted tree, and a forest is a digraph the
connected components of which are rooted trees. For a forest $F$, we denote by
$m(F)$ the maximum number of vertices in a tree of $F$ and by $\mu(F)$ the
number of trees of $F$ having $m(F)$ vertices.

Denote

  * •

by ${\mathcal{RT}}(n)$ the set of trees on $n$ vertices,

  * •

by ${\mathcal{F}}(n)$ the set of forests on $n$ vertices,

  * •

by ${\mathcal{F}}(n,m)$ the set of forests $F\in{\mathcal{F}}(n)$ with
$m(F)=m$,

  * •

by
${\mathcal{F}}^{\leq}(n,m)=\cup_{m^{\prime}\in[m]}{\mathcal{F}}(n,m^{\prime})$
the set of forests $F\in{\mathcal{F}}(n)$ with $m(F)\leq m$,

  * •

by ${\mathcal{F}}(n,m,\mu)$ the set of forests of $F\in{\mathcal{F}}(n,m)$
with $\mu(F)=\mu$, and

  * •

by
${\mathcal{F}}^{\leq}(n,m,\mu)=\cup_{\mu^{\prime}\in[\mu]}{\mathcal{F}}(n,m,\mu^{\prime})$
the set of forests of $F\in{\mathcal{F}}(n,m)$ with $\mu(F)\leq\mu$.

####  3.1.1 Enumeration

Under these definitions one can enumerate all the rooted trees on $n$ vertices
as described by the pseudo code in Algorithm 3. The pseudo code contains three
generators that recursively invoke one another. Namely,
EnumerateRootedTrees(n) generates ${\mathcal{RT}}(n)$,
$\textsc{EnumerateForests}(n,m)$ that generates ${\mathcal{F}}^{\leq}(n,m)$,
and $\textsc{EnumerateForests}(n,m,\mu)$ that generates
${\mathcal{F}}(n,m,\mu)$. We adopted the yield statement from languages such
as Python, C#, PHP to return an object from the set being generated. The
return statement signals the termination of the set.

EnumerateRootedTrees repeatedly invokes EnumerateForests to get one forest of
$n-1$ nodes at-a-time and attaches to each forest a root to get a rooted tree
on $n$ vertices.

$\textsc{EnumerateForests}(n,m)$ iterates over all possible largest tree sizes
$m^{\prime}\leq m$ and number $\mu$ of largest trees. For each such pair
$m^{\prime},\mu$ it yields all the forests yielded by
$\textsc{EnumerateForests}(n,m^{\prime},\mu)$

Finally, $\textsc{EnumerateForests}(n,m,\mu)$ iterates over all multisets with
$\mu$ elements of the set ${\mathcal{RT}}(m)$ of trees on $m$ vertices
($highForest$). For each such multiset, it iterates over all forests on
$n-\mu\cdot m$ vertices with largest tree size at of most $m-1$ ($lowForest$)
and it returns the union of the two ($highForest\cup lowForest$).

Algorithm 3 Enumerating Rooted Trees and Forests

1:Enumerates the set ${\mathcal{RT}}(n)$ of rooted trees on $n$ vertices.

2:function EnumerateRootedTrees($n$)

3: for $F\in$ EnumerateForests($n-1,n-1$) do

4: yield the tree obtained from $F$ by connecting all its roots to a new root.

5:

6:Enumerates the set ${\mathcal{F}}^{\leq}(n,m)$ of rooted forests on $n$
vertices

7: with largest tree size of at most $m$.

8:function EnumerateForests($n,m$)

9: if $n=0$ then

10: yield the empty forest

11: return

12: if $m=0$ then

13: return

14: for $m^{\prime}\in[m]$ do

15: for $\mu\in[\lfloor n/m^{\prime}\rfloor]$ do

16: for $F\in$ EnumerateForests($n,m^{\prime},\mu$) do

17: yield $F$

18:

19:Enumerates the set ${\mathcal{F}}(n,m,\mu)$ of rooted forests on $n$
vertices

20: with $\mu$ largest trees, each having size $m$.

21:function EnumerateForests($n,m,\mu$)

22: for $highForest\in$ multi-subsets with $\mu$ elements of
${\mathcal{RT}}(m)$ do

23: for $lowForest\in$ EnumerateForests($n-\mu\cdot m,\min(n-\mu\cdot m,m-1)$)
do

24: yield $highForest\cup lowForest$

25: return

Given the above definitions, the correctness of the functions
EnumerateRootedTrees and EnumerateForests are obvious. We now give a time
complexity analysis of this enumeration. The _delay_ time of an algorithm that
enumerates a set of objects is the maximum time elapsed between the emission
of two consecutive objects (and the time elapsed until the first object is
emitted). We will consider the _output delay_ time complexity in which the
delay time is measured as a function of the output size, i.e., the size of the
emitted object. Throughout the analysis, the _size_ of an object is the number
of bits of its representation. In particular, the size of a set is the sum of
the sizes of its elements (as opposed to the number of its elements). The size
of a graph $(V,E)$ is ${\cal O}(\left|V\right|+\left|E\right|)$. In
particular, the size of a tree is ${\cal O}(\left|V\right|).$ We do not
consider any possible compact representations that might exist for special
cases 444For instance, a path on $n$ vertices can be represented by the
integer $n$..

We start with the analysis of enumerating the multi-subsets of a set $A$ given
by a function $f$ that enumerates its elements. A pseudo code of an algorithm
for such an enumeration is given in Algorithm 4.

Algorithm 4 Enumerating Multisets

1:$f$ enumerates a finite set $A=\left\\{a_{1},\ldots\right\\}$ of objects.

2:Bounded($f,i$) enumerates the first (at most) $i$ elements of $A$

3:Enumerates all the multisets with exactly $k$ elements chosen from the first
$upperBound$ elements of $A$.

4:function EnumerateMultisets($f,k,upperBound$)

5: if $k=0$ then

6: yield $\emptyset$.

7: return

8: $i\leftarrow 0$

9: for $item\in$ Bounded($f,upperBound$) do

10: $i\leftarrow i+1$

11: for $multiset\in$ EnumerateMultisets($f,k-1,i$) do

12: yield $multiset\uplus\left\\{item\right\\}$ return

###### Observation 1

The delay time of EnumerateMultisets to emit a multiset
$S=\left\\{s_{1},\ldots,s_{k}\right\\}$ is ${\cal
O}\left(\sum_{j=1}^{k}D_{f}(size(s_{j}))\right)$ where $D_{f}(size(s))$ is the
delay time of $f$ to emit the object $s$.

Proof: By induction on $k$. In order to emit the multiset $S$,
EnumerateMultisets makes one recursive invocation of itself and possibly one
invocation to ${\textsc{Bounded}(f,upperBound)}$. We note that one invocation
of ${\textsc{Bounded}(f,upperBound)}$ consists of one invocation of $f$ and an
additional bound-check that takes constant time. By the inductive assumption,
the recursive invocation takes ${\cal
O}\left(\sum_{j=1}^{k-1}D_{f}(size(s_{j}))\right)$ time and the invocation of
${\textsc{Bounded}(f,upperBound)}$ to get $item=s_{k}$ takes
$D_{f}(size(s_{k}))$ time. All the other operations including the $\uplus$
operation take constant time. $\square$

Since $size(S)=\left(\sum_{j=1}^{k}size(s_{j})\right)$, we have the following.

###### Corollary 1

If $D_{f}$ is linear then the output delay time complexity of
EnumerateMultisets is linear.

We are now ready to complete the delay time analysis of our enumeration
algorithms.

###### Theorem 1

The output delay time complexity of EnumerateRootedTrees is linear.

Proof: We will show that each of the functions in Algorithm 3 has linear
output delay time complexity, by induction on the size of the input.

Clearly, all the functions return in constant time when invoked with $n=1$. We
now analyze each function separately and assume that the claim inductively
holds for all the invocations.

  * •

$\textsc{EnumerateRootedTrees}(n)$ invokes
$\textsc{EnumerateForests}(n-1,n-1)$ that returns a forest $F$ of $n-1$
vertices in ${\cal O}(size(F))$ time, by the inductive assumption. It then
adds a root and its incident edges to return a tree $T$. Therefore, it takes
time ${\cal O}(size(T))$ to return a tree $T$.

  * •

$\textsc{EnumerateForests}(n,m)$ needs only one invocation of
$\textsc{EnumerateForests}(n,m^{\prime},\mu)$ to return the forest $F$
returned by the invocation. By the inductive assumption, this takes ${\cal
O}(size(F))$ time.

  * •

$\textsc{EnumerateForests}(n,m.\mu)$ makes one invocation of EnumerateForests
to get $lowForest$. By the inductive assumption, this takes ${\cal
O}(size(lowForest))$ time. It may possibly invoke
$\textsc{EnumerateMultisets}(\textsc{EnumerateRootedTrees})$ that takes also
linear time, i.e., ${\cal O}(size(highForest))$ by the inductive assumption
and Corollary 1. Then it combines the two forests in constant time for an
overall time complexity of ${\cal O}(size(highForest))+{\cal
O}(size(lowForest))$ which is ${\cal O}(size(F))$ where $F$ is the returned
forest.

$\square$

####  3.1.2 Unranking

In this part, our goal is to present an algorithm that, given two non-negative
integers $n,i$, returns the $i$-th tree in ${\mathcal{RT}}(n)$ (if such a tree
exists). For this purpose we need the sizes of the sets under consideration.
We now denote $rt_{n}\stackrel{{\scriptstyle
def}}{{=}}\left|{\mathcal{RT}}(n)\right|$, $f_{n}\stackrel{{\scriptstyle
def}}{{=}}\left|{\mathcal{F}}(n)\right|$, $f_{n,m}\stackrel{{\scriptstyle
def}}{{=}}\left|{\mathcal{F}}(n,m)\right|$,
$f^{\leq}_{n,m}\stackrel{{\scriptstyle
def}}{{=}}\left|{\mathcal{F}}^{\leq}(n,m)\right|$,
$f_{n,m,\mu}\stackrel{{\scriptstyle
def}}{{=}}\left|{\mathcal{F}}(n,m,\mu)\right|$, and
$f^{\leq}_{n,m,\mu}\stackrel{{\scriptstyle
def}}{{=}}\left|{\mathcal{F}}^{\leq}(n,m,\mu)\right|$. It follows immediately
from the definitions that

$\displaystyle rt_{n}$ $\displaystyle=$ $\displaystyle f_{n-1}$ (1)
$\displaystyle f_{n,m}$ $\displaystyle=$ $\displaystyle\sum_{\mu=1}^{\lfloor
n/m\rfloor}f_{n,m,\mu}$ (2) $\displaystyle f^{\leq}_{n,m}$ $\displaystyle=$
$\displaystyle\sum_{m^{\prime}=1}^{m}f_{n,m^{\prime}}$ (3) $\displaystyle
f^{\leq}_{n,m,\mu}$ $\displaystyle=$
$\displaystyle\sum_{\mu^{\prime}=1}^{\mu}f_{n,m,\mu^{\prime}}$ (4)
$\displaystyle f_{n}$ $\displaystyle=$ $\displaystyle f^{\leq}_{n,n}.$ (5)

Finally,

$f_{n,m,\mu}=CC^{rt_{m}}_{\mu}\cdot f^{\leq}_{n-\mu\cdot
m,\min\left\\{n-\mu\cdot m,m-1\right\\}}$ (6)

where $CC^{i}_{j}$ is the number multisets of $j$ elements of a set of $i$
elements, i.e. $CC^{i}_{j}={{i-1+j}\choose{j}}$. Indeed, a forest
$F\in{\mathcal{F}}_{n,m,\mu}$ is uniquely determined as the union of $\mu$
trees on $m$ vertices and a forest $F^{\prime}$ of $n-\mu\cdot m$ vertices
with trees of at most $\min\left\\{n-\mu\cdot m,m-1\right\\}$ vertices each.

Once this values are computed, we can use the unranking algorithms the pseudo
codes of which are given in Algorithm 5. The indices of the forests and trees
are zero-based and defined by the order that the objects would be returned by
the enumeration algorithms (Algorithm 3) presented in the previous section.

FindRootedTree$(n,i)$ invokes FindForest to get the $i$-th forest on $n$
vertices and attaches a root to it. In order to get the $i$-th forest $F$ on
$n$ vertices, FindForest first determines the size $m$ of a largest tree in
$F$ (Line 12), and the index $i^{\prime}$ of $F$ within the set
${\mathcal{F}}_{n,m}$ of these trees (Line 13). Then, it determines the number
$\mu$ of the largest trees of $F$ (Line 14) and the index $i^{\prime\prime}$
of $F$ in ${\mathcal{F}}_{n,m,\mu}$ (Line 15). Finally, with these numbers at
hand, it invokes $\textsc{FindForest}(n.m,\mu,i^{\prime\prime})$ to find the
forest $F$ within ${\mathcal{F}}_{n,m,\mu}$ (Line 16).

To get the $i$-th forest $F$ of ${\mathcal{F}}_{n,m,\mu}$, we partition
${\mathcal{F}}_{n,m,\mu}$ into equivalence classes according to the multiset
of the largest trees. The size of each equivalence class is
$j=f^{\leq}_{n-\mu\cdot m,\min(n-\mu\cdot m,m-1)}$, i.e. as the number of
forests on $n-\mu\cdot m$ vertices with largest tree size of at most $m-1$
(Line 21). We then determine the index of the relevant equivalence class and
the index of $F$ in its class (Lines 22 \- 23). With these numbers at hand, it
remains to find the multiset of trees that corresponds to the chosen
equivalence class (Line 27), the forest consisting of the remaining trees
(Line 26), and return their union (Line 28).

Algorithm 5 Unranking Rooted Trees and Forests

1:$0\leq i<rt_{n}$

2:Return the $i$-th tree of ${\mathcal{RT}}(n)$

3:function FindRootedTree($n,i$)

4: $F\leftarrow$ FindForest($n-1,i$)

5: return the tree obtained from $F$ by connecting all its roots to a new
root.

6:

7:$0\leq i<f_{n}$

8:Return the $i$-th forest of ${\mathcal{F}}(n)$

9:function FindForest($n,i$)

10: if $n=0$ then

11: return the empty forest

12: $m\leftarrow$ the smallest integer $m$ such that $f^{\leq}_{n,m}>i$

13: $i^{\prime}\leftarrow i-f^{\leq}_{n,m-1}$

14: $\mu\leftarrow$ the smallest integer $\mu$ such that
$f^{\leq}_{n,m,\mu}>i^{\prime}$

15: $i^{\prime\prime}\leftarrow i^{\prime}-f^{\leq}_{n,m,\mu-1}$

16: return FindForest($n,m,\mu,i^{\prime\prime}$)

17:

18:$0\leq i<f_{n,m,\mu}$

19:Return the $i$-th forest of ${\mathcal{F}}(n,m,\mu)$

20:function FindForest($n,m,\mu,i$)

21: $j\leftarrow f^{\leq}_{n-\mu\cdot m,\min(n-\mu\cdot m,m-1)}$

22: $lowForestIndex\leftarrow i\mod j$

23: $highForestIndex\leftarrow\lfloor i/j\rfloor$

24: $\triangleright$ The choice of the index and the order of forests
guarantee

25: $\triangleright$ that the size of the largest tree in $lowForest$ is at
most $m-1$

26: $lowForest\leftarrow$ FindForest($n-\mu\cdot m,lowForestIndex$)

27: $highForest\leftarrow$ the $i$-th multiset in the multi-subsets with $\mu$
elements of ${\mathcal{RT}}(m)$

28: return $highForest\cup lowForest$

We now analyze the time complexity of our algorithms. For this purpose, in the
following Lemma, we present a multiset unranking algorithm.

###### Lemma 1

Algorithm 6 returns the $i$-th multiset among the multisets consisting of $k$
elements from the integers $0$ to $n-1$ in ${\cal O}(k^{2}\log n)$ time.

Proof: We represent a multiset of $k$ elements by a sequence of length $k$ of
its elements in non-increasing order. We order the multisets in the
lexicographic order of their representative sequence. Consider the first
multiset $S$ in the lexicographic order whose largest element is $\ell$. We
observe that a multiset $S^{\prime}$ precedes $S$ in the lexicographic order
if and only if $S\subseteq[0,\ell-1]$. Therefore, the zero-based index of $S$
in the lexicographic order is the number of such multisets $S^{\prime}$, i.e.,
$CC^{\ell}_{k}$ 555As a quick validation, $CC^{1}_{k}={{1-1+k}\choose{k}}=1$
is the index of the first multiset whose largest element is $1$. Indeed, there
is exactly one set before it, which is the only set whose largest element is
zero.. Using this observation, the algorithm determines the largest element
$\ell$ of the sought set as the largest integer such that $CC^{\ell}_{k}\leq
i$ (Line 5). In order to determine the rest of the set, we recursively search
for a multiset $\bar{S}$ of $k-1$ elements from the set $[0,\ell]$ (Line 6).
In order to make the recursive invocation, it remains to determine the index
of $\bar{S}$ among the multisets of $k-1$ elements from $[0,\ell]$. Since the
index of the first such set is $CC^{\ell}_{k}$, the index of $\bar{S}$ is
$i-CC^{\ell}_{k}$.

We now proceed with the time complexity. Since $CC^{\ell}_{k}$ can be computed
in ${\cal O}(k)$ time, $\ell$ can be determined by a binary search on the $n$
possible values of $\ell$, i.e., in ${\cal O}(k\log n)$ time. Therefore,

$T(n,k)={\cal O}(k\log n+T(\ell+1,k-1))\leq{\cal O}(k\log n)+T(n,k-1)$

where $T(n,k)$ denotes the running time of finding a multiset with $k$
elements from $[0,n-1]$. We conclude that $T(n,k)$ is ${\cal O}(k^{2}~{}\log
n)$. $\square$

Algorithm 6 Unranking Multisets

1:Returns the $i$-th multiset among the multisets consisting of $k$ elements
from the integers $0$ to $n-1$

2:function FindMultiset($n,k,i$)

3: if $n=1$ or $k=0$ then

4: return the multiset consisting of $k$ zeros.

5: $\ell\leftarrow$ the largest integer such that $CC^{\ell}_{k}\leq i$

6: $\bar{S}\leftarrow\textsc{{FindMultiset}}(\ell+1,k-1,i-CC^{\ell}_{k})$

7: return $\left\\{\ell\right\\}\uplus\bar{S}$

In the following lemma we analyze the time and space complexity of
precomputing all the values (1) thru (6) needed to run Algorithm 5.

###### Lemma 2

For every positive integer $N$, all the values
$rt_{n},f_{n},f_{n,m},f^{\leq}_{n,m}$, $f_{n,m,\mu}$, $f^{\leq}_{n,m,\mu}$ and
$CC^{rt_{m}}_{\mu}$ where $n\in[N]$ and $\mu\cdot m\leq n$ can be computed in
${\cal O}(N^{2}\log N)$ time and space.

Proof: The required memory is dominated by the size of the $f_{n,m,\mu}$
values. For every $n,m$ pair the required memory is ${\cal O}(\frac{n}{m})$.
Therefore, the overall memory requirement is proportional to

$\sum_{n=1}^{N}\sum_{m=1}^{n}\frac{n}{m}=\sum_{n=1}^{N}n\sum_{m=1}^{n}\frac{1}{m}=\sum_{n=1}^{N}n\cdot{\cal
O}(\log n)={\cal O}(N^{2}\log N)$

We now consider the evaluation of the right hand sides. (1) and (5) can
clearly be computed in constant time. Every partial sum, in particular (3) and
(4) can be computed in constant time too. We note that
$CC^{rt_{m}}_{1}=rt_{m}$ and for $\mu>1$ $CC^{rt_{m}}_{\mu}$ can be computed
from $CC^{rt_{m}}_{\mu-1}$ in constant time (one multiplication, one division
and one addition). Then (6) can be computed in constant time. Therefore, the
computation time of these values is bounded by the memory size. We remain with
the computation of $\eqref{eqn:rec_f_nm}$. We observe that every $f_{n,m,\mu}$
value is accessed exactly once during the computation of these values.
Therefore, the computation time of $\eqref{eqn:rec_f_nm}$ is bounded by the
memory size too. $\square$

We are now ready to analyze the time complexity of the rooted tree unranking
algorithms which assume that the values mentioned in Lemma 2 are pre-computed.

###### Theorem 2

$\textsc{FindRootedTree}(n,i)$ returns the $i$-th tree of ${\mathcal{RT}}(n)$
in ${\cal O}(n^{3})$ time.

Proof: Let $T(n)$ (resp. $T^{\prime}(n,m,\mu)$) be the maximum time needed for
an invocation of $\textsc{FindForest}(n,i)$ (resp.
$\textsc{FindForest}(n,m,\mu,i)$) to return. An invocation
$\textsc{FindForest}(n,i)$ can find the value $m$ in ${\cal O}(\log n)$ time
by performing a binary search on the table $f^{\leq}_{n,m}$. Similarly, $\mu$
can be found in ${\cal O}(\log n/m)$ time by performing a binary search on all
$\lfloor n/m\rfloor$ possible values of $\mu$. It then invokes
$\textsc{FindForest}(n,m,\mu,i)$ and the rest of the operations take constant
time. We therefore have

$T(n)\leq{\cal O}(\log n)+\max_{m,\mu}T^{\prime}(n,m,\mu).$ (7)

An invocation of $\textsc{FindForest}(n,m,\mu,i))$, invokes
$\textsc{FindForest}(n-\mu\cdot m,lowForestIndex)$ which takes at most
$T(n-\mu\cdot m)$ time. It finds a multiset of $\mu$ integers from
$[0,rt_{m}]$ which takes $\mu^{2}\log rt_{m}$ time. Then it invokes $\mu$
times $\textsc{FindForest}(m-1,i^{\prime})$ for some $i^{\prime}$. Since the
other operations take constant time, we get:

$\displaystyle T^{\prime}(n,m,\mu)$ $\displaystyle=$ $\displaystyle
T(n-\mu\cdot m)+\mu\cdot T(m-1)+\mu^{2}\log rt_{m}$ $\displaystyle=$
$\displaystyle T(n-\mu\cdot m)+\mu\cdot T(m-1)+{\cal O}(\mu^{2}\cdot m\log m)$

where the second equality is due to the fact that the number of rooted trees
on $m$ vertices is at most $m!$. Indeed, a rooted tree on $n$ vertices can be
obtained by adding a leaf to any one of the vertices of a rooted tree on $n-1$
vertices, i.e., $rt_{m}\leq(m-1)rt_{m}$.

If $T(n)$ is ${\cal O}(n)$ then the claim is correct and we are done.
Otherwise, $T(n)$ is $\Omega(n)$. Therefore, $T(n-\mu\cdot m)+\mu T(m-1)\leq
T(n-\mu\cdot m+\mu(m-1))=T(n-\mu)$ for sufficiently large values of $n$ and
$m$. We proceed as follows:

$\displaystyle T^{\prime}(n,m,\mu)$ $\displaystyle=$ $\displaystyle
T(n-\mu\cdot m)+\mu\cdot T(m-1)+{\cal O}(\mu^{2}\cdot m\log m)$
$\displaystyle\leq$ $\displaystyle T(n-\mu)+{\cal O}(\mu^{2}\cdot m\log
m)<T(n-\mu)+{\cal O}((\mu\cdot m)(\mu\cdot\log m))$ $\displaystyle\leq$
$\displaystyle T(n-1)+{\cal O}(n^{2}).$

We now substitute in (7)

$T(n)\leq{\cal O}(\log n)+\max_{m,\mu}T^{\prime}(n,m,\mu)\leq{\cal O}(\log
n)+T(n-1)+{\cal O}(n^{2})=T(n-1)+{\cal O}(n^{2})$

concluding that $T(n)$ is ${\cal O}(n^{3})$. $\square$

###  3.2 Free Trees

A _free tree_ is an unlabeled undirected tree. In this section, unless stated
otherwise, a tree is a free tree. Let ${\mathcal{T}}(n)$ be the set of free
trees on $n$ vertices. Fact 1 states that a tree is either monocentroidal or
bicentroidal. Moreover, we note that the conditions on the weight stated in
Fact 1 constitute a dichotomy, thus characterize in which case a tree falls
in. Associate with a monocentroidal tree the rooted tree obtained by
designating its centroid as root. In this case, every subtree of the root has
at most $(n-1)/2$ vertices. With a bicentroidal tree we can associate the two
rooted trees obtained by the removal of the edge joining them. In this case,
Fact 1 implies that each of them has $n/2$ vertices (thus $n$ is even). We
enumerate all the free trees by first enumerating the monocentroidal ones,
i.e. those rooted trees on $n$ vertices with subtrees of at most $(n-1)/2$
vertices, and then all the bicentroidal ones, i.e., the pairs of subtrees of
at most $n/2$ vertices (see Algorithm 7). This technique, introduced in [19],
clearly guarantees that we generate all the (non-isomorphic) free trees.

Algorithm 7 Enumerating Free Trees

1:Lazily returns ${\mathcal{T}}(n)$

2:function EnumerateFreeTrees($n$)

3: ${\cal T}\leftarrow\emptyset$

4: for $F\in~{}$FindForest($n-1,\lfloor\frac{n-1}{2}\rfloor$) do

5: $T\leftarrow$ the tree obtained from $F$ by connecting all its roots to a
new root.

6: yield $T$

7: if $n\equiv 0\mod 2$ then

8: for each pair $\left\\{T_{1},T_{2}\right\\}\in{{\mathcal{RT}}(n/2)\choose
2}$ do

9: $T\leftarrow$ the tree obtained by joining the roots of $T_{1}$ and $T_{2}$

10: yield $T$

11: return

12:

We now proceed with unranking. Let $t_{n}=\left|{\mathcal{T}}(n)\right|$. Let
also, for $i\in\left\\{1,2\right\\}$, $t^{(i)}_{n}$ be the number of trees on
$n$ vertices with $i$ centroids. Since a tree has either one or two centroids,
we have $t_{n}=t^{(1)}_{n}+t^{(2)}_{n}$. Moreover,

$\displaystyle t^{(1)}_{n}$ $\displaystyle=$ $\displaystyle
f^{\leq}_{n-1,\lfloor(n-1)/2\rfloor},~{}\textrm{and}$ $\displaystyle
t^{(2)}_{n}$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}CC^{rt_{n/2}}_{2}&\textrm{if~{}}n\equiv
0\mod 2\\\ 0&\textrm{otherwise}.\end{array}\right.$

###### Observation 2

$t^{(2)}_{n}$ can be computed in constant time from $rt_{n/2}$.

Therefore, all the values $t^{(i)}_{n}$ can be computed in ${\cal O}(N^{2}\log
N)$ time together with the values in Section 3.1.

Algorithm 8 Unranking Free Trees

1:$0\leq i<t_{n}$

2:Return the $i$-th tree of ${\mathcal{T}}(n)$

3:function FindFreeTree($n,i$)

4: if $n\equiv 0\mod 2$ and $i\geq t^{(1)}_{n}$ then

5: $i\leftarrow i-t^{(1)}_{n}$

6: $\left\\{T_{1},T_{2}\right\\}\leftarrow$ the $i$-th multiset of two rooted
trees from ${\mathcal{RT}}(n/2)$

7: return the tree obtained by connecting the roots of $T_{1}$ and $T_{2}$

8: else

9: $\triangleright$ The order of forests and the value of $i$ guarantees

10: $\triangleright$ that the size of the largest subtree is at most $(n-1)/2$

11: return FindRootedTree(n,i)

12:

##  4 Weighted Trees

In [2], the authors show that Fact 1 is valid also for weighted trees with
strictly positive weights. Since we will be dealing with weighted trees where
we allow zero weights as well, in Section 4.1, we extend Fact 1 to all non-
negatively weighted trees, generalizing the result in [2]. In Theorem 3, we
show that in this case the number of centroids is not limited to two; however
they still enjoy some nice properties. On the other hand, Fact 1 holds for the
so-called central centroids. Since, due to zero weights, the number of trees
of total weight $n$ is unbounded, subsequently, we focus on the so-called
canonical weighted trees in which we bound the number of zero-weight vertices
in a certain way. In Corollary 2 we show that the number of centroids in
canonical weighted trees is again limited, this time by three. In Section 4.2,
we explain how centroid-rooted canonical weighted trees are used to generate
(non-isomorphic) weighted trees.

###  4.1 Structural Properties

Weighted Trees and Centroids: A _weighted tree_ is a pair $(T,w)$ where $T$ is
a tree and $w$ is a non-negative integral weight function on its vertices such
that at least one vertex has strictly positive weight. We extend the weight
function $w$ to sets of vertices naturally, so that for every subset $U$ of
the vertices of $T$, we have $w(U)\stackrel{{\scriptstyle def}}{{=}}\sum_{u\in
U}w(u)$. Moreover, we denote $w(T)\stackrel{{\scriptstyle
def}}{{=}}w(V(T))>0$.

Let $(T,w)$ be a weighted tree of weight $W$ and $v$ a vertex of $T$. A
subtree $T^{\prime}$ of $v$ in $T$ is _heaviest_ if its weight is maximum
among all subtrees of $v$ in $T$. We will term this weight as the _heaviest
subtree weight_ of $v$ in $(T,w)$ and denote it by
$\operatorname{hs}_{T,w}(v)$ or simply $\operatorname{hs}(v)$ when $(T,w)$ is
clear from the context. In the degenerated case where $v$ is the only vertex
of $T$, i.e., there is no heaviest subtree, $\operatorname{hs}(v)$ is zero. A
_centroid_ of $(T,w)$ is a vertex with minimum heaviest subtree weight in
$(T,w)$.

The following notions are frequently used in the proof of Theorem 3. For
brevity, we denote a weighted tree $(T,w)$ simply as $T$ and we assume that
the weight function is $w$. Given a non-trivial path $P$ in a tree $T$ and a
vertex $v$ of $P$, denote by $T_{v,P}$ (or $T_{v}$ if no ambiguity arises) the
maximal subtree of $T$ containing $v$, but no other vertex of $P$. We denote
by $T_{P}$ the maximal subtree of $T$ that contains all the internal vertices
of $P$ but not its endpoints (see Figure 1). From these definitions it follows
that if $P$ is a non-trivial $(a-b)$-path (i.e., $a\neq b$) then
$\left\\{V(T_{a}),V(T_{b}),V(T_{P})\right\\}$ is a partition of $V(T)$.
Therefore, $w(T)=w(T_{a})+w(T_{b})+w(T_{P})$. Note that if $P$ has no internal
vertices then $T_{P}$ is empty.

Figure 1: The partition of a tree $T$ implied by a non-trivial $a$-$b$ path
$P$

###### Theorem 3

Let $(T,w)$ be a weighted tree with $w(T)=n$. Then all the centroids of $T$
are located on a path $P$ with endpoints $c_{1}$ and $c_{2}$ with
$w(T_{P})=0$, that is, the weight of the maximal subtree of $T$ containing
$P\setminus\\{c_{1},c_{2}\\}$ is zero. Moreover, if $P$ is non-trivial then
$\operatorname{hs}(c_{1})=\operatorname{hs}(c_{2})=w(T_{c_{1},P})=w(T_{c_{2},P})=n/2$;
otherwise $P$ is a trivial path consisting of one vertex $c$ where
$hs(c)<n/2$.

Proof: The claim trivially holds for a tree with one vertex $v$ since
$\operatorname{hs}(v)=0<n/2$. Let $(T,w)$ be a weighted tree on at least two
vertices. We consider two disjoint and complementing cases:

  * Case 1:

$T$ has exactly one centroid $c$: Then the unique centroid is on a trivial
path $P=c$. In this case $T_{P}$ is empty, thus $w(T_{P})=0$.
Since $T$ has at least two vertices, $c$ has at least one heaviest subtree.
Without loss of generality, let $T_{1}$ be a heaviest subtree of $c$ and
assume by way of contradiction that $w(T_{1})=\operatorname{hs}(c)\geq n/2$.
Then $w(T\setminus T_{1})\leq n/2\leq w(T_{1})$. Consider the vertex $v$ of
$T_{1}$ that is adjacent to $c$. The subtrees of $v$ are $T\setminus T_{1}$
and other subtrees contained in $T_{1}-v$. Clearly, for a subtree $T_{i}$
contained in $T_{1}-v$ we have $w(T_{i})\leq w(T_{1})$. Then
$\operatorname{hs}(v)\leq w(T_{1})=\operatorname{hs}(c)$, contradicting the
fact that $c$ is the unique centroid of $T$.

  * Case 2

$T$ has at least two centroids: Let $c_{1},c_{2}$ be two distinct centroids
farthest from each other, i.e. there is no other centroid $c_{3}$ such that
$c_{1}$ (resp. $c_{2}$) is on the path between $c_{2}$ (resp. $c_{1}$) and
$c_{3}$. Without loss of generality, let $T_{1}$ be a heaviest subtree of
$c_{1}$. If $w(T_{1})=\operatorname{hs}(c_{1})=0$, then all the subtrees of
$c_{1}$ have zero weight. Thus $w(c_{1})=w(T)=n>0$ and $c_{1}$ is the unique
centroid of $T$, a contradiction. Therefore, $w(T_{1})>0$, and in particular
$T_{1}$ is not empty. Let $v$ be the vertex of $T_{1}$ adjacent to $c_{1}$.
Consult Figure 2 for this discussion. We will now show that $c_{2}$ is in
$T_{1}$.

Figure 2: Showing that $c_{2}$ is in $T_{1}$

Suppose that $c_{2}$ is not in $T_{1}$ and let $P$ be the path between $v$ and
$c_{2}$. The path $P$ partitions the vertex set of $T$ into subtrees
$T_{v}=T_{1},T_{c_{2}}$ and $T_{P}$. Since $c_{2}$ is a centroid, we have

$w(T_{1})=\operatorname{hs}(c_{1})=\operatorname{hs}(c_{2})\geq
w(T_{1})+w(T_{P})\geq w(T_{1}).$

implying that the inequalities hold by equality. Then the last equality
implies $w(T_{P})=0$. By the choice of $c_{1}$ and $c_{2}$, $v$ is not a
centroid. Therefore, $\operatorname{hs}(v)>\operatorname{hs}(c_{1})=w(T_{1})$.
All the subtrees of $v$ except $T_{P}\cup T_{c_{2}}$ are contained in $T_{1}$.
Therefore, $v$ has a unique heaviest subtree, namely $T_{P}\cup T_{c_{2}}$.
Therefore,

$w(T_{1})<\operatorname{hs}(v)=w(T_{P})+w(T_{c_{2}})=w(T_{c_{2}}).$

On the other hand, we have

$w(T_{1})=\operatorname{hs}(c_{1})\geq w(T_{c_{2}})$

which contradicts the previous inequality. Therefore, $c_{2}$ is in $T_{1}$
which must be the unique subtree of $c_{1}$. By symmetry, $c_{1}$ is in the
unique subtree $T_{2}$ of $c_{1}$.

In the rest of the proof we consider the path $P^{\prime}$ between $c_{1}$ and
$c_{2}$ that partitions $T$ into subtrees $T_{c_{1}},T_{c_{2}}$ and
$T_{P^{\prime}}$, and we show that the statement holds for $P^{\prime}$. Since
$c_{2}$ is in the heaviest subtree of $c_{1}$ we have
$\operatorname{hs}(c_{1})=w(T_{P^{\prime}})+w(T_{c_{2}})$ and symmetrically,
$\operatorname{hs}(c_{2})=w(T_{P^{\prime}})+w(T_{c_{1}})$. Since both vertices
are centroids, we have $\operatorname{hs}(c_{1})=\operatorname{hs}(c_{2})$
which implies $w(T_{c_{1}})=w(T_{c_{2}})$.

We now show that $w(T_{P^{\prime}})=0$. Suppose that $w(T_{P^{\prime}})>0$.
Then $P^{\prime}$ contains at least one internal vertex $u$ such that
$w(T_{u,P^{\prime}})>0$. Note also that $w(T_{c_{1}})>0$ since otherwise
$c_{1}$ is not a centroid. Then

$\displaystyle\operatorname{hs}(u)$ $\displaystyle\leq$
$\displaystyle\max\left\\{w(T_{c_{1}})+w(T_{P^{\prime}})-w(T_{u}),w(T_{u})\right\\}$
$\displaystyle<$
$\displaystyle\max\left\\{w(T_{c_{1}})+w(T_{P^{\prime}}),w(T_{c_{1}})+w(T_{u})\right\\}$
$\displaystyle=$ $\displaystyle
w(T_{c_{1}})+\max\left\\{w(T_{P^{\prime}}),w(T_{u})\right\\}=w(T_{c_{1}})+w(T_{P^{\prime}})=\operatorname{hs}(c_{2})$

contradicting the fact that $c_{2}$ is a centroid. Therefore,
$w(T_{P^{\prime}})=0$. We conclude that

$\operatorname{hs}(c_{1})=\operatorname{hs}(c_{2})=w(T_{c_{1}})=w(T_{c_{2}})=n/2$

as claimed.

Let $u$ be an internal vertex of $P^{\prime}$. Then
$\operatorname{hs}(u)=\max\left\\{w(T_{c_{1}}),w(T_{c_{2}}\right\\}=n/2$,
implying that $u$ is a centroid. Therefore all the vertices of $P^{\prime}$
are centroids. We now show that there are no other centroids in $T$. There is
no centroid in $T_{c_{1}}$ (resp. $T_{c_{2}}$) except $c_{1}$ (resp. $c_{2}$)
by the way $c_{1}$ and $c_{2}$ are chosen. We remain with the vertices of
$T_{P^{\prime}}$ that are not in $P^{\prime}$. Let $u^{\prime}$ be a vertex of
$T_{P^{\prime}}\setminus P^{\prime}$. Then
$\operatorname{hs}(u^{\prime})=w(T_{c_{1}})+w(T_{c_{2}})=n>n/2=\operatorname{hs}(c_{1})$,
thus $u^{\prime}$ is not a centroid.

$\square$

The notion of isomorphism extends naturally to weighted graphs in the
following way. We say that two vertex-weighted graphs (resp. digraphs) are
_isomorphic_ if there is a bijection between their vertex sets that preserves
both adjacencies (resp. directed adjacencies) and weights. Our objective is to
generate non-isomorphic free weighted trees. We will achieve this goal by
establishing a one-to-one mapping between the set of free weighted trees and
the set of rooted weighted trees in Lemma 3. To this end, we follow the
technique employed in [19] that makes use of the centroids. Instead, we use
the notion of central centroids defined below.

###### Definition 1

(Central centroid:) A centroid is _central_ if it is a center of the path of
centroids.

Clearly, a weighted tree $T$ has one or two central centroids. The following
definition assumes a predefined total order $\prec$ on the set of weighted
rooted trees.

###### Definition 2

(Centroid-rooted tree:) The _centroid-rooted tree_ $\overrightarrow{T}$ of the
weighted tree $T$ is the rooted tree obtained from $T$ by designating a root
$r$ as follows:

  * •

If $T$ has exactly one central centroid $c$ then $r=c$.

  * •

Otherwise, $T$ has two adjacent central centroids. Let $T_{1}$ and $T_{2}$ be
the rooted subtrees of $T$ obtained by the removal of the edge $c_{1}c_{2}$,
where $c_{i}\in V(T_{i})$ and $c_{i}$ is the root of $T_{i}$ for
$i\in\left\\{1,2\right\\}$. If $T_{1}$ and $T_{2}$ are isomorphic, then one of
$c_{1},c_{2}$ is arbitrarily designated as $r$. If $T_{1}$ and $T_{2}$ are
non-isomorphic, then designate $r=c_{1}$ if $T_{1}\prec T_{2}$ and $r=c_{2}$
otherwise.

An illustration of centroid-rooted trees is given in Figure 3 for a weighted
block tree, once block trees are introduced in Section 5.

###### Lemma 3

Two weighted trees $T$ and $T^{\prime}$ are isomorphic if and only if
$\overrightarrow{T}$ and $\overrightarrow{T^{\prime}}$ are isomorphic.

Proof: ($\Leftarrow$) Suppose that $\overrightarrow{T}$ and
$\overrightarrow{T^{\prime}}$ are isomorphic. Since $T$ and $T^{\prime}$ are
their respective underlying graphs, $T$ and $T^{\prime}$ are isomorphic.

($\Rightarrow$) Conversely, suppose that $T$ and $T^{\prime}$ are isomorphic,
and let $f:V(T)\to V(T^{\prime})$ an adjacency-preserving bijection. Then $f$
preserves the non-arcs of $\overrightarrow{T}$. As for the arcs, they are also
preserved except possibly their direction. It remains to show that $f$
preserves the directions of the arcs. We observe that $f$ preserves the
subtrees of a vertex, and in particular their set of weights. Thus $f$
preserves the $\operatorname{hs}$ values, i.e.,
$\operatorname{hs}_{T^{\prime}}(f(v))=\operatorname{hs}_{T}(v)$. Therefore,
$f$ preserves the set of vertices attaining the minimum of
$\operatorname{hs}$, i.e. the path of centroids. We conclude that $f$
preserves the set of central centroids. By Theorem 3, a weighted tree has
either one or two central centroids.

  * •

Case 1: If $T$ has exactly one central centroid $c$ then $T^{\prime}$ has
exactly one central centroid $c^{\prime}$ and $c^{\prime}=f(c)$. Then the
edges of $\overrightarrow{T}$ and $\overrightarrow{T^{\prime}}$ are directed
towards $c$ and $c^{\prime}$, respectively. Therefore, $f$ preserves the
directions of the arcs.

  * •

Case 2: If $T$ has two central centroids $c_{1}$ and $c_{2}$ then $T^{\prime}$
has two central centroids $c^{\prime}_{1}=f(c_{1})$ and
$c^{\prime}_{2}=f(c_{2})$. Assume, without loss of generality, that the arc
between $c_{1}$ and $c_{2}$ is directed from $c_{1}$ to $c_{2}$. Let also
$T_{1},T_{2}$ (respectively $T^{\prime}_{1},T^{\prime}_{2}$) be the two rooted
subtrees of $T$ (respectively $T^{\prime})$ obtained as in Definition 2. Since
the edges of $T_{i}$ are directed towards $c_{i}$ and the edges of
$T^{\prime}_{i}$ are directed towards $c^{\prime}_{i}=f(c_{i})$, for
$i\in\left\\{1,2\right\\}$ $f$ preserves the directions of all the arcs except
possibly the arc between $c_{1}$ and $c_{2}$, that might be directed from
$c^{\prime}_{2}$ to $c^{\prime}_{1}$. If $T_{1}$ and $T_{2}$ are isomorphic
that we define a new bijection $f^{\prime}$ that coincides with $f$
everywhere, except that $f^{\prime}(c_{1})=c^{\prime}_{2}$ and
$f^{\prime}(c_{2})=c_{1}$. Then $f^{\prime}$ is an isomorphism from
$\overrightarrow{T}$ to $\overrightarrow{T^{\prime}}$. Otherwise, since
$c_{1}c_{2}$ is directed from $c_{1}$ to $c_{2}$ in $\overrightarrow{T}$ we
have $T_{1}\prec T_{2}$. Then $T^{\prime}_{1}\prec T^{\prime}_{2}$ since $f$
preserves subtrees. This contradicts the assumption that $c_{1}c_{2}$ is
directed from $c_{2}$ to $c_{1}$ in $\overrightarrow{T^{\prime}}$.

$\square$

It is noted that, since we allow for zero weights, the number of vertices of a
weighted tree of a given weight $n$ is unbounded. Therefore, the following
definition is introduced, partitioning the set of weighted trees of a given
weight $n$ into a finite set of equivalence classes, by assigning a canonical
representative to each equivalence class. The idea is to use these canonical
representations to enumerate non-isomorphic weighted tree.

###### Definition 3

(Canonical weighted tree:) A weighted tree $(T,w)$ is _canonical_ if the set
of zero weight vertices of $T$ constitutes an independent set and every leaf
of $T$ has positive weight.

Given a weighted tree, we can obtain a unique canonical tree of the same
weight by first contracting every subtree consisting of zero-weight vertices
to a single vertex and then removing all zero-weight leaves. For weighted
trees, we have the following corollary that is based on Theorem 3.

###### Corollary 2

If $(T,w)$ is a canonical weighted tree then exactly one of the following
holds.

  1. 1.

$T$ has exactly one centroid $c$ and $\operatorname{hs}(c)<\frac{n}{2}$.

  2. 2.

$T$ has exactly two centroids $c_{1},c_{2}$ which are adjacent and the removal
of the edge $c_{1}c_{2}$ partitions $T$ into two subtrees $T_{1},T_{2}$ of
weight $\frac{n}{2}$ each. Moreover, every proper subtree of $T_{1}$ (resp.
$T_{2}$) has weight at most $\frac{n}{2}-1$.

  3. 3.

$T$ has exactly three centroids with a unique central centroid $c$ with
$w(c)=0$ whose removal partitions $T$ into two subtrees of weight
$\frac{n}{2}$ each.

Proof: Let $(T,w)$ be a canonical weighted tree and $P$ the path of the
centroids of $(T,w)$. Clearly, the stated cases are mutually-disjoint.

  1. 1.

If $(T,w)$ has exactly one centroid then the first case follows from Theorem
3.

  2. 2.

If $(T,w)$ has exactly two centroids $c_{1},c_{2}$ then they are clearly
adjacent and the removal of the edge $c_{1}c_{2}$ partitions $T$ into two
subtrees $T_{1},T_{2}$ each of which has weight equal to $n/2$ by Theorem 3.
Suppose that $T_{1}$ has a proper subtree $T^{\prime}$ of weight
$\frac{n}{2}$. Then $w(c_{1})=0$ and the vertex of $T^{\prime}$ adjacent to
$c_{1}$ would be a (third) centroid.

  3. 3.

If $(T,w)$ has at least three centroids, we recall that $w(P)=0$ by Theorem 3.
In particular, all the internal vertices of $P$ have zero weight. Since no
pair of zero-weight vertices is adjacent, $P$ has exactly one internal vertex
$v$ and $w(v)=0$. Moreover, since $w(P)=0$, $v$ has no adjacent vertices
except the endpoints, say $c_{1},c_{2}$ of $P$. Since $c_{1}$ and $c_{2}$ are
adjacent to $v$ we have $w(c_{1})\neq 0$ and $w(c_{2})\neq 0$. By Theorem 3,
we have $\operatorname{hs}(c_{1})=\operatorname{hs}(c_{2})=n/2$. Therefore,
each one of the subtrees of $v$ has weight of exactly $n/2$, since otherwise
either $\operatorname{hs}(c_{1})$ or $\operatorname{hs}(c_{2})$ would exceed
$n/2$, contradicting Theorem 3.

$\square$

We extend the notion of canonical (weighted) trees to directed weighted trees
in a natural way: a directed weighted tree is canonical if its underlying
weighted tree is canonical. Now, we use the following consequence of Lemma 3
and Corollary 2 to enumerate non-isomorphic weighted trees.

###### Corollary 3

Two canonical weighted trees $T$ and $T^{\prime}$ are isomorphic if and only
if $\overrightarrow{T}$ and $\overrightarrow{T^{\prime}}$ are isomorphic and
both are canonical.

Therefore, the generation of canonical weighted trees is equivalent to the
generation of canonical centroid-rooted trees. In the rest of this section, we
provide the implementation details of such a generation.

###  4.2 Generation algorithms for weighted trees

We now describe the modifications to the algorithms from Section 3 needed to
generate weighted trees. For this purpose, we first consider positive-weighted
trees and then proceed with weighted trees.

Positive-weighted trees: In order to extend the rooted tree generation
algorithms to weighted trees (with no zero weights allowed), it is sufficient
to modify the parts of the algorithms that generate vertices, i.e., the root
of a tree. Specifically, we have to modify the first functions of both
Algorithm 3 and Algorithm 5 in such a way that, instead of connecting a root
to a forest of $n-1$ vertices, they consider each of the possible weights
$w\in[n]$ for the root and connect it to a forest of weight $n-w$.

As for rooted trees, since Fact 1 holds also for positive-weighted trees,
again, it is sufficient to modify Algorithm 7 as follows: when generating the
root of a mono-centroidal tree, it tries all the $w\in[n]$ and then generates
a forest of weight $n-w$ with maximum subtree-weight of at most $n/2-1$.

As our goal is to derive a single generic algorithm that can generate both
unweighted and positive-weighted trees, we can generalize as follows. Define
two parameters, say $minw$ and $maxw$ and restrict the possible weights to
$w\in[minw..maxw]$ instead of $w\in[n]$. Clearly, setting $minw=maxw=1$
corresponds to unweighted trees, and $minw=1$, $max_{w}=n$ corresponds to
positive weighted trees.

Canonical weighted trees: Extending the above approach to weighted trees (that
allow zero weights) seems, at first glance, to be as simple as setting
$minw=0$. However, zero-weight vertices introduce two problems: a) enabling
the possibility of three centroids, and b) disabling the possibility of
adjacent zero-weight vertices. The solution of the first problem can be easily
derived from Corollary 2. In this part we will address the second problem.
First, consider rooted trees. If a root vertex has zero weight then none of
its children may have zero weight. A possible solution is to divide vertices
into two sets, say, ”green” and ”white” vertices where ”green” stands for
”positive-weighted” and ”white” stands for ”zero-weight”. The children of
white vertices should be all green, and the children of green vertices may be
either green or white. To generalize this approach, for each color $c$ define
three parameters. Namely, the minimum and maximum vertex weights
$minw(c),maxw(c)$, and a set $chld(c)$ of possible colors for its children. In
the sequel, the color of a rooted tree is the color of its root, and the
color-set $cs(F)$ of a forest $F$ is the set of colors of its trees. In order
to generate a tree of a certain color $c$, one has to try all the possible
weights $w\in[minw(c)..maxw(c)]$, then one has to generate all the forests $F$
of weight $n-w$ with $cs(F)\subseteq cs_{c}$. Table 1 shows the setting for
weighted and unweighted trees. The set of weighted trees is the union of green
and white trees whose parameters are defined as mentioned above. The set of
unweighted trees is exactly the set of gray trees. Indeed, the root $r$ of a
gray tree is gray and thus $w(r)\in[1..1]$, i.e., $w(r)=1$. Moreover, every
subtree of $r$ is gray. This inductively defines the set of unweighted trees.

$c$ | $minw(c)$ | $maxw(c)$ | $chld(c)$
---|---|---|---
Gray | 1 | 1 | { Gray }
Green | 1 | $\infty$ | {White, Green}
White | 0 | 0 | { Green }
Table 1: The color parameter values used to construct weighted and unweighted
trees.

##  5 Weighted Block Trees

In this section, we extend the previous notions and algorithms to weighted
block trees. This allows us to enumerate and generate u.a.r. block graphs
which form a subclass of chordal graphs where each block consists of a
complete graph.

###  5.1 Structural Properties

A _block_ of a graph is a maximal biconnected component of it. The _block
tree_ (a.k.a. _block-cutpoint_ tree [10], a.k.a _super graph_ [6]) of a
connected graph $G$ is a tree each vertex of which is associated either with a
cut vertex of $G$ or with a block of $G$. We will refer to a vertex associated
with a block as a _block vertex_ and name it after the block it is associated
with. With a slight abuse of terminology, we refer as a cut vertex to a vertex
(of the block tree) associated with a cut vertex of $G$, and name it after its
associated cut vertex (in $G$). A cut vertex $v$ is adjacent (in the block
tree) to a block vertex $B$ if and only if $v$ is a vertex of $B$ (in $G$).
Cut vertices (resp. block vertices) are pairwise non-adjacent in a block-tree.

It follows from the above definitions that the degree of a cut vertex (in the
block tree) is the number of blocks to which it belongs (in the graph). Since
a cut-vertex belongs to at least two blocks it cannot be (associated with) a
leaf (of the block tree). Stated differently, all the leaves of a block tree
are associated with blocks. It also follows from the definitions that block
vertices and cut-vertices constitute the (unique) bipartition of the block
tree. Therefore, the leaves of the block tree are in one part of the
bipartition. In other words, in any bi-coloring of the block tree, the set of
leaves is monochromatic. Equivalently, the distance between any pair of leaves
is even. In fact this is one characterization of block trees [10].

An example of the block cut-vertex tree and their centroids is given in Figure
3.

Figure 3:  A graph $G$, its block tree $T$, its weighted block tree $(T,w)$
and its centroid-rooted tree. The graph $G$ depicted at the top-left has three
cut-vertices, namely $a,b$ and $c$. It has four blocks which are the three
triangles $A,B,C$ and the $K_{2}$ induced by $\left\\{a,b\right\\}$. Every cut
vertex of $G$ is in exactly two blocks and every such block contains at most
two cut-vertices. Thus we obtain the block cut-vertex tree $T$ which is the
path depicted at the top-right. The block $\left\\{a,b\right\\}$ contains only
cut-vertices, the triangle $B$ contains two cut-vertices (namely $b$ and $c$)
and each of the other two triangles contains one cut-vertex each. Therefore,
the number of remaining vertices in these blocks are 0, 1, 2 and 2,
respectively. These weights are shown at the bottom-right together with the
weights of the cut-vertices which are all one. The sum of the weights is
therefore $0+1+2+2+3\cdot 1=8$ which is equal to the number of vertices of
$G$. The centroids of $(T,w)$ are $b$ and $B$. The removal of the edge between
them separates $(T,w)$ into two subtrees of weight 4, each. At the bottom-
right is depicted the centroid-rooted tree in which all the edges are directed
towards these centroids. As our example lacks the definition a total order
$\prec$, the orientation of the edge between the two centroids is chosen
arbitrarily.

###### Definition 4

(Weighted block tree:) A _weighted block tree_ is a weighted tree $T$ with the
following weight function. The weight of a cut vertex is 1 and the weight of a
block vertex is the number of (possibly zero) vertices in the block that are
not cut vertices.

It follows from the definition that if $T$ is the block tree of a graph $G$,
then every vertex of $G$ contributes exactly 1 to $w(T)$, i.e.,
$w(T)=\left|V(G)\right|$. This is because blocks intersect only at cut
vertices. We now note that a block tree is canonical: a) zero weight vertices,
being blocks are pairwise non-adjacent, b) the weight of a leaf cannot be zero
since a block contains at least two vertices and a leaf block contains at most
one cut-vertex.

We now restate Corollary 2 for the special case of block trees.

###### Corollary 4

If $T$ is the weighted block tree of a graph $G$ on $n$ vertices exactly one
of the following holds.

  1. 1.

$T$ has exactly one centroid $c$ and $\operatorname{hs}(c)<\frac{n}{2}$.

  2. 2.

$T$ has exactly two centroids $v,B$ where $v\in B$ is a cut vertex of $G$ and
the removal of the edge $vB$ partitions $T$ into two subtrees $T_{1},T_{2}$ of
weight $\frac{n}{2}$ each. Moreover, every proper subtree of $T_{1}$ (resp.
$T_{2}$) has weight at most $\frac{n}{2}-1$.

  3. 3.

$T$ contains a zero-weight (block) vertex $B$ which is the unique central
centroid of $T$ whose removal partitions $T$ into two subtrees of weight
$\frac{n}{2}$ each. Therefore, the block $B$ is a $K_{2}$.

Let $f:V(G)\to V(G^{\prime})$ be an isomorphism. Since $f$ preserves
adjacencies, it preserves paths. Therefore, it preserves cut-vertices and
connected components. On the other hand, $f$ preserves induced subgraphs,
i.e., for any subset $U$ of $V(G)$, $G^{\prime}[f(U)]$ is isomorphic to
$G[U]$. Being maximal subgraphs that do not contain cut-vertices, $f$
preserves blocks. It also preserves the memberships of cut-vertices in blocks.
These facts imply an isomorphism from the block tree of $G$ to the block tree
of $G^{\prime}$. Since the sizes of the blocks and the number of cut-vertices
in a block are preserved we get the following observation.

###### Observation 3

If two graphs $G$ and $G^{\prime}$ are isomorphic then their weighted block
trees are isomorphic.

###### Definition 5

Let $T$ be the block tree of a graph $G$ and $T^{\prime}$ a subtree of $T$. We
denote by $G[T^{\prime}]$ the subgraph of $G$ induced by the union of all
blocks in $T^{\prime}$. Let $T_{1},\ldots,T_{k}$ be the subtrees of a (cut or
block) vertex of $T$. We term the subgraphs $G[T_{1}],\ldots,G[T_{k}]$ as the
_subgraphs_ defined by this vertex.

Block Graphs: The block graph $B(G)$ of a given graph $G$ is the intersection
graph of its blocks. A graph is a block graph if it is isomorphic to $B(G)$
for some graph $G$.

###### Theorem 4

There is a one-to-one correspondence between the class of connected block
graphs on $n$ vertices and the class of weighted block-trees of weight $n$.

Proof: Let $\operatorname{bcw}(G)$ be the weighted block tree of a connected
block graph $G$. We have to show that this mapping is a bijection, i.e., (a)
for every weighted block tree $(T,w)$, there exists a block graph $G$ on
$w(T)$ vertices such that $\operatorname{bcw}(G)=(T,w)$ and (b) if
$(T,w)=\operatorname{bcw}(G)=\operatorname{bcw}(G^{\prime})$ for two block
graphs $G$ and $G^{\prime}$ then these graphs are isomorphic.

It is well-known that a graph is a block graph if and only if its blocks are
cliques [9].

(a) Let $(T,w)$ be a weighted block tree. We construct a block graph $G$ as
follows. For every vertex $B$ of $T$ that must correspond to a block (i.e.,
one that is at even distance from the leaves) construct a clique on
$w(B)+d_{T}(B)$ vertices. For every other vertex $v$ of $T$ (that must
correspond to a cut-vertex) choose a vertex (that is yet not chosen) from each
one of the $d_{T}(v)$ blocks adjacent to $v$ in $T$ and identify them. Note
that the number of vertices created initially is
$\sum_{B}(w(B)+d_{T}(B))=\sum_{B}w(B)+\sum_{B}d_{T}(B)=\sum_{B}w(B)+\sum_{v}d_{T}(v)$
where the last equality holds because $(B,v)$ is a bipartition of $T$. At
every identification operation $d_{T}(v)$ vertices are replaced by a single
vertex, i.e., the number of vertices drops by $d_{T}(v)-1$. Therefore, the
number of vertices of $G$ is
$\sum_{B}w(B)+\sum_{v}d_{T}(v)-\sum_{v}(d_{T}(v)-1)=\sum_{B}w(B)+\sum_{v}1=w(T)$.

(b) Let $B_{1},\ldots,B_{k}$ be the blocks of $G$, and let
$B^{\prime}_{1},\ldots,B^{\prime}_{k}$ be the blocks of $G^{\prime}$
corresponding to the same block vertices in $T$ in the same order. Similarly,
let $v_{1},\ldots,v_{\ell}$ be the cut-vertices of $G$, and let
$v^{\prime}_{1},\ldots,v^{\prime}_{\ell}$ be the cut-vertices of $G^{\prime}$
corresponding to the same vertices in $T$ in the same order. The blocks
$B_{i}$ and $B^{\prime}_{i}$ have the same number of vertices (i.e.,
$w(B_{i})+d_{T}(B_{i})$), for every $i\in[k]$. Therefore, $B_{i}$ and
$B^{\prime}_{i}$ are cliques of the same size. Let $f:V(G)\to V(G^{\prime})$
such that $f(v_{j})=v^{\prime}_{j}$ for every $j\in[\ell]$, and for every
$i\in[k]$, the $w(B_{i})=w(B^{\prime}_{i})$ non-cut-vertices of $B_{i}$ are
mapped to the non-cut-vertices of $B^{\prime}_{i}$ arbitrarily. The mapping
$f^{\prime}$ is clearly a bijection. We note that $N_{G}(v)=\bigcup_{v\ni
B_{i}}B_{i}$, i.e., the union of the blocks that contain $v$. For a non-cut-
vertex, this neighborhood is clearly preserved by $f^{\prime}$. Let $v_{j}$ be
a cut-vertex of $G$ that is contained in blocks $B_{j_{1}},\ldots$. Then
$v_{j}$ is adjacent to $B_{j_{1}},\ldots$ in $T$. Since $v^{\prime}_{j}$ is
mapped to the same vertex of $T$, it is contained in blocks
$B^{\prime}_{j_{1}},\ldots$. Therefore, the neighbourhood of $v_{i}$ is
preserved by $f^{\prime}$. We conclude that $f^{\prime}$ is an isomorphism.
$\square$

###  5.2 Generation algorithms for weighted block trees

We now describe the modifications to the algorithms in the previous sections
needed to generate weighted block trees, thus connected block graphs by
Theorem 4. We will call the resulting generation algorithm BlockGraphGen.

A _rooted block tree_ is a block tree with an arbitrarily chosen root. Color
the vertices of a rooted block tree with two colors ”yellow” and ”red” where
cut vertices are yellow and block vertices are red.

The structural properties of the block trees can be stated as follows.

  * •

The children of a yellow vertex are all red.

  * •

The children of a red vertex are all yellow.

  * •

The weight of a yellow vertex is 1.

  * •

The weight of a red vertex is unrestricted. However,

  * •

The weight of a red vertex that is a leaf is at least 1.

  * •

A yellow vertex cannot be a leaf.

The first four conditions above can be expressed by the framework described in
Section 4.2, In order to express the last two conditions we first restate them
as follows:

  * •

The weight of a red tree is at least 1.

  * •

The weight of a yellow tree is at least 2.

Now it is sufficient to add a new parameter $mintw(c)$ which is the minimum
weight of a subtree whose root is colored $c$. We now note that a simple
modification of the algorithms is sufficient to support this parameter.
Namely, when considering the weight of $m$ of the largest subtree we do not
allow values below $mintw(c)$. Table 2 extends Table 1 with the new parameter
$minwt$ and colors introduced in this section.

$c$ | $minw(c)$ | $maxw(c)$ | $mintw(c)$ | $chld(c)$
---|---|---|---|---
Gray | 1 | 1 | 1 | { Gray }
Green | 1 | $\infty$ | 1 | { White, Green}
White | 0 | 0 | 1 | { Green }
Yellow | 1 | 1 | 2 | { Red }
Red | 0 | $\infty$ | 1 | { Yellow }
Table 2: The color parameter values used to construct weighted, unweighted and
block trees.

##  6 A General Framework and Implementation

Framework: In this section we formally describe the framework developed in the
previous sections. For simplicity, we confine ourselves to the case where
$\left|chld(c)\right|=1$ that is sufficient to generate unweighted, positive-
weighted and weighted block trees. We extend the notation given in Section 3.1
by a) replacing the number of vertices $n$ by the weight $w$ of a tree, and b)
introducing the color parameter $c$. For instance, ${\mathcal{RT}}_{w,c}$ is
the set of all trees of total weight $w$ colored $c$. The correctness of the
following equations that extend equations (1) - (6) can be easily verified.

$\displaystyle rt^{\leq}_{w,c,m}$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{cc}0&\textrm{if~{}}w<mintw(c)\\\
\sum_{r=minw(c)}^{\min(maxw(c),w)}f^{\leq}_{w-r,chld(c),\min(m,w-r)}&\textrm{otherwise}\end{array}\right.$
(11) $\displaystyle rt_{w,c}$ $\displaystyle=$ $\displaystyle
rt^{\leq}_{w,c,w}$ (12) $\displaystyle f_{w,c,m,\mu}$ $\displaystyle=$
$\displaystyle CC^{rt_{m,c}}_{\mu}\cdot f^{\leq}_{w-\mu\cdot
m,c,\min\left\\{w-\mu\cdot m,m-1\right\\}}$ (13) $\displaystyle
f^{\leq}_{w,c,m,\mu}$ $\displaystyle=$
$\displaystyle\sum_{\mu^{\prime}=1}^{\mu}f_{w,c,m,\mu^{\prime}}$ (14)
$\displaystyle f_{w,c,m}$ $\displaystyle=$ $\displaystyle
f^{\leq}_{w,c,m,\lfloor\frac{w}{n}\rfloor}$ (15) $\displaystyle
f^{\leq}_{w,c,m}$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}1&\textrm{if~{}}w=0\\\
\sum_{m^{\prime}=mintw(c)}^{m}f^{\leq}_{w,c,m^{\prime},\lfloor
w/m^{\prime}\rfloor}&\textrm{otherwise}\end{array}\right.$ (18) $\displaystyle
f_{w,c}$ $\displaystyle=$ $\displaystyle f^{\leq}_{w,c,w}$ (19)

It can be easily verified that these values can be computed in ${\cal
O}(N^{2}\log N)$ time. Moreover, using the technique used for unweighted trees
one can show that the output delay time complexity of the enumeration
algorithm is linear. Finally, the complexity analysis of unranking can be
computed along the same lines of Theorem 2.

Implementation: The algorithms were implemented in Python. The source code of
the library can be found in [16]. In addition, a Google Colaboratory (or
Colab, for short) demonstrating the usage of the library is published in [17]
for convenience. Figure 4 shows the running times taken from a sample run of
the Colab. The chart shows the average (amortized) construction time of a
rooted tree of weight $n$ when all the trees of weight $n$ are constructed. We
enumerated all (12,826,228) rooted trees on 20 vertices using a standard
(free) Colab with 12GB of memory. It can be seen that except a few
irregularities when the number of trees is small, that are apparently caused
by system overhead in various levels, the construction time per tree remains
constant. This is an experimental evidence that our algorithms are CAT.

Figure 4: Amortized enumeration time in milliseconds.

See Figure 5 in the Appendix for a list of positive-weighted trees of weight
5, and Figure 6 in the Appendix for a list of all weighted block trees of
graphs on 6 vertices categorized by their types. See also Table 3 in the
Appendix for the numbers of (non-isomorphic) block trees of total weight $n$
for $n\in[30]$, or equivalently, the numbers of (non-isomorphic) connected
block graphs with $n$ vertices for $n\in[30]$. These graphs up to 19 vertices
are enumerated using BlockGraphGen and can be downloaded from [1]. Block
graphs with more vertices can be generated using our open source codes in [16]
and [17], which can also be easily adapted for a generation u.a.r..

##  7 Conclusion

We presented a generic framework (as formalized in Section 6) to solve
enumeration problems of structured graphs using some tree structure such as
tree decomposition, clique-width decomposition, block-trees, etc. We
demonstrate this approach for block graphs using their block trees that
uniquely identifies them. In the sequel we mention possible future works.

We strongly believe that our enumeration algorithms are CAT. Namely, they have
Constant Amortized Time. This is due to the fact that the order of the
generated trees is similar to the order of trees in previous algorithms that
are proven to be CAT. Specifically, most of the generated trees are obtained
by a few changes to the preceding tree in the order. In this work, we provided
experimental evidence of this.

We have shown that the output delay time of our enumeration algorithms is
linear. Whereas, as said above, most of the trees are obtained by a few
changes to the preceding tree, this does not hold for all the trees. Some
trees are very different than their preceding tree. Therefore, they cannot be
obtained from the previous tree in the order, in constant time.

Enumerating weighted/block trees in some other order that will allow for sub-
linear delay time and the rigorous analysis of the amortized enumeration time
are left as open questions.

Future works:

U.a.r. generation: As mentioned in the introduction, one can generate objects
uniformly at random using a counting and an unranking algorithm. However, this
approach is not time-efficient since at each step of the generation of the
object, one has to compute the exact path to get an object of the given rank.
A more time-efficient approach would be to make random decisions at each step
which can be done by simple computations on our coefficients.

Improving the time complexity of unranking: In Lemma 1, we have shown that the
$i$-th multiset of $k$ elements over a set of $n$ elements can be found in
${\cal O}(k^{2}\log n)$ time. In the proof, we used a subroutine that performs
a binary search on an array of exponential size each element of which is a
binomial coefficient that can be computed in ${\cal O}(k)$ time. This can be
possibly improved by performing a ”fuzzy” binary search using an oracle that
computes approximations of binary coefficients, faster.

Improving the complexity analysis of unranking: The analysis in Theorem 2
might not be tight. It might be possible to show that the time-complexity of
unranking is ${\cal O}(n^{2}\log n)$.

Extensions: We note that our framework can be applied to other types of tree-
based decompositions of graphs whenever there exists a bijection between the
graphs and their decompositions.

In some cases such a bijection does not exist as in the case of cactus graphs
that are exactly the class of graphs whose blocks are either cycles or $K_{2}$
s. In this case, one weighted block tree may correspond to multiple cactus
graphs. As opposed to block graphs, this requires a more complex algorithm
since, unlike the cliques in which every bijection is an isomorphism, cycles
induce a smaller symmetry group.

In other cases where the blocks do not exhibit symmetry properties that can be
exploited, one may resort to isomorphism checks of the individual blocks. This
approach can be promising especially when the blocks have bounded size.

Our approach can be promising in generating several subclasses of chordal
graphs, such as chordal graphs of bounded tree-width and $k$-separator chordal
graphs. In these cases, one can first generate a weighted clique-tree and then
generate the corresponding chordal graphs and perform isomorphism checks of
the subgraphs.

## References

  * [1] The House of Graphs - Block Graphs.  https://houseofgraphs.org/meta-directory/block-graphs.
  * [2] H. Bielak and M. Panczyk.  A self-stabilizing algorithm for finding weighted centroid in trees.  Ann. UMCS Informatica, 12(2):27–37, 2012.
  * [3] H. L. Bodlaender, P. Heggernes, and D. Lokshtanov.  Graph Modification Problems (Dagstuhl Seminar 14071).  Dagstuhl Reports, 4(2):38–59, 2014.
  * [4] K. Coolsaet, S. D’hondt, and J. Goedgebeur.  House of graphs 2.0: A database of interesting graphs and more.  Discrete Applied Mathematics, 325:97–107, 2023.  Available at https://houseofgraphs.org.
  * [5] R. Diestel.  Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics.  Springer, 2012.
  * [6] S. Even.  Graph Algorithms.  Computer Science Press, 1979.
  * [7] M. C. Golumbic.  Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57).  North-Holland Publishing Co., Amsterdam, The Netherlands, 2004.
  * [8] M. Grohe and P. Schweitzer.  The graph isomorphism problem.  ACM, 63:128–134, 2020.
  * [9] F. Harary.  A characterization of block-graphs.  Canadian Mathematical Bulletin, 6(1):1–6, 1963.
  * [10] F. Harary.  Graph Theory.  Addison Wesley series in mathematics. Addison-Wesley, 1971.
  * [11] F. Harary and E. M. Palmer.  Graphical enumeration.  Academic Press, 1973.
  * [12] P. Kelsen.  Ranking and unranking trees using regular reductions.  In C. Puech and R. Reischuk, editors, STACS 96, pages 581–592, Berlin, Heidelberg, 1996. Springer Berlin Heidelberg.
  * [13] A. Kerber, R. Laue, R. Hager, and W. Weber.  Cataloging graphs by generating them uniformly at random.  Journal of Graph Theory, 14(5):559–563, 1990.
  * [14] D. E. Knuth.  The Art of Computer Programming, Volume I: Fundamental Algorithms.  Addison-Wesley, 1968.
  * [15] G. Li.  Generation of rooted trees and free trees.  Master’s thesis, University of Victoria, 1996.
  * [16] Enumeration and unranking of trees with weight restrictions in Python.  https://github.com/cmshalom/Enumerations/tree/master/code, 2023.
  * [17] Enumeration and unranking of trees with weight restrictions in Python.  https://colab.research.google.com/drive/1-k6lj7WArJQKJkqtqIpCBvbZoBeFMdeB?usp=sharing.
  * [18] R. Uehara, S. Toda, and T. Nagoya.  Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs.  Discrete Applied Mathematics, 145(3):479–482, 2005.
  * [19] H. S. Wilf.  The uniform selection of free trees.  J. Algorithms, 2(2):204–207, 1981.
  * [20] H. S. Wilf and A. Nijenhuis.  Combinatorial Algorithms for Computers and Calculators.  Academic Press, 1978.
  * [21] M. A. Yirik and C. Steinbeck.  Chemical graph generators.  PLOS Computational Biology, 17(1):e1008504, 2021.

## Appendix

Figure 5: Positive-weighted free trees of weight 5

(a) Block Trees with one red centroid

(b) Block Trees with one yellow centroid

(c) Block Trees with two centroids

(d) Block Trees with three centroids

Figure 6: Block Trees of Graphs on 6 vertices $n$ | Block Trees of Weight $n$
---|---
1 | 1
2 | 1
3 | 2
4 | 4
5 | 9
6 | 22
7 | 59
8 | 165
9 | 496
10 | 1,540
11 | 4,960
12 | 16,390
13 | 55,408
14 | 190,572
15 | 665,699
16 | 2,354,932
17 | 8,424,025
18 | 30,424,768
19 | 110,823,984
20 | 406,734,060
21 | 1,502,876,903
22 | 5,586,976,572
23 | 20,884,546,416
24 | 78,460,794,158
25 | 296,124,542,120
26 | 1,122,346,648,913
27 | 4,270,387,848,473
28 | 16,306,781,486,064
29 | 62,476,518,448,854
30 | 240,110,929,120,323
Table 3: Number of connected block graphs with up to 30 vertices.