Skip to content
a fast uniform random tree generator
OCaml Makefile
Find file
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.

   A      ...:'....:'':...':......
   R    :''   ._   .  `.  \   ,   '':
   B    ':  .   \" .|    \  `>/   _.-': 
   O   .:'  .`'.   `-.  '. /'  ,..  .:
   G  :'        `.    `\| \./   ' :
   E  :. ,,-'''''  \"-.  |   | ....:
   N   '.      ..'''  `\ :   |
         ''''''''       \'   |
*fast* uniform random    |  =|
       tree generator    |   |
                         |-  |
(C) F. Peschanski et al. under the GPL

Arbogen is a fast uniform random generator of tree structures. The tool reads a grammar file describing a tree structure (e.g. binary trees, 2-3-4 trees, etc.) and a size interval (eg. trees of size 1000+-100). From the grammar one or many trees satisfying the structure and the size interval are produced (following simple file formats). The generated tree are generated with a guarantee of uniformity, which means that it is the "average" tree for the given size.

Tree example

Note: this example is a plane rooted tree of more than 100.000 nodes obtained in a few seconds on a standard PC.

Internally, the tool is based on recent advances in analytic combinatorics and Boltzman generators. The generation is roughly linear in the size of the trees, which means huge trees (e.g. of more than 1 millions nodes) can be generated in a few seconds, memory management being the main performance bottleneck.

Arbogen can be used in the very many situations when tree-shaped datastructures must be manipulated, e.g. in random testing.

This software was inspired by the research work of Alexis Darasse. It is distributed under the GNU Public license v.2 (cf. LICENSE.txt).

Something went wrong with that request. Please try again.