RandomTree.jl

RandomTree.jl is a Julia package for simulations on random trees, in particular Conditional Galton-Watson trees. It can efficiently generate several types of random trees up to size 10^8, including

• Conditional Galton Watson tree
  • Cayley
  • Binary
  • Catalan
  • DAry
  • Motzkin
• Random Recursive Trees (up to size 10^7)

as well as carry out these simulations

• k-cut
• sum of log(subtree sizes) over all fringe subtrees
• height
• total path length
• leaf number count

The package also provides a simply function for drawing trees.

You can use RandomTree.jl as a library in your code, in Julia REPL, or in a Jupyter notebook. It can also run as a stand-alone script.

The generation of conditional Galton-Watson trees uses a very efficient algorithm introduced by Luc Devroye. Generating a Galton-Watson tree of 1 million nodes takes about 20-30 ms.

Installation

Start Julia REPL and enter the package mode by pressing ]. You should see the prompt

(v1.1) pkg>

Type

(v1.1) pkg> dev https://github.com/newptcai/RandomTree.jl

should add RandomTree.jl to your default Julia environment. Then you can just use it as any other Julia package. You can also find the source code of the package at ~/.julia/dev/RandomTree.

Usage

Use RandomTree.jl In interactive environment

In Julia REPL, load RandomTree.jl by

julia> using RandomTree

To get the degree sequence of a (random) Cayley tree of size 5 in depth-search-first order, type

julia> tree = CayleyTree(5)
Cayley Tree of size 5

julia> degrees(tree)
5-element Array{Int32,1}:
 3
 1
 0
 0
 0

Note that since we are simulating a random tree, each time degrees(tree) is called, a random degree sequence is returned.

Simulations on random trees usually need to compute a property of trees from its degree sequence. Several such simulations has been implemented in src/simulator.jl. For example, to generate 1000 Cayley Trees and calculate their height, type

julia> sim = HeightSimulator(tree)
height simulation of Cayley Tree of size 5

julia> sim_result = simulation(sim, 1000)
1000-element Array{Any,1}:
 4
 3
 ⋮
 5
 4
 4

See example.ipynb in the notebook directory for more demonstrations.

Use RandomTree.jl as a script

In a terminal, change directory to the ~/.julia/dev/RandomTree/src and run the command

julia simtree.jl -l 5 -n 10000 -t Cayley height

will generate 10000 Cayley trees of size 10^5 and print out their heights. Run

julia simtree.jl --help

to see the other options.

The simulations can made parallel. For example

julia -p 4 simtree.jl -l 5 -n 10000 -t Cayley height

will start 4 local processes on your local machine to run the simulation. You can also run simulations across several nodes of a cluster by using

julia --machine-file machines.txt simtree.jl -l 5 -n 10000 -t Cayley height

where machines.txt contains the information for finding remote nodes. See Julia's documentats for details.

Future plan

Several random trees will be added in the future

• binary search trees
• split trees in general
• preferential attachment