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

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) [[],[[],[]]]

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, ReingoldTilford 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 2dimensional 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.

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 nonnegative 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:

Set T in global (e.g. T:value; then, draw_rt()).

Use "T:value" as an argument. (e.g. draw_rt(T:value)).

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.

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

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 nodesymbol 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 trueleaves; default red.

fc : the colour of falseleaves; 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.