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

I thought of a simple to explain algorithm which answers the original question without requiring "transitive closure". First, let me show 3 possible dependency graphs, then explain the algorithm. It is absolutely necessary that the dependency graphs contain no cycles - the algorithm detects cycles and just throws an exception if there is one. The graphs (displayed graphically ;-)

The first example is from the original question. You could also add an arrow directly from A to C, but it's not necessary.

The second example shows that dependencies don't have to form a true tree as long as there are no cycles.

The third example is a bit more complex. You should try the algorithm on it. Note that there are multiple possible different results, but all will fulfill the requirement that processing nodes in the resulting order means that when a node is processed, all of its dependencies have already been processed.

The algorithm in pseudo code is:

list = []
while there are still nodes in the graph:
   find a leaf node (i.e. one with no children)
   add the leaf node to the list
   remove the leaf node and arrows leading to it from the graph
return list

In the step "find a leaf node", if there are nodes, but no leaf node, it just means that there's a cycle so we just throw an exception in that case. If there are multiple leaf nodes to choose from, it doesn't matter which you pick, though depending on the node picked, you'll get a different (but valid) ordering in the list.

Also, though I believe that the correctness of the algorithm is pretty clear from the way I've written it, it does modify the graph as it runs which isn't ideal. I'd recommend a variation where instead of "find a leaf node", you could substitute "find a node whose children all appear in list. Note that initially, since list is empty, only leaf nodes would satisfy that criteria.

Here is a JavaScript implementation with a simple test. I've changed the data structure used to make it simpler, plus it creates Sets, which make more sense in this context. I'm sure you could write an algorithm to convert the original data structure to the one I use here:

function getDependencies (hDep) {

    let setDependencies = new Set();
    let setKeys = new Set(Object.keys(hDep));
    while (setDependencies.size < setKeys.size) {

        // --- get a new key whose dependencies
        //     have all been added
        let ok = undefined;
        for (let item of setKeys.values()) {
            if (!setDependencies.has(item)
                    && hDep[item].isSubsetOf(setDependencies)) {
                setDependencies.add(item);
                ok = true;
                break;
                }
            }
        if (!ok) throw new Error("Circular dependencies");
        }
    return Array.from(setDependencies.values());
    }

// --------------------------------------------

let hDep = {
    a: new Set(['b','c']),
    b: new Set(['f','d']),
    c: new Set(['d','e']),
    d: new Set([]),
    e: new Set([]),
    f: new Set(['g']),
    g: new Set([]),
    }

let lResults = getDependencies(hDep, 'debug');
console.log(lResults.join(' '));

The result of running this code is:

d e c g f b a

In case you're wondering, a Set remembers the order that you insert things into it, so Array.from(setDependencies.values()) returns an array of names in the order that they were inserted into the Set.

Answer 2

Elaborating on my comments to the answer posted by Fez Vrasta:

Let's say that instead of the elements in the original question, we had:

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

what I've done is remove the explicit "a requires c" entry, though that's implied by the fact that a requires b, and b requires c. Now, I want to check if Fez Vrasta's answer works for this set of data, i.e. the order of processing should be c, then b, than a. However, I know that the result of sorting can depend on the order of items in the original list, so to be safe, I'm going to generate all possible permutations of the original list, sort each (via Fez Vrasta's algorithm), then display the order of the items in the resulting list. I stole a list permutating algorithm from somewhere. You can either 1) trust me, 2) get your own algorithm or 3) just form all permutations manually (since there are only 3 entries, there are only 6 possible permutations anyway).

My test algorithm is:

import {generatePermutations} from './utils.js';

let elements = [
    { name: 'a', requires: ['b'] },
    { name: 'b', requires: ['c'] },
    { name: 'c', requires: [] },
    ]
for (let lItems of generatePermutations(elements)) {
    let org = lItems.map(x => x.name).join(' ');
    lItems.sort((a, b) =>
          a.requires.includes(b.name) ? 1
        : b.requires.includes(a.name) ? -1
        : 0
        );
    let result = lItems.map(x => x.name).join(' ');
    console.log(org, ' => ', result);
    }

And the result of running it is:

$ node dep.js
a b c  =>  c b a
a c b  =>  a c b
b a c  =>  b a c
b c a  =>  c b a
c a b  =>  c b a
c b a  =>  c b a

As you can see, it doesn't always give the correct results. Spoiler alert: if I add 'c' to the list of a's requirements, I get the correct results for all possible permutations of the original list of elements.

Answer 3

Your data can be represented via graph. So you could use topological sort for this problem.

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

Answer 5

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 6

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 7

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