python - 在 python 中为节点赋予权重的关键错误

Question

我有一个具有以下路径的图表:

{45,412,460,462},{45,457}

我必须分配权重，使得从叶到根:

1. 所有叶节点的权重为A

2. 如果一个节点只有一个 child :那么这个节点的权重就变成了它的单个 child 的A*权重

3. 如果一个节点有两个或更多子节点，则该节点的权重为:

   weight of its child1\*weight of child2\*A\*B
   

   例如，输出是节点的最终权重:

   462: A, 457: A, 460: A\*A, 412: (A\*A\*A) , 45: A\*B(A\*A\*A\*A)
   

我正在使用 python 编写代码，但遇到了 keyerror 412。

我有三个字典:

parent_of[node['id']]=parent # parent of a node as value
child_of[node['id']]=children # the list of children of a node
no_child_of[node['id']]=len(child_of[node['id']]) # number of children

#assigning weights to leaf
for c in no_child_of.keys():
    if no_child_of[c]==0:
        weight[c]=A
# assigning weight to the parent
for w in weight.keys():
    par=parent_of[w]
    n=len(child_of[par])
    if n > 1:
        weight[par]=B
        for i in range(n):
            weight[par]=weight[par]*weight[child_of[par][i]]

Answer 1

让我们假设为父节点分配权重的循环从节点 457 开始。par 则为 45，它有多个子节点，因此内部 for 循环尝试得到那些 child 的体重。 weight 包含子节点 457 的值，但显然还没有另一个子节点的值:节点 412。因此出现 KeyError。

无论如何，我看不到您使用该循环的方法如何将权重分配给叶节点的直接父节点以外的其他节点。

像这样的问题通常用递归来解决。例如这样:

from operator import mul


def assign_weights(parent_of, children_of, a_value, b_value):
    weight_of = dict()

    def calculate_weight(node):
        weight = weight_of.get(node)
        if weight is None:
            children = children_of[node]
            weight = reduce(
                mul,
                (calculate_weight(c) for c in children),
                a_value * (b_value if len(children) > 1 else 1)
            )
        weight_of[node] = weight
        return weight

    for root in (node for node, parent in parent_of.items() if parent is None):
        calculate_weight(root)

    return weight_of


def main():
    # 
    # Data for a tree described by two paths (root to leaf):
    # [45, 412, 460, 462] and [45, 457].
    # 
    parent_of = {45: None, 412: 45, 460: 412, 462: 460, 457: 45}
    children_of = {45: [412, 457], 412: [460], 460: [462], 462: [], 457: []}
    print(assign_weights(parent_of, children_of, 23, 42))


if __name__ == '__main__':
    main()