摘要：可以用于模型化许多不同种类的信息，因此将一个数据结构可视化的需求也变得非常普遍。并且由于大部分图的数据都非常复杂甚至动态变化，所以自动可配置的可视化布局算法显然比人为排版更为高效且可靠。
有向无环图（DAG）布局 有向无环图及其布局算法
有向无环图（directed acyclic graph，以下简称 DAG）是一种常见的图形，其具体定义为一种由有限个顶点和有限条带有方向的边组成的图，并且其中任意一个顶点都不能沿着边再次指向自己。
DAG 可以用于模型化许多不同种类的信息，因此将一个 DAG 数据结构可视化的需求也变得非常普遍。并且由于大部分图的数据都非常复杂甚至动态变化，所以自动、可配置的 DAG 可视化布局算法显然比人为排版更为高效且可靠。
为满足笔者所在项目一个可视化功能（其逻辑可视为一个 DAG）的开发，我们需要一个可在浏览器端进行布局计算的 js 库，并且基于计算结果进行渲染。经过调研，社区的一个项目 dagre 基本可以满足我们的需求，但需要彻底掌握其计算逻辑我们还需要理解一些基本概念和对应配置项之间的关系。
基本概念dagre 主要基于《A Technique for Drawing Directed Graphs》 的理论进行实现，因此也有以下几类单位：
graph，即图整体，我们可以对图配置一些全局参数。
node，即顶点，dagre 在计算时并不关心 node 实际的形状、样式，只要求提供维度信息。
edge，即边，edge 需要声明其两端的 node 以及本身方向。例如A -> B表示一条由 A 指向 B 的 edge。
rank，即层级，rank 是 DAG 布局中的核心逻辑单位，edge 两端的 node 一定属于不同的 rank，而同一 rank 中的 node 则会拥有同样的深度坐标（例如在纵向布局的 graph 中 y 坐标相同）。下文中我们会用示例 graph 进一步解释 rank 的作用。
label，即标签，label 不是 DAG 中的必要元素，但 dagre 为了适用更多的场景增加了对 edge label 的布局计算。
深入 rank接下来的示例中我们会用一种易懂的描述语言表达一个 DAG 的 node 与 edge：A -> B代表 A 和 B 两个 node 以及一条由 A 指向 B 的 edge。
示例 1A->B;
B->C;
+---+ +---+ +---+
| A |------>| B |------->| C |
+---+ +---+ +---+
在这个示例中，node A, B, C 分别属于 3 个 rank。
示例 2A->B;
A->C;
+---+
--> | B |
+---+--/ +---+
| A |
+---+-- +---+
--> | C |
+---+
在这个示例中，A 在 rank1 中，而 B 和 C 都比 A 低一个层级，属于 rank2，因此 B 和 C 拥有同样的 x 坐标（示例图为横行延伸，因此深度方向为 x 方向）。
示例 3A->B;
B->C;
A->C;
+---+
-->| B |---
+---+---/ +---+ --->+---+
| A | | C |
+---+------------------->+---+
在这个示例中，我们发现 edge 两端的 node 可以相差超过一个 rank。由于 edge 两端的 node 不可属于同样的 rank，所以我们不能让 B 和 C 属于同一个 rank，进而最优的绘制结果为 A 和 C 之间相隔两个 rank。
在这三个例子中，我们已经对 rank 的含义和规则有了更好的理解，接下来可以看看 dagre 允许我们对各类布局元素做怎样的配置。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/107710.html
摘要：判断是否成环执行拓扑排序，如果序列中的顶点数不等于有向图的顶点个数，则说明图中存在环。如果访问过，且不是其父节点，那么就构成环图有向无环图的最小路径覆盖图存储邻接矩阵图的邻接矩阵存储方式是用两个数组来表示图。 何为有向无环图？ 1、首先它是一个图，然后它是一个有向图，其次这个有向图的任意一个顶点出发都没有回到这个顶点的路径，是为有向无环图2、DAG（Directed Acyclic G...
摘要：而对于依赖关系的抽象，业界最通行的做法即使用有向无环图，来描述事务间的依赖关系。图表并行遍历，执行资源动作从根节点开始，并行地去编排整个资源拓扑，遍历整个有向无环图，直到所有资源都被成功编排，并执行清理操作。前言Terraform 是 Hashicorp 公司开源的一种多云资源编排工具。使用者通过一种特定的配置语言（HCL Hashicorp Configuration Language）来...
摘要：遇到问题分析之后搞了个还没仔细了解可参考的与的有区别及并发控制先看看的，与的这几个概念。一个可以认为就是会最终输出一个结果的一条由组织而成的计算。在中，我们通过使用新极大地增强对状态流处理的支持。 Spark Streaming遇到问题分析 1、Spark2.0之后搞了个Structured Streaming 还没仔细了解,可参考：https://github.com/lw-lin/...
摘要：只好特地拎出来记录证明一下算法步骤第一步在逆图上运行，将顶点按照逆后序方式压入栈中显然，这个过程作用在有向无环图上得到的就是一个拓扑排序作用在非上得到的是一个伪拓扑排序第二步在原图上按第一步的编号顺序进行。等价于已知在逆图中存在有向路径。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslat...
摘要：有向无环图，以下简称是其中的代表之一。的去中心化和可扩展性可认为是一体两面的，因为基于数据结构带来的异步记账特性，同时实现了高度的参与网络节点的去中心化和交易的可扩展性。因此，目前对于双花问题，需要综合考虑实际情况进行设计。 本报告由火币区块链研究院出品，作者：袁煜明、胡智威。原文地址 相关报告： 【超越白皮书2】EOS主网上线前夕的实测分析与技术建议 【超越白皮书1】EOSIO程序实...
阅读 1255·2021-10-11 11:12
阅读 2978·2021-09-30 09:46
阅读 1486·2021-07-28 00:14
阅读 3047·2019-08-30 13:49
阅读 2479·2019-08-29 11:27
阅读 2899·2019-08-26 11:52
阅读 482·2019-08-23 18:14
阅读 3326·2019-08-23 16:27
