用于生成软件堆栈图的算法

Question

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

​​

Answer 1

虽然不是一种算法（这是你要的），你可能想看看NDepend的执行类似的分析，并产生类似于图来你后一个：

http://ndepend.com/

（我与NDepend没有隶属关系）

Answer 2

这并不总是可能的。的（无环的）依赖关系：

A依赖于X，Y，Z

B依赖于X，Y，Z

，c取决于X，Y，Z

描述了六个顶点的完整二部图，即non-planar。这对于您显示的图的类型的结果是，图中至少有一个区域必须分成两个独立的部分，并且/或者至少有一个区域不能直接连接到它的相关部分。

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

启发式算法的轮廓生成排序图的您正在寻找如下：

1. 解析依赖关系树来计算每个项目的一个“等级”。在上面给出的例子中，X，Y和Z在每个等级1的图中将分别出现三次，分别为A，B和C（0级）的子元素
2. 以明显的方式绘制树，每个'水平'上的项目在同一水平上，他们的祖先/孩子分别低于/高于他们。可以选择在每个级别放置物品的顺序。
3. 根据单个项目在图形上分成多个区域的次数，计算图表的质量。如果项目的顺序是好的，并且代表相同项目的两个或多个区域彼此接触，则可以将它们融合在一起。
4. 使用此度量标准可以使用组合优化算法（例如Metropolis algorithm）来优化相同级别项目的排列。

这样每次都不会产生最好的图形（如果这样的概念甚至定义得很好......），但应该为您的示例等问题做出合理的工作。

Answer 3

STAN4J从java代码生成这种图。