deblocker - 4 months ago 21

Javascript Question

I am receiving this data from a JSON export:

`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]}

]

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

Now, i need to aggregate the values of the

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

EDIT: the final result for the example provided shall be as follows:

`[`

{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: this is a drawing of the graph resulting from the data structure above, made by me:

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

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.

A non-recursive approach (if possible) would be greatly appreciated.

Answer

What makes this question hard, is that the `parentOf`

lists sometimes not only contain the *id* values of direct children, but also (some) of more remote descendants. So the true graph is not directly apparent.

For instance, the sample data lists node 9 as parent of nodes 2, 8 and 7. Yet the image shows that of those only 2 is a direct child of 9, while 8 and 7 are more distant descendants. Node 1, which is also a descendant of 9, is not listed in the `parentOf`

property of node 9.

The information of which are truly direct children *can* be deduced from the data as it is given, but it requires some work. Yet, this information is needed to be able to calculate the sums correctly.

Note that as a consequence of this kind of redundant input, it is impossible to define a triangle in the graph. Let's say node A has nodes B and C as children, and node B has node C as child: such a triangle will not be encodable in the above data structure, as the link between A and C will be considered as a redundant "grandchild" link.

In the solution I present here, I have used `Set`

for recording the descendants and direct children, as this allows for faster look-up than arrays do.

I also created a `Map`

for making the nodes accessible by their *id*. Again, this is for performance reasons.

When a cycle is detected in the graph, an exception will be thrown.

As requested, the algorithm does not rely on recursion.

Here is the 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);
```