OKlibrary  0.2.1.6
Tutorial.hpp File Reference

Tutorial on trees in Maxima/Lisp. More...

Go to the source code of this file.

## Detailed Description

Tutorial on trees in Maxima/Lisp.

# Trees via Maxima in the OKlibrary

1. For the OKlibrary, An "unlabelled rooted tree" ("rt") is recursively defined as a list [T_1, ..., T_n], where the T_i are the subtrees (the case n=0, i.e., the empty list, represents the trivial tree).
(%i1) T:[[],[[],[]]];
(%o1) [[],[[],[]]]

2. Similarly, a "labelled rooted tree" ("lrt") is recursively defined as a list [L, T_1, ..., T_n], n >= 0, where L is the label, and the T_i are the subtrees.
(%i2) T:[1,[2],[3,[4],[5]]];
(%o2) [1,[2],[3,[4],[5]]]

# Tree drawing algorithm

• Currently, Reingold-Tilford algorithm is used for producing layered tree drawing. we implemented reingold_tilford_rt in Maxima. Given an unlabelled rooted tree and the root coordinate as input, a labelled rooted tree with 2-dimensional coordinates will be produced.
(%i27) reingold_tilford_rt([[],[]],[0,0]);
(%o27) [[[0,0]],[[[-1,-1]]],[[[1,-1]]]]

# Visualisation of trees

• Both unlabelled and labelled rooted trees can be handled and visualised via Maxima in the OKlibrary. For splitting trees we use a different function to handle them. A splitting tree is a labelled rooted tree, where each inner node is labelled by a number (natural number) while leaves are labelled by the boolean values 'true' or 'false'. In the following part, we will give the detailed usage of tree drawing functions.
1. draw_rt
• draw_rt can handle unlabelled rooted trees; at least one argument (an unlabelled rooted tree T) must be given, all other possible parameters are optional. The default value will be set if any optional parameter is not given.
• Possible parameters are listed as follows:
• T : an unlabelled rooted tree.
• p : the root coordinates of the tree [x,y]; default [0,0].
• xran : the range for the x coordinate [x_min,x_max]; default auto.
• yran : the range for the y coordinate [y_min,y_max]; default auto.
• pts : the size of a point (a non-negative number); default computed.
• ptt : the type of points (either as name or as integer). Available names and integers are: \$none (-1), dot (0), plus (1), multiply (2), asterisk (3), square (4), filled_square (5), circle (6), filled_circle (7) *default*, up_triangle (8), filled_up_triangle (9), down_triangle (10), filled_down_triangle (11), diamant (12), filled_diamant (13).
• ptc : the colour of points (red, blue, ...); default red.
• edgc : the colour of edges (red, blue, ...); default blue.
• output: if output is set to "true", the tree drawing will be output to a file called "output.eps" in the current directory. Otherwise, the tree drawing will be displayed normally.
• T is a compulsory parameter that can be accepted by a function call in the following ways:
1. Set T in global (e.g. T:value; then, draw_rt()).
2. Use "T:value" as an argument. (e.g. draw_rt(T:value)).
3. Use the "value" of T as the first argument. (e.g. draw_rt(value)).
The other parameters are optional, the usage of which are similar to the parameter T which is listed above except 3. Furthermore, the optional parameters can be set to "unknown" (e.g. draw_rt(pts:unknown)) so that the default values of the parameters will be used.
2. draw_lrt
• draw_lrt handles labelled rooted trees. RGB colour model is used for the colouring schemes. The usage of the function is similar to draw_rt except the compulsory parameter T which is a labelled rooted tree here. (Please refer to draw_rt).
3. draw_st
• draw_st is used for visualising splitting trees. For visualisation of splitting trees, we just print the labels of inner nodes up to depth d, where d is a natural number >= -1, and for the inner nodes of depth <= d then the labels are printed, while otherwise nothing shows. Leaves are treated differently, where the leaves that are labelled by "true" show the node-symbol with red colour, otherwise grey colour. For draw_st, the compulsory parameter T is a splitting tree. Some optional parameters are listed below:
• lbc : the colour of labels; default red.
• tc : the colour of true-leaves; default red.
• fc : the colour of false-leaves; default grey.
• d : the maximum depth which the labels will be printed. (d is a natural number >= -1).
For the usage and other possible parameters, please refer to draw_rt.

Definition in file Tutorial.hpp.