How does the front end draw a DAG diagram?

This time, I will share an experience I had with a team in the company half a year ago. I will pick out a small part of the functions that are more common and irrelevant to business.

What is a DAG diagram?

DAG stands for Directed Acyclic Graph, Directed Acyclic Graph is a kind of logical image.

A graph is called a DAG graph if it consists of independent nodes and directional lines, and it is impossible for any node to return to itself by traversing the lines.

In simple terms, the entire diagram rendering has a unified direction, and does not form any loop.

For a more professional introduction, go to Wikipedia.

Are there any additional constraints in the business?

It’s boring to talk about DAG drawing in general, because DAG images can be drawn in any way. And standard DAG images allow for multiple starts and ends.

In our business, we have made a more detailed specification design for the application of DAG diagrams, which is related to rendering as follows:

1. A DAG used by a business needs to have a start node and only one end node is allowed. It is similar to the normal flow chart, except that the flow of the business is one-way.

2. Nodes are divided into two types: one is the functional node that bears the business, and the other is the virtual node that diverges and collects branches. They always come in pairs, similar to {and} in the for loop.

Figure 1. Screenshot of DAG example

DAG data model design

Now that you know what a DAG diagram is, the business specification, and the renderings, it’s time to get started.

In order to render workflow DAG charts, we need to build a clean and rigorous data model to support, and need related algorithms to assist rendering and editing.

According to the two characteristics of DAG chart, directed and acyclic, we make two layers of abstraction on the data model.

The first layer is the diagram itself, which contains layout information, node list, association list, and is equipped with rich method support. It is the upper model that defines the entire DAG.

The second layer is node and associated relation.

Node holds the detailed configuration of individual nodes and screen coordinate data.

Relation model is relatively simple, which only describes the start node ID and target node ID, along with screen coordinate data.

With the help of these two layers of data model design, flow information of a DAG chart and data storage of each node can be described.

Figure 2. Data model of DAG chart

DAG rendering algorithm

Before we talk about rendering algorithms, let’s talk about the logic of rendering diagrams. Conventional diagrams have two rendering logic, one is free drag and drop, and the other is adaptive rendering.

Users can drag and drop nodes to any position at will. The problem is that adding and deleting nodes may make the diagram too messy.

However, adaptive rendering needs to adjust the position of nodes according to the chart data, and the neat layout will be displayed regardless of the addition and deletion of nodes. The disadvantage is also obvious, the user can not freely adjust the node position.

Based on the nature of our business, we eventually adopted the latter solution, adaptive rendering.

I believe you have noticed that in the data model section above, nodes and association lines have screen coordinate data. How are coordinates calculated here?

4.1. Sample code

Let’s expand with an example. There are eight nodes on the canvas, and the relationship is shown in the following data:

let nodeList = ['a'.'b'.'c'.'d'.'e'.'f'.'g'.'h']
let relationList = [
  ['a'.'b'],
  ['a'.'c'],
  ['b'.'d'],
  ['d'.'h'],
  ['c'.'e'],
  ['c'.'f'],
  ['e'.'g'],
  ['f'.'g'],
  ['g'.'h']]Copy the code

Hopefully you can see what these two arrays do, which is important because they correspond to the list of nodes and the list of lines in the data model. You can take out a piece of paper and try to draw an outline of the picture.

Here’s a quick look at the algorithms we used, in order of rendering.

4.2. Find the starting point of the graph

So this is the first algorithm that we’re going to need, and if you look at the data, you might not have a clue, but if you sort of simplify the logic, you’ll be able to quickly write a way to find the starting point.

In a normal DAG diagram, every node except the starting point and end point has upstream and downstream relationships, while the starting point has only downstream nodes and the end point has only upstream nodes.

Therefore, we can describe the starting point as: in all relation, the node that exists only in the upstream and not in the downstream is the starting point.

Based on this logic, you can convert relationList to:

// Raw association list
let relationList = [
  ['a'.'b'],
  ['a'.'c'],
  ['b'.'d'],
  ['d'.'h'],
  ['c'.'e'],
  ['c'.'f'],
  ['e'.'g'],
  ['f'.'g'],
  ['g'.'h']]// Enumerates all upstream and downstream data
let fromList = ['a'.'a'.'b'.'d'.'c'.'c'.'e'.'f'.'g']
let toList = ['b'.'c'.'d'.'h'.'e'.'f'.'g'.'g'.'h']

// do the reprocessing
fromList = ['a'.'b'.'d'.'c'.'e'.'f'.'g']
toList = ['b'.'c'.'d'.'h'.'e'.'f'.'g']

// Remove nodes in both upstream and downstream lists
fromList = ['a']
toList = ['h']

// Get the starting point and the ending point
let root = fromList[0] // 'a'
let end = toList[0] // 'h'

Copy the code

By doing this transformation, we have a starting point and an ending point, isn’t it easy?

Of course, there are two exceptions to deal with here!

First, fromList or toList may be empty. As long as either of them is empty, the chart must have a circular structure, which does not conform to the definition of DAG, that is, the data is illegal.

The other is if the fromList or toList return length is greater than one, that is, there are multiple starts or ends. Although this meets the definition of DAG, it does not meet the constraints of our business on DAG. Such exceptions can also be classified as data illegal.

4.3. Find all paths from the start to the end

This step is the key to building the visualization, and subsequent renderings will be based on the results of this calculation.

What does it mean to find the entire path from start to end? Simply put, it lists all the steps from the starting point to the end point, similar to the itinerary planning of Baidu map navigation.

Compared to navigation, the path traversal of a DAG chart is relatively simple, because once the starting point is clear, we simply enumerate the entire path by recursively looking downstream of the node. The process is as follows:

// Raw association list
let relationList = [
  ['a'.'b'],
  ['a'.'c'],
  ['b'.'d'],
  ['d'.'h'],
  ['c'.'e'],
  ['c'.'f'],
  ['e'.'g'],
  ['f'.'g'],
  ['g'.'h']]// The starting point found in the previous step
let root = 'a'

// Define the method: find the downstream node
const findLowerNodes = nodeName= > {
	let lowerNodes = []
	let hasUpperNodeRelations = relationList.forEach(item= > {
    if (item[0] === nodeName) {
			lowerNodes.push(item[1])}})return lowerNodes
}
// Define the method: recursively find a node
const recursionGetPath = (nodeName, basePath, pathList) = > {
	basePath = basePath || []
  pathList = pathList || []
	basePath.push(nodeName)
	let lowerNodes = findLowerNodes(nodeName)
	lowerNodes.forEach(lowerNodeName= > {
		// Make a copy of path
		let newBasePath = basePath.slice(0)
		recursionGetPath(lowerNodeName, newBasePath, pathList)
	})
	if (lowerNodes.length === 0) {
		pathList.push(basePath)
	}
  return pathList
}
// Start from the starting point 'a' and recursively find the downstream node
let pathList = recursionGetPath(root)

// Get the path list
pathList = [
	["a"."b"."d"."h"],
	["a"."c"."e"."g"."h"],
	["a"."c"."f"."g"."h"]]Copy the code

Through this process, we can obtain the following information: the graph has three paths from the starting point to the end point, the largest path needs five nodes, and the shortest one only needs four nodes.

If you can’t see what this pathList does, let’s keep going.

4.4. Build the prototype of flow chart

The drawing of the flow chart requires a two-dimensional structure. All the paths in the previous step can be used as the basis of the two-dimensional structure. Let’s do the transformation again.

// The result of the previous step
pathList = [
	["a"."b"."d"."h"],
	["a"."c"."e"."g"."h"],
	["a"."c"."f"."g"."h"]]// Rotate the two-dimensional array 90 degrees
let map = [
  ['a'.'a'.'a'],
  ['c'.'c'.'b'],
  ['f'.'e'.'d'],
  ['g'.'g'.'h'],
  ['h'.'h']]// The line is not heavy
let map = [
  ['a'],
  ['c'.'b'],
  ['f'.'e'.'d'],
  ['g'.'h'],
  ['h']]// Global deduplication, with priority reserved for the lower nodes
let map = [
  ['a'],
  ['c'.'b'],
  ['f'.'e'.'d'],
  ['g'],
  ['h']]Copy the code

If you look at the data structure of map and you feel a little bit interesting, let’s move on.

4.5. Draw flow charts

The map of the previous step is the preparation of DAG diagram drawing. Then we combine relationList to further explain the data.

// The result of the previous step
let map = [
  ['a'],
  ['c'.'b'],
  ['f'.'e'.'d'],
  ['g'],
  ['h']]// Raw association list
let relationList = [
  ['a'.'b'],
  ['a'.'c'],
  ['b'.'d'],
  ['d'.'h'],
  ['c'.'e'],
  ['c'.'f'],
  ['e'.'g'],
  ['f'.'g'],
  ['g'.'h']]/ * * * DAG graphical structure left ↘ * * a * b * c left ↘ ↘ * f d e * left ↙ ↙ left ↙ ↙ * * h * * * g /
Copy the code

At this point, the entire DAG diagram is already in shape.

The ‘A’ ‘b’ ‘C’ in the whole example is only illustrative. As mentioned in figure 2, DAG chart data model, each node is an object with a separate structure and contains the location information displayed on the screen. This step is the time to calculate the screen coordinates of the node.

4.5.1 Calculate the coordinates of each node

In the data model section, the Map -> Layout section records the canvas size at a specific time and pre-configures the horizontal spacing range and vertical spacing range of nodes.

The coordinates of each node can be obtained by calculating the number of map rows and the maximum width calculated in the previous step and matching the map -> Layout configuration items.

The code implementation will not be expanded here. It should be noted that the horizontal position of each node should be adjusted appropriately according to the relationship between upstream and downstream nodes to ensure visual stability.

4.5.2 Calculate the coordinates of the associated lines

The coordinate calculation of the correlation line is put in the last step, because this is the easiest step, we just need to copy the coordinates of the start and end nodes.

4.5.3 Page rendering

Because the coordinates of each node and line have been calculated, the next is to draw gourd gourd gourd.

We can use SVG, Canvas, CSS, or D3 to draw.

Figure 3. DAG sample effect sketch

At the end

You may scold the play: “I promised to teach me how to draw DAG, but I didn’t write a line of drawing code!”

That’s the way we do complex business, and if you think logically, one, two, three steps out, you can see what you want in the end.

Like the DAG diagrams shared in this article, when no tools are available, if you can design the data structure clearly from the beginning and the data transformation process is clearly defined, the final drawing becomes relatively less important.

---

---

Author: Dramatis personae

Originally published by: Xiaoju Inn

Link: bh-lay.com/blog/1ft2kl…