Js to achieve automatic flow graph layout algorithm?

the real problem at present: we need a general method of drawing the connection path drawLinePath

.
let drawLinePath = (node1,node2nodes) => {
  //node1node2
  return linePath;
}

more: according to the current algorithm and demand analysis, the introduction of force-guided layout algorithm may be the optimal solution. The current practice is to use Webgraphviz to render the svg artboard when you need automatic layout, and then set the dom generated by setTimeout (Viz rendering to be not available in the main thread), get the information and coordinates of the newly generated dom node in it , and assign the coordinate information to the real flow graph artboard. At this point, the svg artboard generated by Viz () retired and destroyed the body.

as a result, the coordinate information is obtained, the relative position of the difference between the coordinates and the connection path.
found that there is an error between the coordinates obtained and the coordinates of the nodes in the real artboard (this can only be adjusted manually). The main thing missing in
is the connection path, and there is no unified connection formula for . To be exact, it is that you do not know the connection rules in viz .

I have tried to read the d3 source code in the past two days (because I can"t find any other js code implementation or easy-to-solve examples of force-guided layout), but I"m still blinded.

< hr >

original problem description:
objective: to give the json data of nodes and connections, and draw a flow graph with vue. The flow graph in the artboard is composed of several directed graphs , the artboard in the flow graph is required to be scaled , the node size can be set , the coordinates can be obtained , the can fill the picture , the label information can be displayed below, and the node and connection all have event listeners , the node is mobile , and the connection position of is updated accordingly < / strong. The most important thing is that the artboard can be automatically laid out .

json:
{
    "nodes":{
      "node1":{
        "id": "node1",
        "imgSrc": "img1",
        "label": "1",
        "width": "50",
        "height": "50",
      },
      "node2":{
        "id": "node2",
        "imgSrc": "img2",
        "label": "2",
        "width": "50",
        "height": "50",
      },
      "node2":{
        "id": "node2",
        "imgSrc": "img1",
        "label": "2",
        "width": "50",
        "height": "50",
      }
    },
    "lines":[
      ["node1","node2"] //node1->node2
    ]
}

clipboard.png

the above picture is previously implemented with vue+svg, without other frameworks and libraries. The above requirements have been realized, that is, the automatic layout algorithm is a bit rough.
now want to optimize the automatic layout algorithm, automatic layout and connection of the path drawing is related, do not want to have line overlap to affect the connection judgment.
there is a force-guided layout on the Internet, and I think this may achieve my goal. But I don"t know how to use it, and how to set the connection path after using it. I hope the old driver can give me some advice

.

this is a very complex project, it is recommended to refer to the D3 implementation code about the force directed graph processing algorithm.
in addition, I provide another idea:
all paths are generated recursively, one branch at a time (depth first), so that for one branch, the location of each node can be determined, so that there is no crossover problem. Because all the later drawn nodes are drawn on the existing basis, the existing nodes are positioned, such as

root--node1--node1-1--node1-1-1
    |      |        |-node1-1-2
    |      |
    |      |-node1-2--node1-2-1
    |      |        |-node1-2-2
    |      |
    |      |-node1-3
    |
    |-node2
    
    ...         

for flow graph (directed acyclic graph) layout, it is not recommended to guide the layout by force. You can use bary-center algorithm to scan from left to right, and the order of the points in the next layer is obtained by the average value of the parent node in the upper layer. After getting the order, the specific coordinates are calculated, and then scanned from right to left until the iteration reaches the appropriate line crossing rate. You can refer to the d3-sankey implementation of d3 for
, or you can refer to dagre.js (both of which I call directly). ).

Menu