我有一个元素列表,我需要找出依赖关系。Javascript依赖列表
我:
[{
"a": ["b", "d"]
}, {
"d": ["c", "e"]
}]
a
取决于b
和d
和d
上c
和e
。有没有办法以这种巧妙的方式构建依赖关系?输出应该(可能)是:
["b", "c", "e", "d", "a"]
/克里斯蒂安
我有一个元素列表,我需要找出依赖关系。Javascript依赖列表
我:
[{
"a": ["b", "d"]
}, {
"d": ["c", "e"]
}]
a
取决于b
和d
和d
上c
和e
。有没有办法以这种巧妙的方式构建依赖关系?输出应该(可能)是:
["b", "c", "e", "d", "a"]
/克里斯蒂安
假设你想要一个元素的递归依赖性,包括元素本身的列表,以任何顺序:
“为每个依赖,将它的依赖添加到依赖列表“足够聪明了吗?
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())
如果你想以这样的顺序你的依赖,每一个元素之前的元素依赖于它,那么你将不得不定义如何处理循环依赖。处理该问题的一种方法是检测循环依赖性并失败。
如果最多由一个元件需要每依赖性,然后就可以使用前面的算法:简单地读取向后的输出(或反向阵列或使用unshift
代替push
(警告:性能下降))
依赖关系形成一个图,并且您正在寻找它的拓扑排序。一种(无效的)方法是按照深度优先的顺序对节点进行排序,如果它们重新进入,则重新插入它们。你可以使用Open stack来检测错误 - 如果一个孩子从其父母重新进入,那么你有一个循环依赖。
一个更好的解决办法是使用标准的拓扑排序算法:虽然有无序的节点,挑选一个没有未解决的依赖性:
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;
}
什么是背后的逻辑?你想实现什么? –
定义'聪明'。迭代对象不够好吗? –
不确定数组发布的含义。你想要一个元素的依赖关系(以任何顺序)+这个元素本身? –