How to traverse a graph where a node has multiple parents and sum up values?

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 nodes array. Now, i need to aggregate the values of the data field.

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.

trincot · Accepted 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);

How to traverse a graph where a node has multiple parents and sum up values?

Answers (2)

Related Questions