Group array by nested dependent array element

Question

I have an array store Task information. Each task has also an array of taskId that it is depending on.

Input

let inputArr = [
    {
        id: 1,
        dependOnTasks: [2, 3]
    },
    {
        id: 2,
        dependOnTasks: [3]
    },
    {
        id: 3,
        dependOnTasks: []
    },
    {
        id: 4,
        dependOnTasks: [5]
    },
    {
        id: 5,
        dependOnTasks: []
    },
    {
        id: 6,
        dependOnTasks: [5]
    }
]

The expected output is grouping all the depending task into one array for displaying into the UI.

Output

[
    [
        {
            id: 1,
            dependOnTasks: [2, 3]
        },
        {
            id: 2,
            dependOnTasks: [3]
        },
        {
            id: 3,
            dependOnTasks: []
        }
    ],
    [
        {
            id: 4,
            dependOnTasks: [5]
        },
        {
            id: 5,
            dependOnTasks: []
        },
        {
            id: 6,
            dependOnTasks: [5]
        }
    ]
]

I have made a function to do it but seem I was thinking wrong by hard-coded it. Hope someone can help me archive it right way using pure JavaScript/TypeScript or Underscore since we have already used in the project.

Noted: TaskId will be random string like "5878465507b36e1f9c4c46fe"

What would be the expected output if e.g. task 3 depends on task 4 ? Or task 5 depends on task 1? — Robin Mackenzie
– Robin Mackenzie, Commented Jan 16, 2017 at 4:11
If task 3 depend on task 4, we can conclude that all the task depending each other. So the result will be a group of 6 task. The same for If task 5 depend on task 1. Is this clear enough for you? Just let me know If any more queries. — trungvose
– trungvose, Commented Jan 16, 2017 at 4:19
Is the IDs like that (1 for the first object, 2 for the second, and so on ...)? Or they're random numbers? — ibrahim mahrir
– ibrahim mahrir, Commented Jan 16, 2017 at 4:45

ibrahim mahrir · Accepted Answer · 2017-01-18 14:55:07Z

// will contain the groups (results).
var result = [];

// will serve as a holder of the already treated indexes of inputArr.
var indexCache = [];

// insert obj into a group, insert its dependencies and the object that depend on it as well.
function insertWithDependencies(obj, group){
    // insert this obj into this group
    group.push(obj);

    // First: look for the objects it depends on
    obj.dependOnTasks.forEach(function(id){
        for(var i = 0; i < inputArr.length; i++){
            // if the object in this index is already treated, then ignore it
            if(indexCache.indexOf(i) != -1) continue;
            // if this object is a dependency of obj then insert it with its own dependencies.
            if(inputArr[i].id == id){
                var o = inputArr[i];
                indexCache.push(i); // cache this i as well
                insertWithDependencies(o, group);
            }
        }
    });

    // Then: look for the objects that depends on it
    for(var i = 0; i < inputArr.length; i++){
        // if the object in this index is already treated, then ignore it
        if(indexCache.indexOf(i) != -1) continue;
        // if this object depends on obj then insert it with ...
        if(inputArr[i].dependOnTasks.indexOf(obj.id) != -1){
            var o = inputArr[i];
            indexCache.push(i); // cache i 
            insertWithDependencies(o, group);
        }
    }
};

// while there is element in the inputArr that haven't been treated yet
while(inputArr.length != indexCache.length){
    // the group that will hold the depending tasks all together
    var group = [];

    // look for the first untreated object in inputArr
    var i;
    for(i = 0; i < inputArr.length; i++)
        if(indexCache.indexOf(i) == -1)
            break;
    var obj = inputArr[i];

    // cache its index
    indexCache.push(i)

    // insert it along its dependencies
    insertWithDependencies(obj, group);

    // push the group into the result array
    result.push(group);
}

ANOTHER WAY:

Here is an optimised way to do it, but the data inside inputArr will be lost afterwards. It won't use the indexCache to see if an index is already treated or not but instead it will make all treated items null in inputArr. So if you don't care or won't use inputArr afterwards, use this instead:

var result = [];
function insertWithDependencies(obj, group){
    group.push(obj);
    obj.dependOnTasks.forEach(function(id){
        for(var i = 0; i < inputArr.length; i++){
            if(!inputArr[i]) continue;
            if(inputArr[i].id == id){
                var o = inputArr[i];
                inputArr[i] = null;
                insertWithDependencies(o, group);
            }
        }
    });
    for(var i = 0; i < inputArr.length; i++){
        if(!inputArr[i]) continue;
        if(inputArr[i].dependOnTasks.indexOf(obj.id) != -1){
            var o = inputArr[i];
            inputArr[i] = null;
            insertWithDependencies(o, group);
        }
    }
};

function findNotNull(){
    for(var i = 0; i < inputArr.length; i++)
        if(inputArr[i]) return i;
    return -1;
}

var index;
while((index = findNotNull()) != -1){
    var group = [];

    var obj = inputArr[index];
    inputArr[index] = null;
    insertWithDependencies(obj, group);

    result.push(group);
}

console.log(result);

Low Flying Pelican · Accepted Answer · 2017-01-16 06:01:54Z

1

The solution is straightforward,

Initialize empty group list
For each task find if there is a group in the group list with id or id of any dependent tasks
If not add a new group with task id and dependent tasks

var input = [
    { id: 1,  dependOnTasks: [2, 3]   },
    { id: 2,  dependOnTasks: [3]  },
    { id: 3,  dependOnTasks: [] },
    { id: 4,  dependOnTasks: [5] },
    { id: 5,  dependOnTasks: [] },
    { id: 6,  dependOnTasks: [5] }
];

var groups = [];

for (var i = 0; i < input.length; i++){
  var group = findGroup(groups,input[i]);
  if (!group){
    group = {ids : []};
    group.ids.push(input[i].id);
    groups.push(group);
  }
  
  if (group.ids.indexOf(input[i].id) === -1){
    group.ids.push(input[i].id);    
  }
  
  for (var j = 0; j < input[i].dependOnTasks.length; j++){
    if (group.ids.indexOf(input[i].dependOnTasks[j]) === -1){
      group.ids.push(input[i].dependOnTasks[j]);    
    }
  }
}
document.write(groups[0].ids + '</br>');
document.write(groups[1].ids + '</br>');

function findGroup(groups,task){
  for (var i = 0; i < groups.length; i++){
    var group = groups[i];
    if (group.ids.indexOf(task.id) !== -1){
      return group;
    }
    
    for (var j = 0; j < task.dependOnTasks.length; j++){
      if (group.ids.indexOf(task.dependOnTasks[j]) !== -1){
        return group;
      }
    }
  }
  return null;
}

answered Jan 16, 2017 at 6:01

Low Flying Pelican

6,0621 gold badge36 silver badges44 bronze badges

1 Comment

trungvose Over a year ago

With my data, it appear to be wrong somehow. I will update the question with this data later.

Allen · Accepted Answer · 2017-01-16 06:09:26Z

If you don't care about the order of the tasks in the same group. Using union and find to implement a disjoint set might be an option.

Util data structure:

function UnionFind(n) {
  this.parent = [...Array(n+1).keys()]
}

UnionFind.prototype.find = function(x) {
  if (this.parent[x] === x) {
    return x
  }
  const ret = this.find(this.parent[x])
  this.parent[x] = ret
  return ret
}

UnionFind.prototype.union = function(x, y) {
  let x_rep = this.find(x)
  let y_rep = this.find(y)
  if (x_rep !== y_rep) {
    this.parent[x_rep] = y_rep
  }
}

Dumb data source:

let inputArr = [
    {
        id: 1,
        dependOnTasks: [2, 3]
    },
    {
        id: 2,
        dependOnTasks: [3]
    },
    {
        id: 3,
        dependOnTasks: []
    },
    {
        id: 4,
        dependOnTasks: [5]
    },
    {
        id: 5,
        dependOnTasks: []
    },
    {
        id: 6,
        dependOnTasks: [5]
    }
]

Driver program:

let len = inputArr.length
let uf = new UnionFind(len)

// iterate through all tasks to group them
inputArr.forEach(entry => {
  entry.dependOnTasks.forEach(depsId => {
    uf.union(entry.id, depsId)
  })
})

// reiterate to retrieve each task's group and group them using a hash table
let groups = {}
inputArr.forEach(entry => {
  const groupId = uf.find(entry.id)
  if (!groups.hasOwnProperty(groupId)) {
    groups[groupId] = [entry]
    return
  }
  groups[groupId].push(entry)
})

let result = Object.keys(groups).map(groupId => groups[groupId])
console.log(JSON.stringify(result, null, 2))

note: if id is random string in your case, simply change this.parent to hash map, and if you care about the order(as there're dependency trees), consider using topological sort instead.

Tung Hoang · Accepted Answer · 2017-01-16 07:58:53Z

You can try with my code

var inputArr = [
    {
        id: 1,
        dependOnTasks: [2, 3]
    },
    {
        id: 2,
        dependOnTasks: [3]
    },
    {
        id: 3,
        dependOnTasks: []
    },
    {
        id: 4,
        dependOnTasks: [5]
    },
    {
        id: 5,
        dependOnTasks: []
    },
    {
        id: 6,
        dependOnTasks: [5]
    }
]

// make matrix graph
var map = {};
for (var i = 0; i < inputArr.length; i++) {
    var task = inputArr[i];
    map[task.id] = map[task.id] || {};
    for (var j = 0; j < task.dependOnTasks.length; j++) {
        var dependId = task.dependOnTasks[j];
        map[dependId] = map[dependId] || {};
        map[task.id][dependId] = true;
        map[dependId][task.id] = true;
    }
}

var groupTasks = [];

for (var key in map) {
    var group = groupTasks.filter(function(e) {
        return e.indexOf(key) >= 0;
    })[0]

    if (!group) {
        group = [key];
        groupTasks.push(group);
    }

    for (var dependKey in map[key]) {
        if (group.indexOf(dependKey) == -1) {
            group.push(dependKey);
        }
    }
}

var result = groupTasks.map(function(group) {
    var tasks = [];
    group.forEach(function(id) {
        var task = inputArr.filter(function(e) { return e.id == id })[0];
        tasks.push(task);
    });
    return tasks;
})

console.log(JSON.stringify(result, null, 4));

Collectives™ on Stack Overflow

Group array by nested dependent array element

4 Answers 4

Comments

1 Comment

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related