Rekursive Baumsumme ohne Definition einer Baumstruktur

Question

Ich habe ein Wörterbuch (1) von Knoten und Kindknoten Dictionary<int,int[]> und eine Liste (2) von Gewichten, die jedem Knoten zugeordnet sind. Das Wörterbuch kann wie folgt interpretiert werden: zB: Schlüssel 1 hat Werte 3,4, was bedeutet, dass die Knoten-ID = 1 den Knoten 3 und 4 übergeordnet ist. Schlüssel 3 hat Werte 5,6,8, was bedeutet, dass Knoten-ID = 3 ist Eltern zu den Knoten 5, 6 und 8 usw. Die zweite Liste ist nur eine Liste von Gewichtungen, wobei der Index die Knoten-ID darstellt, der das Gewicht zugeordnet ist.

Ich möchte für jede Schlüsselknoten der Liste (1) seine Summe aller untergeordneten Knoten Gewichte berechnen.

Ich denke, dieses Problem ähnelt einer rekursiven Baumsumme, obwohl meine Listen nicht als Baumstrukturen eingerichtet sind.

Wie soll ich fortfahren?

Answer 1

Hier ist eine Python-Version einer Lösung zu dem, was Sie erreichen wollen:

dctNodeIDs_vs_Childs = {} 
dctNodeIDs_vs_Childs[1] = (2,3,4) 
dctNodeIDs_vs_Childs[2] = (13,14,15) 
dctNodeIDs_vs_Childs[3] = (5,6,7,8) 
dctNodeIDs_vs_Childs[4] = (9,10,11,12) 
lstNodeIDs_vs_Weight = [None,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] 

def getSumOfWeights(currNodeID, lstNodeIDs_vs_Weight = lstNodeIDs_vs_Weight, dctNodeIDs_vs_Childs = dctNodeIDs_vs_Childs): 
    sumOfWeights = 0 
    print("#currNodeID", currNodeID) 
    if currNodeID not in dctNodeIDs_vs_Childs: 
     sumOfWeights += lstNodeIDs_vs_Weight[currNodeID] 
    else: 
     for childNodeID in dctNodeIDs_vs_Childs[currNodeID]: 
      print("## childNodeID", childNodeID) 
      if childNodeID not in dctNodeIDs_vs_Childs: 
       sumOfWeights += lstNodeIDs_vs_Weight[childNodeID] 
      else: 
       sumOfWeights += lstNodeIDs_vs_Weight[childNodeID] + sum([ getSumOfWeights(nodeID) for nodeID in dctNodeIDs_vs_Childs[childNodeID] ]) 
    return sumOfWeights 

lstNodeIDs_vs_WeightsOfChildNodes = [None for _ in range(len(lstNodeIDs_vs_Weight)+1)]  
for nodeID in dctNodeIDs_vs_Childs.keys(): 
    print("nodeID =", nodeID) 
    lstNodeIDs_vs_WeightsOfChildNodes[nodeID] = getSumOfWeights(nodeID) 
print("---") 
print(lstNodeIDs_vs_WeightsOfChildNodes) 

die folgende Ausgabe geben:

nodeID = 1 
#currNodeID 1 
## childNodeID 2 
#currNodeID 13 
#currNodeID 14 
#currNodeID 15 
## childNodeID 3 
#currNodeID 5 
#currNodeID 6 
#currNodeID 7 
#currNodeID 8 
## childNodeID 4 
#currNodeID 9 
#currNodeID 10 
#currNodeID 11 
#currNodeID 12 
nodeID = 2 
#currNodeID 2 
## childNodeID 13 
## childNodeID 14 
## childNodeID 15 
nodeID = 3 
#currNodeID 3 
## childNodeID 5 
## childNodeID 6 
## childNodeID 7 
## childNodeID 8 
nodeID = 4 
#currNodeID 4 
## childNodeID 9 
## childNodeID 10 
## childNodeID 11 
## childNodeID 12 
--- 
[None, 119, 42, 26, 42, None, None, None, None, None, None, None, None, None, None, None, None] 

Answer 2

Ein Kollege bei der Arbeit mit dieser eleganten Lösung kam (2 Wörterbücher erforderlich). Vielleicht nicht die effizienteste.

double MethodName(int Id) => FirstDic.ContainsKey(Id) ? FirstDic[Id].Sum(n => MethodName(n)) : SecondDic.Where(y => y.Key == Id).Select(x => x.Value).Sum();