Visualizing layered graphs using Sugiyama method

One of the most recent add-ons to Plumbr monitoring solution happened to be the application architecture discovery & visualization. This visualization gives you an overview how your end users are accessing different infrastructure components in your infrastructure.

The feature was effectively decoupled to two individual tracks: data gathering and visualization. I was convinced that the challenges will be related to data gathering track. The visualisation was originally dismissed as a trivial exercise. After all, there are countless number of graph visualisation libraries out there, so it should be a matter of grabbing the suitable library, massaging the backend data to suitable format and off you go. Right?

Boy was I wrong.

The wrong mindset started from the requirements. Simple visuals like the following illustrated the solution we had in mind:

Apparently the real world is a whole lot messier place than the whiteboard. Luckily I discovered this quickly. The moment we had data from real world deployments I started using GraphViz to get insights into how the real world architecture models look like. Apparently it looks more like the following:

It became obvious that you just can’t toss hundreds of nodes and thousands of edges into a display hoping a human interpreter can understand anything about it. Different aspects, such as the node placings and edge crossings made the result incomprehensible. So, back to the drawing board, or, like in this case, reading research papers.

First step in this path was apparently deciding the layout method to be used. Apparently there exist several methods, each suitable for specific graph type and specific goals in mind. As the runtime application architecture happens to be represented as directed graph, we experimented with several methods designed for visualizing directed structures. The experiments quickly revealed that the best method for us is called “Sugiyama-style graph drawing” or “layered graph drawing”.

The reason why Sugiyama style suites well for visualizing the runtime application architecture is in the inherent nature of the structure we are visualizing. The graphs are directed, contain more or less limited number of nodes and only a few (ideally zero) cycles. There are always starting and terminating nodes and almost always intermediate nodes. In addition, the edges on the graph contain crossings, the number of which varies a lot. This makes convenient to draw such graphs from top to bottom with starter nodes in upper positions, and terminating nodes in lower positions (thus the term “layered graph”). Walking through different real-world deployments indeed revealed that graphs drawn in layered style were almost always visually superior to alternatives, such as spectral, force based or arc methods.

Now after understanding the method suitable for the job, the research part of the job was over and engineering questions followed. As it often happens – when you have the right question, the answers are simple. Apparently the D3 library coupled with the Dagre layout engine already implemented the Sugiyama style visualization we were after. The results quickly proved it:

Of course, there were still numerous aspects specific to the domain which visualization and layout engines were not providing, but the foundation was strong enough to sort out such issues one by one.

As a take-away I once again got a confirmation that almost every complex problem can and should be reduced to the underlying fundamental concepts. Doing so helps you to categorize the task at hand properly and seek out for the answers using the correct questions.