algorithm - 增量检测 DAG 中的支配者

Question

假设我们有一个只有一个来源的 DAG。我想找到节点 n 使得来自源的任何完整路径都贯穿 n (即 n 支配所有汇)。换句话说:如果我们删除了 n 的所有后继，那么所有路径都将以 n 结尾。问题是节点在 DAG 中被增量标记为已删除。当节点被标记为已删除时，其他节点可以开始满足上述属性。我如何才能在这种情况发生时有效地检测到它？

奖励积分如果数据结构可以以比在每个源上分别为单个源运行算法更有效的方式对多个源执行此操作。

Answer 1

对该 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

对于多源的情况，可以使用相同的算法，但为每个节点保留一个“值”列表，每个源一个值。算法复杂度为 O(Nodes * Sources)，与对每个源的独立搜索相同。但如果使用矢量化，程序可能会变得更有效率。 “值”可以与 SIMD 指令并行处理。现代编译器可能会自动矢量化来实现这一点。