用于操作无限树的python库。
lazytree的Python项目详细描述
懒树
目录
安装
如果您只需要使用lazytree，您可以运行：
$ pip install lazytree
对于开发人员，请注意此项目使用 poetrypython包/依赖项 管理工具。请熟悉它，然后 运行：
$ poetry install
用法
aLazyTree是一个三元组，(root, child_map, view)，其中root : A
以及子映射child_map，它将a映射到
子级child_map : A -> List[A]定义树的结构和
view : A -> B定义树表示的内容。默认视图为
身份映射，lambda x: x。
此结构对于建模无限（或非常大）树非常有用 其中只需要访问有限数量的节点。例如， 下面的二叉树表示 间隔[0，1]。
fromlazytreeimportLazyTreedefsplit(itvl):lo,hi=itvlmid=lo+(hi-lo)/2return(lo,mid),(mid,hi)tree=LazyTree(root=(0,1),# Initial Itvlchild_map=split# Itvl -> [Itvl])
在概念上，一个LazyTree对象可以被认为包含了数据片段。
- 树的
root。 - 由
root表示的数据，通过view方法访问。 - 子子树-使用
child_map计算并通过.children属性访问。
例如，在我们的间隔示例中，每个节点对应于间隔(0, 1)，并且有两个子树。
# View the current root.asserttree.view()==tree.rootsubtrees=tree.childrenassertlen(subtrees)==2
通常，对于树中的每个节点，人们都对计算特定的函数感兴趣。这可以使用map和view方法来完成。例如，在map树中每个间隔的大小下。这将产生一个新的LazyTree对象。
tree2=tree.map(lambdaitvl:itvl[1]-itvl[0])# Change view to itvl size.asserttree2.view()==1# Access the root's subtreessubtrees=tree2.childrenassertlen(subtrees)==2assertsubtrees[0].root==(0,0.5)assertsubtrees[0].view()==0.5
还实现了LazyTree对象的travesals。例如，
# Breadth First Search through tree.## Note: calls .view() before returning. itvls=tree.bfs()# returns a generator.sizes=tree2.bfs()# returns a generator.assertnext(itvls)==(0,1)assertnext(sizes)==1assertnext(itvls)==(0,0.5)assertnext(sizes)==0.5assertnext(itvls)==(0.5,1)assertnext(sizes)==0.5# Cost guided traversal.## Note: Smaller means higher priority.sizes=tree2.cost_guided_refinement(cost=lambdax:x)assertnext(sizes)==1# (0, 1)assertnext(sizes)==0.5# (0, 0.5)assertnext(sizes)==0.25# (0, 0.25)# Iterative Deepening Depth First Traversalsizes=tree2.iddfs(max_depth=3)# returns a generator.assertlist(sizes)==[1,0.5,0.5,0.25,0.25,0.25,0.25,0.125,0.125,0.125,0.125,0.125,0.125,0.125,0.125]# Note, you can reset the current view.tree3=tree2.with_identity_view()asserttree3.view()==tree.view()
最后，可以使用prune方法将子树标记为叶节点来“修剪”子树。如果确定生成的树是有限的（由于修剪或提供的child_map），则可以计算树的叶子。
# Prune subtrees with a root of size less than 0.1.tree4=tree2.prune(isleaf=lambdas:s<0.2)sizes=tree.bfs()assertall(s>0.001forsinsizes)# Note that sizes is now finite.# Compute leafs of tree. Careful! Could be infinite!assertall(s==0.125forsintree4.leaves())assertlen(list(tree4.leaves()))==8
欢迎加入QQ群-->： 979659372
