How to traverse a graph where a node has multiple parents and sum up values?
<p>I am receiving this data from a JSON export:</p>

<pre><code>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]}
]
</code></pre>

<p>This is a data structure from a graph where a a node can have zero or more parents. The graph has been flattened for export into the <strong>nodes</strong> array.
Now, i need to aggregate the values of the <strong>data</strong> field.</p>

<p>How can i traverse this graph to get the total sum of data for each node?</p>

<p>EDIT: the final result for the example provided shall be as follows:</p>

<pre><code>[
    {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
]
</code></pre>

<p>EDIT 2: this is a drawing of the graph resulting from the data structure above, made by me:</p>

<p><a href="https://i.stack.imgur.com/9CJ8E.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/9CJ8E.png" alt="enter image description here"></a></p>

<p>I see now, in the parentOf array of the nodes, there is some redundant information. </p>

<p>Despite the fact that the provided example has just only node without parents (id:6), i'm searching a solution to handle the normal case where the nodes without parents are more than one. So i think the graph traversal should start from the leaf nodes, i.e. id:1 and id:7.</p>

<p>A non-recursive approach (if possible) would be greatly appreciated.</p>