D3 flextree plugin


This plugin provides a more general version of the D3 tree layout
module. Unlike tree, this plugin
allows for nodes of variable sizes; like tree, the algorithm is fast, running
in O(n) time.


See the demo.

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 various parameters
of the algorithm.

Try d3-flextree in your browser.

Installing

If you use npm, npm install d3-flextree.
Otherwise, download the latest
release.
AMD, CommonJS, and browser environments are supported.

Alternatively, you can use it straight from the jsdelivr CDN at
https://cdn.jsdelivr.net/npm/d3-flextree@2.0.0/build/d3-flextree.min.js. or d3-flextree.js

Overview

Computing the layout of a tree data structure involves two steps: first,
create a hierarchy from the data, and second, invoke the layout function.

In a Node environment:

``javascript
const flextree = require('d3-flextree').flextree;
const layout = flextree();
const tree = layout.hierarchy({
size: [1, 1],
children: [
{ size: [2, 4] },
{ size: [3, 1],
children: [
{ size: [4, 1] },
],
},
],
});
layout(tree);
tree.each(node => console.log((${node.x}, ${node.y})));
`

In a browser, flextree is attached to a d3 global (which is created
if necessary):

`html


`

When creating the hierarchy, the library uses the children accessor
function to determine the children of a data node. When the layout is
computed, two other accessor functions are used: nodeSize (to get the
node sizes) and spacing (to determine how far apart adjacent
nodes in the diagram should be placed).

The example above uses the default accessors:

`javascript
children: data => data.children,
nodeSize: node => node.data.size,
spacing: 0,
`

If the data is structured differently, the children and nodeSize
accessors can be customized. For example, here is the same tree encoded in a
nested array structure, along with the code to compute the layout using a
spacing function that increases the gap between more distantly related
nodes:

`javascript
const data = [
1, 1,
[ 2, 4 ],
[ 3, 1,
[ 4, 1 ],
],
];
const layout = flextree({
children: data => {
const kd = data.slice(2);
return kd.length ? kd : null;
},
nodeSize: node => node.data.slice(0, 2),
spacing: (nodeA, nodeB) => nodeA.path(nodeB).length,
});
const tree = layout.hierarchy(data);
layout(tree);
console.log(layout.dump(tree)); //=> prints the results
`

The accessors can also be set using D3-style chained methods:

`javascript
const layout = flextree()
.children(data => {
const kd = d.slice(2);
return kd.length ? kd : null;
})
.nodeSize(node => node.data.slice(0, 2))
.spacing((nodeA, nodeB) => nodeA.path(nodeB).length);
`

One thing to keep in mind is that the argument passed to the
children accessor is a node in the data structure,
whereas the arguments to nodeSize and spacing are nodes of
the hierarchy.

The layout.hierarchy method is a convenience form
of the d3.hierarchy
function, and creates a set of objects that are instances of
a class that derives from d3.hierarchy. It's not required to
use the d3-flextree version. The following code is equivalent to
the example above, with three custom accessors. Note that the
children accessor needs to be passed as the second argument
to the d3.hierarchy function:

`javascript
const layout = flextree({
nodeSize: node => node.data.slice(0, 2),
spacing: (nodeA, nodeB) => nodeA.path(nodeB).length,
});
const tree = hierarchy(data, data => {
const kd = d.slice(2);
return kd.length ? kd : null;
});
layout(tree);
`

API Reference

# flextree(accessors)

Creates a new layout with the specified accessors. Any subset of
children, nodeSize, and spacing can be specified in the
argument object. If one is not specified, then the default is used:

`javascript
children: data => data.children,
nodeSize: node => node.data.size,
spacing: 0,
`

The accessors can also be changed using chained methods, for example:

`javascript
const layout = flextree()
.spacing((nodeA, nodeB) => nodeA.path(nodeB).length);
`

# layout.hierarchy(data)

Creates a new hierarchy from the data, using the children accessors
in effect when called. This is an enhanced version of the
d3.hierarchy
function, and produces a tree of instances of a class derived from
d3.hierarchy.

Each node of the hierarchy inherits all of the methods defined
in d3.hierarchy, including:

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() - this
method is re-implemented in flextree, such that it preserves the
class.

In addition, each of the objects in the returned hierarchy has
several property getters. Many of these will be meaningless
until layout is called on this tree. They include:

x - the computed x*-coordinate of the node position.
y - the computed y*-coordinate of the node position.
* data - reference to the original data object
* nodes - all of the nodes in this subtree (same as descendants())
* parent - the parent node, or null for the root.
* children - the array of child nodes, or null for leaf nodes.
* numChildren
* hasChildren
* noChildren
* depth - the depth of the node, starting at 0 for the root.
* height - the distance from this node to its deepest descendent,
or 0 for leaf nodes.
* length - number of nodes in this subtree
* size - size of this node (the values fetched by the nodeSize accessor)
as a two-element array.
* xSize
* ySize
* top
* bottom
* left
* right
* extents - the minimum top and left, and the maximum bottom and
right values for all of the nodes in this subtree

# layout(tree)

Computes the layout of a hierarchy. x and y properties are
set on each node, and many other properties useful in rendering
are available -- see the list above.

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.

# 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 property, whose value is either an array or null if there
are no children:

`javascript
data => data.children
`

Note that unlike the other accessors, this takes a data node
as an argument. This is used only in the creation of a hierarchy,
prior to computing the layout, by the layout.hierarchy method.

# layout.nodeSize([nodeSize])

If nodeSize is specified as a two-element array [xSize, ySize], then
this sets that as the fixed size for every node in the tree. If nodeSize
is a function, then that function is passed the hierarchy node as an argument,
and should return a two-element array. If nodeSize is not specified, this
returns the current setting.

The default nodeSize assumes that a node's size is available as a
property on the data item:

`javascript
node => node.data.size
`

# layout.spacing([spacing])

If a spacing argument is given as a constant number, then the layout
will insert the given fixed spacing between every adjacent node.
If it is given as a function, then that function will be passed two
nodes, and should return the minimum allowable spacing between those
nodes. If spacing is not specified,
this returns the current spacing, which defaults to 0.

To increase the spacing for nodes as the distance of their relationship
increases, you could use, for example:

`javascript
layout.spacing((nodeA, nodeB) => nodeA.path(nodeB).length);
``

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][1]. The algorithm was improved over time by others, including Walker,
in a paper in 1989, [A Node-Positioning Algorithm for General Trees][2], and
the latest improvement by Bucheim, Junger, and Leipert in 2002, described in their
paper, [Improving Walker's Algorithm to Run in Linear Time][2].

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, allowing variable node sizes, is often
preferable.

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][3]. 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.

[1]: http://emr.cs.iit.edu/~reingold/tidier-drawings.pdf
[2]: http://www.cs.unc.edu/techreports/89-034.pdf
[2]: http://dirk.jivas.de/papers/buchheim02improving.pdf
[3]: http://oai.cwi.nl/oai/asset/21856/21856B.pdf