algorithm - 分层数据的最佳图形绘制算法？

Question

我有一组有向非循环图，它们几乎树，在以下意义上:每个图都有一个根，并且顶点被组织成级别，这样如果v₁ 和v₂ 是顶点，那么如果v₁的层数小于v₂的层数，那么就没有边图中从v₂到v₁，虽然从v<可能有很多条边/em>₁ 到相同或更高级别的顶点。例如，表达式树、函数调用图或线性类层次结构都是此类图的示例。这是此类图表的示例:

              A1            
             /  \           A1 -> A4, A3
            /    \          A3 -> A2, A6, A7
          A4  A2--A3        A2 -> A6
              | \ / \
              A6 \_ A7

有大量的图形绘制算法，我无法确定哪种最适合这种情况。一些初步研究表明，绘制哈斯图的算法可能是合适的，但此类算法的输出似乎并不适合我尝试建模的数据结构类型。还有几种用于分层数据建模的算法，但我不确定哪种算法可以平衡实现的容易性和效率。前一种方法的一个问题是这些图有一个根和一个方向。如果可能，该算法将支持循环 图，并尽量减少数值计算的数量，但这不是必需的。出于这些原因，我宁愿避免力导向算法，如果可能的话，GraphViz 算法，例如 dot。

Answer 1

这不是真正的答案，但评论太长了。

您的图与一般有向无环图有何不同？

DAG 不一定要有根，但我认为这对绘制图形影响不大。

就层级而言，对于任何 DAG，都可以定义一个函数层级 (v)，使得对于任何边 v_i → v_j，层级(i) ≤ 级别 (j)。平凡级函数是顶点在顶点拓扑顺序中的索引。另一种是从根到顶点的最长路径的长度。

Reingold-Tilford 树绘制算法绘制有序树(即顶点的边是有序的树)。您的示例表明您的图形没有排序，实际上您面临的主要问题是找到一种边缘排序，它可以最大限度地减少边缘交叉。所以这可能就是您要解决的问题。 (这不是一个简单的问题。)

dot 实际上在 DAG 方面做得很好，根据我的经验，尽管它有时需要一点帮助。特别是，如果你知道每个顶点的级别，你可以为每个级别创建一个子图，属性为 `rank = "same"'。 (参见 this example。)