Order array of objects based on dependencies list?

Question

I need to order an array of objects, composed by a name and a dependencies list (made out of names).

An example of this array could be:

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

I'd like this array to be sorted so that the items which require a specific set of dependencies will be positioned after its required dependencies.
The array could actually contain more items, I'm okay if the sorting function throws an error in case of circular dependencies.

Example output:

[
  { 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's the most concise way to do it?

Answer 1

You can try following (changed 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);

Answer 2

Update: thanks to Nina Scholz, I updated the code so that sort should work

This might do the job. The idea behind is, to user the sort and check if element a is in the requires of element b. If so, we can assume, that ashould be before b. But I´m not 100% sure, I just checked against your example and the example of @nikhilagw. I might have forgotten something. Please let me know if it worked!

For every element, I additionally inherit all 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);

Answer 3

This proposal looks for previous elements and checks if the actual element has the wanted requirements sorted before.

If all requirements are found the object is spliced to the index.

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

Answer 4

After several years I found this super short solution to the problem, a friend of mine shared it with me, I don't take credits.

elements.sort((a, b) =>
  a.requires.includes(b.name) ? 1 : b.requires.includes(a.name) ? -1 : 0
);