All geek questions in one place

Group array by nested dependent array element

I have a task data warehouse. Each task also has an array of taskId , on which it depends.

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 result is a grouping of all dependent tasks into one array for display in the user interface.

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 made a function to do this, but it seems I was thinking wrong by hard-coded it. Hope someone can help me archive it properly using pure JavaScript / TypeScript or Underscore since we already used it in the project.

Note: TaskId will be a random string like "5878465507b36e1f9c4c46fe"

+4
4
// 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);
}

:

, inputArr . indexCache, , , null inputArr. , inputArr, :

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);
+2

order . union and find disjoint set .

:

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

:

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

:

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 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: id - , this.parent -, ( ), topological sort.

+1

,

  • For each task, find if there is a group in the list of groups with id or id of any dependent tasks
  • If you do not add a new group with a task identifier 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;
}
Run code
+1
source

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));
Run code
+1
source

Source: https://habr.com/ru/post/1666869/

More articles:


All Articles