如何检查合并 2 个节点后的两个 DAG 是否没有循环？

Question

给定 2 个随机 DAG，它们可能有也可能没有公共节点。我们从每个节点中随机选择一个节点，并分别称它们为 A 和 B。 A != B.

如何在合并前检查，如果我们将节点B合并到节点A中（通过将B中的边复制到A中的边，并销毁节点B），将不会有循环？

我想避免穷举搜索 - 当我们 'virtually' 合并这些节点时，然后为结果图中的所有节点搜索从该节点到自身的路径。

一个节点有唯一的ID，大致定义如下：

class Node:
  def __init__(self, id):
    self.id = id
    # set of outgoing nodes
    self.deps = set()
    # set of incoming nodes
    self.dependants = set()

# in the end, I want to write function like this:
def check(A, B):
  assert isinstance(A, Node) and isinstance(B, Node)
  if "there will be no cycles":
    return True # we can merge
  else:
    return False # we can not merge

我不需要代码，算法描述或算法名称就足够了。

Answer 1

当 B 不是 A 的前导时，就没有循环。
如果 B 是 A 的直接前导，而没有 A 边的 B 不是 A 的前导。没有循环
否则有循环

嗯，伪代码

if not A in DFS(B) // B is not a predecessor
  return noCycle
if A in B.outEdges and not A in DFS(B less A-Edge) // direct predecessor
  return noCycle
return cycle

可优化为

if not A in DFS(B less A-Edge) 
  return noCycle
return cycle

考虑

B->C->A

合并 A 和 B 将导致

C->A->C

这是一个循环。

B->A
 ->C

变成

A->C

在哪里

B->A
 ->C->A

成为一个循环

A->C->A

如何检查合并 2 个节点后的两个 DAG 是否没有循环？

How to check if two DAGs after merge of 2 nodes will not have cycles?

python

algorithm

graph-algorithm