Graphviz点算法 [英] Graphviz Dot Algorithm

问题描述

我只发现了一些部分的伪代码文档。

解决方案

以下是一些参考资料。最完整的（短点源代码本身）可能是＃2，这是由几个Graphiz贡献者自己写的论文绘制有向图的技巧。

（1）用圆点绘制图形

在用点绘图，点的布局算法如下所示：

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

该段引用的论文是这些：

• [Car80] M. Carpano。自动显示用于计算机辅助决策分析的分层图。 IEEE Transactions on Software Engineering，SE-12（4）：538-546，April 1980.（显然可购买

，Kiem-Phong Vo。一种绘制有向图的技巧。 IEEE Trans。 Sofware Eng。，19（3）：214-230，1993年5月。（可在此处 ）。

[STT81] K. Sugiyama，S. Tagawa和M. Toda。可视化理解分层系统结构的方法。 IEEE Transactions on Systems，Man，and Cyber​​netics，SMC-11（2）：109-125，1981年2月（显然可以购买 here 。） 交叉理论与层次映射。 IEEE Transactions on Systems，Man，and Cyber​​netics，SMC-7（7）：505-523，1977年7月。（显然可购买

（2）A技术对于绘制直方图

dot的算法在文章中详细介绍 1993年出版的IEEE Transactions on Software Engineering 杂志上的一种绘制有向图的技术（可在Graphviz.org网站上免费获得）。这是上面引用的[GKNV93]来源。

摘要，值得一提的是：

我们描述了绘制有向图的四遍算法。第一遍使用网络单纯形算法找到最佳排名分配。第二遍通过迭代启发式来设置排名内的顶点顺序，所述迭代启发式结合了新颖的权重函数和局部转置来减少交叉。第三遍通过构建和排列辅助图来找到节点的最佳坐标。第四遍使样条曲线绘制边缘。

（3）使用Graphviz作为库

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

点算法在可能的情况下产生关于边缘方向的排列的图形布局。它特别适合显示层次或有向无环图。基本的布局方案归因于Sugiyama等人[STT81] dot使用的特定算法遵循Gansner等人[GKNV93]描述的步骤

点布局是：1）初始化2）等级3）最小交叉4）位置5）相同的端口6）样条7）复合边

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

[GKNV93]的引用是A Technique for绘制有向图，如上所链接。

[STT81]引用是上面引用的可视化理解分层系统结构的方法。

（4）您可能也有兴趣：
$ b $ ul

Graphviz的文档索引，其中包含指向详细文档和其他背景材料的链接。

Graphviz的理论页面，链接到更多的背景材料。

dot 的原始源代码，可在GitHub上获得。 一些相关的讨论 d3.js Google群组。

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 dot source code itself) is probably #2, the paper "A Technique for Drawing Directed Graphs" which is written by several of the Graphiz 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 dot, which is available on GitHub.

• Some related discussion on the d3.js Google Group.

这篇关于Graphviz点算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！