Graphviz 点算法 [英] Graphviz Dot Algorithm
问题描述
Graphviz 库中是否有关于 dot 算法的文档(完整的伪代码?)?
我只找到了部分伪代码文档.
这里有一些参考资料供您参考.最完整的(缺少 Graphviz 源代码本身)可能是 #2，论文A Technique"用于绘制有向图"这是由几位 Graphviz 贡献者自己编写的.
(1)用点画图"
在用点绘制图形中，点的布局算法是这样描述的:<块引用>
dot 在四个主要阶段绘制图形.了解这一点有助于您了解 dot 的布局类型以及如何控制它们.dot 使用的布局过程依赖于非循环图.因此，第一步是通过反转某些循环边的内部方向来打破输入图中出现的任何循环.下一步将节点分配给离散的等级或级别.在从上到下的绘图中，等级确定 Y 坐标.跨越一个以上等级的边被分解为虚拟"节点链和单位长度边.第三步对等级内的节点进行排序以避免交叉.第四步设置节点的 X 坐标以保持边短，最后一步路由边样条.这是与大多数分层图形绘制程序相同的通用方法，基于 Warfield [War77]、Carpano [Car80] 和 Sugiyama [STT81] 的工作.我们将读者推荐给 [GKNV93] 以获得对 dot 算法的全面解释
该段引用的论文如下:
[Car80] M. Carpano.用于计算机辅助决策分析的分层图形的自动显示.IEEE 软件工程汇刊，SE-12(4):538–546，1980 年 4 月.(显然可以购买 此处.)
[GKNV93] Emden R. Gansner、Eleftherios Koutsofios、Stephen C. North 和 Kiem-Phong Vo.一种绘制有向图的技术.IEEE 翻译软件工程，19(3):214–230，1993 年 5 月.(可用 此处在 Graphviz.org 网站上.)
[STT81] K. Sugiyama、S. Tagawa 和 M. Toda.分层系统结构的视觉理解方法.IEEE Transactions on Systems, Man, and Cybernetics, SMC-11(2):109–125, February 1981.(显然可以购买 此处.)
[War77] 约翰·沃菲尔德.交叉理论和层次映射.IEEE Transactions on Systems, Man, and Cybernetics，SMC-7(7):505–523，1977 年 7 月.(显然可以购买 此处.)
(2)一种绘制有向图的技术"
dot 的算法在论文 A Technique for Drawing Directed Graphs"中有详细描述，1993 年发表在 IEEE Transactions on Software Engineering 期刊上(可在 Graphviz.org 站点上免费获得).这是[GKNV93]"上面引用的来源.
就其价值而言，摘要是这样的:
<块引用>我们描述了一种用于绘制有向图的四遍算法.第一遍使用网络单纯形算法找到最佳等级分配.第二遍通过迭代启发式方法设置等级内的顶点顺序，该方法结合了新颖的权重函数和局部转置以减少交叉.第三遍通过构建和排序辅助图来找到节点的最佳坐标.第四遍使样条曲线绘制边缘.该算法画得好，运行速度快.
(3)使用 Graphviz 作为库"
将 Graphviz 用作库" 提供了每个布局引擎算法的摘要在第 3.1 节中.点的部分描述是这样的:
<块引用>如果可能，点算法会根据边缘方向生成图形的排序布局.它特别适用于显示层次结构或有向无环图.基本布局方案归功于 Sugiyama 等人.[STT81] dot 使用的具体算法遵循 Gansner 等人描述的步骤.[GKNV93]
点布局的步骤是:1) 初始化 2) 秩 3) mincross 4) 位置 5) 相同端口 6) 样条 7) 复合边
初始化后，算法使用整数程序将每个节点分配给离散秩(rank)，以最小化(离散)边长度的总和.下一步 (mincross) 重新排列等级内的节点以减少边缘交叉.接下来是将实际坐标分配(位置)到节点，使用另一个整数程序来压缩图形并拉直边缘.此时，所有节点都会在 coord 属性中设置一个位置.另外，设置了所有簇的边界框bb属性.
[GKNV93]"参考的是上面链接的绘制有向图的技术".
[STT81]"参考文献是层次系统结构的视觉理解方法".如上所述.
(4) 您可能还感兴趣:
Graphviz 的文档索引，其中包含指向详细文档和其他背景材料的链接.>
Graphviz 的理论"；页面链接到更多背景材料.
dot的原始源代码 现在在 GitLab 上，参见 dotgen 和 dotgen2.dot的原始源代码，可在 GitHub 上找到.
Is there any documentation (full pseudo code?) on the algorithm from dot within the Graphviz Library?
I only found some partial pseudo code documentation.
Here are a few references for you. The most complete (short of the Graphviz source code itself) is probably #2, the paper "A Technique for Drawing Directed Graphs" which is written by several of the Graphviz contributors themselves.
(1) "Drawing graphs with dot"
In Drawing graphs with dot, dot's layout algorithm is described like this:
dot draws graphs in four main phases. Knowing this helps you to understand what kind of layouts dot makes and how you can control them. The layout procedure used by dot relies on the graph being acyclic. Thus, the first step is to break any cycles which occur in the input graph by reversing the internal direction of certain cyclic edges. The next step assigns nodes to discrete ranks or levels. In a top-to-bottom drawing, ranks determine Y coordinates. Edges that span more than one rank are broken into chains of "virtual" nodes and unit-length edges. The third step orders nodes within ranks to avoid crossings. The fourth step sets X coordinates of nodes to keep edges short, and the final step routes edge splines. This is the same general approach as most hierarchical graph drawing programs, based on the work of Warfield [War77], Carpano [Car80] and Sugiyama [STT81]. We refer the reader to [GKNV93] for a thorough explanation of dot’s algorithms
The papers cited in that paragraph are these:
[Car80] M. Carpano. Automatic display of hierarchized graphs for computer aided decision analysis. IEEE Transactions on Software Engineering, SE-12(4):538–546, April 1980. (Evidently available for purchase here.)
[GKNV93] Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, and Kiem-Phong Vo. A Technique for Drawing Directed Graphs. IEEE Trans. Sofware Eng., 19(3):214–230, May 1993. (Available here on the Graphviz.org site.)
[STT81] K. Sugiyama, S. Tagawa, and M. Toda. Methods for Visual Understanding of Hierarchical System Structures. IEEE Transactions on Systems, Man, and Cybernetics, SMC-11(2):109–125, February 1981. (Evidently available for purchase here.)
[War77] John Warfield. Crossing Theory and Hierarchy Mapping. IEEE Transactions on Systems, Man, and Cybernetics, SMC-7(7):505–523, July 1977. (Evidently available for purchase here.)
(2) "A Technique for Drawing Directed Graphs"
dot's algorithm is described in detail in the paper "A Technique for Drawing Directed Graphs", published in the journal IEEE Transactions on Software Engineering in 1993 (and available for free on the Graphviz.org site). This is the "[GKNV93]" source cited above.
The abstract, for what it's worth, is this:
We describe a four-pass algorithm for drawing directed graphs. The first pass finds an optimal rank assignment using a network simplex algorithm. The second pass sets the vertex order within ranks by an iterative heuristic incorporating a novel weight function and local transpositions to reduce crossings. The third pass finds optimal coordinates for nodes by constructing and ranking an auxiliary graph. The fourth pass makes splines to draw edges. The algorithm makes good drawings and runs fast.
(3) "Using Graphviz as a Library"
"Using Graphviz as a Library" provides a summary of each layout engine's algorithim in Section 3.1. Part of the description for dot is this:
The dot algorithm produces a ranked layout of a graph respecting edge directions if possible. It is particularly appropriate for displaying hierarchies or directed acyclic graphs. The basic layout scheme is attributed to Sugiyama et al.[STT81] The specific algorithm used by dot follows the steps described by Gansner et al.[GKNV93]
The steps in the dot layout are: 1) initialize 2) rank 3) mincross 4) position 5) sameports 6) splines 7) compoundEdges
After initialization, the algorithm assigns each node to a discrete rank (rank) using an integer program to minimize the sum of the (discrete) edge lengths. The next step (mincross) rearranges nodes within ranks to reduce edge crossings. This is followed by the assignment (position) of actual coordinates to the nodes, using another integer program to compact the graph and straighten edges. At this point, all nodes will have a position set in the coord attribute. In addition, the bounding box bb attribute of all clusters are set.
The "[GKNV93]" reference is to "A Technique for Drawing Directed Graphs", as linked above.
The "[STT81]" reference is to "Methods for Visual Understanding of Hierarchical System Structures" as cited above.
(4) You might also be interested in:
Graphviz's Documentation Index, which has links to detailed documentation and additional background material.
Graphviz's "Theory" page which links to even more background material.
The raw source code for
dotis now on GitLab, see dotgen and dotgen2.The raw source code fordot, which is available on GitHub.Some related discussion on the d3.js Google Group.
这篇关于Graphviz 点算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
