6

1つのソースを持つDAGがあるとします。nソースからの完全なパスが通過するn（つまりn、すべてのシンクを支配する）ノードを見つけたいと思います。言い換えると、のすべての後続を削除するとn、すべてのパスはで終わりnます。問題は、DAGでノードが削除済みとして段階的にマークされることです。ノードが削除済みとしてマークされると、他のノードが上記のプロパティを満たし始めることができます。発生したときにこれを効率的に検出するにはどうすればよいですか？

データ構造が、各ソースで個別に単一のソースに対してアルゴリズムを実行するよりも効率的な方法で複数のソースを使用してこれを実行できる場合、ボーナスポイントが得られます。

4

1 に答える 1

3

このDAGをトポロジカルソートして、ノードの順序を確立します。各ノードの値は、先行するすべてのノードからの発信エッジの数から、先行するすべてのノードと現在のノードへの着信エッジの数を引いたものになります。「ドミネーター」ノードの値は常にゼロです。

一部のノードが「削除済み」とマークされたら、その先行ノードと後続ノードを優先キューに入れます。優先度はトポロジカルソート順で決まります。「削除された」ノードに続いて、すべてのノードの値を更新します（着信ノードの数を加算し、このノードの発信ノードの数を減算します）。同時に（同じ順序で）優先キュー内の先行ノードと「削除済み」ノードの間の各ノードの値をデクリメントし、優先キュー内の後続ノードから開始して各ノードの値をインクリメントします。一部のノードの値がゼロにデクリメントされたら停止します。これは新しい「ドミネーター」ノードです。すべての「ドミネーター」ノードが必要な場合は、グラフの最後まで続行します。

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命令と並行して処理できます。最近のコンパイラは、これを実現するために自動ベクトル化を行う場合があります。

于 2012-02-06T16:08:50.660 に答える