D3-dag

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 structures for manipulating DAGs that mimics the API of d3-hierarchy as much as possible.

Installing

If you use NPM, npm i d3-dag . Otherwise you can load it using unpkg :

<script src="https://unpkg.com/d3-dag"></script>
<script>

var dag = d3.sugiyama();

</script>

Try d3-dag in your browser.

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; otherwise, you can rearrange tabular data into a DAG using

d3. dierarchy () <>

Constructs a new hierarchy operator with the default settings.

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

dierarchy. id ([ id ]) <>

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

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

dierarchy. children ([ children ]) <>

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

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

Stratify

You can rearrange tabularesque data into a DAG using.

d3. dratify () <>

Constructs a new stratify operator with the default settings.

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

dratify. id ([ id ]) <>

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

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

dratify. parentIds ([ parentIds ]) <>

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

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

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

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 .points - an array of points for how to draw the edge. Each point has an x and a y property. This might be undefined if nodes are adjacent in the hierarchy.

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. A layering accessor takes a dag and assigns every node a layer attribute from zero to the number of layers - 1. SeeSugiyama 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. 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. SeeSugiyama 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. 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. SeeSugiyama 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;
}

Sugiyama Layering Accessors

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

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.

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

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.

d3. coordSpread () <>

Construct a spread coordinate accessor. This accessor positions nodes in each layer so that they are the most spread out. This coordinate assignment is not particularly pleasing, but it 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.

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. Seefor an example of what this coordinate assignment looks like.