D3 flextree plugin

This plugin provides a more general version of the D3 tidy-tree layout module. Unlike that module, which assumes fixed-sized nodes, this plugin allows for nodes of variable sizes. Like the d3 tidy-tree module, the algorithm runs in O(n) time.

flextree is a factory function that returns a layout instance. A layout is a function that computes the positions of nodes in a tree diagram. Properties attached to the layout control aspects of the algorithm.

Installing

npm install d3-flextree

API Reference

# flextree()

Creates a new layout with default settings:

• nodeSize: d => d.size
• children: d => d.children || []
• spacing: (a, b) => 0

# layout(root)

Computes the layout of a tree diagram, returning a representation of that diagram, which is a hierarchical set of node objects. Each of the returned objects "wraps" a data node in the original tree. The original tree data is not mutated.

Each of the objects in the returned hierarchy has the following properties:

• node.data - reference to the original tree data object
• node.nodes - all of the nodes in this subtree
• node.parent - the parent node, or null for the root.
• node.children - the array of child nodes, or null for leaf nodes.
• node.depth - the depth of the node, starting at 0 for the root.
• node.height - the distance from this node to its deepest descendent, or 0 for leaf nodes.
• node.x - the computed x-coordinate of the node position.
• node.y - the computed y-coordinate of the node position.

Although the layout is defined in terms of x and y, these represent an arbitrary coordinate system. For example, you can treat x as a radius and y as an angle to produce a radial rather than Cartesian layout.

Additionally, the returned tree nodes inherit all of the methods defined in d3.hierarchy. In particular:

• node.ancestors()
• node.descendants()
• node.leaves()
• node.path(target)
• node.links()
• node.sum(value)
• node.count()
• node.sort(compare)
• node.each(function)
• node.eachAfter(function)
• node.eachBefore(function)
• node.copy() - note that this does not preserve the original class.

# layout.children([children])

If children is specified, sets the specified children accessor function. If children is not specified, returns the current children accessor function, which by default assumes that the input data is an object with a children array:

d => d.children || []

The children accessor is first invoked for the root node in the hierarchy.

# layout.spacing([spacing])

If spacing is specified, uses the specified function to compute spacing between neighboring nodes. If spacing is not specified, returns the current spacing function, which defaults to a function that always returns 0:

(a, b) => 0

A common requirement is to increase the spacing for nodes that are not siblings. This could be accomplished with, for example:

layout.spacing( (a, b) => 10 * a.path(b).length );

# layout.nodeSize([nodeSize])

If nodeSize is specified as a two-element array [width, height], then this sets that as the fixed size for every node in the tree. nodeSize could also be an accessor function, that takes the node as an argument and returns a two-element array. If nodeSize is not specified, this returns the current nodeSize setting.

The Algorithm

The existing D3 tree layout is based on an algorithm developed originally by Reingold and Tilford in their paper from 1981, Tidier Drawings of Trees. The algorithm was improved over time by others, including Walker, in a paper in 1989, A Node-Positioning Algorithm for General Trees, and the latest improvement by Bucheim, Junger, and Leipert in 2002, described in their paper, Improving Walker's Algorithm to Run in Linear Time.

A limitation of that algorithm is that it applies to trees in which all of the nodes are the same size. This is adequate for many applications, but a more general solution would allow variable node sizes.

In a paper from 2013, A.J. van der Ploeg enhanced the algorithm to allow for variable-sized nodes, while keeping its linear runtime nature. He described the algorithm in his paper, Drawing Non-layered Tidy Trees in Linear Time. The author also provided a working Java application on GitHub at cwi-swat/non-layered-tidy-trees.

This module is a port from that Java code into JavaScript.