グラフのシリアル化

Question

私は、有向グラフを「シリアライズ」するための簡単なアルゴリズムを探しています。特に、実行順序に依存関係のある一連のファイルがあり、コンパイル時に正しい順序を探したいと思っています。かなり一般的なことでなければならないことは分かっています。コンパイラはこれをいつもしていますが、私のgoogle-fuは今日弱いです。このための 'go-to'アルゴリズムは何ですか？

Answer 1

Topological Sort：グラフ理論において

、有向 非巡回グラフ（DAG）のトポロジカルソートまたは トポロジー的順序付けは、各 ノードが来たそのノードの線形 順序であります に送信エッジがあるすべてのノードの前にすべてのDAGには、1つまたは複数のトポロジカルなソートが あります。

擬似コード：

L ← Empty list where we put the sorted elements 
Q ← Set of all nodes with no incoming edges 
while Q is non-empty do 
    remove a node n from Q 
    insert n into L 
    for each node m with an edge e from n to m do 
     remove edge e from the graph 
     if m has no other incoming edges then 
      insert m into Q 
if graph has edges then 
    output error message (graph has a cycle) 
else 
    output message (proposed topologically sorted order: L) 

Answer 2

私はこれを必要とするツールが深さ優先の方法でツリーを歩くだけで、葉に当たったときに処理（例：コンパイル）し、グラフから取り除くすべての葉が葉として処理されたノード）。

限り、それはDAGだとして、この単純なスタックベースの散歩は、些細でなければなりません。

Answer 3

私はかなりナイーブ再帰アルゴリズム（擬似コード）を作ってみた：これの最大の問題は、それが循環依存関係を検出する能力がないということである

Map<Object, List<Object>> source; // map of each object to its dependency list 
List<Object> dest; // destination list 

function resolve(a): 
    if (dest.contains(a)) return; 
    foreach (b in source[a]): 
     resolve(b); 
    dest.add(a); 

foreach (a in source): 
    resolve(a); 

- それは無限再帰に行くことができます（つまり、スタックオーバーフロー; - p）。私が見ることのできる唯一の方法は、再帰的アルゴリズムを手作業のスタックを持つ中間的なものに置き換え、繰り返された要素のスタックを手動でチェックすることです。

誰かが何か改善していますか？ （ウィキペディアから）

Answer 4

グラフがサイクルが含まれている場合、どのようにあなたのファイルのために許可され、実行順序が存在することができますか？ グラフにサイクルが含まれている場合、解決策がなく、上記 が正しく報告されているようです。