3

我有一个几乎是树的有向无环图的集合，在以下意义上：每个图都有一个root，并且顶点被组织成级别，如果v 1和v 2是顶点，那么如果v 1的级别是小于v 2的水平，则图中没有从v 2到v 1的边，尽管从v 1可能有很多边到相同或更高级别的顶点。例如，表达式树、函数调用图或线性类层次结构都是此类图的示例。以下是此类图表的示例：

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

有大量的绘图算法，我无法确定哪种算法最适合这种情况。一些初步研究表明，绘制 Hasse 图的算法可能是合适的，但似乎此类算法的输出并不适合我试图建模的数据结构类型。还有几种用于对分层数据进行建模的算法，但我不确定哪种算法会在易于实现和效率之间取得平衡。前一种方法的一个问题是这些图既有根又有方向。如果可能，该算法将支持循环图，并最大限度地减少数值计算的数量，但这不是必需的。由于这些原因，我宁愿避免使用力导向算法，如果可能的话，点。

4

2 回答 2

1

如果它确实是一棵树，那么我之前已经看到这个Reingold-Tilford Tree 绘制算法工作得很好。

顺便说一句，我觉得允许节点 A2 '上升'到与其祖先相同的级别的决定并没有真正帮助那么多。

相反，我会允许一个节点进一步下降而不是上升。在我看来，这个例子可以画得更好，如下所示。

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

这样，您甚至不需要标记边缘方向。【我是不是误会你的原图了？我认为A2和A7之间没有优势对吧？]

于 2012-11-15T01:47:47.713 回答
1

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

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

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

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

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

dot actually does pretty well with DAGs, in my experience, although it sometimes needs a bit of a helping hand. In particular, if you know the level of each vertex, you can make a subgraph for each level with the attribute `rank = "same"'. (See this example.)

于 2012-11-15T06:50:32.847 回答