在有向无环图中增量式检测支配点

Question

在有向无环图中增量式检测支配点

algorithmdata-structuresgraphdirected-acyclic-graphs

6

假设我们有一个只有一个源的有向无环图（DAG）。我想找到节点n，使得从源到所有汇点的路径都经过n（即n支配所有汇点）。换句话说：如果我们删除n的所有后继节点，则所有路径都会以n结束。问题在于，在DAG中逐步标记为已删除的节点。随着节点被标记为删除，其他节点可以开始满足上述属性。当这种情况发生时，如何高效地检测呢？ 奖励分数： 如果数据结构能够以比单独对每个源运行算法更有效的方式来处理多个源，则额外加分。

- Jules

1

这意味着您想要在一个变化的图中逐步确定割吗？您需要所有这样的节点（所有割）还是只需要一个就足够了？ - jpalecek

是的，这是另一种说法：在切割发生之前检测到它（即在导致切割的最后一个节点被删除之前）。 - Jules

回复：编辑：最好是所有这样的切割，但一个切割也足够了。切割应该相对较少发生，因此如果确实发生了，运行慢算法查找其他切割也不会太麻烦。 - Jules

我不明白为什么你的想法失败了。对于每个顶点 v：删除其后继节点 [只删除到后继节点的边], 并检查所有路径是否以 v 结尾 [使用 BFS，您没有到达任何其他节点 u，使得 d_out(u) = 0]，如果是，则 v 是支配者。或者您正在寻找比二次更好的运行时间的解决方案吗？ - amit

是的，每次删除一个顶点时，该算法的时间复杂度是二次的。我正在寻找每次删除一个顶点时更接近常数时间或与受影响顶点的某种度量成比例的时间。也许使用适当的数据结构来表示问题可以实现这一点。 - Jules

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Evgeny Kluev · Accepted Answer

对这个有向无环图进行拓扑排序，以建立其节点的某种顺序。对于每个节点，它的值将是所有前面节点和当前节点连出的边数减去所有前面节点和当前节点连入的边数的数量。"支配者"节点的值始终为零。

在某个节点被标记为“已删除”后，将其前驱和后继放入优先队列中。优先级由拓扑排序顺序确定。更新所有在“已删除”节点之后的节点的值（添加该节点的入度并减去出度）。同时（按相同顺序），减小优先队列中前驱节点与“已删除”节点之间的每个节点的值，并增加从后继节点开始的每个节点的值。当某个节点的值减少到零时停止。这是一个新的“支配者”节点。如果需要所有的“支配者”节点，则继续直到图的末尾。

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指令并行处理“值”。现代编译器可以自动矢量化以实现这一点。