AntV X6-判断节点是否可以嵌入

前言

需求除了实现添加节点和连线等基本功能，还要根据SysML的语义去判断哪些节点可以组合，哪些节点可以在何处添加，并进行判断

示例

官方给出的示例代码如下，即在初始化graph实例的embedding配置中设置findParent函数，通过遍历画布中所有节点的方式，找到data中parent属性为true的节点，并判断是否相交

embedding: {
    enabled: true,
        findParent({ node }) {
        // 获取移动节点的包围盒
        const bbox = node.getBBox();
        // 找到 data 中配置 { parent: true } 的节点，并且移动节点和找到的节点包围盒相交时，返回 true
        return graph.getNodes().filter(node => {
            const data = node.getData<{ parent: boolean }>();
            //如果data存在且data.parent为true(防止访问不到data.parent报错)
            if (data && data.parent) {
                const targetBBox = node.getBBox();
                return bbox.isIntersectWithRect(targetBBox);
            }
            return false;
        });
    },
},

解决

方案1

在每个节点定义时利用map记录父节点信息，组合时直接利用has判断父子关系

export interface NodeData {
  isParent: boolean;
  kind: string;
  parents: Map<string, string>;
}

const childData = child.getData<NodeData>();
const parentData = parent.getData<NodeData>();
if (parentData && parentData.isParent) {
    if (childData && childData.parents && childData.parents.has(parentData.kind)) {
        return child.getBBox().isIntersectWithRect(parent.getBBox());
    }
}
return false;

优点：

查找时复杂度为O(1*n)

缺点：

每个节点初始化时都额外存储了父节点的信息，额外牺牲了一定的空间复杂度，重复的节点数越多，牺牲的空间复杂度越大

方案2

定义string到Array<string>的map，存储每个孩子节点可能的所有父节点

//K-child V-parent
const childParent = new Map<string, Array<string>>([['compositeState', ['region']]]);

const childData = child.getData<NodeData>();
const parentData = parent.getData<NodeData>();
if (parentData && parentData.isParent) {
    if (childData && childData.kind && parentData.kind ) {
        const parents = childParent.get(childData.kind);
        if (parents && parents.includes(parentData.kind)) {
            return true;
        }
    }
}
return false;

优点：

1. 空间复杂度较优，避免了重复空间占用
2. 关系代码集中在childParent中，方便修改，避免遗漏

缺点：

由于一个孩子节点大概率可以嵌入多种父节点，一个key值对应的value为一个数组，数组长度也就是孩子节点对应父节点的个数，假设嵌入时画布上有n个节点，该子节点有m个父节点，一次嵌入的时间复杂度为O(m*n)

效果

目前根据需求，节点的父节点数量要远小于画布上节点的数量，故选择方案2，牺牲一点点时间复杂度

简单状态只能添加到域中，而不能添加到isParent属性也为true的复合状态中