The publication subject of this page has the following reference

van der Ploeg, A. (2014), Drawing non-layered tidy trees in linear time,
Softw. Pract. Exper., 44, pages 1467– 1484, doi: 10.1002/spe.2213

which is the starting point to enhance our own Smalltalk class RSVanDerPloegTreeLayout to be faster by coding the core algorithm direclty in C and using Lua as intermediate for both describing the tree nodes and interfacing with C.

We represent the tree used in the paper as case study to spot the core points of the algorithms looks like either

Spec	Vertically	Horizontally

if oriented vertically or horizontally.

According to the issue https://github.com/Klortho/d3-flextree/issues/1, we take the same fix as done in https://github.com/Klortho/d3-flextree/blob/af196220927218bbe7ac6cad8e059f56430befb6/src/flextree.js#L242, so both

Spec	Layout

and

Spec	Layout

show the fix of such a patch.

Compact	Depth gaps	Breadth gaps	Both gaps

During the computation, the algorithm allows us to collect pairs of nodes that belongs to different contours of subtrees. Such pairs can be used to detect empty areas within the whole tree; for the sake of clarity, consider the following tree

where shapes highlighted in red are empty areas.

The implementation is split over the following components

• non-layered-tidy-trees.c, for the C implementation we refer to https://github.com/massimo-nocentini/non-layered-tidy-trees.c.
• non-layered-tidy-trees.lua, the corresponding Lua layer https://github.com/massimo-nocentini/non-layered-tidy-trees.lua, in turn.
• non-layered-tidy-trees.st, then both of them are used in https://github.com/massimo-nocentini/non-layered-tidy-trees.st which runs the tests and exports pictures.

As required by the issue https://github.com/massimo-nocentini/non-layered-tidy-trees.st/issues/1, we try to answer in the following subsections.

Let $\mathcal{I}$ be the set of items that could appear in a tree layout and let $\mathcal{S} = \mathcal{I}^{*}$, namely $\mathcal{S} = \lbrace()\rbrace \cup \mathcal{I} \cup \left(\mathcal{I}\times\mathcal{I}\right) \cup \left(\mathcal{I}\times\mathcal{I}\times\mathcal{I}\right) \cup \cdots$, be the set of all the sequences of items.

Assume we have a sequence $s \in\mathcal{S}$ (because order matters in what follows) of $n$ nodes, lets define $s = \left(i_{1}, \ldots, i_{n}\right)$ where $i_{j}\in\mathcal{I}$ for all $j\in[1, n]$: the values $w_{j}, h_{j}, m_{j}, x_{j}, y_{j}\in\mathbb{R}$ and $c_{j}\in\mathcal{S}$ are important for us and they denote width, height, margin, abscissa, ordinate and children of the item $i_{j}$, respectively.

In order to feed those values to the layout algorithm efficiently and to get results back, efficiently as well, we describe a schema based on a flat array of $3 n$ memory locations of double values with the following structure

$$ w_{1}\quad w_{2}\quad\ldots\quad w_{n} \quad h_{1}\quad h_{2} \quad \ldots\quad h_{n} \quad m_{1}\quad m_{2} \quad \ldots\quad m_{n} $$

because with one for loop we can fill a tree_t structure easily: let i be the variable of the for loop, so the width w is M[i], the height h is M[i + n] and the margin m is M[i + 2*n], provided that M is the array of $3n$ double values.

In order to support both vertical and horizontal gaps, another flat array of $2n$ memory locations of double values with the following structure

$$ w_{1}^{g}\quad w_{2}^{g}\quad\ldots\quad w_{n}^{g} \quad h_{1}^{g}\quad h_{2}^{g} \quad \ldots\quad h_{n}^{g} $$

is allocated in linear time, again: let i be the variable of the for loop, so the gap's width w is G[i] and the gap's height h is G[i + n], provided that G is the array of $2n$ double values.

That structure will be reused by the algorithm to provide the computed coordinates

$$ x_{1}\quad x_{2}\quad \ldots \quad x_{n}\quad y_{1}\quad y_{2}\quad \ldots\quad y_{n} $$

filled again at the cost of one for loop, as required.

Additionally, we have to allocate $n + k$ memory locations of int values to encode the tree relation defined by the $c_{j}$ sequences, where $j\in[1,n]$ and

$$ k = \sum_{r=1}^{n}{\left|c_{r}\right|}, $$

structured as follows by collecting indexes $p_{j, r}\in[1, n]$, for $r\in\left[1, \left|c_{j}\right|\right]$, of children of each item $i_{j}$

$$ \left|c_{1}\right| \quad \left|c_{2}\right| \quad \ldots \quad \left|c_{n}\right| \quad {p_{1,1}} \quad {p_{1,2}} \quad\ldots \quad {p_{1,\left|c_{1}\right|}} \quad {p_{2,1}} \quad {p_{2,2}} \quad\ldots \quad {p_{2,\left|c_{2}\right|}} \quad \ldots \quad {p_{n,1}} \quad {p_{n,2}} \quad\ldots \quad {p_{n,\left|c_{n}\right|}} $$

provided that $c_{j} = \left(i_{p_{j, 1}}, i_{p_{j, 2}}, \ldots, i_{p_{j, \left|c_{j}\right|}}\right)$; in case of $c_{j} = ()$, then the corresponding memory locations reduces to just

$$ \left|c_{1}\right| \quad\ldots\quad\left|c_{j-1}\right| \quad 0 \quad \left|c_{j+1}\right| \quad \ldots \quad \left|c_{n}\right| \quad \ldots \quad {p_{j-1,1}} \quad {p_{j-1,2}} \quad\ldots \quad {p_{j-1,\left|c_{j-1}\right|}}\quad {p_{j+1,1}} \quad {p_{j+1,2}} \quad\ldots $$

where the function $|\cdot|:\mathcal{S}\rightarrow\mathbb{N}$ counts the items of the given sequence, $\left|()\right| = 0$ in particular. Now let consider the following specification given in the Lua language,

local spec = {
		
["doC6dnl"] = { w = 84.09333333333333, h = 21, c = {}, },
["doC6eyv"] = { w = 328.0, h = 32.9, c = {}, },
["doCh0k5"] = { w = 185.94666666666663, h = 21, c = {}, },
["foCcmsslw7m"] = { w = 88.696, h = 25, c = {"doC6eyv","doCh0k5",}, },
["foCcmsslw7o"] = { w = 107.41600000000001, h = 25, c = {}, },
["foCcmsslw7p"] = { w = 97.70400000000001, h = 25, c = {}, },
["doC87sh"] = { w = 259.32, h = 21, c = {}, },
["doC87si"] = { w = 285.84000000000003, h = 21, c = {}, },
["doC87u6"] = { w = 87.88000000000001, h = 21, c = {}, },
["doC87ug"] = { w = 225.81333333333333, h = 21, c = {}, },
["doC87uv"] = { w = 186.0533333333333, h = 21, c = {}, },
["doC87vr"] = { w = 178.34666666666666, h = 21, c = {}, },
["foCcmsslw7q"] = { w = 161.56, h = 25, c = {}, },
["foCcmsslw7n"] = { w = 255.19200000000004, h = 25, c = {"doC87sh","doC87si","doC87u6","doC87ug","doC87uv","doC87vr","foCcmsslw7q",}, },
["foCcmssi4sv"] = { w = 337.8666666666666, h = 46, c = {"doC6dnl","foCcmsslw7m","foCcmsslw7o","foCcmsslw7p","foCcmsslw7n",}, },
    }

that is used in the current implementation. We can translate the values in the two memory chunks as follows:

for the sake of completeness, the tree's root is item $i_{15}$. So, widths and heights are readily encoded while the memory chunk for children lists looks like

$$ 0\quad 0\quad 0\quad 2\quad 0\quad 0\quad 0\quad 0\quad 0\quad 0\quad 0\quad 0\quad 0\quad 7\quad 5\quad 2\quad 3\quad 7\quad 8\quad 9\quad 10\quad 11\quad 12\quad 13\quad 1\quad 4\quad 5\quad 6\quad 14 $$

as required. The algorithm consumes such specification and produces coordinates for us to position some shapes as an horizontally-oriented tree

by the way, we have encountered this tree already in section Detecting empty areas.

The previous example can be encoded using the C# language as follows:

internal class Program
{
    [DllImport("libnonlayeredtidytrees.so", EntryPoint = "layout_api")]
    static extern void layout_api(int n, double[] wh, double[] whg, int[] children, int rooti,
                    int vertically, int centeredxy, double x, double y);

    private static void Main(string[] args)
    {
        int n = 15;

        var wh = new double[] {
            84.09333333333333, 328.0,185.94666666666663,88.696, 107.41600000000001 ,97.70400000000001,259.32,285.84000000000003,87.88000000000001,225.81333333333333,            186.0533333333333,178.34666666666666  ,161.56,255.19200000000004,337.8666666666666,
            21.0, 32.9,21.0,25.0,25.0,25.0,21.0,21.0,21.0,21.0,21.0,21.0,25.0,25.0,46.0,
            0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0};

        var gap = new double[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

        var children = new int[] { 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 5, 2, 3, 7, 8, 9, 10, 11, 12, 13, 1, 4, 5, 6, 14 };

        layout_api(n, wh, gap, children, 14, 0, 1, 0, 0);

        for (int i = 0; i < n; i++)
        {
            Console.WriteLine("{0}: {1} @ {2}", i, wh[i], wh[i + n]);
        }
    }
}

Obtaining the output in the console as a sequence of points:

0: 379.9133333333333 @ 10.5
1: 590.5626666666666 @ 20.025000000000002
2: 519.536 @ 46.975
3: 382.21466666666663 @ 33.5
4: 391.57466666666664 @ 73.97500000000001
5: 386.71866666666665 @ 102.97500000000002
6: 722.7186666666666 @ 67.97500000000001
7: 735.9786666666666 @ 88.97500000000001
8: 636.9986666666667 @ 109.97500000000001
9: 705.9653333333333 @ 130.97500000000002
10: 686.0853333333333 @ 151.97500000000002
11: 682.232 @ 172.97500000000002
12: 673.8386666666667 @ 195.97500000000002
13: 465.4626666666666 @ 131.97500000000002
14: 168.9333333333333 @ 71.23750000000001

For the sake of clarity, the above code has been tested on Ubuntu using the libnonlayeredtidytrees.so shared library but we provide the counter part for Windows too (please check the artifacts of the latest successful release at https://github.com/massimo-nocentini/non-layered-tidy-trees.c/releases/latest). The code binds over the layout_api function that is the API to use the algorithm. Here is a complete C# interface:

private Dictionary<DiagramShape, Point> Layout(Dictionary<DiagramShape, List<DiagramShape>> children, Dictionary<DiagramShape, int> indexes, DiagramShape rootNode)
{
    int n = indexes.Count();

    var wh = new double[n * 3];
    var gap = new double[n * 2];

    foreach (var node in indexes.Keys)
    {
        var i = indexes[node] - 1;
        var i_n = i + n;

        wh[i] = node.Width;
        wh[i_n] = node.Height;
        wh[i_n + n] = node == rootNode ? 0.0 : 10.0;

        gap[i] = node == rootNode ? 0.0 : 10.0;
        gap[i_n] = 0.0;
    }

    var child = new int[n];

    for (int i = 0; i < n; i++) child[i] = 0;

    var rev = new Dictionary<int, int[]>();

    foreach (var node in children.Keys)
    {
        var i = indexes[node] - 1;

        child[i] = children[node].Count();

        var chunk = new List<int>();

        foreach (var c in children[node])
        {
            chunk.Add(indexes[c]);
        }

        rev.Add(indexes[node], chunk.ToArray());
    }

    var rel = new List<int>(child);

    var l = rev.Keys.ToList<int>();
    l.Sort();
    l.ForEach(x => rel.AddRange(rev[x]));

    layout_api(n, wh, gap, rel.ToArray(), indexes[rootNode], 0, 0, 0.0, 0.0);

    Dictionary<DiagramShape, Point> positions = new Dictionary<DiagramShape, Point>();

    foreach (var node in indexes.Keys)
    {
        var i = indexes[node] - 1;
        positions.Add(node, new Point(wh[i], wh[i + n]));
        //Console.WriteLine("{0}: {1} @ {2}", i, wh[i], wh[i + n]);
    }

    return positions;
}

[System.Runtime.InteropServices.DllImport("lib\\libnonlayeredtidytrees.dll", EntryPoint = "layout_api")]
static extern void layout_api(int n, double[] wh, double[] whg, int[] children, int rooti,
            int vertically, int centeredxy, double x, double y);

The following message shows how the abstract framework can be reified,

On the biggest tree we possess we observe the following running times:

Another approach could be to produce a string representation of the specification, have a look at https://github.com/massimo-nocentini/non-layered-tidy-trees.st/blob/master/lua-test-data/big-tree.lua for a big tree with 25416 nodes. Then such a string has to be interpreted as a Lua chunk via the message LibLua>>#luaL_loadstring:chunk: available in https://github.com/massimo-nocentini/LibLua-st, then proceed as usual.

Finally, we can use again the FFI library https://github.com/massimo-nocentini/LibLua-st directly to build the specification table with the inner tables filled by the required values. Messages like LibLua>>#lua:create:table:, LibLua>>#lua:set:field: and more in general LibLua>>#on:push: are already provided by our own repo.

Many thanks to Richard Uttner for ideas, corrections and inspiration of fine tricks about optimizations.