A library for interacting with and laying out directed acyclic graphs (DAGs)

Using d3-dag is usually a two step process. First you must create a Graph from your data. There are several available methods:

• graph - when you want to start with an empty graph and build dynamically.
• graphHierarchy - when your data already has a graph-like structure.
• graphStratify - when your graph has a tabular structure, referencing parents by id.
• graphConnect - when your graph has a link-based structure specifying pairs of node ids.
• graphJson - when you serialized your graph using JSON.stringify.

Then you lay it out using one of the provided algorithms. Each algorithm emits a LayoutResult with width and height, while updating the x and y coordinate of each node, and the control points of all links. The provided layout methods are:

• sugiyama - for a general layered representation.
• zherebko - for a simple topological layout.
• grid - for an alternate topological layout.

Example

This renders a simple graph with a -> b -> c.

// import relevant functions in whatever way is necessary
import { graphConect, sugiyama } from "d3-dag";
const builder = graphConnect(); // optionally customize with fluent interface
const graph = builder([["a", "b"], ["b", "c"]]);
const layout = sugiyama(); // optionally customize with fluent interface
const { width, height } = layout(dag);
for (const node of dag.nodes()) {
  console.log(node.data, node.x, node.y);
}
Copy

API Overview

This gives a brief overview of the design and related common themes of the api. This started trying to mimic d3-hierarchy as closely as possible, although due to different design constraints many of the apis have diverged.

Naming

Functions are named with the prefix of their class to help indicate their usage. This mimic the flat structure and naming found in d3, e.g. coordSimplex and coordGreedy are two coordinate assignment operators.

All operators create their Default variant, e.g. the function sugiyama is used to create general operators following the Sugiyama interface, but specifically always return the type DefaultSugiyama.

Types that start with Mut are mutable, incontrast to their immutable non-prefixed siblings. Note that this only refers to their inherent structural properties, exposed data can still be altered. Graphs can only be traversed while MutGraphs also allow nodes to be added.

Some interfaces start with Callable this often indicates another interface without that prefix that is the union of a const return type or an accessor, e.g. SimplexWeight and CallableSimplexWeight. In these instances the non-callable variant is the same as a function that returns a constant, but will sometimes result in faster layouts.

A few operators will default to expected data with a certain interface (which is then checked at runtime). These interfaces all start with Has, e.g. HasId.

Operators

This library mimics d3 in that you primarily interact with it through operators. Operators are just functions whos behavior might be able to be altered using a fluent api. Alterations are always immutable, returning a new object with altered behavior. In order to track parameterizations, each operator may be parametrized with an Ops type that specifies the type of various parameters. These Ops types also allow infering the type of allowable data. See Ops below.

Due to their immutability, you can't directly tweak operators that are already set, instead needing to assign new ones.

const layout = sugiyama().decross(decrossOpt());
// this creates a new decross opt, but doesn't change the existing layouts behavior
layout.decross().dist(true); // noop
// correctly assigns a new operator
const newLayout = layout.decross(layout.decross().dist(true));
Copy

Since most operators are functions of user data, their most general typing involves data of type never, e.g. data that can never be accessed. However in a lot of instances you may want operators that take unknown data, e.g. data of any time. This is actually the most narrow class of an operator. Sometimes type inference on functions can fail, and you'll see typescript errors relating to never data. This can usually be fixed by specifying types everywhere.

Ops

Ops types allow this library to track typing requirements dynamically as different callbacks are passed. The upside to this is that types are always sound, appropriately detecting the proper types of their inputs. The downside is that you need to explicitely type anonymous functions so that the types can be inferred appropriately.

For example, look at d3.line. With d3.line you specify the types at the beginning d3.line<{ x: number; y: number }>(). However, this operator is current invalid, because by default d3.line actually expects tuples. However you can then easily specify d3.line<{ x: number; y: number }>().x(({ x }) => x).y(({ y }) => y), because it's already expecting the appropriate type. The d3-dag version of this wouldn't allow setting an initial type, and instead you'd have to call it like: d3.line().x(({ x }: { x: number }) => x).y(({ y }: { y: number }) => y). At this point the input type would correctly be { x: number } & { y: number }. Keeping track of the function types in the Ops parameter allows doing this inference correctly. However, if the types aren't specified, the data type can get miss-inferred create problems downstream when data is actually passed in.

Layouts

The three layouts: sugiyama, zherebko, and grid have several common features.

• They all return the width and height of the final layout as a LayoutResult.
• They all take a NodeSize which specifies how large nodes are, and can either be a constant tuple of width and height, or a callback that's applied to each node.
• They all take a gap which specifies the minimum width and height gap between nodes.
• They all take an array of Tweaks that allows modifying the final layout in reusable ways.
• They almost all take a Rank that allows overriding the order of a subset of the nodes. For the sugiyama layout this is internal to the Sugiyama#layering.