Hello, everyone!
Today I'm going to introduce you DAYU
Overview
After we have finalized the design draft and technical selection, the next step is to start drawing this dependency graph. The simplest composition of the dependency graph is the connection between the node Node and the node. What we have to deal with in this section is the processing of node location information. In order to determine the location information of the nodes, the nodes must be hierarchized first, and the hierarchical information depends on the dependencies between the nodes.
problem analysis
At present, our default graph is laid out from top to bottom with hierarchical nodes. The easiest thing to think of is topological sorting. Through BFS width-first traversal, the step length of each node is calculated.
Top-down BFS
As shown in the figure above, if we are a normal BFS, we will find that the D node should be the second layer, in fact D should be the third layer, so in fact, each node should take the largest step size, the implementation is as follows
function calcLayer(nodes){
var queue = [];
var maxLayer = 1;
var nodesT = nodes; // The point with an in-degree of 0 is put into the queue
for (var i = 0; i <nodesT.length; i++) {
if (nodesT[i].inputNode.length === 0) {
nodesT[i].layer = 1;
queue.push(nodesT[i]);
}
}
while(queue.length> 0){
var tNode = queue.shift();
if (tNode.outputNode && tNode.outputNode.length> 0) {
for (var j = 0; j <tNode.outputNode.length; j++) {
var outputNodeIndex = getNodeIndex(tNode.outputNode[j], nodesT);
if(outputNodeIndex <0) continue;
if (nodesT[outputNodeIndex].layer === -1) {
nodesT[outputNodeIndex].layer = tNode.layer + 1;
}else{
nodesT[outputNodeIndex].layer = Math.max(nodesT[outputNodeIndex].layer,tNode.layer + 1);
} // Update the node level, select the maximum value
maxLayer = Math.max(maxLayer, nodesT[outputNodeIndex].layer);
queue.push(nodesT[outputNodeIndex]);
}
}
}}So far, the layering is basically completed, but another situation is found, as follows:
If it is distributed according to the kind just now, the nodes with an indegree of 0 must be in the first layer. In fact, we may prefer G to be in the third layer and F to be in the second layer, as shown in the figure below.
Shown in this way, the graph will be more compact. Observing the graph, we can see that the nodes in the middle of the link have a fixed level, such as D node, but some do not have upstream nodes, such as G and F. The positions of F can indeed be selected in multiple ways. . In observation, we can know that if we go up from E to BFS, we will find that G and F nodes are the levels we need. Therefore, at this time, we need to perform BFS again from bottom to top to get a new level, and It is very important to use bottom-up results to correct top-down results .
Bottom-up BFS
function bottomToTop (nodes){
var queue = [];
var maxLayer = 1;
for (var i = 0; i <nodes.length; i++) {
if (nodes.outputNode.length === 0) {
nodes[i].layer = 1;
queue.push(nodes[i]);
}
}
while(queue.length> 0){
var tNode = queue.shift();
if (tNode.inputNode && tNode.inputNode.length> 0) {
for (var j = 0; j <tNode.inputNode.length; j++) {
var inputNodeIndex = getNodeIndex(tNode.inputNode[j], nodes);
if(inputNodeIndex <0) continue;
if (nodes[inputNodeIndex].layer === -1) {
nodes[inputNodeIndex].layer = tNode.layer + 1;
}else{
nodes[inputNodeIndex].layer = Math.max(nodes[inputNodeIndex].layer,tNode.layer + 1);
}
maxLayer = Math.max(maxLayer, nodes[inputNodeIndex].layer);
queue.push(nodes[inputNodeIndex]);
}
}
} // count from bottom to top, here to be converted from top to bottom
for(var i = 0; i <nodes.length; i++){
nodes[i].layer = maxLayer + 1-nodes[i].layer;
}}Revised result set
function fixLayer (nodesT, nodes){
for(var i = 0; i <nodesT.length; i++){
if(nodesT[i].inputNode.length === 0){
var minL = maxLayer;
var minT = maxLayer;
if(nodesT[i].outputNode && nodesT[i].outputNode.length> 0){
for(var j = 0; j <nodesT[i].outputNode.length; j++){
var inputNodeIndex = getNodeIndex(nodesT[i].outputNode[j], nodes);
var inputNodeIndexT = getNodeIndex(nodesT[i].outputNode[j], nodesT);
if(inputNodeIndex <0) continue;
if(inputNodeIndexT <0) continue; // Note that the result of the correction cannot be higher than the level of its child nodes. Here we have to compare it with its child nodes
minL = Math.min(minL, nodes[inputNodeIndex].layer-1);
minT = Math.min(minT, nodesT[inputNodeIndexT].layer-1);
}
}
nodesT[i].layer = Math.min(minL,minT);
}
}}to sum up
BFS is mainly used here. If you are familiar with this algorithm, it is still very simple. At the same time, you need to observe some actual conditions and do some optimizations!
