DAG内のドミネーターをインクリメンタルに検出

Question

DAGが1つのソースであるとします。ソースからの完全なパスがn（つまり、nがすべてのシンクを占める）を通過するように、ノードnを見つけたいと思います。つまり、nのすべての後継者を削除した場合、すべてのパスはnで終了します。問題は、ノードがDAGで削除されたものとして段階的にマークされることです。ノードが削除マークされると、他のノードが上記のプロパティを満たすことができます。どのようにして効率よくこれを検出できますか？

ボーナスポイントデータ構造は、ソースのそれぞれに別々に単一のソースのためのアルゴリズムを実行するよりも、より効率的な方法で複数のソースでこれを行うことができれば。

Answer 1

このノードをトポロジ的に並べ替え、ノードの順序を確立します。各ノードについて、その値は、先行するすべてのノードからの出て行くエッジの数から、先行するすべてのノードおよび現在のノードへの入ってくるエッジの数を差し引いたものになります。 「dominator」ノードの値は常にゼロです。

ノードが「削除済み」とマークされた後、その先行ノードと後続ノードを優先キューに入れます。優先度は、トポロジカルなソート順によって決定されます。削除されたノードに続いて、すべてのノードの値を更新します（受信ノードの数を追加し、このノードの送信ノードの数を減算します）。優先度キュー内の先行ノードと「削除済み」ノードとの間の各ノードの（同じ順序で）デクリメント値と、優先度キュー内の後続ノードから始まる各ノードの増分値。ノードの値が0になると停止します。これは新しい「支配者」ノードです。すべての「dominator」ノードが必要な場合は、グラフの終わりまで続けます。複数のソースの場合について

delete(delNode): 
    for each predecessor in delNode.predecessors: queue.add(predecessor) 
    for each successor in delNode.successors: queue.add(successor) 
    for each node in DAG: 
    if queue.top.priority == node.priority > delNode.priority: 
     ++accumulator 

    node.value += accumulator 
    if node.value == 0: dominatorDetected(node) 

    if node.priority == delNode.priority: 
     accumulator += (delNode.predecessors.size - delNode.successors.size) 
     node.value = -1 

    if queue.top.priority == node.priority: 
     queue.pop() 
     if node.priority < delNode.priority: 
     --accumulator 

    if queue.empty: stop 

、同じアルゴリズムを使用するが、各ノードの「値」のリストを維持し、各ソースに対して1つの値が可能です。アルゴリズムの複雑さはO(Nodes * Sources)であり、各ソースの独立した検索と同じです。しかし、ベクトル化を使用すれば、プログラムをより効率的にすることができます。 「値」は、SIMD命令と並行して処理することができる。現代のコンパイラはこれを実現するために自動ベクトル化を行うかもしれません。