基于 x6 自定义DAG 布局实战和坑

# 什么是DAG

有向无环图DAG 是常见的数据关系可视化方式,DAG 是有方向的关系图一类总称,流程图、树形图等都是属于特别类型的 DAG 布局方式。

树形图:每个节点有且只有一个父节点,比如部门结构,项目管理结构,脑图等 流程图:流程图不总是DAG 图,只有箭头没有循环的过程,才被视为 DAG。它更是是一种交互很强的关系表示,而非用户数据可视化。

通用的 DAG 父子节点可以是多对多,一个节点既可以有多个字节点,也可以有多个父节点。

# 什么是 X6

X6 是 AntV 旗下的图编辑引擎,提供了一系列开箱即用的交互组件和简单易用的节点定制能力,方便我们快速搭建 DAG 图、ER 图、流程图等应用。

选型上上注意区别于G6, G6 也是 Antv 团队的一个图可视化引擎,它也可以做同样的事情,但是使用成本更高;好处是基于 canvas 绘制,性能很好。而 X6 是基于 SVG,性能一般,如果是大量数据可视化场景,G6 应该是优先考虑,而 X 6 侧重编排和易用性(支持 vue/react 等组件作为节点渲染)。

# 如何布局

理论上,只要满足数据关系的方向性,可视化图形可以任意随机分布节点的位置,但这样会让界面看起来混乱无序,无法清晰表达出数据的关系。层次化布局,即给每个节点分配一个层次,让底层的节点指向高层的节点,是业界通用的做法。为了实现这种效果,研发人员多年来做了各种研究和改进,x6 中的drage 布局即使采用了业界优秀的层次布局算法。

drage层级布局整个流程其实非常复杂,但核心主要分几个步骤:

# 1去环

循环关系环会导致布局算法陷入死循环,为了保证数据干净,需要先检测闭环的节点,并进行去除(或修改),这一步会影响原始数据,目的是让数据符合 DAG 的关系。

这里有个问题,因为既然存在环,说明不管从哪里节点出发,都会回到原节点,每个边都是成环的重要部分,我们如何确定要移除哪个边呢?这里主要是通过贪婪算法的实现专注于找到(出度-入度)最大的节点并处理这个节点的边。对于一个节点,(出度-入度)的值就是从这个节点出发的边的数量减去指向这个节点的边的数量。

所以最终的步骤就是深度遍历节点,记录节点子节点数量(出度),父节点数量(入度),直到找到环,从行程环的节点中选取出度-入度的节点,并去除形成环的这个边。

# 2确定节点层级

试想下,我们如何分配层级才是合理的?其实并没有最优答案,但是直觉告诉我们,最简单的就是从一个没有父亲节点的开始,遍历它的孙子节点,每向下寻找一次,就增加一层,这样每个节点的层级则自动为遍历的时候确定的层级,层级最大为节点的最深路径。这种方法叫最长路径法,遍历的方式也称拓扑排序,其性能最优。我做过一些随机测试,发现大部分数据,这个算法就能很好的满足布局上的视觉需要,并且和另外两种(一会提到)不会相差很大。

我们能否进一步优化呢),可以的。最长路径最大的问题是,它以来数据的默认顺序,在一些复杂的场景,绘制出来的相邻节点路径会比较长,导致整个视觉效果看起来不平衡。

# 3 优化

● 紧凑树 紧凑树是以最长路径算法为基础,试图找出尽可能让相邻的节点之间更紧凑(更短),代价是更多的计算,用上下的空间,替代了左右的空间。原理就是定义一个最短路径(路径是几何概念,通常就是层级数,比如 1),不断去比较节点是否和它相邻的节点的距离层级,把满足条件的加入到新的紧凑树,如果不能满足,则调整两边层级。

● 单纯形算法(Simplex Algorithm) Simplex其实我也没有太完全理解(还在研究中),这个是运筹学和优化理论中,一种用于求解线性规划问题的常见方法。但是DAG布局问题是图形理论中的一个问题,可以被转化为线性规划问题。

Simplex ,需要在紧凑树的基础上进一步继续,它视图最小化整体路径的长度。

上面3 种算法可以在 x6 的drage 布局中进行选择(默认是复杂度最高的Simplex)。

这两个算法感兴趣的可以参考antv 团队的wiki 深入解读Dagre布局算法

# 4确定同层级的位置

这步主要是确定相同层级中,哪个节点排前面,哪个节点排后面,目的是让线条交叉最少,这里也很复杂,是一个NP 完全问题。

最简单的做法就是两两节点位置互换,然后比较线条交叉数是否减少,是则换位置,否则保持,然后不断遍历下一个节点,但是这种计算量非常大,层级和节点数的指数增长。所以只能采用贪心策略,找到布局最优,drage 算法会给它设置一个最大的遍历次数,如果超过了则不会再进行。

# 5 计算宽高、间距等进行绘制

这步主要是基于上面的确定的层级和节点位置,控制间距、大小、换行等调用图形 api 遍历节点进行绘制。

# 自定义X6 布局

图形库虽然提供了大量常见的算法支持,但是业务总是有超出框架覆盖的需求,比如一个特殊的 DAG 图,已经根据业务需要分配了固定的层级,每个层级有默认的顺序,每个层级有特定的个性化样式和UI,这个时候 darge 不能满足定制化排版,需要运用 X6 的节点,进行自定义绘制。这种情况没有办法复用 drage 的自动布局能力,因为它是为通用的 DAG 而实现的。

# 绘制步骤

自定义 dag 布局相对于普通的 html + css工作量更大,需要处理全部的细节。其过程主要有一下步骤:

1.确定层级,这里由后台根据业务,从数据库直接确定,而不是基于纯 UI 算法布局

2.基于给定层数,从左到右自动排列节点

3.节点 x (距离画布最左)位置以层最大宽度为基准,自动居中

4.根据预设间距进行排列,超过最大宽度,自动换行

5.线条可跨层直线连接

6.自动渲染虚线矩形围绕层数,并且每个矩形x 对齐最宽的层数的外围矩形,宽高一致

7.绘制每层区块标题,对齐最上左

8.绘制 toolips

上面的过程无法使用 CSS,需要用 JS 手动控制 x6 节点节点大小、x、y间距、行间距、每行放多少个、居中偏移量、标题占据空间。这边列举几个重点和调试工作量大的地方:

# 居中和换行

居中 = 节点内容总宽(每个节点的宽度 + 边距 )向右相对画布偏移 50%,在相对自身左偏移50%。这是常见的居中算法。

行 = 当前第几个层 * (每行高度 + 间距) + 区块内第几行 * 节点大小和间距 + 标题占据的高度

下面代码不到 50 行主要是给节点进行居中和换行,通过遍历节点得到它们的 x、y 位置。除此以外还要考虑绘制其他区域,逻辑类似。

// 每层最大宽度
  const maxBlockWidth = containerRef.value.offsetWidth - 50
  // 计算每个节点的大小
  const nodeSize = 24
  // 节点 y 纵向的间距
  const nodeGap = 20
  // 节点 x 横向的间距
  const blockGap = 20

  // 每行能容纳的最大节点数
  const maxNodeCountPerLine = Math.floor(maxBlockWidth / (nodeSize + blockGap))

  const maxRowHeight = nodeSize + nodeGap
  // 偏移量,用于将节点相对区块居中的偏移量
  let xOffset = 0
  // 计算出区块相对画布居中需要的偏移量
  const containerCenterX = containerRef.value.offsetWidth / 2
  const maxBlockCenterX = maxBlockWidth / 2
  const canvasOffsetX = containerCenterX - maxBlockCenterX
  // 设置区块标题
  const titleHeight = 30 // 设置标题的高度
  const titleGap = 10 // 设置标题和节点的行间距
  // 全局行索引
  let globalRowIndex = 0

  Object.values(blocks).forEach((block: any, blockIndex: number) => {
    block.forEach((node: any, nodeIndex: number) => {
      // 计算节点在当前行的位置
      const xInLine = nodeIndex % maxNodeCountPerLine
      if (xInLine === 0 && nodeIndex !== 0) {
        globalRowIndex++
      }
      // 当我们开始处理新的一行时,计算新的偏移量,用于居中
      if (xInLine === 0) {
        const nodesInCurrentRow = nodeIndex + maxNodeCountPerLine < block.length ? maxNodeCountPerLine : block.length - nodeIndex
        const totalWidthInCurrentRow = nodesInCurrentRow * nodeSize + (nodesInCurrentRow - 1) * blockGap
        xOffset = (maxBlockWidth - totalWidthInCurrentRow) / 2
      }
      // 每个节点 y 的位置 = 当前第几个区块 * (每行高度 + 间距) + 区块内第几行 *  节点大小和间距 + 标题占据的高度
      const y = blockIndex * (maxRowHeight + blockGap) + globalRowIndex * (nodeSize + nodeGap) + titleHeight + 2 * titleGap
      const x = xOffset + xInLine * (nodeSize + blockGap) + canvasOffsetX
      node.x = x
      node.y = y
      // console.log('node.y:', y)
      // 使用 x6,你可以这样来创建节点:
      //... 略
    // 如果最后一行的节点数超过了 maxNodeCountPerLine,增加 globalRowIndex
    if (block.length % maxNodeCountPerLine !== 0) {
      globalRowIndex++
    }
  })

# 深度优先搜索关系链

DAG 最场景的使用场景是根据一个节点,我们需要找出其全部的祖先节点。比如如图所示,点击其中的一个分析结果,寻找其全部的祖先节点,并进行高亮和显示关系。

【图略...】

我们可以通过深度遍历 nodes 、edges,取出全部的祖先节点和边,因为我们使用的是 x6 graph图形化2布局的,最简单的做法是用 x6 的图形api

 const ancestors = graph.getPredecessors(node)

反之,全部孙子节点关系网也可以通过如下方式

 const descendants = graph.getSuccessors(node)

通过遍历节点找边

// 遍历上面的节点再取对应的边 const edges = graph?.getConnectedEdges(descendant) 在处理交互的时候,通常需要高亮显示和隐藏,为了隐藏的时候全量遍历,我们可以在显示的时候,把节点和边添加到缓存数组中,隐藏的时候直接遍历缓存中的节点,可以提高性能。

# 基于 vue 绘制节点

x6默认情况下是通过 svg 添加的节点的,下图shape 默认为 rect 矩形框。

    graph?.addNode({       
       id: node.id,
       // shape: 默认是 svg的 rect 
        x: node.x,
        y: node.y,
        width: nodeSize,
        height: nodeSize,
        zIndex: 99,
        className: 'node-cell-box',
      })
    })

svg 节点的样式操控能力比基于 canvas (浏览器图形 api)绘制要高很多了。但是效率仍然比现代化的 MVVM 框架组件低很多,除了无法方便的数据驱动UI 外,svg 样式编写和 html + css 不太一样,一般前端开发不会很熟悉,需要现查API 。x6 提供了一种机制让你使用 vue 组件渲染节点的方式。

# 自定义 vue 组件的 shape

先引入 @antv/x6-vue-shape' 依赖

import '@antv/x6-vue-shape' shape 是一个用于定义 x6 如何渲染节点的参数,我们可以自定义一个 vue组件的 shape 名为node-title-box(唯一的) 的渲染方式。它的原理是利用 svg 的foreignObject 对象,将 html 挂载到其内部。

 // 注册
   Graph.registerNode('node-title-box', {
    inherit: 'vue-shape',
    component: {
      render: () => {
        return createVNode(title, {
          graph
        })
      }
    }
  })
  // 使用
    graph?.addNode({
      shape: 'node-title-box',
      x: canvasOffsetX,
      y: minY - padding - titleHeight,
      width: maxBlockWidth,
      height: titleHeight,
    })

通过 inherit: 'vue-shape', 然后component 参数返回一个组件 createVNode 的节点即可。

要注意,这里的 createVNode 就是 vue 原生的API,所以我们可以把 组件的外部依赖通过 props 传递到组件内部,从而利用响应式达到通信(这个很重要,在发现这个问题之前,我是用侵入性更强的全局事件机制)。

最后,在graph?.addNode 过程中把 shape 指定为上面的node-title-box 就会在渲染过程中把组件挂载进去。

# vue 节点性能

vue 组件是基于原生 html + js 的再次抽象,其性能成本会更大,额外的响应式跟踪、虚拟 dom 计算等,在很图形简单、量级巨大的节点绘制是不适合的。

下面是一个在 100 节点 600 多边绘制的性能对比,原生 svg 和 vue 组件渲染的差别会很大。

由此可见,效率和性能难以兼得。在这次场景我只是用 vue节点创建标题和 tooltips ,更多节点的关系链则是有原生 svg 绘制的。

在前端图形绘制中,性能关系一般如下 webgl > canvas > html + js > MVVM 组件。

而开发效率则反之 MVVM 组件 > html + js > canvas2d > webgl

canvas 和 webgl 开发也有很多框架和库,但在开发效率上和响应式驱动的 MVVM 组件还是差别很大。这里我们不展开。

#

使用外部库,最大的问题就是它不是浏览器的标准实现,质量和api 往往是隐晦的,这里记录了一些在 x6 目前版本(1.34.5)遇到的问题和心得。

● getDescendants 无效?

这个文档的api 没有效果(也可能是我的使用方式不对)。但用上面案例的 getPredecessors 写法替换即可。

● import '@antv/x6-vue-shape'

这个是必要的,要单独引用,不在x6 核心库 ,否则挂载 vue 组件不会初始化成功

● item 节点错误

在生产构建 构建下 x6 会有一个报错(具体忘记了), 和 dev 开发模式构建不会。

解决方案是直接通过 webpack 把别名统一指向相同的文件库。

  resolve: {
    alias: {
      '@': fileURLToPath(new URL('./src', import.meta.url)),
      '@antv/x6': '@antv/x6/dist/x6.js',
      '@antv/x6-vue-shape': '@antv/x6-vue-shape/lib'
    }
  }

● 设置的节点层级 z-index 失效

需要 sorting 属性设置 approx 。

浏览器原生并没有提供像 html 一样的z-index 属性,来定义哪些元素在上层,哪些在下层,而是需要开发自己实现,先绘制的在下层,后绘制的在上面,所以 下x6 提供了几种绘制方式的选择。(不详细搜文档和调试很难发现这个坑。)

● 线条路由模式有好多种,会影响路径效果

通过 router 属性进行控制

https://antv-x6.gitee.io/zh/docs/api/registry/router/#gatsby-focus-wrapper

● 组件销毁需要手动解除引用

销毁 vue 组件的时候,最好主动释放 x6 的引用,因为它是全局的,一直在内存中(如果不是因为事件系统异常排错,这个问题肯本发现不了)。

  // 组件销毁、手动解除引用
  Node.registry.unregister('tree-node')
  Edge.registry.unregister('tree-edge')
  Graph.unregisterNode(currentNodeId)
  Graph.registerNode

这个是因为 x6 node 节点注册时一种全局标识。我们既要销毁 Graph 对象本身,也要效注册的自定义节点(记住 id 唯一)。这两个销毁方式直接用 x6 提供的 api 就行(理论上设置 null 也行,没有试过)。

—————— 结

更新时间: