Ключевая ошибка в придании веса к узлам питона

Question

У меня есть график, который имеет следующие пути {45,412,460,462},{45,457}

Я должен назначить веса таким образом, что от листа к корню:

1. Все листовые узлы получают вес

2. Если узел имеет одного ребенка: Тогда вес узла становится * вес своего единственного ребенка

3. Если узел имеет двух или более детей, то вес этого узла:

   вес его ребенка1 * вес child2 * A * B

   например, выход конечные веса узла:

   462: А, 457: А, 460: А * А, 412: (А * А * А), 45: А * в (А * А * А * А)

Я работаю с код в 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 петля пытается получить вес этих детей. weight содержит значение для дочернего узла 457, но, по-видимому, еще не значение для другого дочернего узла: node 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()