5

依存関係を理解する必要がある要素のリストがあります。

私は持っています：

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

aとに依存し、とにb依存しています。このための賢い方法で依存関係を構築する方法はありますか？出力は次のようになります（可能性があります）。ddce

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

/クリスチャン

4

1 に答える 1

7

要素自体を含む、要素の再帰的な依存関係のリストが任意の順序で必要であると仮定します。

「すべての依存関係について、その依存関係を依存関係リストに追加する」は十分に賢いですか?

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/

于 2012-11-09T06:28:44.313 に答える