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.
• Examples with Arquint Layout - Allows you to experiment with different layouts and different datasets for the arquint layout.

Installing

If you use NPM, npm i [email protected]. Otherwise you can load it using unpkg:

<script src="https://unpkg.com/[email protected]"></script>
<script>

var dag = d3.sugiyama();

</script>

API Reference

• Hierarchy
• Stratify
• Connect
• DAG
• Sugiyama
• Zherebko
• Arquint

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

# d3.dagHierarchy() <>

Constructs a new hierarchy operator with the default settings.

# dagHierarchy(...roots) <>

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'.

# dagHierarchy.id([id]) <>

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.

# d3.dagStratify() <>

Constructs a new stratify operator with the default settings.

# dagStratify(data) <>

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"]
  }
]

# dagStratify.id([id]) <>

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.

# d3.dagConnect() <>

Constructs a new connect operator with the default settings.

# dagConnect(data) <>

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.

# node.descendants() <>

Return an array of all descendant nodes of this node.

# node.links( <>)

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.

# node.copy() <>

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

# node.reverse() <>

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.

# node.count( <>)

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

# node.depth() <>

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.

# node.height() <>

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.

# node.each(function) <>

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

# node.eachAfter(function) <>

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.

# node.equals(that) <>

Return true if this dag is equal to that dag. For two dags to be equal the data must be strictly (===) equal.

# node.every(function) <>

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

# node.some(function) <>

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

# node.sum(function) <>

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.

# d3.sugiyama() <>

Construct a new Sugiyama layout operator with the default settings.

# sugiyama(dag) <>

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.

# sugiyama.debug([debug]) <>

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.

# sugiyama.size([size]) <>

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.

# sugiyama.coord([coord]) <>

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.

# d3.layeringLongestPath() <>

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.

# d3.layeringSimplex() <>

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.

# d3.layeringTopological() <>

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.

# d3.decrossOpt() <>

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.

# decrossOpt.debug(debug) <>

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.

# d3.decrossTwoLayer() <>

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.

# d3.twolayerMedian() <>

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

# d3.twolayerMean() <>

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

# d3.twolayerOpt() <>

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.

# twolayerOpt.debug(debug) <>

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.

# d3.coordCenter() <>

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.

# d3.coordVert() <>

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.

# d3.coordMinCurve() <>

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.

# d3.coordGreedy() <>

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.

# d3.coordTopological() <>

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.

# d3.zherebko() <>

Construct a new Zherebko layout operator with the default settings.

# zherebko(dag) <>

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.

# zherebko.size([size]) <>

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

Arquint

This treats nodes not as points (i.e. producing x & y coordinates) but as rectangles. Each node has a property heightRatio specifying its height in comparison to other nodes. The implementation was contributed by the author L. Arquint and provides different algorithms to distribute the nodes along the x-axis.

# d3.arquint() <>

Construct a new Arquint layout operator with the default settings.

# arquint(dag) <>

Lays out the specified DAG while respecting (vertical) node.heightRatio together with (vertical) inter layer separation, (horizontal) column width, as well as (horizontal) column separation. It assigns the following properties:

• node.x0 - the left x-coordinate of the node.
• node.x1 - the right x-coordinate of the node.
• node.y0 - the bottom y-coordinate of the node.
• node.y1 - the top 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, that corresponds to the bottom (source) resp. top (target) center of the node.

In the following example, the default options were used and node.heightRatio was set to Number(node.id)+1:

# arquint.size([size]) <>

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

# arquint.layering([layering]) <>

If layering is specified, sets the layering accessor to the specified function and returns this arquint layout. If layering is not specified, returns the current layering accessor, which defaults to d3.layeringLongestPath().topDown(false). 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.

# arquint.decross([decross]) <>

If decross is specified, sets the decross accessor to the specified function and returns this arquint 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.

# arquint.columnAssignment([columnAssignment]) <>

If columnAssignment is specified, sets the column accessor to the specified function and returns this arquint layout. If columnAssignment is not specified, returns the current column accessor, which defaults to d3.columnComplex(). A column accessor takes a dag as an array of layers where each layer is an array of nodes, and sets node.columnIndex to the index of the column in which it should appear. See Arquint Column Accessors.

# arquint.column2Coord([coord]) <>

If column2Coord is specified, sets the column to coord accessor to the specified function and returns this arquint layout. If column2Coord is not specified, returns the current column to coord accessor, which defaults to d3.column2CoordRect(). A column to coord accessor takes a dag as an array of layers where each layer is an array of nodes and each node has an assigned column index, a column width function and a column separation function. The column to coord accessor assigns every node an x0 and x1 property in [0, 1] to specify the actual layout. See Arquint Column To Coord Acessors.

# arquint.interLayerSeparation([interLayerSeparation]) <>

If interLayerSeparation is specified, sets the inter layer accessor to the specified function and returns this arquint layout. If interLayerSeparation is not specified, returns the current inter layer accessor, which defaults to 1. A inter layer accessor takes a layer (i.e. an array of nodes) and its index and returns the relative distance to the previous layer. It is not called for the first layer, because it does not have a previous layer.

# arquint.columnWidth([columnWidth]) <>

If columnWidth is specified, sets the column width accessor to the specified function and returns this arquint layout. If columnWidth is not specified, returns the current column width accessor, which defaults to 10. A column width accessor takes a column index and returns the relative width of the column.

# arquint.columnSeparation([columnSeparation]) <>

If columnSeparation is specified, sets the column separation accessor to the specified function and returns this arquint layout. If columnSeparation is not specified, returns the current column separation accessor, which defaults to 1. A column separation accessor takes a column index and returns the relative distance to the next column.

Arquint Column Accessors

Several built-in column accessors are provided for use with arquint. They take an array of layers as input and set node.columnIndex for each node to the index of the column in which the node should appear. columnSimpleLeft and columnSimpleCenter determine the column index just by considering a layer. On the contrary, columnComplex follows a global approach in assigning column indices and tries to place a node in a column as close as possible to the column in which its successors are placed in.

# d3.columnSimpleLeft() <>

Constructs a column simple left accessor. For each layer, this accessor assigns each node to a column starting from the left side. Due to the layer local decision process, nodes can overlap if nodes in different layers have different heights. Therefore, the following example sets node.heightRatio to 1 for all nodes:

# d3.columnSimpleCenter() <>

Constructs a column simple center accessor. For each layer, this accessor assigns each node to a column while centering them (per-layer). Due to the layer local decision process, nodes can overlap if nodes in different layers have different heights. Therefore, the following example sets node.heightRatio to 1 for all nodes:

# d3.columnAdjacent() <>

Constructs a column adjacent accessor. Assigns column indices to the layer with most nodes first. Afterwards starting from the layer with most nodes, column indices are assigned to nodes in adjacent layers. Column indices are assigned with respect to the node's parents or children while maintaining the same ordering in the layer. In comparison to columnSimpleLeft and columnSimpleCenter, this accessor takes the adjacent layer into account and tries to assign a column index that is near the column index of the child or parent. Because nodes can be placed in the same column even though they do not have a children/parents relation with each other, nodes can overlap if nodes in different layers have different heights. Therefore, the following example sets node.heightRatio to 1 for all nodes:

# columnAdjacent.center(center) <>

Set whether the column adjacent accessor should center the adjacent node. It defaults to false. For the particular example with default options, this property has no influence and results in the exact same graph.

# d3.columnComplex() <>

Constructs a column complex accessor. Instead of doing the assignment of nodes to columns per-layer, this accessor considers the entire subtree per node. Therefore, the assignment happens depth-first.

# columnComplex.center(center) <>

Set whether the column complex accessor should center the parent node for each subtree. It defaults to false.

Arquint Column To Coord Acessors

Currently only a single column to coord accessor is provided for use with arquint.

# d3.column2CoordRect() <>

Construct a column to coordinate accessor for rectangles. This accessor assigns x0 and x1 coordinates to each node based on their layering and columnIndex. Furthermore, columnWidth and columnSeparation are used to calculate the width of each column (and hence the width of nodes in that column) resp. the distance between columns.