Demo: https://vizstack.github.io/nodal/docs/
To be honest, we've been trying to avoid having to write a graph library for a year now. "Surely one of the open-source libraries is powerful enough to do what we need!" we'd exclaim hopefully. Alas, it was not to be. After rewriting our entire DagLayout Vizstack component twice using different open-source libraries, we're no longer the innocents we used to be. We've seen the horrors of this world.
But we can't give up on graphs. So many software abstractions are best visualized with them: dependencies, distributed systems, neural networks, computation graphs, association nets, linked lists ...
So, we've decided to write a graph layout library, and we're trying our best to do it right. These are some of the features that we've desparately wanted:
But we also recognize that there may be features other developers want that we haven't thought of. That's why, unlike most of the solutions out there, we adopt a much more modular and compositional design, inspired by libraries like ProseMirror. By developing clean abstractions in a layered architecture, we'll allow power users to customize as much as they want, while also providing sensible presets for less intense users.
The first step was to familarize ourselves with some of the state-of-the-art techniques by reading the literature. Luckily, coming from a background in machine learning, we felt somewhat comfortable with the math that the field applies, e.g. constrained optimization, majorization, and gradient descent.
These were the papers we found most useful:
SGD rules! That's a platitude in the ML community, but apparently its a relatively new in its application to graph layout. In this paper, the authors adopt a spring model with ideal spring length between nodes proportional to their graph distance:
Using repeated constrain projection with a decaying learning rate, they are able to achieve much lower overall stress compared to existing methods, like force majorization.
This paper provides a great treatment of the difference between the Spring model (Kamada-Kawai) and Spring-Electrical model (Fruchterman-Reigold). It also show how the Spring-Electrical model can be made to work for graphs with a huge number of nodes by (1) using a quadtree-based approximation of long-range pairwise forces, (2) multilevel graph coarsening to lay out global clusters before focusing on local details.
This paper describes a general class of Euclidean distance constraint that can be used to build a variety of higher-level constraints. It's written by the same professor that maintains the WebCola graph layout library, though WebCola uses a less advanced version of the constraint and require quadratic programming techniques to solve. The main idea is to enforce a distance between a pair of points, optionally after projection onto a specified axis vector:
It turns out that the gradient for this constraint is easy to compute geometrically, and through repeated iterative projection (inspired by computer simulation cloth models), can produce remarkably stiff constraint satisfaction.
"Octilinear force-directed layout with mental map preservation for schematic diagrams," Chivers & Rodgers, 2014.
We were curious about this paper because we greatly admire metro map design: it helps convey complex information to people in a digestable and even aesthetically pleasing way. This paper focuses on how force-directed techniques can be used to layout an octilinear metro map by enforcing edge orientation constraints. Rather than imposing the constraints from the start in addition with the repulsive/attractive forces, they induce a curriculum that interpolates between the two for the best results.
This paper also is written by Dwyer, and covers how edges can be routed around obstacles on its way from its source to its target. We mainly chose this paper because we wanted to do edge routing to produce orthogonal edges and/or edges with few crossings. The technique uses stress majorization to reduce stress on a graph by moving nodes and edge bend points.
As stated above, our goal was to design a highly modular and extensible library that allows fiddling with low-level details and high-level presets. To this end, we developed a layered architecture:
-
Optim Layer: Low-level manipulation of
Vectors withGradients. AnOptimizerprovides a scheme for adjusting the learning rate multiplier on the gradient. We implemented a constant rate (BasicOptimizer) and adaptive (TrustRegionOptimizer) version, but also think it would be interesting to port some of the ideas from the ML field, e.g.RMSPropOptimizer,AdamOptimizer. -
Graph Layer: Higher-level constructs like
NodeandEdge(produced from lightweightNodeSchemaandEdgeSchema) are just collections ofVectorobject. Constraints and forces can be exerted on theirVectorcomponents through functions that generateGradients. The entire graph is stored in aStoragewhich may have different features including performant spatial lookup of elements and complex manipulation/traversal of the graph structure. A developer writes aLayout, which is a graph layout procedure, e.g. i iterations of force application, then j iteractions of constrain projection, repeated for N steps.
We encourage you to check out the code! https://github.com/vizstack/nodal/tree/master/src
Interactive demo: https://vizstack.github.io/nodal/docs/
Vizstack Core schema of visualization data structures.
https://www.npmjs.com/package/@vizstack/schema
Vizstack Core components to render visualizations with React.
https://www.npmjs.com/package/@vizstack/viewer
Vizstack Core bindings for Javascript and Typescript.
https://www.npmjs.com/package/@vizstack/js
Multi-platform and web-based logger, built with Vizstack.