# Find order to install dependencies

Given a JavaScript map object of dependencies and their dependencies, determine order to install them:

Example:

Input:

{
p1: [p2, p3],
p2: [p3],
p3: []
}


Output:

[p3, p2, p1]


I really feel like there's a dynamic or recursive solution to this that I can't figure out. Is this true? Can it be done better than my approach? Here's my approach with a while loop.

function installDeps(depsList) {
var installed = [];
var order = [];

while (order.length < Object.keys(depsList).length) {

for (var depsItem in depsList) {

if (!installed[depsItem]) {
var installable = true;

for (var dep = 0; dep < depsList[depsItem].length; dep++) {
if (!installed[depsList[depsItem][dep]]) {
installable = false;
break;
}
}

if (installable) {
order.push(depsItem);
installed[depsItem] = true;
}
}
}
}

return order;
}


Heres how I did it properly with topological sorting. Each key of the object is a vertex on a graph, the value dependencies are the adjacent vertices. https://www.youtube.com/watch?v=ddTC4Zovtbc

var deps = {
p1: ['p2', 'p3'],
p2: [],
p3: ['p3']
};

function depSort(deps) {
var visited = [];
var sorted = [];

for (var dep in deps) {
if (!visited[dep]) {
depSortUtil(dep, visited, sorted);
}
}

return sorted;
}

function depSortUtil(dep, visited, sorted) {
visited[dep] = true;

for (var i = 0; i < deps[dep].length; i++) {
if (!visited[deps[dep][i]]) {
depSortUtil(deps[dep][i], visited, sorted);
}
}
sorted.push(dep);
}

console.log(depSort(deps));