Somme de l'arbre récursif sans définir une structure arborescente

Question

J'ai un dictionnaire (1) de nœuds et de nœuds enfants Dictionary<int,int[]> et une liste (2) de poids associés à chaque nœud. Le dictionnaire peut être interprété comme suit: par exemple: la clé 1 a des valeurs 3,4 ce qui signifie que le nœud id = 1 est parent aux nœuds 3 et 4. la clé 3 a des valeurs 5,6,8 ce qui signifie que le nœud id = 3 est parent aux nœuds 5,6 et 8 ... etc. La deuxième liste est juste une liste de poids où l'index représente l'identifiant de nœud auquel le poids est associé.

Je veux calculer pour chaque nœud clé de la liste (1) sa somme de tous les poids des nœuds enfants.

Je pense que ce problème est similaire à une somme arborescente récursive, bien que mes listes ne soient pas configurées en tant que structures arborescentes.

Comment dois-je procéder?

Answer 1

Voici une version Python d'une solution à ce que vous voulez atteindre:

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) 

qui donnent la sortie suivante:

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

Un collègue de travail est venu avec cette solution élégante (2 dictionnaires nécessaire). Peut-être pas le plus efficace cependant.

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