检查 DAG 的两个节点是否在恒定时间内在同一条路径上

Question

我有一个由边列表表示的 DAG（有向无环图），例如

edges = [('a','b'),('a','c'),('b','d')]

将给出图表

a - > b -> d
|
v
c

我正在做很多操作，我必须检查两个节点是否在同一条路径上（b 和 d 在同一条路径上，而 b 和 c 不是来自上面的示例）这反过来又减慢了我的程序。我希望我能以某种方式遍历一次图形并保存所有路径，这样我就可以在恒定时间内检查它。

这种加速是否可能，我将如何在 python 中实现它？

编辑：请注意，我需要检查两个方向，所以如果我有一对节点 (a,b) 我需要同时检查 a 到 b 和 b 到 a.

Answer 1

您实际上想要找到图表的 transitive closure。

In computer science, the concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions. That is, can one get from node a to node d in one or more hops?

有多种方法可以找到图的传递闭包。最简单的方法是使用 floyd-warshall algorithm O(|V|³). Explained here。

另一种方法是从每个节点执行DFS并将您访问的所有节点标记为从当前节点可达。解释 here.

还有一种方法只适用于 DAG。首先对您的 DAG 执行拓扑排序。然后在拓扑排序表和OR当前节点的子节点的传递闭包中逆向计算，得到当前节点的传递闭包。解释 here.

下面是基于 DFS 的方法的 Python 实现：

def create_adj_dict_from_edges(edges):
    adj_dict = {}

    for e in edges:
        for u in e:
            if u not in adj_dict:
                adj_dict[u] = []

    for e in edges:
        adj_dict[e[0]].append(e[1])
    return adj_dict

def transitive_closure_from_adj_dict(adj_dict):

    def dfs(node, visited):
        if node not in adj_dict:
            return
        for next in adj_dict[node]:
            if next in visited:
                continue
            visited.add(next)
            dfs(next,visited)

    reachable = {}
    for node in adj_dict:
        visited = set(node,)
        dfs(node,visited)
        reachable[node] = visited

    return reachable

def main():
    edges = [('a','b'),('a','c'),('b','d')]
    adj_dict = create_adj_dict_from_edges(edges)
    tc = transitive_closure_from_adj_dict(adj_dict)
    print tc
    # is there a path from (b to d) or (d to b)
    print 'd' in tc['b'] or 'b' in tc['d']
    # is there a path from (b to c) or (c to b)
    print 'c' in tc['b'] or 'b' in tc['c']


if __name__ == "__main__":
    main()

输出

{'a': set(['a', 'c', 'b', 'd']), 'c': set(['c']), 'b': set(['b', 'd']), 'd': set(['d'])}
True
False

检查 DAG 的两个节点是否在恒定时间内在同一条路径上

Check if two nodes are on the same path in constant time for a DAG

python

algorithm

graph-traversal

directed-acyclic-graphs

graph-algorithm