Javascript依赖列表 [英] Javascript dependency list

问题描述

我有一个元素列表，我需要找出依赖项。

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

我有：

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

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

/Kristian

推荐答案

假设你想要一个元素的递归依赖列表，包括元素本身，按任何顺序：

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

如果你想把元素本身放在最后而不是开头，你可以修复 output.push（output.shift（））

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.

如果最多只有一个元素需要每个依赖项，那么你可以使用前面的算法：只需阅读向后输出（或反转数组或使用 unshift 而不是 push （警告：性能下降））

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

依赖关系构成一个图形，您正在寻找它的拓扑排序。一种（无效的）方式是以深度优先顺序对节点进行排序，并在重新进入时重新插入它们。您可以使用Open堆栈来检测错误 - 如果从其父项重新输入子项，则您具有循环依赖项。

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

小提琴： http://jsfiddle.net/Xq5dz/4/

这篇关于Javascript依赖列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！