Javascript dependency list

Question

I have a list of elements where I need to figure out the dependency.

I have:

[{
  "a": ["b", "d"]
}, {
  "d": ["c", "e"]
}]

a is depending on b and d, and d on c and e. Is there a way to construct the dependencies in a clever way for this? The output should (could) be:

["b", "c", "e", "d", "a"]

/Kristian

Answer 1

Assuming you wanted the list of recursive dependencies of an element, including the element itself, in any order:

"for every dependency, add its dependencies to the dependency list" is clever enough?

function recursiveDependencies (dependencies, element){
  var output = [element];
  for(i=0; i<output.length(); i++){
    dependencies[output[i]].forEach(function(x){
      if(output.indexOf(x)<0){ //prevent duplicates
        output.push(x)
      }
    })
  }
  return output;
}

If you want the element itself at the end rather than the beginning, you can fix that with output.push(output.shift())

---

If you want your dependencies in such an order that every element precedes the elements that depend on it, then you'll have to define how to handle circular dependencies. One way to handle that is detect a circular dependency and fail.

If every dependency is needed by at most one element, then you can use the previous algorithm: simply read the output backwards (or reverse the array or use unshift instead of push (warning: performance drop))

---

The dependencies form a graph, and you are looking for its topological sort. One (inefficent) way would be to order the nodes in depth-first order and reinsert them if they are reentered. You could use the Open stack to detect errors - if a child is reentered from its parent, then you have a circular dependency.

A better solution would be to use the standard topological sort algorithm: While there are unsorted nodes, pick one that has no unresolved dependencies:

function recursiveDependencies (dependencies, root){
  var nodes={};
  var nodeCount=0;
  var ready=[];
  var output=[];

  // build the graph
  function add(element){
     nodeCount++;
     nodes[element]={needs:[], neededBy:[], name: element};
     if(dependencies[element]){
       dependencies[element].forEach(function(dependency){
         if(!nodes[dependency]) add(dependency);
         nodes[element].needs.push(nodes[dependency]);
         nodes[dependency].neededBy.push(nodes[element]);
       });
     }
     if(!nodes[element].needs.length) ready.push(nodes[element]);
  }

  if(root){
    add(root)
  } else {
     for (element in dependencies){
       if(!nodes[element]) add(element);
    }
  }


  //sort the graph
  while(ready.length){
    var dependency = ready.pop();
    output.push(dependency.name);
    dependency.neededBy.forEach(function(element){
      element.needs = element.needs.filter(function(x){return x!=dependency})
      if(!element.needs.length) ready.push(element)
    })
  }

  //error-check
  if(output.length != nodeCount){
    throw "circular dependency detected"
  }

  return output;
}

fiddle: http://jsfiddle.net/Xq5dz/4/