CODEWITHSUNDEEP
arraysalgorithmsumhierarchical-data
Alexi Coard
Alexi Coard

Reputation: 7772

Array get sum of all children bottom up

I have an javascript array which looks like this :

[
    {
        used : 24000,
        service : service A,
        parent : service B,
    },
    {
        used : 450,
        service : service B,
        parent : service C,
    },
    ...
]

I would like to iterate over the array to get the sum of each service child. For example if a service got A and B as a child, then its used attribute will be its own used + the sum of his child used. As a consequence, I need to get the deepest services in the hierarchy first.

Then final output could be : 

[
    {
        used : 24000,
        service : service A,
        parent : service B,
    },
    {
        used : 24450, //Sum here has changed
        service : service B,
        parent : service C,
    },
    ...
]

One last thing, the top service doesn't always have a null parent...

If need I can transform the array into a hierarchical one

Does anyone have a good algorithm which can do such a thing (posssibly in javascript, but pseudo code is cool too) ?

Upvotes: 3

Views: 259

Answers (2)

Jayson Boubin
Jayson Boubin

Reputation: 1504

This problem reminds me a lot of dependency building. In a dependency building problem, you have to schedule jobs based on their dependencies (Jobs that must come before them). If you have jobs A, B, and C, where A depends on B and C, you must schedule jobs B and C before A. Your problem appears to be not with scheduling, but adding numbers from your dependent jobs into your current job. To get the total "used" amount from Service A, you must first calculate the totals for Services B and C. Your array is a representation of a dependency graph, but instead of scheduling jobs, you are calculating the used attribute.

The trouble is that your implementation must be very different if your graph is not a tree. From the description of your problem, it sounds like we're dealing with a tree. If we are not, then please let me know in the comments and I can update my answer. If you think of your graph as a dependency tree, then all you need to do is guarantee that, for every node in the graph, you evaluate it's children before you evaluate it. This can be done by using a post order traversal http://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/. If you can implement a post order traversal on this dependency graph, you can simply add the values returned by the left size and right side traversals to your current total, then return the new "users" attribute for it's parents to use. This is a O(n) algorithm which calculates your values.

Upvotes: 0

fafl
fafl

Reputation: 7387

You can use map, reduce and filter to do it in a couple of lines:

var services = [{
        used : 24000,
        service : "A",
        parent : "B",
    }, {
        used : 450,
        service : "B",
        parent : "C",
    }, {
        used : 150,
        service : "C",
    }, {
        used: 100,
        service: "D"
    }
]

// Update one service, children first
var _update_service_sums = function(service, services) {
    var children = services.filter(s => s.parent === service.service)
    children.forEach(c => _update_service_sums(c, services))
    service.used_sum = service.used + children.map(c => c.used_sum).reduce((a, b) => a + b, 0);
}

// Update all services
var update_service_sums = function(services) {
    var roots = services.filter(s => s.parent === undefined)
    roots.forEach(r => _update_service_sums(r, services))
}

update_service_sums(services)
console.log(services)

I didn't want to change the value of used, so that you can call the function multiple times in a row.

I'm assuming here that there can be multiple root services and they all have no parent. If you wish to compute the used_sum for other services you can call _update_service_sums(service, services) directly.

Upvotes: 2

Related Questions