论文标题
使用重量序列快速生成未标记的免费树木
Fast Generation of Unlabelled Free Trees using Weight Sequences
论文作者
论文摘要
在本文中，我们介绍了有序树的新表示形式，即重量序列表示。然后，我们使用它来为根部树和自由树构建新的表示，即规范的重量序列表示。我们构建算法，以生成订单n的所有根和游离树的权重序列表示，然后添加许多修改以提高算法的效率。该算法的Python实现结合了进一步的改进，通过使用发电机来避免存储递归调用返回的长树，并缓解小订单的扎根树的清单，从而消除许多递归呼叫。我们进一步展示了如何修改算法以生成邻接列表和免费树的邻接矩阵表示。我们比较了Python实施的跑步时间，该实施方式与从NetworkX获取的著名WROM算法的Python实现。我们的算法的实现速度超过了WROM算法的实现的四倍。生成邻接列表和矩阵的运行时间比重量序列的运行时间要长，但仍然是WROM算法的相应实现的三倍。
In this paper, we introduce a new representation for ordered trees, the weight sequence representation. We then use this to construct new representations for both rooted trees and free trees, namely the canonical weight sequence representation. We construct algorithms for generating the weight sequence representations for all rooted and free trees of order n, and then add a number of modifications to improve the efficiency of the algorithms. Python implementations of the algorithms incorporate further improvements by using generators to avoid having to store the long lists of trees returned by the recursive calls, as well as caching the lists for rooted trees of small order, thereby eliminating many of the recursive calls. We further show how the algorithm can be modifed to generate adjacency list and adjacency matrix representations for free trees. We compared the run-times of our Python implementation for generating free trees with the Python implementation of the well-known WROM algorithm taken from NetworkX. The implementation of our algorithm is over four times as fast as the implementation of the WROM algorithm. The run-times for generating adjacency lists and matrices are somewhat longer than those for weight sequences, but are still over three times as fast as the corresponding implementations of the WROM algorithm.
