python - 树或图收缩

我目前正在使用python来解决“树摘要”问题。我的树由具有权重和子节点的节点组成。一个例子

Node(
    name: "Parent", weight: 20, children: {[
        Node(name: "Child 1" weight: 10, children: {[]},
        Node(name: "Child 2", weight: 10, children: {[
           Node(name: "Grandchild 1", weight: 5, children: {[]}
        ]}
     ]})

我感兴趣的是找到所有可能的图可以得到的边缘压缩。当我收缩两条边时，旧的顶点将被一个新的顶点替换，新的顶点的权重是旧顶点的总和。例如，将子2与孙子1签约会导致：

Node(
    name: "Parent", weight: 20, children: {[
        Node(name: "Child 1" weight: 10, children: {[]},
        Node(name: "(Child 2, Grandchild 1)", weight: 15, children: {[]}
     ]})

当然这只是一种可能的边缘收缩。即使对于这棵小树，也有更多的收缩（例如(child 1, child 2)，(child 1, parent)，(child 2, parent)）。
对于每个新树，我需要再次找到通过收缩一个节点获得的所有树（最终，问题是将一个n节点树减少为m节点树）。
我现在是“暴力强制”，递归地调用edge_contract（），直到达到正确节点大小的树但是代码需要能够在中等大小的树（大约25-50个节点）上工作，而当前的实现不是。
这种类型的树收缩是一个解决的问题。有什么好的方法来解决这个问题？

最佳答案

每次变换树时，都要确定收缩的边集。在您给出的示例中，集合将只包含从“Child 2”到孙子1的一条边。
如果你想找到所有可以通过收缩边得到的树，那就是2^d（其中d是原始树中边的总数）。
如您所说，您希望将n节点树转换为m节点树如果您已经知道“m”，那么您需要从具有m-1元素的2^d个集合中找到所有集合（因为m节点树将具有m-1边）。
如果只对m节点树的一个子集感兴趣，则随机选择所需的数量。