1

I am currently using Python to solve a "tree summarization" problem. My tree consists of nodes which have weights and children. An example

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: {[]}
        ]}
     ]})

I am interested in finding all possible graphs obtainable by edge contractions. When I contract two edges, the old vertices are replaced by a new vertex whose weight is the sum of the old vertices. For example, contracting Child 2 with Grandchild 1 results in:

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

Of course this is only one possible edge contraction. Even for this small tree, there are many more contractions (e.g. (child 1, child 2), (child 1, parent), (child 2, parent)).

For each of these new trees, I need to again find all trees obtained by contracting one node (ultimately, the problem is to reduce a n-node tree to an m-node tree).

I am currently "brute forcing", recursively calling edge_contract() until I reach trees of the right node size. But the code needs to be able to work on moderately sized trees (~25-50 nodes) and the current implementation is not.

Is this type of tree contraction a solved problem. What are some good ways to tackle the problem?

4

1 回答 1

1

每次转换树时，您都在决定要收缩的边集。在您给出的示例中，该集合将仅包含从“子 2”到孙 1 的一条边。

如果您有兴趣找到通过收缩边可以得到的所有树，那将是 2^d（其中 d 是原始树中边的总数）。正如您所说，您想将 n 节点树转换为 m 节点树。如果您已经知道“m”，那么您需要从总共 2^d 个具有 m-1 个元素的集合中找到所有集合（因为 m 节点树将具有 m-1 个边）。

如果您只对 m 节点树的一个子集感兴趣，那么随机选择您想要的数量。

于 2015-12-23T19:33:23.600 回答