Order an array of objects based on a list of dependencies?

Question

I need to arrange an array of objects consisting of a name and a list of dependencies (made from names).

An example of this array might be:

[
  { name: 'a', requires: ['b', 'c'] },
  { name: 'b', requires: ['c'] },
  { name: 'c', requires: [] },
]

I would like this array to be sorted so that elements requiring a specific set of dependencies are located after the necessary dependencies.
An array can contain more elements, I'm fine if the sort function throws an error in the case of circular dependencies.

Output Example:

[
  { name: 'c', requires: [] }, // first, no dependencies, and required by both the others
  { name: 'b', requires: ['c'] }, // second, because it needs `c` first
  { name: 'a', requires: ['b', 'c'] }, // last, because requires both the others
]

What is the most concise way to do this?

Answer 1

You can try the following (modified test case to support more possible combinations)

var arr = [
  { name: 'd', requires: ['a', 'c'] },
  { name: 'a', requires: ['b', 'c'] },
  { name: 'b', requires: ['c'] },
  { name: 'e', requires: ['d'] },
  { name: 'c', requires: [] },
];

var map = {}; // Creates key value pair of name and object
var result = []; // the result array
var visited = {}; // takes a note of the traversed dependency

arr.forEach(function(obj){ // build the map
  map[obj.name]  = obj;
});

arr.forEach(function(obj){ // Traverse array
  if(!visited[obj.name]) { // check for visited object
    sort_util(obj);
  }
});

// On visiting object, check for its dependencies and visit them recursively 
function sort_util(obj){
    visited[obj.name] = true;
    obj.requires.forEach(function(dep){
        if(!visited[dep]) {
           sort_util(map[dep]);
        } 
    });
    result.push(obj);
}

console.log(result);

Run codeHide result

Answer 2

, , .

, .

function order(array) {
    var i = 0,
        j,
        temp;

    while (i < array.length) {
        temp = array.slice(0, i);
        for (j = i; j < array.length; j++) {
            if (array[j].requires.every(n => temp.some(({ name }) => n === name))) {
                array.splice(i++, 0, array.splice(j, 1)[0]);
                break;
            }
        }
    }
    return array;
}

var array = [{ name: 'd', requires: ['a', 'c'] }, { name: 'a', requires: ['b', 'c'] }, { name: 'b', requires: ['c'] }, { name: 'e', requires: ['d'] }, { name: 'c', requires: [] }];

console.log(order(array));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Hide result

Answer 3

Update: thanks to Nina Scholz, I updated the code to sortwork

It can do the job. The idea is to have the user sortand check if the item is ain the item requirement b. If so, we can assume what ashould be before b. But I'm not 100% sure, I just checked your example and @nikhilagw example. Maybe I forgot something. Please let me know if this worked!

For each element, I additionally inherit all the dependencies.

const list = [
{ name: 'b', requires: ['c'] },
{ name: 'e', requires: ['d'] },
{ name: 'd', requires: ['a', 'c'] },
{ name: 'c', requires: [] },  
{ name: 'a', requires: ['b', 'c'] }, 
];

// indexed by name
const mapped = list.reduce((mem, i) => {
  mem[i.name] = i;
  return mem;
}, {});

// inherit all dependencies for a given name
const inherited = i => {
  return mapped[i].requires.reduce((mem, i) => {
  return [ ...mem, i, ...inherited(i) ];
  }, []);
}

// order ... 
const ordered = list.sort((a, b) => {
  return !!~inherited(b.name).indexOf(a.name) ? -1 : 1;
})

console.log(ordered);

Run codeHide result