使用 NetworkX 有效地检查路径在图中是否有效？

Question

我想找到一种有效的方法来通过图表检查给定的 "Walk" 是否有效。

这样的函数应该接受一个图（节点，边）和一串节点名称，如果节点可以根据图按给定的顺序访问，则输出True，否则输出false。

我最好使用 NetworkX 库，因为我已经使用它来存储和表示图形。

类似这样的东西：

""" G:
    Q1 -> Q1
    Q1 -> Q2
    Q2 -> Q2
"""
accepts(G, ["Q1", "Q1", "Q2"]) 
>> True
accepts(G, ["Q2", "Q2", "Q2"]) 
>> True
accepts(G, ["Q2", "Q2", "Q1"]) 
>> False
accepts(G, ["Q1", "Q2", "Q1"]) 
>> False
accepts(G, ["Q1", "Q1", "Q2", "Q1"]) 
>> False

这将用于自动机 class。基本上检查给定图形表示的语言的字符串的成员资格。

Answer 1

你只需要检查路径的所有边是否都有效。

def accepts(g, path):
    return all([(path[i],path[i+1]) in g.edges() for i in range(len(path)-1)])

示例：

g=nx.DiGraph()
g.add_edge("Q1","Q1")
g.add_edge("Q1","Q2")
g.add_edge("Q2","Q2")

print(accepts(g, ["Q1", "Q1", "Q2"]))
print(accepts(g, ["Q2", "Q2", "Q2"]))
print(accepts(g, ["Q2", "Q2", "Q1"]))
print(accepts(g, ["Q1", "Q2", "Q1"]))
print(accepts(g, ["Q1", "Q1", "Q2", "Q1"]))

Answer 2

虽然@newbie 的观点 "You only need to check if all the edges of the path are valid" 是正确的，但他给出的实现远非高效； graph.edges() 为路径中的每条边从头开始重建所有图边的列表。您应该始终使用 g.has_edge(u, v) 而不是 (u, v) in g.edges()，这是一个恒定时间操作。尽管目前您似乎正在使用 DiGraph，但后一种方法还具有同时适用于 Graph 和 DiGraph 的额外好处，而较早的方法仅适用于 DiGraph。（这是因为 Graph 的 edges() 方法仅 returns 一个（随机）方向的边缘，因此仅检查一个方向的边缘是不够的；g.has_edge() 在这里为 Graph 和 DiGraph)

做了正确的事情

长话短说，使用：

def accepts(g, path):
    return all([g.has_edge(path[i], path[i+1]) for i in range(len(path)-1)])

或者，更简洁一点：

def accepts(g, path):
    return all(map(g.has_edge, path, path[1:]))

使用 NetworkX 有效地检查路径在图中是否有效？

Efficiently check if path is valid in graph using NetworkX?

python

automata

networkx