从演示文稿中: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的经验)
我一直在寻找和实验如何做到这一点几天了,所以你的帮助是非常感谢!
2条答案
按热度按时间kd3sttzy1#
我发现jwpat7's answer中列出的文章非常有用,尽管我花了一段时间才弄清楚这个算法所需的确切逻辑,所以我写了我的own blog post来简化解释。
以下是如何确定X节点位置的纯文本逻辑:
previousSibling + 1
。Mod
属性设置为(X - centeredX)
,以移动所有子节点,使其位于该节点下的中心。树的最后一次遍历将使用此Mod
属性来确定每个节点的最终X值。X
和Mod
属性。X
和Mod
属性中,以移动整个树Mod
值之和添加到它的X
属性中上面树的最终X值看起来像这样:
我有一些更多的细节和my blog post中的一些示例代码,但它太长了,无法在这里包含所有内容,我想专注于算法的逻辑而不是代码细节。
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之后不久),“到目前为止,我们在这篇文章中研究一个简单的算法时,我们发现它是不够的......”所以更简单的方法工作正常的可能性很小。