How to Build a Graph Visualization Engine and Why You Shouldn’t

Building something from scratch is rarely a good idea. Especially in the rich world of web technologies full of solutions for problems we didn’t even know existed. In our first iteration of Memgraph Lab, we did just that - we used Vis.js for our graph visualization engine. But that solution turned into a nightmare because the library was deprecated and didn’t allow multithreading. User experience (UX) was a disaster since rendering a large graph would block the entire application. You can read about our troubles here. So this time around, in our pursuit to create the go-to interactive graph development environment, we made the difficult decision to create our own library - Orb. Let us take you on the journey of how we did it, along with the challenges that we faced.

First, we’ll cover the general architecture of the library - how Orb handles data structures and different views, and how we organized our developer API through events and callbacks.

Then, we’ll take a deeper dive into the simulator engine - how the resulting graph layout calculations are performed using d3-force in parallel through WebWorkers.

After that, we’ll touch upon the HTML5 Canvas rendering engine - how to optimize it and how we structured it so you can easily add your own views.

And finally, how to neatly package everything together using TypeScript and Webpack.

Orb structure

In the image below you can see the high-level architecture of the Orb. There are three main parts that we’ll dig deeper into - Data (modal), View, and Events.

Orb Data

Orb Data is actually an in-memory graph data structure defined by nodes and edges connecting those nodes. It contains all the information about each node and edge:

• User-defined information upon node/edge creation: Any property node/edge has is available in other Orb components (views, events).
• Style information: Size, color, width, background image, and so on. You can define a default style for the whole graph and set up specific style properties for each node/edge.
• Graph context information: Each edge will link to the start and end node it connects, and each node will link to inbound and outbound edges as well as adjacent nodes.
• State information: Indicates if a node/edge is selected, hovered, or none of those.
• Graph topology information: Depending on how many edges there are between two nodes, each edge will be specified with an edge line type to avoid overlapping: straight, curved, or circular line (connecting the same node). Check the example below to see how edge line type changes depending on the number of edges between the nodes:

The example below first initializes a graph with three nodes and two edges. Then an additional edge is merged into the existing graph. Lastly, a node is removed from the graph by its unique ID:

const nodes = [
  { id: 1, label: 'Orb' },
  { id: 2, label: 'Graph' },
  { id: 3, label: 'Canvas' },
];
const edges = [
  { id: 1, start: 1, end: 2, label: 'DRAWS' },
  { id: 2, start: 2, end: 3, label: 'ON' },
];
// Initialize the graph with input nodes and edges
orb.data.setup({ nodes, edges });

const newEdges = [
  { id: 3, start: 1, end: 2, label: 'HANDLES' },
];
// Add (merge) new edge to the existing graph nodes and edges
orb.data.merge({ edges: newEdges });

// Remove the node with unique id = 3
orb.data.remove({ nodeIds: [3] });

Orb View

Orb View is what makes a graph visible and intractable in the defined HTML container. The main purpose of the View is to do two things:

• Layout and position the graph - done by the Simulator, which uses a d3-force library to simulate physical forces on particles. It supports the main thread simulation and offloaded simulation using WebWorkers for a performance boost.
• Render the graph - done by the Renderer, which takes the graph model, and graph positions (defined by a Simulator) and renders the graph within the <canvas> HTML element. Currently, Orb only uses CanvasRenderingContext2D Renderer, but there is a plan to add support for the WebGL Renderer too.

In the image below, you can see a snippet of the Pandora Papers dataset rendered with the default Orb’s view:

Orb Events

Orb Events is an implementation of the in-browser EventEmitter that offers several events (e.g. node/edge clicked, render started/ended, node dragged, etc.). You can subscribe to those events and do any action on top of them. A full list of events that the Orb emits can be found here.

The example below shows how to subscribe to a node click event. If a node is clicked on, a message is printed out in the console and the node’s title is expanded by the string “- Clicked!”:

orb.events.on('node-click', (event) => {
  console.log('Node is clicked: ', event.node);
  node.data.title = `${node.data.title} - Clicked!`
});

Offloading graph position computation with WebWorkers

One of the key requirements of the library is that the computation of positions is done in a separate thread. Otherwise, the computationally expensive operations would block the main thread and severely impact the user experience.

For WebWorkers to actually work, it's critical that the most computationally expensive operations do not depend on the DOM (Document Object Model). This is a limitation of WebWorkers, as they do not have access to the browser window reference, so any library with that dependency will not work with WebWorkers.

In our scenario, the expensive operations are physics simulations - algorithms that stabilize the graph to produce the final layout. The rendering part is done relatively quickly. From an architectural point of view, it's important that the simulation library is separate from the rendering library.

This is why we chose the d3-force library, which is a part of the D3.js. In the Benchmarking blog post we explained our decision-making process in detail.

WebWorkers

We won’t go in-depth on how to use WebWorkers, since there are a ton of articles explaining it far better than we ever could. It’s important to us that WebWorks rely on an isolated JavaScript file to execute operations in a separate thread. This thread then communicates with the main browser thread via events and messages. We use WebWorkers to offload the computationally expensive physics simulations from d3-force to calculate the final graph layout. These operations are pure JavaScript that don’t depend on the browser window reference.

But what happens when, for whatever reason, WebWorkers aren’t available in the host environment? In that case, we also provided a fallback implementation which is done completely in the main browser thread.

Combining two words - parallel and main thread

So we have 2 main contexts for our simulations - the parallel background thread context and the main thread context. In the image below, you can see how we organized the two to use the same engine to avoid code duplication and difficult maintenance.

First, we separated all the engine functionality into a separate entity called D3SimulatorEngine. This class actually implements all of the data and simulation logic using d3-force.

Then we created two classes: MainThreadSimulator and WebWorkerSimulator. Both of these classes implement a common interface called ISimulator. They essentially serve as a wrapper for the D3SimulatorEngine, which does the actual computation through d3-force.

We then expose a factory that tries to return a WebWorkerSimulator if possible, otherwise, it falls back to the MainThreadSimulator. We then communicate with the simulator through an event emitter with callbacks.

Challenges of the canvas rendering

On Orb initialization, you need to provide a container, HTML element, where Orb will create all necessary HTML elements to render various elements such as background, foreground, graph structure, shadows, etc.

One of the key created HTML elements is the <canvas> element. Renderer class creates CanvasRenderingContext2D which is used for drawing shapes, text, images, and other objects. As we used vis.js before creating Orb, credit for some of the drawing logic in Orb (shapes, arrows, curved lines) goes to the developers who created it. They did a great job, and we didn’t want to reinvent the wheel. Canvas API with CanvasRenderingContext2D is easy to use and offers a lot of API methods to work with, but there are a few items that we still need to optimize in the Orb, especially for rendering large graphs:

• Redraw only the visible section of the graph - currently, the whole graph is rerendered.
• Group nodes and edges with equal style properties to draw them in batches with an efficient canvas pipeline (draw blue nodes first, then red nodes, etc.) - currently there is only a rule to draw selected or hovered nodes/edges last because of the transparency of other nodes/edges.
• Add strategies in drawing text and shadows as they degrade performance considerably.
• Add offscreen canvas to pre-render similar or repeating objects.
• Add support for WebGL rendering.

All of these are solvable to some extent. You can read more about the canvas rendering optimizations on MDN web docs.

Creating new custom views

Currently, Orb comes with two different views to use: DefaultView and MapView. DefaultView is, as the name suggests, a default view where the graph is rendered on a blank canvas. MapView, on the other hand, renders a graph on top of the map background where each node needs to have a geo position (latitude and longitude). MapView uses Leaflet which is the leading open-source JavaScript library for interactive maps.

This is what it looks like to change the view to MapView in Orb:

orb.setView((context) => new MapView(context, {
  getGeoPosition: (node) => ({
    lat: node.data.latitude,
    lng: node.data.longitude,
  }),
}));

In the image below, you can see the result of Orb’s MapView where the graph model of capital cities is rendered on top of the map background provided by MapBox.

The whole idea behind Orb’s views is to allow custom views. Orb is not at that stage yet, but our plan is to enable an AbstractView with all the Orb engines like Simulator, and Renderer where you can implement your own logic on how and where to render a graph model, e.g. rendering a graph with fixed x and y coordinates on a custom background image.

Packaging

Of course, none of this would matter if people weren’t able to use our library easily. We spent a great deal of time configuring Webpack and figuring out how to properly set up the package so it can be consumed in a browser context as well as in other TypeScript and JavaScript projects.

There are two main ways of using Orb. If you are using it in a browser environment by importing a script form here, you won’t have WebWorker support because it’s not a local script. If you’re using Orb in your JavaScript/TypeScript project through npm install, then you have full access to WebWorkers.

Conclusion

Visualizing graphs is difficult and we’ve spent a great deal of time trying to properly structure a library that can handle such a task seamlessly. Orb uses d3-force in the background to calculate graph layouts and does so by conveniently juggling between WebWorkers and the browser main thread behind the scenes.

Orb offers a flexible graph styling mechanism that allows you to decorate your graphs any way you want to. Besides the default graph layout view, Orb includes a map view, which uses Leaflet to position your nodes on a map by providing latitudes and longitudes. And if that doesn’t fit your needs, feel free to contribute and create your own custom views - it’s as easy as extending an existing one or implementing the provided interface.

The HTML5 Canvas rendering engine is partly derived from Vis, but we’ve left space to introduce other rendering engines such as a WebGL-based implementation in the future.

Feel free to check out Orb on GitHub, give us a star, experiment, play or contribute to it! If you want to see more examples and how Orb can be used, check the blog post: How to use Orb.