Using WebCola and D3.js to create hierarchical layout

• • • |

A good layout is essential to uncover the inherent structure in the connected data. Hierarchical layouts are typically used to display parent-child relationships among the graph nodes. D3.js off-the-shelf D3.js implementation of hierarchical layout cannot be used in case of the real-world data in which a child node can have multiple parent nodes. We use WebCola and D3.js to draw hierarchical graph layout using declarative constraint specification in a few lines of code.

The real world is richly interconnected and I think that our user interfaces should mimic those connections. Connections in network convey information. A cursory glance at network, if depicted right, can uncover inherent structures that are not superficially visible. Given the highly connected nature of our customers’ data, at Alyne, we decided to invest some time in a scalable visualisation which would represent the data and the connections among them in an intuitive way.

One of the use cases that will leverage it most at Alyne is our Object Library. We enable our customers to replicate their digital and physical assets within the Object Library in our application. Typically, such assets are hierarchical in nature, and we identified that network diagram can be a good tool to enable customers to have a birds-eye view over their object landscape.

Network Visualisation

One of the simplest and most powerful ways to visualise the networks is in a force directed network. Force directed networks rearranges the nodes and edges in such a way that there is a minimal amount of node overlap and edge intersections. Force directed layouts are a good representation of the networks since they unravel common patterns like node clusters, high degree nodes, connected components, etc. but they cannot depict hierarchical information in a straightforward way.

There are several excellent libraries out there such as D3 to compute the position information of the network layouts.

In this post, we are focussing particularly on the hierarchical representation of the data. D3 provides out of the box hierarchical layout to compute positions of nodes in hierarchical way. However, hierarchical layout works on the data which is in a tree-like format (implicit parent-child structure), with a constraint that one node must not have more than one parent. Therefore, we cannot use d3-hierarchy to create tree-like layouts to denote hierarchical information when the data structure looks like graph.

We can solve this problem by leveraging the D3 force directed layout in order to achieve the non-overlapping nodes and putting additional constraints on geometric node positions to achieve hierarchical layout. It can be achieved purely in D3, however, it is a bit tedious to write constraints in plain JavaScript.

There is an easier way – WebCola.

WebCola offers us a way to specify the layout information in terms of geometric constraints. Additionally, it dynamically generates constraints for flow layout, non-overlapping nodes etc. to declutter the network diagram. I like WebCola because it is simple and flexible to use.

Let us start with a simple d3 force layout network with the following data. As you can see there is no inherent parent child structure in this data. Therefore, to arrange the nodes in the hierarchical fashion, we introduce a level property per node; it denotes the position of a node in a hierarchy.

We are going to display a vanilla force directed layout for the following data using D3 force layout library.

const nodes = [
  { id: 1, level: 1 }, { id: 2, level: 2 },
  { id: 3, level: 2 }, { id: 4, level: 2 },
  { id: 5, level: 3 }, { id: 6, level: 3 },
  { id: 7, level: 3 }, { id: 8, level: 3 }, 
  { id: 9, level: 3 }, { id: 10, level: 3 },
  { id: 10, level: 3 }, { id: 11, level: 4 },
  { id: 12, level: 4 }, { id: 13, level: 4 },
  { id: 14, level: 4 }, { id: 15, level: 4 },
  { id: 16, level: 4 }
];
const links = [
  { start: 1, end: 2 },
  { start: 1, end: 3 },
  { start: 1, end: 4 },
  { start: 2, end: 5 },
  { start: 2, end: 6 },
  { start: 3, end: 7 },
  { start: 3, end: 8 },
  { start: 3, end: 9 },
  { start: 4, end: 5 },
  { start: 4, end: 9 },
  { start: 4, end: 10 },
  { source: 5, target: 11 },
  { source: 5, target: 12 },
  { source: 7, target: 13 },
  { source: 8, target: 14 },
  { source: 10, target: 15 },
  { source: 10, target: 16 },
  { source: 9, target: 16 },
];

For the sake of observability, in the visualisation above, we display the nodes with the same level attribute with the same color, and we tune the radius of node based on the level i.e. the higher the level value, the smaller the radius.

As you can see in the diagram, the force directed layout only generates the constraint for the non-overlapping nodes with the help of various forces. But there is no easy way in D3, out of the box, to arrange the data hierarchically based on the exogenous property of the node.

We can leverage WebCola to add the geometric constraints to align nodes at different levels based on its level property.

WebCola Constraints

There are different categories of constraints in WebCola such as alignment, grouping, equality constraints etc. We are going to use the alignment constraints and inequality constraints to align the nodes with the same level along the y-axis. These can be specified in JSON as follows:

{
  "type": "alignment",
  "axis": "y",
  "offsets": [
    { "node": 1, "offset": 0 },
    { "node": 2, "offset": 0 },
    { "node": 3, "offset": 0 }
  ]
}

This specified constraint would align node with indices 1,2,and 3 along the y-axis, i.e. horizontally. offset denotes the displacement of the center of node which is typically used in case of variable-sized nodes.

Now let us try to arrange our network as a tree. We need to have two types of constraints as follows:

  1. Alignment constraint – We want the nodes with the same level property to have the same y coordinate
  2. Equality constraint – The nodes on the same level should have a margin on the left and right for better readability.

So in our example, we group the nodes by level attribute and for every node in the same group, we specify alignment constraint along y-axis. Moreover, in each group, we assign positional equality constraint along x-axis with gap of 50 pixels; it helps us declutter the nodes on the same level. The gap value can be derived dynamically based on the size of the node but that is a rendering specific decision.

const constraints = [];
const { nodes, links } = loadData();
const groups = _.groupBy(nodes, "level");

for (const level of Object.keys(groups)) {
  const nodeGroup = groups[level];
  const constraint = {
    type: "alignment",
    axis: "y",
    offsets: [],
  };
  let prevNodeId = -1;
  for (const node of nodeGroup) {
    constraint.offsets.push({
      node: _.findIndex(nodes, (d) => d.id === node.id),
      offset: 0,
    });

    if (prevNodeId !== -1) {
      constraints.push({
        axis: "x",
        left: _.findIndex(nodes, (d) => d.id === prevNodeId),
        right: _.findIndex(nodes, (d) => d.id === node.id),
        gap: 50,
      });
    }

    prevNodeId = node.id;
  }

  constraints.push(constraint);
}

d3Cola
  .nodes(nodes)
  .links(links)
  .constraints(constraints)
  .flowLayout("y", 80)
  .linkDistance(50)
  .symmetricDiffLinkLengths(40)
  .avoidOverlaps(true)
  .on("tick", ticked)
  .start(10, 40, 50);

The constraints based on the level attribute of the node are user-defined constraints. In addition to this user-defined constraints, WebCola dynamically generate constraints to determine the length of the links (linkDistance, flowLayout), non-overlapping constraint (avoidOverlaps) etc.

We perform the simulation in which we apply dynamically generated constraints for 10 iterations, user-defined constraints for 40 iterations and both the sets of constraints together for 50 iterations. These numbers can be varied heuristically based on number of nodes and constraints in the simulation.

With these constraints, we get a tree-like layout using force directed simulation despite not having the tree like data structure. You can see that the nodes with the same level value have the same color and are located at the same height. Moreover, our visualisation is stable to several nodes having multiple parents.

This is just a glimpse of how WebCola can be used to apply different layouts to the network diagram in a few lines of code. I would recommend you to check out SetCola which is a high level language for creating WebCola constraints and with a few lines of codes, you can create complex graph layouts.

[content_block id=53166]