G6
G6 copied to clipboard
antvis
[讨论] Dagre 分组复合图布局算法优化讨论
Description
Dagre combo 例子: https://g6.antv.vision/zh/examples/net/dagreFlow#dagreCombo
在 G6 中，有非常多优秀的布局实现 👍🏻 ，满足了大部分场景需求，可是在特定场景中，比如具有层级结构的分组流程图中，目前基于 dagre 的流程图布局，可以结合 Combo 实现分组展示，但是在复杂数据情况下仍然遗留了 dagre 边交叉严重的问题，分组节点与其他节点的关联关系也没办法联系起来，所以如果有兴趣的话是否有同学想讨论下基于 dagre 优化（可先新增一种布局方式）复合分组情况下的布局场景，复用重复边、并保留分组节点与内外节点的连接关系，具体思路如下（具体参考了 Tensorflow 的论文与实现：https://idl.cs.washington.edu/files/2018-TensorFlowGraph-VAST.pdf）。
Implementation
思路：
A、B 属于同组 G，C 在组外，A、B 分别与 C 连接，原有方案穿透组节点直接相连，
新方案将 A、B 与组节点G相连，然后连接点 G‘ 与 C 相连，这样在大数据量下组内节点按照 dagre 布局，
外层 组节点 G 与 节点 C 继续按照 dagre 布局，不仅有效地降低了边交叉情况，同时组节点的关联关系也得以保留。
+-----------+ +-----------+
| | | |
| +---+ | | +---+ |
| | A +-------\ | | A |X |
| +---+ | +--->+---+ | +---+ X | +---+
| | | C | --------> | X+----->+ C |
| +---+ | +--->+---+ | +---+ X | +---+
| | B +-------/ | | B |X |
| +---+ | | +---+ |
| | | |
+-----------+ +-----------+
以上方案引入了一个新的辅助节点（G’）与辅助边来帮助构建组节点内部布局与外部的连接关系，同时保留了 dagre 布局的对齐方式，所有节点位置与边位置都可以通过转换得出绝对/相对定位，可以应用到 G6 中来，但是分组节点与当前 Combo 组存在一些gap，就是组节点G是依赖与内部节点确定位置的，如有必要可允许 Combo指定 position 或者探索 dagre 布局是否可手动优化来适配 Combo。
最终的 dagre 效果与优化后效果如图所示：
对于此方案，我的建议是单独发布一个布局库，作为外部依赖引入 G6 layout（类似于 dagre），可以从 自定义布局 -> layout 布局底层的方式逐步验证体验。这部分与 combo 布局优化也可结合起来看，与G6当前的的规划应该没有冲突的点，抛砖引玉，希望得到更多同学的讨论与建议 :)
Contributor
@simplejason
非常感谢，非常专业。这个功能确实有很多用户提需求。
- 关于共建：
之前 G6 的 dagre 引用的外部开源库。今年我们为了满足支持指定节点的布局层级、支持动态数据变化时布局保持连贯性这两个需求，fork 了原有的 dagre 外部开源库进行改造，目前改造成果暂时在个人仓库中，但 @antv/layout 已经改为引用我们改造的这个包替代外部依赖。现在正在将该代码迁移到 @antv/layout 仓库下面。
是否等待迁移完成之后，可以在 @antv/algorithm/dagre 下面进行改造呢？还是说因为逻辑、代码结构和 dagre 区别较大，希望单独成为一个算法放在 @antv/algorithm/xxxx ？虽然对于用户使用来说可能更倾向于用同一个布局，通过配置决定最终是什么效果。但是我觉得还是得考虑代码结构、维护成本等问题，所以二者都 ok。如果选择前者，可以等迁移完成后改造。如果选择后者，有兴趣的话可以直接贡献代码到 @antv/layout 中。这将对 G6 有很大的帮助！再次感谢。
- 关于 combo 的机制：
但是分组节点与当前 Combo 组存在一些gap，就是组节点G是依赖与内部节点确定位置的
如果有必要，我可以优化 combo 的机制，让它支持指定坐标。但是没有非常理解这里的意思，目前 Combo 的位置也是由内部元素的位置决定的，布局是否能够根据 combo 信息计算好节点的位置，然后相关的 combo 就会自动放在合适的位置套住它们了？是什么情况下需要指定 combo 的位置呀？
- 关于节点、边的机制：
建议不要改变节点/边的机制，A->B A->E 仍然是两条边，B->C B->D 也仍然是两条边，但使用 polyline 边并通过给这些边增加多个 controlPoints，达到上图右侧效果（边的部分绘制之后看起来是重合在一起的，实际还是两条边）。
@Yanyan-Wang 感谢回复
1、关于共建
非常高兴听到 G6 团队在 dagre 上的优化，目前这套方案与dagre并无大冲突，原则上完全可以基于你们改进完的dagre进行兼容（当然如果可以的话我想提前看下具体在哪些方面优化了），期望能够将层级布局方案作为补充，实现对dagre的增强，作为独立布局来使用。当然，在那之前，可以从自定义布局验证。
如果选择前者，可以等迁移完成后改造。如果选择后者，有兴趣的话可以直接贡献代码到 @antv/layout 中。: 非常期望这部分工作能够落到底层布局库，也希望与社区同学随时保持沟通 :)
2、关于 combo 的机制
Combo 强依赖节点具体位置，如果算法有自己的节点位置微调，如上述算法存在部分辅助节点是基于内部节点所属的container确认的，也就意味着外部节点自带了布局位置信息情况下可能与默认的 Combo 计算存在微小的差别，在多级嵌套情况下会放大这个问题。当然，我觉得有两种方案来解决：
- 让复合布局算法基于 Combo 原理来进行优化适配（即探索 dagre 默认布局位置与 Combo 是否可以对应）
- 优化 Combo 来支持用户自定义 position 时优先按照自定义位置放置（这种方案可能需要评估下 Combo 内部是否是有状态的，如果可以的话我可以仔细阅读一下 Combo 的设计原理）
3、关于节点、边的机制
这个是没问题的，因为上述方案虽然内部使用了这些辅助边、节点，但是透出时仍然会将这些辅助的信息应用到原始节点上，对于用户是无感的。
再次感谢社区同学的回复，目前不管是社区还是很多公司对于 DAG 图布局可视化的需求都很迫切，希望能够和 G6 一起让复合分层 DAG 流程图应用到更多场景中。
@Yanyan-Wang Hi，辛苦有时间看一下上面这个实现，我在 dagre 基础上优化了分组模式下的布局，如果希望进入 @antv/layout 底层库（可以先作为 beta 版），还需要哪些改造呢？
layout 库实现（原则上可以兼容 dagre，可以支持内置的 dagre 或者 dagrejs 依赖），因为 g6 的一些bug 和限制，所以存在部分兼容性代码：https://github.com/simplejason/G6/blob/feat%2Fdagre-compound/src/layout/dagre-compound.ts
区别： dagre-compound 布局针对边交叉、多层复合情况做了优化，combo 节点位置确认是由内部节点位置和复用的边共同决定的，达到最优的布局渲染结果，在收起 combo 或节点跨组连接时不会出现边错乱等情况。
这个版本的有作为layout 底层库上去吗，感觉现在combo 不参与布局 存在挺多问题的
可以参考 https://stackblitz.com/edit/react-lvta5h-gzvmk9?file=index.js 这个 demo
dagreCompound 布局已由 @simplejason 贡献集成在 @antv/layout 中💪👏👏，G6 中也可以使用啦，欢迎试用 https://github.com/antvis/layout/blob/master/src/layout/dagreCompound.ts
另外，我们最近还新增了 comboCombined 布局，可以配置 combo 内、外的布局算法
- demo: https://g6.antv.antgroup.com/examples/net/comboLayout/#comboCombined
- API: https://g6.antv.antgroup.com/en/api/graphlayout/combocombined
dagreCompound 布局已由 @simplejason 贡献集成在 @antv/layout 中💪👏👏，G6 中也可以使用啦，欢迎试用 https://github.com/antvis/layout/blob/master/src/layout/dagreCompound.ts
另外，我们最近还新增了 comboCombined 布局，可以配置 combo 内、外的布局算法
- demo: https://g6.antv.antgroup.com/examples/net/comboLayout/#comboCombined
- API: https://g6.antv.antgroup.com/en/api/graphlayout/combocombined
求问有G6里使用dagreCompound的示例么，怎么用
