3
\$\begingroup\$

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;
}
\$\endgroup\$
2
3
\$\begingroup\$

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));
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.