# d3-dag

Often data sets are hierarchical, but are not in a tree structure, such as genetic data. In these instances `d3-hierarchy`

may not suit your needs, which is why `d3-dag`

(Directed Acyclic Graph) exists. This module implements a data structure for manipulating DAGs that mimics the API of `d3-hierarchy`

as much as possible, while allowing layouts of acylic DAGs.

## Updating from 0.1 to 0.2

The update from 0.1 to 0.2 includes a few small backwards incompatible changes.

`dratify`

was renamed to`dagStratify`

and`dierarchy`

was renamed to`dagHierarchy`

in order to pollute the d3 namespace less.- After running a
`sugiyama`

layout, the`points`

attribute will always exist for every links data, and it now also contains the start and end points. `coordSpread`

was removed in favor of`coordCenter`

which produces a slightly better layout in the same amount of time.`test/data`

was moved to`examples`

. This isn't technically part of the api, but it may break examples that required the old file location.- Link data is created at dag creation time. This also isn't technically backwards compatible but might increase memory consumption.

## Examples

- Examples with Sugiyama Layout - Allows you to experiment with different layouts and different datasets for the sugiyama layout.
- Examples with Topological Layout - Allows you to experiment with different layouts and different datasets for topological layouts.
- Example with Arrows - This example shows a simple, if inexact, way to render edge arrows with d3.

## Installing

If you use NPM, `npm i d3-dag@0.2.3`

. Otherwise you can load it using `unpkg`

:

```
<script src="https://unpkg.com/d3-dag@0.2.3"></script>
<script>
var dag = d3.sugiyama();
</script>
```

## API Reference

### Hierarchy

Before you can compute a DAG layout, you need a DAG structure. If your data is already in a DAG structure, you can pass it directly to `d3.dagHierarchy`

; otherwise, you can rearrange tabular data into a DAG using `d3.dagStratify`

Constructs a new hierarchy operator with the default settings.

Construct a DAG from the specified root nodes. Each root node must be an object representing a root node. For example:

```
{
"id": "Eve",
"children": [
{
"id": "Cain"
},
{
"id": "Seth",
"children": [
{
"id": "Enos"
},
{
"id": "Noam"
}
]
},
{
"id": "Abel"
},
{
"id": "Awan",
"children": [
{
"id": "Enoch"
}
]
},
{
"id": "Azura"
}
]
}
```

The DAG must be connected, i.e. each roots descendants must overlap. Node ids must be unique, and can't contain the null character `'\0'`

.

If *id* is specified, sets the id accessor to the given function and returns this dagHierarchy operator. Otherwise, returns the current id accessor, which defaults to:

```
function id(d) {
return d.id;
}
```

# dagHierarchy.**children**([*children*]) <>

If *children* is specified, sets the children accessor to the given function and returns this dagHierarchy operator. Otherwise, returns the current children accessor, which defaults to:

```
function children(d) {
return d.children;
}
```

# dagHierarchy.**linkData**([*linkData*]) <>

If *linkData* is specified, sets the linkData accessor to the given function and returns this dagHierarchy operator. The link data accessor takes the source and target data objects associated with a link and returns an object with data on the link. Otherwise, returns the current linkData accessor, which defaults to:

```
function linkData(source, target) {
return {};
}
```

### Stratify

You can rearrange tabularesque data into a DAG using `d3.dagStratify`

.

Constructs a new stratify operator with the default settings.

Construct a dag from the specified *data*. The data should be an array of data elements that contain info about their parents' ids. For example:

```
[
{
"id": "Eve"
},
{
"id": "Cain",
"parentIds": ["Eve"]
},
{
"id": "Seth",
"parentIds": ["Eve"]
},
{
"id": "Enos",
"parentIds": ["Seth"]
},
{
"id": "Noam",
"parentIds": ["Seth"]
},
{
"id": "Abel",
"parentIds": ["Eve"]
},
{
"id": "Awan",
"parentIds": ["Eve"]
},
{
"id": "Enoch",
"parentIds": ["Eve"]
},
{
"id": "Azura",
"parentIds": ["Eve"]
}
]
```

If *id* is specified, sets the id accessor to the given function and returns this dagStratify operator. Otherwise, returns the current id accessor, which defaults to:

```
function id(d) {
return d.id;
}
```

# dagStratify.**parentIds**([*parentIds*]) <>

If *parentIds* is specified, sets the parentIds accessor to the given function and returns this dagStratify operator. Otherwise, returns the current parentIds accessor, which defaults to:

```
function parentIds(d) {
return d.parentIds;
}
```

# dagStratify.**linkData**([*linkData*]) <>

If *linkData* is specified, sets the linkData accessor to the given function and returns this dagStratify operator. The linkData accessor takes the source and target data and returns an object with data for the link between them. Otherwise, returns the current linkData accessor, which defaults to:

```
function linkData(source, target) {
return {};
}
```

### Connect

You can rearrange raw edge data into a DAG using `d3.dagConnect`

.

Constructs a new connect operator with the default settings.

Construct a dag from the specified *data*. The data should be an array of data elements that contain info about links in the graph. For example:

```
[
["Eve", "Cain"],
["Eve", "Seth"],
["Seth", "Enos"],
["Seth", "Noam"],
["Eve", "Abel"],
["Eve", "Awan"]
]
```

# dagConnect.**sourceAccessor**([*sourceAccessor*]) <>

If *sourceAccessor* is specified, sets the source accessor to the given function and returns this dagConnect operator. The source accessor takes the link data and returns the source id for the link. Otherwise, returns the current source accessor, which defaults to:

```
function sourceAccessor(link) {
return link[0];
}
```

# dagConnect.**targetAccessor**([*targetAccessor*]) <>

If *targetAccessor* is specified, sets the target accessor to the given function and returns this dagConnect operator. The target accessor takes the link data and returns the target id for the link. Otherwise, returns the current target accessor, which defaults to:

```
function targetAccessor(link) {
return link[1];
}
```

# dagConnect.**linkData**([*linkData*]) <>

If *liknData* is specified, sets the linkData accessor to the given function and returns this dagConnect operator. The linkData accessor takes the link data and returns a data object to use for the link data. Otherwise, returns the current target accessor, which defaults to:

```
function targetAccessor(link) {
return link;
}
```

### DAG

A DAG is simply a collection of nodes, defined by every reachable child node from the current returned node. If a DAG contains multiple roots, then the returned node will be special in that it will have an `undefined`

`id`

and `data`

and will be ignored when calling normal methods. Each child of this special returned node will be one of the roots of the DAG. Each child node on its own will function as a valid DAG with a single root. Each node has the following properties:

*node*.id - a unique string identification for each node. This is necessary in order to check if two nodes are identical. For internal purposes, ids may not contain the null character (`'\0'`

).*node*.data - the associated data as specified in the constructor.*node*.children - an array of all child nodes. Empty if this is a leaf.

Each node also has the following methods.

Return an array of all descendant nodes of this node.

Returns an array of every link in the DAG. Each link has the following properties:

*link*.source - a node that is a parent of target.*link*.target - a node that is a child of source.*link*.data - an object with data attached to the link. Modifying this object will preserve the data for that link.

Copies the dag structure and returns it. The data associated with every node is not copied.

Copy and reverse the DAG, returning a new root or pseudo root depending on if there are multiple roots. This is particularly useful if you want to use the opposite accessor in DAG creation. For example, if your data set has childIds, you can use *dagStratify* with parentIds and simply reverse the DAG post creation.

Set the *value* of each node to be the number of descendants including itself.

Set the *value* of each node to be zero if its a root node, or the greatest distance to any root node for other nodes.

Set the *value* of each node to be zero if its a leaf node, or the greatest distance to any leaf node for other nodes.

Invoke the specified *function* on each node in an arbitrary order.

Invoke the specified *function* on each node such a node is called before any of its parents.

# node.**eachBefore**(*function*) <>

Invoke the specified *function* on each node such a node is called before any of its children.

# node.**eachBreadth**(*function*) <>

Invoke the specified *function* on each node in breadth first order.

Return `true`

if *this* dag is equal to *that* dag. For two dags to be equal the data must be strictly (`===`

) equal.

Return `true`

if *function* returns true for every node in the DAG.

Return `true`

if *function* returns true for at least one node in the DAG.

Set the *value* of every node to be the sum of this *functions* return value on the current node's data and the value of every descendant's return value.

### Sugiyama

This constructs a layered representation of the DAG meant for visualization. The algorithm is based off ideas presented in K. Sugiyama et al. [1979], but described by S. Hong. The sugiyama layout can be configured with different algorithms for different stages of the layout. For each stage there should be adecuate choices for methods that balance speed and quality for your desired layout, but any function that meets the interface for that stage is valid.

Construct a new Sugiyama layout operator with the default settings.

Lays out the specified DAG, assigning the following properties:

*node*.x - the x-coordinate of the node.*node*.y - the y-coordinate of the node.*link*.data.points - an array of points for how to draw the edge. The first point will always be the same as*source*and the last point will always be the same as*target*. Each point has an x and a y property.

If *debug* is specified, sets sugiyama to debug to *debug*. If *debug* is not specified, returns the current debug value, which defaults to false. If debug is true, dummy nodes will be given more human readable ids, but this can cause conflicts with poorly chosen ids, so it it disabled by default.

If *size* is specified, sets this sugiyama layout's size to the specified two-element array of numbers [*width*, *height*] and returns this sugiyama layout. If *size* is not specified, returns the current layout size, which defaults to [1, 1].

# sugiyama.**layering**([*layering*]) <>

If *layering* is specified, sets the layering accessor to the specified function and returns this sugiyama layout. If *layering* is not specified, returns the current layering accessor, which defaults to *d3.layeringSimplex()*. A layering accessor takes a dag and assigns every node a layer attribute from zero to the number of layers - 1. See Sugiyama Layering Acessors.

# sugiyama.**decross**([*decross*]) <>

If *decross* is specified, sets the decross accessor to the specified function and returns this sugiyama layout. If *decross* is not specified, returns the current decross accessor, which defaults to *d3.decrossTwoLayer()*. A decross accessor takes a dag as an array of layers where each layer is an array of nodes, and modifies the order of nodes in each layer to reduce the number of link crossings. See Sugiyama Decross Acessors.

If *coord* is specified, sets the coord accessor to the specified function and returns this sugiyama layout. If *coord* is not specified, returns the current coord accessor, which defaults to *d3.coordGreedy()*. A coord accessor takes a dag as an array of layers where each layer is an array of nodes and a separation function, which takes adjacent nodes and specifies their relative separation. The coord accessor assigns every node an x property in [0, 1] to specify the actual layout. See Sugiyama Coord Acessors.

# sugiyama.**separation**([*separation*]) <>

If *separation* is specified, sets the separation accessor to the specified function and returns this sugiyama layout. If *separation* is not specified, returns the current separation accessor, which defaults to:

```
function separation(a, b) {
return 1;
}
```

The separation accessor function takes two adjacent dag nodes and sets their relative separation, thus any constant function will produce the same results. Another other common setting is:

```
function separation(a, b) {
return (a.data !== undefined) + (b.data !== undefined);
}
```

which will wrap edges around nodes, but give them no spaceing themselves.

### Sugiyama Layering Accessors

Several built-in layering accessors are provided for use with *sugiyama*.

Construct a longest path layering accessor. This layering accessor assigns every node a layer such that the longest path (the height) is minimized. This often results in very wide graphs, but is fast.

# layeringLongestPath.**topDown**(*topDown*) <>

Set whether longest path should go top down or not. If set to true (the default), longest path will start at the top, putting only nodes that need to be at hte top layer, otherwise it will put as many nodes as possible in the top layer.

# d3.**layeringCoffmanGraham**() <>

Constructs a Coffman-Graham layering accessor with default options. Assigns every node a layer such that the width, not counting dummy nodes, is always less than some constant. This can result in tall graphs, but is also reasonably fast.

# layeringCoffmanGraham.**width**(*width*) <>

Set the maximum width of any layer. If set to 0 (the default), the width is set to the rounded square root of the number of nodes.

Constructs a simplex layering accessor with default options. Assigns every node a layer such that the number of dummy nodes, nodes inserted on edges that span more than one layer, is minimized. This is often known as the network simplex layering from Gansner et al. [1993]. This is the most expensive built-in layering assignment accessor.

# layeringSimplex.**debug**(*debug*) <>

Setting *debug* to true will cause the simplex solver to use more human readable names, which can help debug optimizer errors. These names will cause other types of failures for poorly constructed node ids, and is therefore disabled by default.

Construct a topological layering accessor. This layering accessor assigns every node a unique layer resulting is extremely tall layouts. However, when combined with the *coordTopological* coordinate assignment accessor, this can produce pleasing dag layouts. This is a very fast layering assignment method, but may cause other steps to take lponger due to the introduction of many dummy nodes.

### Sugiyama Decross Accessors

Several built-in decross accessors are provided for use with *sugiyama*. This step is entirely optional, so a noop function can be used to save time, but this will likely result in very ugly layouts.

Construct a an optimal decross accessor with default arguments. This operator minimized the number of crossings, but does so by solving a mixed-integer linear program (MILP), and may therefore be very slow.

If set, the variables for the MILP will be given more human readable names, which can help debug optimization errors. This can cause new optimization errors if the node ids are poorly formed, and is disabled by default.

Construct a two layer decross accessor with default arguments. The two layer accessor heuristically minimizes the crossings between each layer one at a time by adjusting the positions of the bottom layer. This can much much faster than using the optimal method.

# decrossTwoLayer.**order**(*order*) <>

If *order* is specified, sets the order accessor to the specified function and returns this decrossTwoLayer accessor. If *order* is not specified, returns the current order accessor, which defaults to *d3.twolayerMedian()*. A twolayer accessor takes two layers of nodes as arrays, and changes the order of the second layer in order to minimize the number of crossings.

#### Sugiyama Two Layer Accessors

Several built-in twolayer accessors are provided for use with *decrossTwoLayer*.

Construct a twolayer median accessor. This accessor orders the bottom layer by the medians of their parents.

Construct a twolayer mean accessor. This accessor orders the bottom layer by the means of their parents.

Construct a twolayer optimal accessor. This accessor orders the bottom layer to minimize the number of crossings. This is done using a MILP, and so will be much slower than the other two layer accessors, but generally faster than the full optimal corssing minimiztion.

If *debug* is specified, sets twolayerOpt to debug to *debug*. If *debug* is not specified, returns the current debug value, which defaults to false. If debug is true, the optimization formulation will be given more human readable names that help debugging the optimization, but may cause conflicts if used with poorly chosen node ids.

### Sugiyama Coord Accessors

Several built-in coord accessors are provided for use with *sugiyama*.

Construct a center coordinate accessor. This accessor keeps spread every node apart by separation and then centers each layer. The result isn't a particularly great distribution of nodes, but it doesn't require any type of optimization, and so is very fast.

Construct a vertical coordinate accessor. This accessor positions nodes so that the distance between nodes and the their neightbors is minimized, while the curve through dummy nodes is minimized. This accessor solves a quadratic program (QP) and so may take significant time, especially as the number of nodes grows.

Construct a minimum curve accessor. This accessor weights between minimizing all curves through nodes, and the distance between a node and it's neightbor, including dummy nodes. This also solves a QP and so is about as performant as *coordVert*.

# coordMinCurve.**weight**(*weight*) <>

If *weight* is specified, sets the weight to the specified number and returns this coordMinCurve accessor. If *weight* is not specified, returns the current weight, which defaults to 0.5. Weight must be a value between 0 includive and 1 exclusive. Heigher weights prioritize minimizing curves more, while lower weights prioritize minimizing child closeness. Since minimizing only curves is not well defined, weight can not be 1.

Construct a greedy coordinate accessor. This accessor assigns coordinates as the mean of their parents and then spaces them out to respect their separation. Nodes with higher degree that aren't dummy nodes are given higher priority for shifting order, i.e. are less likely to be moved from the mean of their parents. This solution results in a layout that is more pleaseoing than spread, but much faster to compute than vert or minCurve.

Construct a topological coordinate accessor. This accessor only works with a topological layering, and minimizes the curve of edges such that all nodes are positioned vertically. See *layeringTopological* for an example of what this coordinate assignment looks like.

### Zherebko

This constructs a topological representation of the DAG meant for visualization. The algorithm is based off a PR by D. Zherebko. The nodes are topologically ordered, and edges are positioned into "lanes" to the left and right of the nodes.

Construct a new Zherebko layout operator with the default settings.

Lays out the specified DAG, assigning the following properties:

*node*.x - the x-coordinate of the node.*node*.y - the y-coordinate of the node.*link*.data.points - an array of points for how to draw the edge. The first point will always be the same as*source*and the last point will always be the same as*target*. Each point has an x and a y property.

If *size* is specified, sets this zherebko layout's size to the specified two-element array of numbers [*width*, *height*] and returns this zherebko layout. If *size* is not specified, returns the current layout size, which defaults to [1, 1].