Drawing planar forests in LaTeX

Here is a LaTeX package for drawing planar forests. The package depends on PythonTeX and TikZ.

Introduction

In some calculations in numerical analysis (e.g. order calculation of Runge–Kutta methods) it is immensely helpful to use (planar) trees. As a generalization of such trees, we sometimes also need trees where the nodes have different colours, and also forests (i.e. ordered collections of trees). I set out to make a small package for typesetting such trees and forests in LaTeX.

My first task was to find out what makes a forest look beautiful. Here are some examples of what I had in mind:

After some consideration, I came up with the following recursive definition of beauty in the context of forests and trees:

A forest is beautiful if:

• Each subtree is beautiful.
• The horizontal distance between two adjacent subtrees is one unit.
• The roots of the subtrees are spaced out as evenly as possible.

A tree is beautiful if:

• The forest you get by removing the root of the tree is beautiful.
• The vertical distance between the root and the next level of nodes is one unit.
• The horizontal position of the root is the median of the horizontal positions of the roots of the subtrees.

In addition:

• The tree consisting of a single node is beautiful.

This definition can be converted into an algorithm by observing that we have optimal substructure. Once we have found an optimal configuration for a subtree, we never change the configuration of that subtree again.

In theory, the resulting algorithm is able to handle any forest.

I decided to program the algorithm using Python, and incorporate it into LaTeX using PythonTeX. I don't know TeX programming, so Python was the easiest choice for me. It should be possible to make a pure TeX implementation, thus getting rid of the PythonTeX dependency.

Installation

The package is hosted on GitHub. Simply download all the files to the same folder as your main LaTeX document.

You also need to install the PythonTeX and TikZ packages. To have a working PythonTeX installation, you also need a Python interpreter. All of these are easy to install in Linux. You may find that they are already installed on your system.

Usage

First of all, you need to insert

\usepackage{planarforest}

in the preamble of your main LaTeX document.

Important: Every time you change the forests in your document, you must invoke pdflatex, then pythontex, and then pdflatex again to get correct results. If your main document is called document.tex, the sequence of commands will be

pdflatex document
pythontex document
pdflatex document

If you want to use other node colours than black and white, these can be defined using

\newnodecolor{c}{colour}

Here, c is a letter, and colour is the name of a colour that TikZ knows about. For example, we can define r as red using \newnodecolor{r}{red}. Black and white are predefined as b and w respectively.

Forests are drawn using

\forest{string}

Here, string specifies the forest in the following way: A letter signifies a node of the colour assigned to that letter, (e.g. b gives a black node and w gives a white node). A forest is specified by a comma-separated list of subtrees (e.g. b,b,b). A node followed by brackets with a forest inside means that the forest is connected to the node (e.g. b[w,w]).
 
Here are some examples:

\forest{b[w,r]}

\forest{b[b,b,b],b}

 \forest{b[b,b[b]]}




See planarforest_test.tex for a LaTeX document with more examples.

Enjoy!

Edit (11 March 2014): After writing this post and the LaTeX package, I found out that this problem has been solved earlier by John Q. Walker in "A node‐positioning algorithm for general trees" Software: Practice and Experience 20.7 (1990): 685-705. His algorithm is slightly better than mine, since it ensures that symmetric trees always give symmetric drawings. However, my algorithm also handles forests.

Edit (12 March 2014): A new version of the package is now online. This version ensures that symmetric forests are indeed drawn in a symmetric way.

Edit (18 March 2014): The source code is now hosted on GitHub. I have changed the license to GPLv3.