ttdot: Drawing Trees in Dot

ttdot (tree-to-dot) is a preprocessor for the dot graph description and visualization language. It takes an input that describes a rooted tree in a form where node branching is represented by indentation, and produces a description of that tree in dot. The result can be transformed to a graphics file using graphviz, or it can be further developed as a dot file.

Binary trees are recognized as a special kind of rooted trees and are processed accordingly.

The dot language has no means of distinguishing a tree from a graph in general. Because of that, a description of a tree in the language is necessarily redundant, each node being repeated for each edge that links it to another node. Besides, not knowing, in general, that it draws a rooted tree means that graphviz will not necessarily produce a visually symmetric and otherwise specific diagram which we are used to with regard to trees.

Actually, the dot layout processor of graphviz is smart enough to automatically detect if a graph is indeed a tree and is very good at finding a space-optimal layout, which is indispensable for really large trees. However, in many practical cases one may be willing to trade space-minimality for legibility and other benefits of aesthetic character.

Binary trees are particularly problematic for dot, because a node with no siblings must be specifically identified as a left or right descendant of its parent, which dot as a language does not provide for, and which cannot be derived automatically.

The only way that graphviz can be guaranteed to produce a rooted tree drawing with a layout that abides with certain requirements is to compute the node coordinates oneself and include them in the dot file that is feeded to graphviz. Of course, computing coordinates must still be done automatically.

Generating a dot file from a simple tree description, along with ensuring specific tree layouts by arranging nodes independently of graphviz, is basically what ttdot does.

Compared to using graphviz alone, enhancing it with ttdot brings the following benefits:

An input file for ttdot representing a rooted tree must be structured according to the following rules.

The input files for binary trees are similar to those for general rooted trees, but the rule 4. must be modified as follows.
Each node has at most two descendants, and if a node has only one, the latter is assumed to be a left descendant. The case of a right descendant that has no left sibling is handled by using a dummy node in place of the missing left descendant: a line holding a single non-blank character, indented so as to align with the right descendant.

Lines with a single non-blank character are also allowed in rooted trees, where they are simply skipped. This is so that any binary tree can be processed by ttdot as an ordinary rooted tree.

ttdot arranges the nodes of rooted and binary trees according to simple principles that result in predictable, readable, and relatively compact layout.

An archetypal tree is one that links a node to one or several descending nodes. The tree can be pictured like this:, where the descending nodes are evenly spaced and the root is centred above them. Drawing rooted trees in ttdot generalizes on this basic idea and is summarized in the following rules.

The leaves of a rooted tree, if projected onto the same horizontal line, will always preserve the left-to-right order of traversing the tree, and two adjacent leaves on this line are always the same distance (dx) one from another. A non-leaf node is always centred with respect to the horizontal extent of the sub-tree rooted at this node. And of course, nodes of the same level (i.e. equally distant from the root) are placed on the same horizontal, any two adjacent levels being at a vertical distance dy from each other.

Somewhat different rules apply for a binary tree. Here, all the nodes of the tree, if projected onto the same horizontal line, will preserve the left-to-right order (a.k.a. inorder) of traversing the tree, and are evenly spaced at a distance dx. It follows that for the whole tree or any of its sub-trees the root is to the right of all its left descendants and to the left of all its right descendants. In other words, a vertical line from any node of a binary tree never crosses an edge or touches another node of the tree.

ttdot reads its input — a tree description — from the standard input, and writes the result in the dot language to the standard output. Thus, assuming that ttdot is in a visible directory and that a tree is defined in the file a.tree, a dot file, say a.dot, can be obtained by running

By default ttdot assumes that its input is an ordinary rooted tree. The b option is used to tell ttdot to consider the input as a binary tree:

Another option, d, instructs ttdot to produce a directed graph, i.e., to put arrowheads at the ends of the edges. Yet another option, x, causes the \(x\) and \(y\) coordinates to be exchanged, so in the resulting diagram the tree’s root will be on the left. If two or all the three options are given in an invocation to ttdot, they must be written as one word, with no space between them. The order of the options is irrelevant.

ttdot assumes nothing of the input file names or their extensions — they are entirely at user’s choice.

Of the several graphviz layout engines, neato is the one that accepts nodes with fixed positions when such are given. So here is how to get a file with, say, an SVG drawing from the source file a.tree:

The so obtained diagram shows the tree as Nature has her trees: with the root at the bottom. This is because ttdot assigns larger \(y\)-coordinates to nodes that are farther from the root, and in the coordinate system of the dot language \(y\)-coordinates increase upwards. Most often, however, graphical trees are drawn with the root at the top of the diagram. This can be achieved by telling neato to reverse the direction of \(y\)-coordinates, but the latter requires an intermediate transform before producing an actual graphical output, such as SVG or PDF. Thus, to do the job in this case, a call of ttdot and two calls of neato are needed, which is unwieldy.

In order to enable the above and other variants of producing graphical trees in an easy to use form, the scripts mktree for Linux and mktree.bat for MS Windows are provided along with ttdot, and it is suggested that ttdot is mostly used through these scripts rather than directly. The description below applies to both scripts.

The scripts assume that ttdot, neato, and dot reside in visible directories, and accept two or three arguments. The first argument is the name of the file that defines the tree as required by ttdot. The proper name can be prefixed with a path as needed. The second argument specifies the output format: svg, ps, pdf, etc. This is also the filename extension of the output file. The output file is created in the same directory, and is given the same name as the input file, but is given the new extension. If the input file name itself has one or more extensions, the last of them is dropped before appending the output-specific extension. Thus, given an input file, e.g. some/path/names/tree.txt, the command

will produce an SVG file some/path/names/tree.svg. The same will happen if the input file is some/path/names/tree and the command

is issued.

A third argument to mktree (or mktree.bat), if present, is one to be passed to ttdot — b, d, x or any combination of these — to which any of the letters i and n, or both, can be added. (i and n are processed by the script itself, and the remainder of the third argument is passed to ttdot.)

The option i refers to inverting the vertical orientation of the tree, so that its root, which by default is placed at the top of the diagram, goes to the bottom. With the option n the script is instructed to use dot in place of neato to generate the diagram. This means that the coordinates assigned to the tree’s nodes by ttdot are ignored and dot's own layout mechanism is used. This also implies that the b and x options of ttdot have no effect in the presence of n. The i option still applies, so one can make use of dot for layout but invert the resulting diagram.

Note that using the i and x options alone or together has these effects on the layout of the tree:

Here are some examples of input files and the corresponding tree diagrams that result from applying ttdot and graphviz.