Javascript依存関係リスト

Question

私は依存関係を理解するために必要な要素のリストを持っています。

私が持っている：

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

aはbとdに応じて、およびcとeにdされます。これのための賢い方法で依存関係を構築する方法はありますか？出力は次のように（可能性）必要があります。

「すべての依存関係のために：任意の順序で、あなたは要素自体を含む要素の再帰的な依存関係のリストを望んでいたと仮定すると、

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

/クリスチャン

Answer 1

依存関係を依存関係リストに追加することは十分に賢明ですか？

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

---

とそれを修正することができますそれに依存する場合、循環依存性をどのように処理するかを定義する必要があります。これを処理する1つの方法は、循環依存を検出して失敗することです。

すべての依存性が最大1つの要素によって必要とされている場合は、以前のアルゴリズムを使用することができます。単純に逆方向の出力を読んで（または配列を逆転またはunshiftの代わりpush（警告使用：パフォーマンスの低下を））

---

依存関係はグラフを形成し、そのトポロジカルソートを探しています。 1つの（非効率的な）方法は、ノードを深度優先順に並べ替え、それらが再入力された場合にそれらを再挿入することである。 Openスタックを使用してエラーを検出することができます。子供が親から再入力された場合、循環依存性があります。

より良い解決策は、標準的なトポロジカルソートアルゴリズムを使用することです：ソートされていないノードがありますが、未解決の依存関係を持っていないものを選択：

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/