子に応じて並び替え配列

Question

子を最初に実行してから親をすべて実行できるように配列を取得したいと考えています。ここで

は一例です：

var p1=[c1,c2,c3] // c1,c2,c3 are children 
var p2=[c4,c5,c6] 
var c1=[c2,p2] // but c1 can depend on parent 

だから、結果は次のようになります。

var result=[c2,c6,c4,c5,c2,c3,p2,c1,p1] 

別の例は、理由の残りの両親は、エラーを回避するために、最初にすべての子をインストールするには、NPMの依存関係の順序を変更することができ子インストールがありません。

ご協力いただきありがとうございます。

Answer 1

topological sortingと呼ばれます。

var graph = { 
 
    p1: ['c1', 'c2', 'c3'], 
 
    p2: ['c4', 'c5', 'c6'], 
 
    c1: ['c2', 'p2'] 
 
}; 
 

 
var terminals = {}, 
 
    sorted = []; 
 

 
Object.keys(graph).forEach(n => 
 
    graph[n].forEach(k => 
 
     k in graph ? '' : terminals[k] = 1)); 
 

 
terminals = Object.keys(terminals); 
 

 
while (terminals.length !== 0) { 
 
    var t = terminals.shift(); 
 
    sorted.push(t); 
 
    Object.keys(graph).forEach(n => { 
 
     graph[n] = graph[n].filter(x => x != t); 
 
     if (graph[n].length === 0) { 
 
      terminals.push(n); 
 
      delete graph[n]; 
 
     } 
 
    }); 
 
} 
 

 
console.log(sorted)