2

我正在寻找一种算法的想法,该算法生成类似于以下的图表,给定一组非循环依赖项(我正在使用此图像来显示依赖项可能很复杂)

替代文字
(来源:interactivetvweb.org

4

3 回答 3

3

制作这样的图表并不总是可能的。(非循环)依赖关系:

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 算法

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

于 2009-05-11T15:15:10.450 回答
2

虽然不是一种算法(这是您所要求的),但您可能需要查看 NDepend,它执行类似的分析并生成与您所追求的类似的图表:

http://ndepend.com/

(我与 NDepend 没有任何关系)

于 2009-05-11T15:01:02.283 回答
0

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

于 2009-07-13T07:46:16.023 回答