25

Graphviz 库中是否有关于 dot 算法的任何文档（完整的伪代码？）？

我只找到了一些部分伪代码文档。

4

1 回答 1

40

这里有一些参考资料供您参考。最完整的（缺少Graphviz 源代码本身）可能是 #2，即由 Graphviz 的几个贡献者自己编写的论文“绘制有向图的技术”。

(1)《用点画图》

在用 dot 绘制图形中，dot 的布局算法是这样描述的：

dot 分四个主要阶段绘制图形。了解这一点有助于您了解 dot 的布局类型以及如何控制它们。dot 使用的布局过程依赖于非循环图。因此，第一步是通过反转某些循环边的内部方向来打破输入图中出现的任何循环。下一步将节点分配给离散的等级或级别。在从上到下的绘图中，等级确定 Y 坐标。跨越一个等级的边被分成“虚拟”节点链和单位长度边。第三步对等级内的节点进行排序以避免交叉。第四步设置节点的 X 坐标以保持边短，最后一步路由边样条。这是基于 Warfield [War77] 工作的大多数分层图形绘制程序的通用方法，Carpano [Car80] 和 Sugiyama [STT81]。我们将读者推荐给 [GKNV93] 以获得对 dot 算法的全面解释

该段引用的论文如下：

  • [Car80] M.卡尔帕诺。自动显示分层图表以进行计算机辅助决策分析。IEEE Transactions on Software Engineering，SE-12(4):538–546，1980 年 4 月。（显然可在此处购买。）

  • [GKNV93] Emden R. Gansner、Eleftherios Koutsofios、Stephen C. North 和 Kiem-Phong Vo。一种绘制有向图的技术。IEEE Trans。软件工程，19(3):214–230，1993 年 5 月。（可在Graphviz.org 网站上获得。）

  • [STT81] K. Sugiyama、S. Tagawa 和 M. Toda。层次系统结构的视觉理解方法。IEEE Transactions on Systems, Man, and Cyber​​netics，SMC-11(2):109–125，1981 年 2 月。（显然可在此处购买。）

  • [War77] 约翰·沃菲尔德。交叉理论和层次映射。IEEE Transactions on Systems, Man, and Cyber​​netics，SMC-7(7):505–523，1977 年 7 月。（显然可在此处购买。）

(2)《一种绘制有向图的技术》

dot 的算法在 1993 年发表在IEEE Transactions on Software Engineering杂志上的论文“A Technique for Drawing Directed Graphs”中有详细描述（可在 Graphviz.org 网站上免费获得）。这是上面引用的“[GKNV93]”来源。

就其价值而言，摘要是这样的：

我们描述了一种用于绘制有向图的四遍算法。第一遍使用网络单纯形算法找到最佳等级分配。第二遍通过迭代启发式设置等级内的顶点顺序，该迭代启发式结合了新颖的权重函数和局部转置以减少交叉。第三遍通过构建辅助图并对其进行排序来找到节点的最佳坐标。第四遍使样条线绘制边缘。该算法可以制作好的图纸并且运行速度很快。

(3) 《将 Graphviz 用作库》

“将 Graphviz 用作库”在第 3.1 节中提供了每个布局引擎算法的摘要。点的部分描述是这样的：

如果可能，点算法会根据边缘方向生成图的排序布局。它特别适用于显示层次结构或有向无环图。基本布局方案归属于 Sugiyama 等人[STT81] dot 使用的具体算法遵循 Gansner 等人描述的步骤[GKNV93]

点布局中的步骤是：1）初始化 2）排名 3）mincross 4）位置 5）sameports 6）样条线 7）compoundEdges

初始化后，该算法使用整数程序将每个节点分配给离散等级（rank），以最小化（离散）边长的总和。下一步（mincross）重新排列等级内的节点以减少边缘交叉。接下来是为节点分配实际坐标（位置），使用另一个整数程序来压缩图形并拉直边。此时，所有节点都会在坐标属性中设置一个位置。另外，设置了所有簇的bounding box bb属性。

“[GKNV93]”参考是“绘制有向图的技术”，如上链接。

“[STT81]”参考了上面引用的“层次系统结构的视觉理解方法”。

(4) 您可能还对以下内容感兴趣：

于 2013-12-12T07:19:47.700 回答