逐步检测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指令并行处理。现代编译器可以进行自动矢量化来实现这一点。