生成软件堆栈图的算法

Question

我正在寻找一种算法的想法，该算法在给定一组非循环依赖关系的情况下生成类似于下图的图表（我使用此图像来表明依赖关系可能很复杂）

_{（来源：interactivetvweb.org）}

Answer 1

并不总是能够制作这样的图表。 （非循环）依赖关系：

A 取决于 X、Y、Z

B 取决于 X、Y、Z

C 取决于 X、Y、Z

描述了六个顶点上的完全二部图，即 非平面。 对于您显示的图表类型来说，这样做的结果是，图表中的至少一个区域必须分为两个单独的部分，和/或至少其中一个区域不得直接连接到其依赖项。

基于图形的可视化（例如 graphvis）可以避免此问题，其中边可以相互交叉。

用于生成您正在寻找的图表的启发式算法的概要如下：

1. 解析依赖关系树以计算每个项目的“级别”。 在上面给出的示例中，X、Y 和 Z 将在该图中在第 1 级分别出现 3 次，作为 A、B 和 C 的子级（在第 0 级）
2. 以明显的方式绘制树，项目位于每个“级别”位于同一水平级别，其祖先/子代分别位于其下方/上方。 可以选择每个级别的项目放置顺序。
3. 根据单个项目被分成图表上多个区域的次数，计算图表的好坏程度。 如果项目的顺序良好，并且代表同一项目的两个或多个区域相互接触，则可以将它们融合在一起。
4. 使用此指标来优化同一级别的项目排列，使用组合优化算法，例如 Metropolis 算法。

这不会每次都产生最好的图表（如果这样的概念是明确定义的......），但应该对像你的例子这样的问题做一个合理的工作。

Answer 2

虽然不是一种算法（这就是您所要求的），但您可能想看看 NDepend，它执行类似的分析并生成与您所追求的类似的图表：

http://ndepend.com/

（我与 NDepend 没有任何关系）

Answer 3

STAN4J 从 java 代码生成这种图表。