Skip to content

Home

Jump to bottom Edit New page
MatthieuDien edited this page Sep 10, 2014 · 4 revisions

Welcome to the arbogen wiki !

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).

Add a custom footer
Add a custom sidebar
Clone this wiki locally