winforms Reingold-Tilford算法的步骤是什么?我如何编程?

cbjzeqam  于 2023-10-23  发布在  Go
关注(0)|答案(2)|浏览(165)

从演示文稿中:Graphs and Trees在第3页,有一个视觉介绍在Reigngold-Tilford过程中发生了什么;对该算法也给出了一个模糊的总结:"...starts with bottom-up pass of the tree; [finishes with] Top-down pass for assignment of final positions..."我可以通过递归方法实现两个方向的传递,并且我知道Y值与每个节点的生成级别相关,但我仍然不知道如何求解X坐标。
我遇到了这个项目:A Graph Tree Drawing Control for WPF但是有这么多的代码,我很难找到一个简单的2-3个方法来定义X值。(也没有WPF的经验)
我一直在寻找和实验如何做到这一点几天了,所以你的帮助是非常感谢!

kd3sttzy

kd3sttzy1#

我发现jwpat7's answer中列出的文章非常有用,尽管我花了一段时间才弄清楚这个算法所需的确切逻辑,所以我写了我的own blog post来简化解释。
以下是如何确定X节点位置的纯文本逻辑:

  • 从树的post-order traversal开始
  • 如果每个节点是集合中的第一个,则将初始X值赋为0,如果不是,则赋为previousSibling + 1

  • 如果一个节点有子节点,找到所需的X值,使其位于子节点的中心。
  • 如果节点是最左边的节点,则将其X设置为该值
  • 如果该节点不是最左边的节点,则将该节点的Mod属性设置为(X - centeredX),以移动所有子节点,使其位于该节点下的中心。树的最后一次遍历将使用此Mod属性来确定每个节点的最终X值。
  • 确定此节点的任何子节点是否与此节点左侧的同级节点的任何子节点重叠。基本上,对于每个Y,从两个节点中获取最大和最小的X,并比较它们。
  • 如果发生任何冲突,则按所需的程度移动节点。移动子树只需要添加节点的XMod属性。
  • 如果节点被移动,也移动两个重叠子树之间的任何节点,使它们等间隔
  • 进行检查以确保计算最终X时没有负X值。如果找到了,将最大的一个添加到根节点的XMod属性中,以移动整个树
  • 使用前序遍历对树进行第二次遍历,并将每个节点的父节点的Mod值之和添加到它的X属性中

上面树的最终X值看起来像这样:

我有一些更多的细节和my blog post中的一些示例代码,但它太长了,无法在这里包含所有内容,我想专注于算法的逻辑而不是代码细节。

yh2wf1be

yh2wf1be2#

有几篇文章提供了代码,在1991年2月1日的Dr. Dobb's Journal article上用python编写的billmill.org和用C编写的page 2。你已经要求了“简单的2-3种方法”(也许意味着食谱方法),但是在它们的一般性中很好地绘制树是一个NP完全问题(参见Supowit,K. J.和E.M. Reingold,“The complex of drawing trees nicely,”Acta Informatica 18,4,January 1983,377-392,ref. 4在DDJ文章中)。Reingold-Tilford方法在线性时间内绘制二叉树或多或少很好,而Buchheim的变体在线性时间内绘制n元树或多或少很好。然而,billmill的文章指出(在陈述原则6之后不久),“到目前为止,我们在这篇文章中研究一个简单的算法时,我们发现它是不够的......”所以更简单的方法工作正常的可能性很小。

相关问题