图灵奖的获得者，Pascal 之父——Niklaus Wirth ，有个经典说法：“算法+数据结构=程序”（Algorithm+Data Structures=Programs）。咱们以这个说法为思路，看在流程画布这个场景中，如何利用数据结构和算法来解决理论的业务需要。
树和图
在数据结构中，对树的形容为：树是n（n≥0）个结点的无限集，它或为空树（n=0）；或为非空树，对于非空树T：
- 有且仅有一个称之为根的结点；
- 除根结点以外的其余结点可分为m（m>0）个互不相交的无限集T1, T2, …, Tm,其中每一个汇合自身又是一棵树，并且称为根的子树（SubTree）。
由上述形容能够看出，树的构造定义是一个递归的定义，即在树的定义中又用到树的定义，它道出了树的固有个性。树罕用的存储构造有：顺序存储、链式存储。
对图的形容为：图G由两个汇合V和E组成，记为G=(V, E)，其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷汇合。V(G)为图的顶点汇合，不能够为空；E(G)为图的边汇合，能够为空。如果边集E(G)为有向边的汇合，则称图为有向图；如果边集E(G)为无向边的汇合，则称图为无向图。
图罕用的存储构造有：邻接矩阵、邻接表、十字链表、邻接多重表。
树和图是画布这个场景中关联度最高的两种数据结构（当然，最根底的还是链表构造）。
G6
G6 是一个图可视化引擎。它提供了图的绘制、布局、剖析、交互、动画等图可视化的根底能力，借助 G6 的能力，咱们能够疾速搭建本人的图剖析或图编辑利用。流程画布底层便应用了 antv/g6 来实现图可视化的性能。
依据对其性能应用水平的不同，咱们梳理 G6 的外围概念如下：
G6中对图 Graph 接管的参数定义如下：
export interface GraphData { nodes?: NodeConfig[]; edges?: EdgeConfig[]; combos?: ComboConfig[]; [key: string]: any;}官网给出的最简略的疾速开始的 demo 代码片段如下：
const data = { nodes: [ { id: 'node1', x: 100, y: 200, }, { id: 'node2', x: 300, y: 200, }, ], edges: [ { source: 'node1', target: 'node2', }, ],}; const graph = new G6.Graph({ container: 'mountNode', width: 800, height: 500,});graph.data(data);graph.render();由下面两段代码能够看出，nodes 和 edges 是对图构造中顶点汇合和边汇合的数据表示，同时通过 combos 字段实现了顶点分组的能力。看到此处，咱们能够得出结论：真正的元素绘制局部其实无需关怀，咱们要做的更多是对顶点集和边集数据的治理。
顶点项中的 x、y 字段是可选的，当数据中没有节点地位信息，或者数据中的地位信息不满足需要时，须要借助一些布局算法对图进行布局。
由G6的外围概念能够看到，框架自身曾经实现了多种经典布局算法，其中不乏以树图为主的脑图布局，但依据需要形容中对UI设计和交互的定义，现有布局算法无奈满足咱们的需要。因而咱们不仅要实现自定义顶点、边，还要实时计算每个顶点的坐标值来实现自定义布局的逻辑。
G6 在提供更高的灵活性的同时，也因解决数据带来了不可避免的复杂性，节点的坐标值计算和节点治理（新增、删除）便是其中的典型场景。
数据结构定义
G6 自身是对图可视化的实现，但流程画布这个场景中，咱们在真正的实现中采纳了链式存储的树结构。
理论开发过程中，对节点的数据类型定义如下：
interface IWorkflowNode<T extends WorkflowNodeParamsXOR> { id: string; type: TWorkflowNodeType; params: T; parent: string[]; children: string[];}阐明：
- parent 为父节点援用（以 id 模式存储）
- children 为子节点援用（以 id 模式存储）
满足二叉数的双向链表构造
算法
咱们须要对数据进行解决的点次要有两个：
- 节点坐标计算
- 节点删除时，对以后节点、关联边和子树的删除
基于上述的数据结构定义，实现上述两点性能均用到同一个算法：二叉树的深度优先、前序遍历算法（采纳递归解法）。
如上图，如果采纳深度优先、前序遍历算法，则拜访节点的程序应为：1、2、4、8、5、9、3、6、7。
到此为止，咱们的准备常识曾经全副给出，接下来是具体的实现细节。
实现
假如当初有如下图所示的一张画布：
nodes 数据细节如下（疏忽了局部与坐标计算无关的字段）。
[ { id: 'root-1630463843227', type: 'start', parent: [], children: ['root-1630463843227-0'], }, { id: 'root-1630463843227-0', type: 'strategy', parent: ['root-1630463843227'], children: ['root-1630463843227-0-0', 'root-1630463843227-0-1'], }, { id: 'root-1630463843227-0-0', type: 'strategy', parent: ['root-1630463843227-0'], children: ['root-1630463843227-0-0-0', 'root-1630463843227-0-0-1'], }, { id: 'root-1630463843227-0-0-0', type: 'action', parent: ['root-1630463843227-0-0'], children: [], }, { id: 'root-1630463843227-0-0-1', type: 'trigger', parent: ['root-1630463843227-0-0'], children: ['root-1630463843227-0-0-1-0'], }, { id: 'root-1630463843227-0-0-1-0', type: 'action', parent: ['root-1630463843227-0-0-1'], children: [], }, { id: 'root-1630463843227-0-1', type: 'action', parent: ['root-1630463843227-0'], children: [], },]坐标计算
1、数据预处理
- 从 nodes 和 edges 的数组列表模式生成依据 id 为 key 的对象类型，不便后续取值
- y累计偏移量 MaxOffsetY 置为 0
- 选定起始节点并设定起始坐标为(0, 0)
- 开始递归求解每个节点的坐标
/*** 计算依赖的相干变量* indentX：x 方向固定偏移量* gapVertical: y 方向固定偏移量* MaxOffsetY: 以后节点计算时 y 方向的累计偏移量*/const indentX = 370;const gapVertical = 50;const MaxOffsetY = 0; const parseWorkflowToDraw = ( workflow: IWorkflow, resolveNode: ResolveNode): [GraphData, IWorkflowNodeMap] => { const nodes = workflow.nodes; const edges = workflow.edges; const nodeMap: IWorkflowNodeMap = {}; const edgeMap: IWorkflowEdgeMap = {}; let rootId = ''; for (const item of nodes) { if (item.type === 'start') { rootId = item.id; } nodeMap[item.id] = { ...item }; } for (const edge of edges) { edgeMap[edge.target] = { ...edge }; } if (!rootId) { throw new Error('Workflow 节点类型谬误，无起始节点！'); } MaxOffsetY = 0; const graphData: GraphData = { nodes: [], edges, }; parseWorkflowToGraphData( nodeMap[rootId], 0, 0, null, [0, 0], nodeMap, edgeMap, resolveNode, graphData ); return [graphData, nodeMap];};2、坐标计算
- 数据预处理（更多的是注入后续自定义节点时draw函数所需的数据）
- 计算本身节点尺寸
- 依据父节点地位、是否为分支流程及分支流程中的地位索引计算以后地位
- 依据系列条件判断是否须要在 y 方向上进行偏移量累加
- 如果有 children，则循环递归求解每一个 children 节点地位
const parseWorkflowToGraphData = ( node: IWorkflowNode<WorkflowNodeParamsXOR>, indexInSibling: number, parentMatrixX: number, parentNodeType: TWorkflowNodeType, parentNodeSize: number[], nodeMap: IWorkflowNodeMap, edgeMap: IWorkflowEdgeMap, resolveNode: ResolveNode, graphData: GraphData): IWorkflowDrawNode => { const nodeType = node.type; const condition = nodeType === 'start' ? true : edgeMap[node.id]?.condition; let newNode = { ...resolveNode(node), nodeType: nodeType, type: tagRenderNodeType(nodeType), condition, }; // 计算节点尺寸 const size = nodeSize(newNode); newNode.size = size; newNode.domSize = isBranchedNodeType(nodeType) ? [size[0] - padding - 130, size[1] - padding - 75] : size; // 计算节点坐标地位 const matrixX = parentNodeType === null ? 0 : parentMatrixX + indentX; const matrixY = !condition && indexInSibling === 0 ? MaxOffsetY + parentNodeSize[1] + gapVertical : MaxOffsetY; newNode.x = matrixX; newNode.y = matrixY; if (!condition && indexInSibling === 0) { MaxOffsetY += parentNodeSize[1] + gapVertical; } const children = []; if (node.children.length > 0) { node.children.forEach((childId, index) => { const childNode = parseWorkflowToGraphData( nodeMap[childId], index, matrixX, nodeType, size, nodeMap, edgeMap, resolveNode, graphData ); children.push(childNode); }); } else { MaxOffsetY += size[1] + gapVertical; } newNode.children = children; graphData.nodes.push(newNode); return newNode;};节点删除
节点删除时，不仅须要删除以后节点，而且以后节点的子树、以后节点的入度边也应该一并删除。此时用到的仍然是 N 叉树的递归解法，同时借助函数援用传参能够扭转参数的个性，实现了对源数据进行间接变更的操作。
/** * 删除任意节点、子树及其入度边 * @param node * @param nodes * @param edges */const removeNode = ( node: IWorkflowNode<any>, nodes: IWorkflowNode<any>[], edges: IWorkflowEdge[]) => { const { children } = node; if (children?.length > 0) { children.forEach((child) => removeNode( nodes.find((n) => n.id === child), nodes, edges ) ); } handleNodeDelete(node, nodes, edges);}; const handleNodeDelete = ( node: IWorkflowNode<any>, nodes: IWorkflowNode<any>[], edges: IWorkflowEdge[]) => { // 定位元素 const nodeIndex = nodes.findIndex((n) => n.id === node.id); const foundEdges = edges.filter((edge) => edge.target === node.id); // 革除父节点指向该节点的指针 const parentNode = nodes.find((n) => nodes[nodeIndex].parent[0] === n.id); if (parentNode.children?.length) { parentNode.children = parentNode.children.filter((child) => child !== node.id); } // 删除元素 nodes.splice(nodeIndex, 1); if (foundEdges?.length > 0) { foundEdges.forEach((v) => { const edgeIndex = edges.findIndex((_) => _.id === v.id); edges.splice(edgeIndex, 1); }); }};ABTest
在未拓展 ABTest 类型节点前，整个画布的数据结构满足二叉树的定义。但扩大之后，因为子节点数量存在大于二的场景，所以不再满足二叉树的定义，但整体不影响链表+树的构造定义，是由二叉到N叉的扩大。
但 ABTest 的特殊性不仅体现在以后节点的后继数量不限，更重要的是他的后继节点能够作为一个容器，再蕴含一个非凡的小型画布。
因而，在本来的数据结构根底上，咱们扩大了节点的类型定义，新增 childNodes 字段。childNodes 次要为了存储 ABTest 节点之后跟的 combo 组的数据，从这里作为入口，在不打断本来树结构的前提下，外部又能够插入一棵树的构造。其实到此处，曾经不再是单纯的双向链表模式，又多了一丝狭义表的滋味。
interface IWorkflowNode<T extends WorkflowNodeParamsXOR> { comboId?: string; id: string; type: TWorkflowNodeType; params: T; parent: string[]; children: string[]; childNodes?: string[];}通过扩大后的数据结构对原有的算法逻辑其实不会影响，咱们要做的是须要解决两头狭义表构造带来的子树逻辑（包含子树的坐标计算、子树对后继节点地位坐标的影响等）。
如果有如上的一棵树，依照扩大后的类型定义及 N 叉数的遍历算法，则遍历程序应该为：1、2、3、5、4、6、10、11、13、12、14、7、8、9。
因而在具体实现中，数据预处理逻辑根本不变，只是新增了 MaxOffsetYSnapshot 变量，作为计算狭义表之前y 偏移量的快照。当两头为了计算狭义表子树而影响到后继节点的 y 偏移量时，能够将后继节点计算时的 y 偏移量重置为快照值，以此保障不影响原有的树结构坐标计算。
坐标计算逻辑新增对 childNodes 带来的狭义表数据的解决：
const parseWorkflowToGraphData = ( node: IWorkflowNode<WorkflowNodeParamsXOR>, indexInSibling: number, parentMatrixX: number, parentNodeType: TWorkflowNodeType, parentNodeSize: number[], nodeMap: IWorkflowNodeMap, edgeMap: IWorkflowEdgeMap, resolveNode: ResolveNode, graphData: GraphData): IWorkflowDrawNode => { const nodeType = node.type; const condition = ['start', 'combo'].includes(nodeType) ? true : edgeMap[node.id]?.condition; let newNode = { ...resolveNode(node), nodeType: nodeType, type: tagRenderNodeType(nodeType), condition, }; // 计算节点尺寸 const size = nodeSize(newNode); newNode.size = size; newNode.domSize = isBranchedNodeType(nodeType) ? [size[0] - padding - 130, size[1] - padding - 75] : size; // 计算节点坐标地位 let matrixX = parentNodeType === null && !node.id.startsWith('combo') ? 0 : parentMatrixX + indentX; const matrixY = !condition && indexInSibling === 0 ? MaxOffsetY + parentNodeSize[1] + gapVertical : MaxOffsetY; newNode.x = matrixX; newNode.y = matrixY; if (!condition && indexInSibling === 0) { MaxOffsetY += parentNodeSize[1] + gapVertical; } // 解决combo类型节点中的小画布数据 if (nodeType === 'combo') { if (node.childNodes?.length > 0) { MaxOffsetY -= gapVertical; } const comboGraphData: GraphData = { nodes: [], edges: [], }; if (node.childNodes?.length) { parseWorkflowToGraphData( nodeMap[node.id.replace('root', 'combo')], 0, matrixX - size[0] - 90, null, [0, 0], nodeMap, edgeMap, resolveNode, comboGraphData ); } let maxXNode = null; let maxYNode = null; comboGraphData.nodes.forEach((node) => { if (!maxXNode || node.x > maxXNode.x) maxXNode = node; if (!maxYNode || node.y > maxYNode.y) maxYNode = node; }); const width = maxXNode && maxXNode.x > 0 ? maxXNode.x + maxXNode.size[0] - matrixX : size[0]; const height = maxYNode && maxYNode.y > 0 ? maxYNode.y + maxYNode.size[1] - matrixY : size[1]; newNode.size = [width, height]; graphData.nodes.push(...comboGraphData.nodes); graphData.edges.push(...comboGraphData.edges); // 计算 combo 组最大偏移量 if (indexInSibling === 0) { MaxOffsetYSnapshot = matrixY + newNode.size[1] + gapVertical; const nodeIds = nodeMap[node.parent[0]].children.map((id) => id.replace('root', 'combo')); const maxWidth = computeComboMaxWidth(nodeIds, nodeMap, edgeMap, resolveNode); matrixX = matrixX + maxWidth; } MaxOffsetY = matrixY; } const children = []; if (node.children.length > 0) { node.children.forEach((childId, index) => { const childNode = parseWorkflowToGraphData( nodeMap[childId], index, matrixX, nodeType, size, nodeMap, edgeMap, resolveNode, graphData ); children.push(childNode); }); MaxOffsetY = Math.max(MaxOffsetYSnapshot, MaxOffsetY); } else { MaxOffsetY += newNode.size[1] + gapVertical; } newNode.children = children; graphData.nodes.push(newNode); return newNode;};节点删除，也是新增对 childNodes 的解决逻辑即可：/** * 删除任意节点、子树及其入度边 * @param node * @param nodes * @param edges */const removeNode = ( node: IWorkflowNode<any>, nodes: IWorkflowNode<any>[], edges: IWorkflowEdge[]) => { const { children, childNodes } = node; if (childNodes?.length > 0) { childNodes.forEach((child) => removeNode( nodes.find((n) => n.id === child), nodes, edges ) ); } if (children?.length > 0) { children.forEach((child) => removeNode( nodes.find((n) => n.id === child), nodes, edges ) ); } handleNodeDelete(node, nodes, edges);};以上，咱们可实现的简单策略配置如下：
结语
“软件的复杂性是一个基本特征，而不是偶尔如此”。但数据结构和算法拉平了程序开发人员对程序的认知，是管制复杂度的卓有成效的伎俩。