Wie durchläuft ein Diagramm, in dem ein Knoten mehrere Eltern hat und Werte summiert?

Question

ich diese Daten aus einer JSON-Export empfange:

nodes = [ 
    {id:1,data:29,parentOf:[]}, 
    {id:2,data:31,parentOf:[1,8,7]}, 
    {id:3,data:41,parentOf:[2,1]}, 
    {id:4,data:89,parentOf:[3,2,1]}, 
    {id:5,data:71,parentOf:[4,3,2,1,9,2,8,7]}, 
    {id:6,data:11,parentOf:[5,4,3,2,1]}, 
    {id:7,data:59,parentOf:[]}, 
    {id:8,data:43,parentOf:[7]}, 
    {id:9,data:97,parentOf:[2,8,7]} 
] 

Dies ist eine Datenstruktur aus einem Diagramm, in dem ein ein Knoten null oder mehr Eltern haben können. Das Diagramm wurde für den Export in das Knoten Array abgeflacht. Jetzt muss ich die Werte der Daten Feld aggregieren.

Wie kann ich diesen Graphen durchlaufen, um die Gesamtsumme der Daten für jeden Knoten zu erhalten?

EDIT: das endgültige Ergebnis für das Beispiel ist wie folgt vorgesehen sein:

[ 
    {id:1,sum:29}, 
    {id:2,sum:162}, // 31+102+29 
    {id:3,sum:203}, // 41+162 
    {id:4,sum:292}, // 89+203 
    {id:5,sum:622}, // 71+292+259 
    {id:6,sum:633}, // 11+622 
    {id:7,sum:59}, 
    {id:8,sum:102}, // 43+59 
    {id:9,sum:259} // 97+162 
] 

EDIT 2: Dies ist eine Zeichnung der graphischen Darstellung von der Datenstruktur führt oben, die von mir:

Ich sehe jetzt, in der parentOf Array der Knoten, gibt es einige redundante Informationen.

Trotz der Tatsache, dass das angegebene Beispiel nur Knoten ohne Eltern (id: 6) hat, suche ich eine Lösung für den Normalfall, wo die Knoten ohne Eltern mehr als eins sind. Also denke ich, dass der Graph Traversal von den Blattknoten beginnen sollte, d.h. id: 1 und id: 7.

Ein nicht-rekursive Ansatz (wenn möglich) würde sehr geschätzt werden.

Answer 1

Was diese Frage schwierig macht, ist, dass die parentOf Listen nur manchmal nicht die id Werte der direkten Kinder enthalten, sondern auch (etwas) von entfernteren Nachkommen. Also ist der wahre Graph nicht direkt ersichtlich. Die Beispieldaten listet beispielsweise Knoten 9 als Elternknoten der Knoten 2, 8 und 7 auf. Dennoch zeigt das Bild, dass von diesen nur 2 ein direktes Kind von 9 ist, während 8 und 7 entferntere Nachkommen sind. Knoten 1, der auch ein Nachkomme von 9 ist, ist nicht im parentOf Eigenschaft des Knotens aufgeführt 9.

Die Informationen, von denen sind wirklich direkte Kinder können aus den Daten abgeleitet werden, wie es gegeben ist, aber es erfordert etwas Arbeit. Diese Information wird jedoch benötigt, um die Summen richtig berechnen zu können.

Beachten Sie, dass es als Konsequenz dieser Art redundanter Eingabe unmöglich ist, ein Dreieck im Diagramm zu definieren.Nehmen wir an, Knoten A hat die Knoten B und C als untergeordnete Knoten und Knoten B hat Knoten C als untergeordnet: Ein solches Dreieck ist in der obigen Datenstruktur nicht codierbar, da die Verbindung zwischen A und C als redundantes "Enkelkind" betrachtet wird. Verknüpfung.

In der Lösung, die ich hier präsentiere, habe ich Set für die Aufzeichnung der Nachkommen und direkte Kinder verwendet, da dies schnelleres Nachschlagen als Arrays ermöglicht.

Ich habe auch eine Map für die Herstellung der Knoten durch ihre ID erstellt. Auch dies ist aus Leistungsgründen.

Wenn ein Zyklus in der Grafik erkannt wird, wird eine Ausnahme ausgelöst.

Wie gefordert, ist der Algorithmus nicht auf Rekursion angewiesen. Hier

ist der Code:

function sumTree(nodes) { 
 
    // Take copy of nodes array, so that the original is not mutated 
 
    var nodes = nodes.map(node => ({ 
 
     id: node.id, 
 
     childrenSet: new Set(node.parentOf), // convert to Set for fast look-up 
 
     childrenSet2: new Set(node.parentOf), // copy 
 
     descendantSet: new Set(node.parentOf), // Will contain ALL descendants 
 
     sum: node.data 
 
    })); 
 
     
 
    // For faster lookup, create a Map with nodes keyed by their node.id. 
 
    var hash = new Map(nodes.map(node => [node.id, node])); 
 

 
    // Create complete descendants set for each node 
 
    nodesCopy = nodes.slice(); 
 
    while (true) { 
 
     // Get index of first node that has no (more) children 
 
     let i = nodesCopy.findIndex(node => !node.childrenSet.size); 
 
     if (i < 0) break; // Not found: then we're done 
 
     let id = nodesCopy.splice(i, 1)[0].id; // extract found node id 
 
     nodesCopy.forEach(parent => { 
 
      if (parent.childrenSet.has(id)) { // Found a parent of it 
 
       // Extend the parent's descendant list with the node's one 
 
       parent.descendantSet = new Set([...parent.descendantSet, 
 
               ...hash.get(id).descendantSet]); 
 
       // Don't consider this node any more. 
 
       // At one point the parent may become a leaf 
 
       parent.childrenSet.delete(id); 
 
      } 
 
     }); 
 
    } 
 
    if (nodesCopy.length) throw "Exception: graph has cycles"; 
 

 
    // Create true children sets (only direct children, without "redundancy"): 
 
    nodes.forEach(node => { 
 
     node.childrenSet = new Set(node.childrenSet2); 
 
     [...node.childrenSet] 
 
      // Collect descendants of children 
 
      .reduce((remote, id) => 
 
       new Set([...remote, ...hash.get(id).descendantSet]), new Set()) 
 
      // Remove any of those from the children's set 
 
      // (so no more "grand" children there) 
 
      .forEach(id => node.childrenSet.delete(id)); 
 
    }); 
 

 
    // Calculate the sums bottom-up 
 
    nodesCopy = nodes.slice(); 
 
    while (true) { 
 
     let i = nodesCopy.findIndex(node => !node.childrenSet.size); 
 
     if (i < 0) break; 
 
     let leaf = nodesCopy.splice(i, 1)[0]; 
 
     nodesCopy.forEach(parent => { 
 
      if (parent.childrenSet.has(leaf.id)) { 
 
       parent.sum += leaf.sum; 
 
       parent.childrenSet.delete(leaf.id); 
 
      } 
 
     }); 
 
    } 
 

 
    // Only return the information we need 
 
    return nodes.map(node => ({ id: node.id, sum: node.sum })); 
 
} 
 

 
// Sample data 
 
var nodes = [ 
 
    {id:1,data:29,parentOf:[]}, 
 
    {id:2,data:31,parentOf:[1,8,7]}, 
 
    {id:3,data:41,parentOf:[2,1]}, 
 
    {id:4,data:89,parentOf:[3,2,1]}, 
 
    {id:5,data:71,parentOf:[4,3,2,1,9,2,8,7]}, 
 
    {id:6,data:11,parentOf:[5,4,3,2,1]}, 
 
    {id:7,data:59,parentOf:[]}, 
 
    {id:8,data:43,parentOf:[7]}, 
 
    {id:9,data:97,parentOf:[2,8,7]} 
 
]; 
 

 
// Calculate sums 
 
var result = sumTree(nodes); 
 

 
// Output result 
 
console.log(result);

Answer 2

Ich glaube, ich bin etwas fehlt ... Bitte schauen Sie auf das, was folgen:

1. Iterate Alle Knoten
2. Summe node.data mit allen parents.data
3. Rückkehr ein Objekt mit nur id und sum Eigentum.

var nodes = [ 
 
    {id:1,data:29,parentOf:[]}, 
 
    {id:2,data:31,parentOf:[1,8,7]}, 
 
    {id:3,data:41,parentOf:[2,1]}, 
 
    {id:4,data:89,parentOf:[3,2,1]}, 
 
    {id:5,data:71,parentOf:[4,3,2,1,9,2,8,7]}, 
 
    {id:6,data:11,parentOf:[5,4,3,2,1]}, 
 
    {id:7,data:59,parentOf:[]}, 
 
    {id:8,data:43,parentOf:[7]}, 
 
    {id:9,data:97,parentOf:[2,8,7]} 
 
]; 
 

 

 
var result = nodes 
 
    .map((item, i, items) => { 
 
    let r = Object.create(null); 
 
    
 
    r.id = item.id; 
 
    
 
    r.sum = item.parentOf.reduce((prev, next, j) => { 
 
     let parent = (items.filter(x => x.id === next)[0] || {}); 
 
     let parentData = parent.data || 0; 
 
     
 
     return prev + parentData; 
 
    }, item.data); 
 

 
    return r; 
 
    }) 
 
; 
 

 
console.log('result', result);